Поиск по большому набору данных

Question

как бы быстро найти список с ~ 5 мил 128-битными (или 256, в зависимости от того, как вы на это смотрите) строками и найти дубликаты (в python)? я могу превратить строки в числа, но я не думаю, что это сильно поможет. так как я мало изучил теорию информации, есть ли что-то об этом в теории информации?

и поскольку это уже хэши, нет смысла их снова хешировать

Answer 1

Если это вписывается в память, используйте set (). Я думаю, что это будет быстрее, чем сортировка. O (n log n) для 5 миллионов предметов обойдется вам.

Если он не умещается в памяти, скажем, вы записали более 5 миллионов, делите и властвуйте Разбить записи в средней точке, как 1 х 2 ^ 127. Примените любой из вышеперечисленных методов. Я предполагаю, что теория информации помогает, утверждая, что хорошая хеш-функция будет распределять ключи равномерно. Таким образом, метод деления на среднюю точку должен работать отлично.

Вы также можете применять принцип «разделяй и властвуй», даже если он умещается в памяти. Сортировка записей 2 х 2,5 мил быстрее, чем сортировка записей 5 мил.

Answer 2

Загрузите их в память (5M x 64B = 320MB), отсортируйте и отсканируйте их, чтобы найти дубликаты.

Answer 3

В Python2.7 + вы можете использовать collections.Counter, для более старого Python используйте collections.deaultdict(int). В любом случае это O (n).

сначала создайте список с несколькими хэшами

>>> import hashlib
>>> s=[hashlib.sha1(str(x)).digest() for x in (1,2,3,4,5,1,2)]
>>> s
['5j\x19+y\x13\xb0LTWM\x18\xc2\x8dF\xe69T(\xab', '\xdaK\x927\xba\xcc\xcd\xf1\x9c\x07`\xca\xb7\xae\xc4\xa85\x90\x10\xb0', 'w\xdeh\xda\xec\xd8#\xba\xbb\xb5\x8e\xdb\x1c\x8e\x14\xd7\x10n\x83\xbb', '\x1bdS\x89$s\xa4g\xd0sr\xd4^\xb0Z\xbc 1dz', '\xac4x\xd6\x9a<\x81\xfab\xe6\x0f\\6\x96\x16ZN^j\xc4', '5j\x19+y\x13\xb0LTWM\x18\xc2\x8dF\xe69T(\xab', '\xdaK\x927\xba\xcc\xcd\xf1\x9c\x07`\xca\xb7\xae\xc4\xa85\x90\x10\xb0']

Если вы используете Python2.7 или новее

>>> from collections import Counter
>>> c=Counter(s)
>>> duplicates = [k for k in c if c[k]>1]
>>> print duplicates
['\xdaK\x927\xba\xcc\xcd\xf1\x9c\x07`\xca\xb7\xae\xc4\xa85\x90\x10\xb0', '5j\x19+y\x13\xb0LTWM\x18\xc2\x8dF\xe69T(\xab']

если вы используете Python2.6 или более раннюю версию

>>> from collections import defaultdict
>>> d=defaultdict(int)
>>> for i in s:
...  d[i]+=1
... 
>>> duplicates = [k for k in d if d[k]>1]
>>> print duplicates
['\xdaK\x927\xba\xcc\xcd\xf1\x9c\x07`\xca\xb7\xae\xc4\xa85\x90\x10\xb0', '5j\x19+y\x13\xb0LTWM\x18\xc2\x8dF\xe69T(\xab']

Answer 4

Этот массив отсортирован?

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

Answer 5

Вы говорите, что у вас есть список из примерно 5 миллионов строк, и этот список может содержать дубликаты. Вы не говорите (1), что вы хотите сделать с дубликатами (зарегистрируйте их, удалите все вхождения, кроме одного, ...) (2) что вы хотите сделать с недубликатами (3), является ли этот список автономная структура или являются ли строки ключами к некоторым другим данным, о которых вы не упомянули (4), почему вы не удалили дубликаты во время ввода, вместо этого создав список, содержащий дубликаты.

Как упражнение «Структуры данных и алгоритмы 101», ответ, который вы приняли, - нонсенс. Если у вас достаточно памяти, обнаружение дубликатов с использованием набора должно выполняться быстрее, чем сортировка списка и его сканирование. Обратите внимание, что удаление M элементов из списка размера N равно O (MN). Код для каждой из различных альтернатив является коротким и довольно очевидным; почему бы вам не попробовать написать их, рассчитать время и отчитаться?

Если это реальная проблема, которая у вас есть, вам нужно предоставить гораздо больше информации, если вы хотите получить разумный ответ.