тип данных Python для отслеживания дубликатов

Question

Я часто отслеживаю дубликаты с чем-то вроде этого:

processed = set() 
for big_string in strings_generator:
    if big_string not in processed:
        processed.add(big_string)
        process(big_string)

Я имею дело с огромными объемами данных, поэтому не хочу сохранять обработанный набор в памяти.У меня есть версия, которая использует sqlite для хранения данных на диске, но затем этот процесс выполняется намного медленнее.

Чтобы сократить объем памяти, используйте то, что вы думаете об использовании хэшей, например:

processed = set() 
for big_string in string_generator:
    key = hash(big_string)
    if key not in ignored:
        processed.add(key)
        process(big_string)    

Недостаток в том, что я мог потерять данные из-за случайных коллизий хешей.1 столкновение в 1 миллиард хешей не будет проблемой для моего использования.

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

Что бы вы предложили вместо этого?

Answer 1

Я собираюсь предположить, что вы хэшируете веб-страницы.Вы должны хешировать не более 55 миллиардов веб-страниц (и эта мера почти наверняка пропускает некоторые совпадения).

Вы готовы принять шанс коллизии менее одного на миллиард, что означает, что если мы посмотрим на хэш-функцию, то число коллизий близко к тому, что мы получили бы, если бы хеш был действительно случайным [ˆ1], нам нужен диапазон хэшей размером (55*10ˆ9)*10ˆ9.Это log2((55*10ˆ9)*10ˆ9) = 66 бит.

[ˆ1]: поскольку хеш можно считать выбранным случайным образом для этой цели, p(collision) = (occupied range)/(total range)

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

Похоже, мы ищем 128-битную версию Murmur3 хеш.Люди сообщают о увеличении скорости в 12 раз по сравнению Murmur3_128 с MD5 на 64-битной машине.Вы можете использовать эту библиотеку для тестирования скорости.См. Также этот связанный ответ , который:

• показывает результаты теста скорости в диапазоне питона str_hash, скорость которого вы уже сочли приемлемым в другом месте - хотя Python hash является 32-битным хешем, оставляя вам только 2ˆ32/(10ˆ9) (то есть только 4) значения, сохраненные с вероятностью столкновения менее одного миллиарда.
• порождает библиотеку привязок Python , которые вы можете использовать напрямую.

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

Answer 2

Вы должны решить, что важнее: пространство или время.

Если время, то вам нужно создать уникальные представления вашего large_item, которые занимают как можно меньше места (возможно, немного str).значение), которое легко (то есть быстро) рассчитать и не будет иметь коллизий, и сохраните их в set.

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

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

Обновление

это строки html-контента

Возможно, тогда это гибридное решение: сохранить set в памяти обычного хэша Pythonсохраняя при этом фактический контент html на диске с ключами этого хэша;когда вы проверяете, находится ли текущий large_item в set, и получаете положительный результат, дважды проверьте решение на основе диска, чтобы увидеть, является ли это настоящим попаданием или нет, тогда пропустите или обработайте, как необходимо.Примерно так:

import dbf
on_disk = dbf.Table('/tmp/processed_items', 'hash N(17,0); value M')
index = on_disk.create_index(lambda rec: rec.hash)

fast_check = set()
def slow_check(hashed, item):
    matches = on_disk.search((hashed,))
    for record in matches:
        if item == record.value:
            return True
    return False

for large_item in many_items:
    hashed = hash(large_item) # only calculate once
    if hashed not in fast_check or not slow_check(hashed, large_item):
        on_disk.append((hashed, large_item))
        fast_check.add(hashed)
        process(large_item)    

К вашему сведению: dbf - это модуль, который я написал, который вы можете найти на PyPI

Answer 3

фильтр Блума? http://en.wikipedia.org/wiki/Bloom_filter

Answer 4

Как вы уже видели несколько вариантов, но, к сожалению, ни один из них не может полностью решить ситуацию частично, потому что

1. Ограничение памяти, чтобы сохранить весь объект в памяти
2. Нет идеальной функции хешированияи для огромного набора данных есть изменение коллизий.
3. Улучшенные хэш-функции (md5) медленнее
4. Использование базы данных, такой как sqlite, на самом деле замедляет работу

Когда я читаю этот отрывок

У меня есть версия, которая использует sqlite для хранения данных на диске, но затем этот процесс работает намного медленнее.

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

