Cách hiệu quả nhất để tra cứu/tìm kiếm trong một danh sách lớn (python)

Question

- Tôi vừa phân tích cú pháp một tệp lớn và tạo danh sách chứa 42.000 chuỗi/từ. Tôi muốn truy vấn [chống lại danh sách này] để kiểm tra xem một từ/chuỗi đã cho thuộc về nó hay không. Vì vậy, câu hỏi của tôi là:

Cách hiệu quả nhất để tìm kiếm như vậy là gì?

Một cách tiếp cận đầu tiên là để sắp xếp danh sách (list.sort()) và sau đó chỉ cần sử dụng

>> if word in list: print 'word' 

mà thực sự tầm thường và tôi chắc chắn có một cách tốt hơn để làm điều đó. Mục tiêu của tôi là áp dụng tra cứu nhanh để tìm xem liệu một chuỗi đã cho có nằm trong danh sách này hay không. Nếu bạn có bất kỳ ý tưởng nào về cấu trúc dữ liệu khác, chúng được hoan nghênh. Tuy nhiên, bây giờ tôi muốn tránh các cấu trúc dữ liệu phức tạp hơn như Tries ... Tôi thích nghe ý tưởng (hoặc thủ thuật) về tra cứu nhanh hoặc bất kỳ phương thức thư viện python nào khác có thể thực hiện tìm kiếm nhanh hơn đơn giản in.

Và cũng tôi muốn biết chỉ số của mặt hàng đó tìm kiếm

Answer 1

Đừng tạo ra một list, tạo một set. Nó tra cứu trong thời gian liên tục.

Nếu bạn không muốn phí trên bộ nhớ của một tập hợp, hãy giữ một danh sách được sắp xếp và tìm kiếm qua nó với mô-đun 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

Một điểm về bộ so với danh sách mà chưa được xem xét: trong "phân tích một tập tin lớn" người ta sẽ mong đợi để cần phải xử lý trùng lặp lời/chuỗi. Bạn đã không đề cập đến điều này cả.

Rõ ràng việc thêm từ mới vào tập hợp sẽ loại bỏ trùng lặp khi đang di chuyển, không mất thêm chi phí thời gian CPU hoặc thời gian suy nghĩ của bạn. Nếu bạn thử với một danh sách nó kết thúc lên O (N ** 2). Nếu bạn chắp thêm mọi thứ vào danh sách và xóa các bản sao ở cuối, cách thông minh nhất là ... cuộn trống ... sử dụng tập hợp và lợi thế bộ nhớ (nhỏ) của danh sách có thể bị choáng ngợp bởi trùng lặp.

Answer 3

Nếu bạn dự đoán tra cứu phức tạp sau này - và phức tạp tôi có nghĩa là không tầm thường - Tôi khuyên bạn nên lưu trữ nó trong sqlite3.

Answer 4

Sử dụng chương trình này có vẻ như dicts là fastes, set thứ hai, danh sách với bi_contains thứ ba:

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