python - 可以使用 Dict 而不是列表来应用 Bisect 吗？

Question

我有一个文件，其信​​息格式如下:

.343423 1
.434322 1
.453434 1
.534342 1

按排序顺序，每一行的大小相等。我有一个带有值的变量“a”，需要获取与第一列中的值相比最接近“a”的行号。

到目前为止，我正在将第一列元素复制到列表中，然后使用二等分方法我得到了 row_num...但是因为我需要执行很多次...这已经变得非常慢，因为我需要复制一些 4000每次都要列出的元素..

所以现在我正在考虑用 dict 而不是数据结构来完成它，因为我会更快...但我不知道我们是否可以在二等分中使用 dict 如果可能的话我们如何在这种情况下使用请建议...如果不可能，他们是否有任何方法可以比正常更快地将数据加载到列表中？？？谢谢你...

Answer 1

与 Dave Kirby 的解决方案类似，请考虑 sortedcontainers模块 PyPI 。它是纯Python，fast ，并提供 SortedDict type with bisect在按键上。对于从文件批量加载数据来说，它也比平衡二叉树类型快得多。

就您而言，类似这样的方法可能会起作用:

from sortedcontainers import SortedDict
with open('data.txt') as fptr:
    sd = SortedDict(map(int, line[1:].split()) for line in fptr)

# sd now contains key, value pairs corresponding to the columns in your data file
# Lookup index of desired key:

pos = sd.bisect(434323)

# pos points to the index of the key 434322
# get that key:

key = sd.iloc[pos]

# now get the value:

value = sd[key]

排序容器模块中的二等分、索引和键查找等操作都非常快。此解决方案要求您可以将文件的全部内容保留在内存中。