Сергей Горностаев, Вот в C++ основная часть решения действительно есть в библиотеке. Наверняка такое и в питоне есть. Но количества все равно придетется руками считать.
res2001, Вы правы про замену хеш таблицы на массив из 20000 элементов. Это будет, несоменно, быстрее. Но про QuickSelect - как раз и нужно, чтобы он частично отсортировал массив. Надо же в задаче выдать не k-ый с конца, а все k максимальных элемента. И QuickSelect, если его попросить k-ый c конца элемент, как раз положит максимальные k-1 справа от него. Ровно как в задаче и надо. И все это за O(n) в среднем.
Adamos, ох, позор мне: с битами напутал. Пхп может это соптимизировать, если функция встроенная. А вообще, может какая-то встроенная процедура в БД будет быстрее работать.
mayton2019, весьма отдаленно. Только тем, что и там и тут есть какая-то метрика близости строк. Только тут вот метрику подсчитать надо, а в задачах кластеризации считается, что метрика вам дана. Так что никакие алгоритмы кластеризации тут никак не применить.
Adamos, заведите таблицу на 32768 чисел. Для каждой позиции предподсчитайте количество единичных бит. Прибавляйте значения из таблицы для каждой четвертинки из 16 бит. А вообще, в php наверняка есть встроенная функция popcnt, которая быстро подсчитает биты.
Неясно, как это аггрегированное количество нулей во всех строках позволит найти строки, где на заданных позициях 0. Если только вы не предлагаете предподсчитывать количество нулей для всех строк на каждом подмножестве позиций.
Adamos, оптимизация в том, что вы 64 символа сравниваете одной процессорной операцией. Пример: вместо 4 сравнений "0001" с "1000" вы or-ите числа 14 и 7, получая 15 за одну операцию. Потом еще за 4 операции (для 64 бит) вы найдете, что там 4 единичных бита, т.е. в 4 позициях нули есть хотя бы в одной строке. Важно строки перевести в числа до запихивания в бд, если переводить в биты каждый раз, то да, никакого ускорения не будет.
Adamos, ксорить-то зачем? Через and считаете нули в обеих строках. Делить надо на нули в искомой строке - их количество отдельно подсчитайте.
Будет быстрее, конечно, если хранить и обрабатывать строки как целые 64-битные числа. Потому что символы вы по одному сравниваете, а биты по 64 за раз. Естественно, подсчет единичных бит в ответе надо делать хитрее, чем проверка каждого бита. Или через таблицу на 16 бит и 4 к ней обращения, или через 8 сдвигов и сложений. Плюс читать и обрабатывать предется в 8 раз меньше байт.
