Вот тут моё решение могло бы спасти всех с участников с «чистыми» решениями.
У него скорость ~50 слов в секунду, плюс обещание тестировать решения на одинаковых блоках :)
Сейчас немного жалею, что не отправил решение со скоростью 10 слов в секунду и +0.1%.
* от слов отрезаются самые частые окончания 's, s, ing; слова с апострофом считаются ложными
* основной алгоритм похож на фильтр Блума:
для каждого слова считается хеш-функция, по получившемуся индексу в чанке устанавливается единичный бит;
размер чанка подобран так, что после прохода по словарю остаётся приблизительно 15 нулевых битов;
позиции этих нулевых битов сохраняются в файл;
дальше происходит заполнение нового чанка с новой хеш-функцией, всего таких хеш-фунций около 3000;
при тестировании слова происходит проверка, не попала ли хеш-функция слова на один из этих нулевых битов
* дополнительно используются эвристики для отсечения ложноположительных срабатываний, подсчёт подряд идущих согласных и т.п. (+4% правильных ответов)
* стоит уделить внимание изменяемой хеш-функции, небольшие изменение в мутаторе хеш-функции дали прирост +3%
* для улучшения сжатия файла (~+7% к степени сжатия), сохраняются только расстояния между нулевыми битами, старшие байты, которые имеют схожие значения рядом с нулём, перенесены в отдельную часть файла (сделано с расчётом на gzip, для других архиваторов такая предварительная обработка может навредить)
Ну вот и я оказался в потенциальной яме.
На одном миллионе тестовых слов 82.05% на другом 82.1%
Все последние изменения, которые я пробовал сделать, приводили к увеличению максимум на +0.01%. Это очень мало, буквально в пределах погрешности. Т.к. я выбрал медленный алгоритм, то ожидание генерации файла и проверка на миллионе слов превратились в пытку :)
feldgendler, моё решение в этом тестовом скрипте проверяется со скоростью ~50 слов в секунду (против 4000 в секунду моим скриптом), я так полагаю, это из-за виртуальной машины.
Это 5 часов на 1 000 000 слов.
Такая скорость проверки считается разумной? Или мне надо что-то исправить?
Зато смотрите, сколько комментариев набирают такие жареные новости!
Помогают раскрепостить людей, вот, например, не может человек ничего написать по основной теме ресурса, а тут заходит в пост и сразу про «Чебурнет» пишет — эксперт! :)
У него скорость ~50 слов в секунду, плюс обещание тестировать решения на одинаковых блоках :)
Сейчас немного жалею, что не отправил решение со скоростью 10 слов в секунду и +0.1%.
* от слов отрезаются самые частые окончания 's, s, ing; слова с апострофом считаются ложными
* основной алгоритм похож на фильтр Блума:
для каждого слова считается хеш-функция, по получившемуся индексу в чанке устанавливается единичный бит;
размер чанка подобран так, что после прохода по словарю остаётся приблизительно 15 нулевых битов;
позиции этих нулевых битов сохраняются в файл;
дальше происходит заполнение нового чанка с новой хеш-функцией, всего таких хеш-фунций около 3000;
при тестировании слова происходит проверка, не попала ли хеш-функция слова на один из этих нулевых битов
* дополнительно используются эвристики для отсечения ложноположительных срабатываний, подсчёт подряд идущих согласных и т.п. (+4% правильных ответов)
* стоит уделить внимание изменяемой хеш-функции, небольшие изменение в мутаторе хеш-функции дали прирост +3%
* для улучшения сжатия файла (~+7% к степени сжатия), сохраняются только расстояния между нулевыми битами, старшие байты, которые имеют схожие значения рядом с нулём, перенесены в отдельную часть файла (сделано с расчётом на gzip, для других архиваторов такая предварительная обработка может навредить)
На одном миллионе тестовых слов 82.05% на другом 82.1%
Все последние изменения, которые я пробовал сделать, приводили к увеличению максимум на +0.01%. Это очень мало, буквально в пределах погрешности. Т.к. я выбрал медленный алгоритм, то ожидание генерации файла и проверка на миллионе слов превратились в пытку :)
Это 5 часов на 1 000 000 слов.
Такая скорость проверки считается разумной? Или мне надо что-то исправить?
Помогают раскрепостить людей, вот, например, не может человек ничего написать по основной теме ресурса, а тут заходит в пост и сразу про «Чебурнет» пишет — эксперт! :)