Поиск элемента в списке с товарами 2MILLION - Python

Question

У меня есть список строк из 1.9-2 MILLION items.

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

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

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

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

---

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

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

---

Любые идеи? Было бы действительно здорово :)

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

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

Answer 3

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

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

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

Update:

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

Answer 4

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

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

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

веселит, P