时间戳

首页 > 解决方案 > 在 dict() 上使用 `bisect_left()` 会引发 `dict is not a sequence` 错误。如何遍历 dict() 以改进搜索过程时间

python - 在 dict() 上使用 `bisect_left()` 会引发 `dict is not a sequence` 错误。如何遍历 dict() 以改进搜索过程时间

问题描述

这是我的代码。我正在尝试从 word 文件创建一个 dict 并将其用于搜索过程。我使用相同的方法bisect_left()会引发序列错误listsdict()

import bisect
fln = open("CROSSWD.TXT")

def create_dict(x):
    new_dict=dict()
    i=0
    for line in x:
        word=line.strip()
        new_dict[word]= i
        i+=1
    return new_dict #create a new_dict

如何在字典上使用 bisect_left？

def search_dict(new_dict,s):
    i= bisect_left(new_dict,s) #raises a sequence error. what other method can I use?
    if s in new_dict[i]:
        return True
    else:
        return False
                            
s='zebra'

new_dict=create_dict(fln)

if search_dict(new_dict,s):
    print(s," in dict")
else:
    print(s," not in dict")

标签： pythonpython-3.x

解决方案

bisect_left需要一个支持整数索引的对象，因为二分算法需要知道“中间”元素是什么才能平分序列。C 实现bisect_left令人困惑地提出了一个TypeError类型对象dict没有长度的声明。虽然这种说法是错误的，但最好dict比纯 Python 版本（见下文）更早地检测和拒绝参数。

也就是说，不需要bisect在 a 上使用dict: adict的目的是允许 O(1) 通过散列访问对象，而不是通过二进制搜索来搜索它 O(log n) 时间。

的纯 Python 版本bisect_left，减去一些注释：

def bisect_left(a, x, lo=0, hi=None):
    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if a[mid] < x: lo = mid+1
        else: hi = mid
    return lo

请注意，这len(a)是在假设您可以稍后a使用从长度派生的整数进行索引的情况下计算的。a 不是这样的dict（或者如果你没有得到 a KeyError，它肯定不会帮助你找到你的目标）。此外，一旦bisect模块定义了纯 Python 函数，它就会尝试用从_bisect. 这些功能显然会提前检查以确保a不是dict. 引发的错误消息有点误导。

推荐阅读