Искать элемент в списке с 2 миллионами элементов - Python

Question

У меня есть список строк из 1,9-2 МИЛЛИОНОВ предметов .

Следующий код:

items = [...]
item_in_list = items[-1] in items

занимает 0,1 секунды

С sqlite3 это занимает 0,7 секунды

---

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

Точнее, я пытаюсь синхронизировать содержимое файла CSV с вычисленными значениями в БД.

---

Есть идеи? Было бы действительно здорово :) 1028 *

Answer 1

Поместите обе коллекции в морозильное устройство.

небольшой тест производительности:

import random
from timeit import Timer

def random_strings(size):
    alpha = 'abcdefghijklmnopqrstuvwxyz'
    min = 3
    max = 8
    strings = []
    for count in xrange(1, size):
        current = ''
        for x in random.sample(alpha, random.randint(min,max)):
            current += x  
        strings.append(current)
    return strings

string_list_1 = random_strings(10000)
string_list_2 = random_strings(10000)

def string_test():
    common = filter(lambda x: x in string_list_2, string_list_1)
    return common

def set_test():
    string_set_1 = frozenset(string_list_1)
    string_set_2 = frozenset(string_list_2)
    common = string_set_1 & string_set_2
    return common

string_timer = Timer("__main__.string_test()", "import __main__")
set_timer = Timer("__main__.set_test()", "import __main__")
print string_timer.timeit(10)
# 22.6108954005
print set_timer.timeit(10)
#  0.0226439453

Как видите, набор экспоненциально быстрее.Должен работать лучше, чем словарь.

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

Answer 2

Для такого поиска я бы выбрал бинарный поиск. Один из быстрых методов для длинных сортированных списков. Если он не отсортирован, не используйте бинарный поиск.

Answer 3

у меня в голове, с такой маленькой информацией о том, почему вы делаете это несколько миллионов раз:

1.) Вы можете импортировать CSV в таблицу и выполнить проверки в SQL?

2.) Как насчет сортировки и индексации списка для быстрого доступа?

cheers, P

Answer 4

У вас есть два миллиона строк, которые нужно сопоставить с миллионом других строк‽

Несколько вещей, которые нужно попробовать:

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

Обновление:

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