Binäre Suche von Wörtern in Python-Liste

Question

Ich habe zwei Listen von Wörtern zu vergleichen. Die erste Liste ist 2 Millionen Wörter, die zweite Liste ist 150.000 Wörter. Was ich tun muss, ist, binäre Suche anzuwenden, um zu sehen, ob Wörter der ersten Liste in der Sekunde erscheinen. Ich versuchte Liner Suche:

for word in words_list: 
    if word in dict_list: 
     print(word, 1) 
    else: 
     print(word, 0) 

Es funktioniert gut, aber es ist sehr langsam. Dann habe ich versucht binäre Suche, aber es funktionierte nicht richtig:

for word in wordlist: 
    lb = 0 
    ub = len(dict_list) 
    mid_index = (lb + ub) // 2 
    item_at_mid = dict_list[mid_index] 
    if item_at_mid == word: 
     print(word) 
    if item_at_mid < word: 
     lb = mid_index + 1 
    else: 
     ub = mid_index 

Am Ende muss ich zwei Liste erste Liste von Wörtern, die im Wörterbuch sind und zweitens, dass es nicht.

Answer 1

Wenn Sie möchte eine binäre Suche durchführen:

present = [] 
absent = [] 
for word in firstList: 
    lb,ub = 0,len(secondList) - 1 
    found = False 
    while lb <= ub: 
     mid = (lb + ub) // 2 
     if secondList[mid] == word: 
      found = True 
      break 
     elif secondList[mid] < word: 
      lb = mid + 1 
     else: 
      ub = mid - 1 

    if found: 
     present.append(word) 
    else: 
     absent.append(word) 

Ihr binärer Suchcode war falsch.

Answer 2

können Sie Sets verwenden:

inter = set(words_list).intersection(dict_list) 
for word in words_list: 
    if word in inter: 
     print(word, 1) 
    else: 
     print(word, 0) 

Answer 3

Eine Lösung ist mit set statt Liste zu bevorzugen, weil der O(1) Komplexität für __contains__ Betrieb, wie in this solution gegeben.

Wenn Speicher ein Problem ist, dann ist die Verwendung eines bloom filter wahrscheinlich ein guter Kompromiss (kein falsches Negativ).

Here is a python implementation.

---

Um einen Binärbaum zu erstellen und zu pflegen, sollten Sie das Standardmodul heapq verwenden.

Answer 4

Wenn Sie die binäre Suche verwenden, sollte Ihre Eingabe geordnet sein. Eine andere Möglichkeit ist, Ihre words_list und dict_list-set wandeln und die Ausgabe zu erhalten, wie folgt:

Wörter beiden gemeinsam:

words_list.intersection(dict_list) 

Worte nicht in einem anderen:

words_list-dict_list 
dict_list-words_list