1. Используйте tmpfs для создания виртуального диска.tmpfs имеет ряд преимуществ по сравнению с другими реализациями, поскольку поддерживает замену менее используемого пространства на пространство подкачки.
2. Сохранение базы данных sqlite на виртуальном диске.
3. Изменение размера виртуального диска и профилирование кодачтобы проверить свою производительность.

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

Предупреждение: Это решение только для Linux

Answer 5

Если many_items уже находится в памяти, вы не создаете другую копию large_item.Вы просто сохраняете ссылку на него в игнорируемом наборе.

Если many_items - это файл или какой-то другой генератор, вам придется искать другие альтернативы.

Например, если many_items - этофайл, возможно, вы можете сохранить указатель на элемент в файле вместо фактического элемента

Answer 6

Этого можно достичь гораздо проще легко , выполнив сначала более простые проверки, а затем исследуя эти случаи с помощью более сложных проверок.В приведенном ниже примере содержатся выдержки из вашего кода: , но он выполняет проверки гораздо меньших наборов данных.Это делается путем первого сопоставления простого случая, который дешево проверить.И если вы обнаружите, что пары (filesize, checksum) недостаточно различают, вы можете легко заменить их на более дешевую, но энергичную проверку.

# Need to define the following functions
def GetFileSize(filename):
    pass
def GenerateChecksum(filename):
    pass
def LoadBigString(filename):
    pass

# Returns a list of duplicates pairs.
def GetDuplicates(filename_list):
    duplicates = list()
    # Stores arrays of filename, mapping a quick hash to a list of filenames.
    filename_lists_by_quick_checks = dict()
    for filename in filename_list:
        quickcheck = GetQuickCheck(filename)
        if not filename_lists_by_quick_checks.has_key(quickcheck):
            filename_lists_by_quick_checks[quickcheck] = list()
        filename_lists_by_quick_checks[quickcheck].append(filename)
    for quickcheck, filename_list in filename_lists.iteritems():
        big_strings = GetBigStrings(filename_list)
        duplicates.extend(GetBigstringDuplicates(big_strings))
    return duplicates

def GetBigstringDuplicates(strings_generator):
    processed = set()
    for big_string in strings_generator:
        if big_sring not in processed:
            processed.add(big_string)
            process(big_string)

# Returns a tuple containing (filesize, checksum).
def GetQuickCheck(filename):
    return (GetFileSize(filename), GenerateChecksum(filename))

# Returns a list of big_strings from a list of filenames.
def GetBigStrings(file_list):
    big_strings = list()
    for filename in file_list:
        big_strings.append(LoadBigString(filename))
    return big_strings

Answer 7

как работает ваша версия sql lite? Если вы вставите все свои строки в таблицу базы данных и затем выполните запрос «выбрать отличную строку большой_строки из имени таблицы», база данных должна оптимизировать ее для вас.

Другим вариантом для вас будет использование hadoop.

Другим вариантом может быть разделение строк на разделы так, чтобы каждый раздел был достаточно маленьким, чтобы поместиться в памяти. тогда вам нужно только проверить наличие дубликатов в каждом разделе. формула, которую вы используете для определения раздела, выберет один и тот же раздел для каждого дубликата. самый простой способ - просто взглянуть на первые несколько цифр строки, например ::1005*

d=defaultdict(int)
for big_string in strings_generator:
    d[big_string[:4]]+=1
print d

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

Answer 8

Я предлагаю вам профилировать стандартные хэш-функции Python и выбирать самые быстрые: все они «безопасны» от коллизий, достаточных для вашего приложения.

Вот некоторые тесты для hash, md5 и sha1:

In [37]: very_long_string = 'x' * 1000000
In [39]: %timeit hash(very_long_string)
10000000 loops, best of 3: 86 ns per loop

In [40]: from hashlib import md5, sha1

In [42]: %timeit md5(very_long_string).hexdigest()
100 loops, best of 3: 2.01 ms per loop

In [43]: %timeit sha1(very_long_string).hexdigest()
100 loops, best of 3: 2.54 ms per loop

md5 и sha1 сопоставимы по скорости.hash в 20 раз быстрее для этой строки, и, похоже, она не сильно зависит от размера самой строки.

Answer 9

Вы можете попробовать функцию str типа __hash__.

In [1]: hash('http://stackoverflow.com')
Out[1]: -5768830964305142685 

Это определенно не криптографическая хеш-функция, но с небольшим шансом у вас не будет слишком большого коллизии.Это работает, как описано здесь: http://effbot.org/zone/python-hash.htm.

Answer 10

ну вы всегда можете украсить large_item флагом processed. Или что-то подобное.