поиск дубликата в pytable hdf5 с 500e6 строками

На ум приходят два очевидных метода: хеширование и сортировка.

A) определить хэш-функцию для объединения идентификатора и счетчика в одно компактное значение.

Б) посчитайте, как часто встречается каждый хэш-код

C) выберите из ваших данных все, что имеет хеш-коллизии (это должен быть гораздо меньший набор данных)

Г) отсортируйте этот набор данных, чтобы найти дубликаты.

Хэш-функцию в A) необходимо выбрать так, чтобы она помещалась в основную память и в то же время обеспечивала достаточную избирательность. Возможно, для этого используйте два набора бит размером 2 ^ 30 или около того. Вы можете позволить себе иметь 5-10% коллизий, это все равно должно уменьшить размер набора данных, чтобы впоследствии обеспечить быструю сортировку в памяти.

По сути, это фильтр Блума.

Подход грубой силы, который вы использовали, похоже, требует, чтобы вы выполняли запросы 500e6, по одному для каждой строки таблицы. Хотя я думаю, что подходы к хешированию и сортировке, предложенные в другом ответе, по сути, верны, стоит отметить, что pytables уже предположительно построен для скорости, и уже следует ожидать, что такие методы будут эффективно включены «под капотом», так что разговаривать.

Я утверждаю, что написанный вами простой код, скорее всего, еще не в полной мере использует возможности, которые pytables уже предоставляет вам.

В документации для create_index () , в нем говорится, что настройки по умолчанию - optlevel=6 и kind='medium'. В нем упоминается, что вы можете увеличить скорость каждого из ваших запросов 500e6, уменьшив энтропию индекса, и вы можете уменьшить энтропию своего индекса до минимально возможного значения (нуля), либо выбрав значения optlevel=9 и kind='full', отличные от значений по умолчанию. или, что то же самое, путем создания индекса с помощью вызова create_csindex () вместо этого. Согласно документации, вы должны заплатить немного больше вперед, потратив больше времени на создание лучше оптимизированного индекса для начала, но затем он окупится позже, сэкономив ваше время на серии запросов, которые вам нужно повторить 500e6 раз.

Если оптимизация индексов столбцов pytables не позволяет в достаточной степени ускорить ваш код, и вы хотите просто выполнить массовую сортировку по всем строкам, а затем просто искать дубликаты, ища совпадения в соседних отсортированных строках, можно выполнить сортировка слиянием за время O (N log (N)) с использованием относительно скромных объемов памяти путем сортировки данные в кусках, а затем сохраняют куски во временных файлах на диске. Примеры здесь и здесь продемонстрируют в принципе, как это сделать в Python. Но вам действительно стоит сначала попробовать оптимизировать индекс pytables, так как это, вероятно, предоставит гораздо более простое и естественное решение в вашем конкретном случае.