Давайте теперь спортивное решение.
По поводу спорта.
Предусловия.
Для современного ПК объем доступной оперативной памяти в среднем составляет 8Г. И на этот объем
мы можем расчитывать в реализации алгоритмов.
Объем диска - неограничен. И характер доступа к файлу - последовательный. Объем файла - 1 000 000 000 * длину строки =
= длина даты + длина хромосомы + пробелы и переводы строк = 1 + 1 + 8 + 60 символов (байт) = 70 000 000 000 байт =
= 70 Гигабайт.
Можно создавать дополнительные служебные файлы для решения данной задачи.
Гипотеза 1.
Если данных - много (миллиард) а ключ такой длинный (5 6 8 11 16 18 19 22 25 34 37 40 42 51 55 59 61 64 65 69)
то велика вероятность что 99.9% данных в таблице - будут уникальны.
Далее.
Если так много уникальных - то они не интересны как исходные данные. Тоесть гистограмма где-то
такая.
1.
2.
3.
4.
5.
6.
7.
8.
9.
COUNT(*), chromosome
500 000, "1 2 3 4 5 5 5 5 5 5..."
250 000, "2 2 3 4 5 5 5 5 5 5..."
150 000, "3 2 3 4 5 5 5 5 5 5..."
10, "4 2 3 4 5 5 5 5 5 5..."
1, "? ? ? ?...."
1, "? ? ? ?...."
1, "? ? ? ?...."
.....
В этой задаче - можно сделать сильную оптимизацию если сделать 2 прохода по текстовому файлу и
отбросить те ключи которые были по 1 разу.
1) За 1 проход отфильтровываем (отбрасываем) эти 99.9% уникальных ключей. Используем in-memory
структуры данных с экономной формой представления ключей. Сохраняем те что остались
как кандидаты с (candidates.csv). Здесь я опираюсь на доступные мне 8Гб.
2) На 2 проходе их кандидатов - формируем хеш-табличку и в ней ведем подсчет количества.
Здесь я тоже предполгагаю что оставшиеся 0.1 % ключей лягут как хеш-табличка в 8Гб.
3) Публикуем top 20 результатов из этой таблички с сортировкой по count.
Весь этот алгоритм потребует 2 пробега по файлу. И он будет работать только на условиях тех гипотез
что я описал. Если баланс уникальных - неуникальных ключей в гистограмме будет не 99 к 1 а более
другой то памяти не хватит для 1 фазы алгортма и мы упадем по out of memory.
