python 列表中单词的二进制搜索

Question

我有两个单词列表要比较。第一个列表是 200 万个单词，第二个列表是 150,000 个单词。我需要做的是应用二进制搜索来查看第一个列表中的单词是否出现在第二个列表中。我正在尝试线性搜索：

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

效果很好，但是速度很慢。然后我尝试了二进制搜索，但它没有正常工作：

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

最后我需要两个列表，第一个是字典中的单词列表，第二个是不在字典中的单词列表。

Answer 1

您可以使用集合：

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

Answer 2

一个解决方案是更喜欢使用 set 而不是列表，因为 __contains__ 操作的 O(1) 复杂性，如 .[=18= 中给出的]

如果内存有问题，那么使用 bloom filter 可能是一个很好的权衡（没有漏报）。

Here is a python implementation.

要创建和维护二叉树，请考虑使用 heapq 标准模块。

Answer 3

如果您使用二进制搜索，您的输入应该是有序的。另一种可能性是将 words_list 和 dict_list 转换为 set 并获得如下输出：

两者共同的词：

words_list.intersection(dict_list)

不属于彼此的单词：

words_list-dict_list
dict_list-words_list

Answer 4

如果您想进行二分查找：

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)

您的二进制搜索代码不正确。

python 列表中单词的二进制搜索

Binary search of words in python list

python

search

list

binary-search