Python: установить только с проверкой существования? - PullRequest
Новая
       25

Python: установить только с проверкой существования?

8 голосов
/ 26 августа 2009

У меня есть множество больших длинных строк, для которых я хочу сделать поиск существования. Мне не нужно, чтобы вся строка была когда-либо сохранена. Насколько я могу судить, set() на самом деле хранил строку, которая поглощает большую часть моей памяти.

Существует ли такая структура данных? 

done = hash_only_set()
while len(queue) > 0 :
   item = queue.pop()
   if item not in done :
      process(item)
      done.add(item)

(Моя очередь постоянно заполняется другими потоками, поэтому у меня нет возможности ее дедуплицировать в начале).

Ответы [ 6 ]

10 голосов
/ 26 августа 2009

Конечно, можно хранить набор только хэшей: 

done = set()
while len(queue) > 0 :
   item = queue.pop()
   h = hash(item)
   if h not in done :
      process(item)
      done.add(h)

Обратите внимание, что из-за коллизий хэшей, есть вероятность, что вы считаете элемент выполненным, даже если это не так.

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

В качестве альтернативы: если вы не можете согласиться хранить строки в памяти, сохраните их в базе данных или создайте файлы в каталоге с тем же именем, что и строка.

4 голосов
/ 26 августа 2009

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

Встроенный метод __hash__() не гарантирует, что у вас не будет дубликатов (а поскольку он использует только 32 бита, вполне вероятно, вы их найдете).

4 голосов
/ 26 августа 2009

Вы можете использовать структуру данных под названием Фильтр Блума специально для этой цели. Реализацию Python можно найти здесь .

РЕДАКТИРОВАТЬ : Важные примечания:

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

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

3 голосов
/ 26 августа 2009

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

Если вы можете сделать функцию process() идемпотентной - то есть дважды вызывать ее для элемента - это только проблема производительности, тогда проблема станет намного проще, и вы сможете использовать структуры данных с потерями, такие как фильтры Блума.

2 голосов
/ 26 августа 2009

Вам следует подумать о том, как выполнить поиск, поскольку существует два метода, которые необходимы для набора: __hash__ и __eq__.

Хеш - это «свободная часть», которую вы можете убрать, но __eq__ - это не свободная часть, которую вы можете сохранить; Для сравнения необходимо иметь две строки.

Если вам нужно только отрицательное подтверждение (этот элемент не является частью набора), вы можете заполнить коллекцию Set, которую вы реализовали, своими строками, а затем «завершить» набор, удалив все строки, кроме строк с коллизиями ( они сохраняются для eq тестов), и вы обещаете не добавлять больше объектов в ваш сет. Теперь у вас есть эксклюзивный тест. Вы можете сказать, не является ли объект не в вашем наборе. Вы не можете быть уверены, является ли «obj in Set == True» ложным срабатыванием или нет.

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

Edit2: Это мой 3-минутный фильтр Блума: 

class BloomFilter (object):
    """ 
    Let's make a bloom filter
    http://en.wikipedia.org/wiki/Bloom_filter

    __contains__ has false positives, but never false negatives
    """ 
    def __init__(self, hashes=(hash, )): 
        self.hashes = hashes
        self.data = set()
    def __contains__(self, obj):
        return all((h(obj) in self.data) for h in self.hashes)
    def add(self, obj):
        self.data.update(h(obj) for h in self.hashes)
0 голосов
/ 27 августа 2009

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

Модуль Python zlib предоставляет встроенные возможности сжатия строк и может использоваться для предварительной обработки строк перед тем, как поместить их в свой набор. Однако обратите внимание, что строки должны быть достаточно длинными (что вы намекаете на это) и иметь минимальную энтропию, чтобы сэкономить много памяти. Другие варианты сжатия могут обеспечить лучшую экономию пространства, и некоторые реализации на основе Python можно найти здесь

...