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

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

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

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

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

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

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

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

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

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

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

Они также появляются время от времени, когда я кодирую. Вы могли бы подумать о переносе второго оператора using в другую функцию?

Если вам нужно только отрицательное подтверждение (этот элемент не является частью набора), вы можете заполнить коллекцию 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)