Python: самый быстрый способ поиска, если длинная строка находится в списке строк
У меня есть входные данные из 2-5 миллионов строк по 400 символов каждая из сохраненного текстового файла. Мне нужно проверить наличие дубликатов, прежде чем добавлять их в список, который я проверяю (не обязательно должен быть список, может быть любой другой тип данных, список технически является набором, поскольку все элементы уникальны).
Я могу ожидать, что максимум 0,01% моих данных будут неуникальными, и мне нужно их отфильтровать.
Мне интересно, есть ли для меня более быстрый способ проверить, существует ли элемент в списке, а не:
a=[]
for item in data:
if item not in a:
a.add(item)
Я не хочу терять заказ.
Будет ли хеширование быстрее (мне не нужно шифрование)? Но тогда мне пришлось бы вести хеш-таблицу для всех значений, которые нужно сначала проверить. Есть ли способ, которым я скучаю?
Я использую Python 2, могу максимально подняться до Python 3.5.
В наборах уже используется хеширование. Честно говоря, я бы просто использовал a=set(data) (обратите внимание, что вам не нужно явно перебирать данные). Если это все еще слишком медленно для вас, вам, возможно, придется отказаться от использования Python, хотя имейте в виду, что Python не особенно медленный для такого рода вещей.
Умещается в оперативной памяти.
Возможно, будет уместно сообщить нам, какой у вас источник данных. В любом случае велика вероятность того, что вы будете ограничены вводом-выводом.
Источник данных - это сохраненный текстовый файл.
Чтобы сохранить порядок, используйте a = dict.fromkeys(data) в последней версии Python (dicts официально поддерживает порядок вставки с Python 3.7 и неофициально с 3.6). Наборов нет.
В Python 2 вы можете сделать a = OrderedDict.fromkeys(data) после from collections import OrderedDict. Но вам, возможно, придется переоценить, поместится ли он по-прежнему в ОЗУ, потому что OrderedDict не является «скудным».
Ответы 2
Вы можете попробовать это,
a = list(set(data))
Список - это упорядоченная последовательность элементов, тогда как Set - это отдельный неупорядоченный список элементов.
Вы потеряете порядок, пройдя Set.
На этот вопрос сложно ответить, потому что он постоянно меняется ;-) В версии, на которую я отвечаю, спрашивается, есть ли более быстрый способ, чем:
a=[]
for item in data:
if item not in a:
a.add(item)
Это будет ужасно медленно, так как время будет квадратичным в len(data). В любой версии Python в len(data) будет линейно линейное время ожидаемого случая:
seen = set()
for item in data:
if item not in seen:
seen.add(item)
emit(item)
где emit() делает все, что вам нравится (добавляет в список, записывает в файл и т. д.).
В комментариях я уже отмечал способы добиться того же самого с упорядоченными словарями (упорядоченными по языковой гарантии в Python 3.7 или через тип OrderedDict из пакета collections). Однако приведенный выше код является наиболее эффективным с точки зрения памяти.
Я пробовал с seen = {} и видел [item] = None, и это было на 1,5% быстрее.
Если он умещается в ОЗУ,
a = set(data)работает настолько быстро, насколько это возможно. Если он не помещается в ОЗУ, нужно так сказать. Наборы используют хэш-коды под крышками, так что не изобретайте их самостоятельно ;-)