Najbardziej efektywny sposób wyszukiwania/wyszukiwania na ogromnej liście (python)

Question

- Właśnie sparsowałem duży plik i utworzyłem listę zawierającą 42 000 ciągów/słów. Chcę zapytać [z tej listy], aby sprawdzić, czy dane słowo/ciąg znaków należy do niego. Więc moje pytanie brzmi:

Jaki jest najbardziej skuteczny sposób takiego wyszukiwania?

Pierwsze podejście jest, aby posortować listę (list.sort()), a następnie po prostu użyć

>> if word in list: print 'word' 

który jest naprawdę trywialne i jestem pewien, że istnieje lepszy sposób to zrobić. Moim celem jest zastosowanie szybkiego wyszukiwania, które wyszuka, czy dany ciąg jest na tej liście, czy nie. Jeśli masz jakieś pomysły na inną strukturę danych, są mile widziane. Jednak chcę teraz na razie unikać bardziej wyrafinowanych struktur danych, takich jak Tries itp. Interesują mnie pomysły (lub triki) dotyczące szybkiego wyszukiwania lub jakiejkolwiek innej metody biblioteki Pythona, która może wykonać wyszukiwanie szybciej niż proste in.

A także chcę wiedzieć indeks szukanej

Answer 1

Nie twórz list utwórz set. Wykonuje wyszukiwanie w stałym czasie.

Jeśli nie chcesz narzucić na pamięć zestawu, zachowaj posortowaną listę i przeszukaj ją za pomocą modułu bisect.

from bisect import bisect_left 
def bi_contains(lst, item): 
    """ efficient `item in lst` for sorted lists """ 
    # if item is larger than the last its not in the list, but the bisect would 
    # find `len(lst)` as the index to insert, so check that first. Else, if the 
    # item is in the list then it has to be at index bisect_left(lst, item) 
    return (item <= lst[-1]) and (lst[bisect_left(lst, item)] == item) 

Answer 2

Punkt o zestawach porównaniu listach, które nie zostało uznane: w „parsowania duży plik” można by oczekiwać, aby trzeba obsłużyć powielać słowa/sznurki. W ogóle o tym nie wspominałeś.

Oczywiście dodawanie nowych słów do zestawu usuwa duplikaty w locie, bez dodatkowych kosztów czasu procesora lub czasu myślenia. Jeśli spróbujesz tego z listą, kończy się ona O (N ** 2). Jeśli dołączysz wszystko do listy i usuniesz duplikaty na końcu, najmądrzejszym sposobem na to jest ... rolka bębna ... użyj zestawu, a przewaga (małej) pamięci listy może zostać przytłoczona przez duplikaty.

Answer 3

Jeśli przewidujesz skomplikowane wyszukiwania później - i przez kompleks rozumiem nie banalne - polecam przechowywać go w sqlite3.

Answer 4

Za pomocą tego programu to wygląda dicts są fastes, zestaw drugi, lista z bi_contains trzecim:

from datetime import datetime 

def ReadWordList(): 
    """ Loop through each line in english.txt and add it to the list in uppercase. 

    Returns: 
    Returns array with all the words in english.txt. 

    """ 
    l_words = [] 
    with open(r'c:\english.txt', 'r') as f_in: 
     for line in f_in: 
      line = line.strip().upper() 
      l_words.append(line) 

    return l_words 

# Loop through each line in english.txt and add it to the l_words list in uppercase. 
l_words = ReadWordList() 
l_words = {key: None for key in l_words} 
#l_words = set(l_words) 
#l_words = tuple(l_words) 

t1 = datetime.now() 

for i in range(10000): 
    #w = 'ZEBRA' in l_words 
    w = bi_contains(l_words, 'ZEBRA') 

t2 = datetime.now() 
print('After: ' + str(t2 - t1)) 

# list = 41.025293 seconds 
# dict = 0.001488 seconds 
# set = 0.001499 seconds 
# tuple = 38.975805 seconds 
# list with bi_contains = 0.014000 seconds