可以用字典而不是列表进行二分查找吗？

Question

我有一个文件，里面的信息是这样的：

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

每一行和每一列的大小都是一样的，并且是排好序的。我有一个变量“a”，它有一个值，我需要找到和“a”最接近的那一行的行号，这个比较是基于第一列的值。

到目前为止，我一直是把第一列的元素复制到一个列表里，然后用二分查找的方法来获取行号……但是因为我需要多次执行这个操作，这样做变得非常慢，因为每次我都要把大约4000个元素复制到列表里。

所以现在我在考虑用字典来代替数据结构，这样可能会更快……但我不知道在二分查找中是否可以使用字典，如果可以的话，应该怎么用呢？如果不行的话，有没有什么方法可以比正常的方式更快地把数据加载到列表里？谢谢你……

Answer 1

我不明白为什么需要复制这些元素。这是比较慢的部分。难道不能在启动时加载一次列表，然后一直使用同一个列表吗？

而且字典的速度总是比列表慢（我觉得[不太确定]它是作为哈希表实现的，所以没有顺序，这样你就不能使用二分查找了）。

Answer 2

这里有一种方法可以使用 bisect，而不需要读取整个文件。无论如何，操作系统最终会读取比你实际需要的更多文件内容，所以直到 data.txt 文件足够大之前，你不会看到性能上的提升。

from os import SEEK_END
from bisect import bisect

class ListProxy(object):
    def __init__(self, f):
        self.f = f
        self.line_len = len(f.readline())
        self.f.seek(0, SEEK_END)
        self.num_lines = self.f.tell()//self.line_len

    def __len__(self):
        return self.num_lines

    def __getitem__(self, idx):
        self.f.seek(idx*self.line_len)
        return float(self.f.read(7))

with open("data.txt") as f:
    lp = ListProxy(f)    
    num = .44
    idx = bisect(lp, num)
    if idx != 0 and num - lp[idx-1] < lp[idx] - num:
        idx -=1
    print num, idx

Answer 3

类似于Dave Kirby的解决方案，可以考虑使用sortedcontainers模块，这个模块在PyPI上可以找到。它是用纯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模块中，进行二分查找、索引和键查找的操作都非常快速。不过，这个解决方案要求你能够将文件的全部内容都放在内存中。