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

Question

我有一个文件包含以下模式的信息:

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

每个行和行按排序顺序大小相等.我有一个带有值的变量"a",需要得到与第一列中的值相比最接近"a"的行号.

直到现在我正在将第一列元素复制到列表中然后使用bisect方法我得到了row_num ...但是因为我需要执行这么多次..这已经变得非常缓慢,因为我需要复制一些4000元素到列表每次..

所以现在我想用dict而不是数据结构这样做,因为我会更快...但我不知道我们是否可以在bisect中使用dict如果可能我们如何使用这种情况请建议...如果不可能是他们将数据加载到列表中的任何方法都比正常情况更快 感谢您...

Answer 1

与Dave Kirby的解决方案类似,请考虑PyPI上的sortedcontainers模块.它是纯Python,快速,并提供SortedDict类型与键的二等分.对于从文件批量加载数据,它也比平衡二叉树类型快得多.

在你的情况下,这样的事情可能会起作用:

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]

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