Python - 高效查找列表中的元素

Question

我有一个列表，叫做 list_a，里面包含了一些浮动的数字：

list_a = [[[ 0 for i in range(40)] for j in range(1000)]for k in range(47)]

还有一个这个列表的排序版本：

list_a_sorted = list_a
list_a_sorted[0].sort()

所以 list_a_sorted 是经过排序的，里面的值是从小到大排列的。假设它是这样的：

[2.3,3.1.........9]

在这个列表中，2.3 是最小的值，但我怎么知道它在 list_a 中是第8个元素，还是第15个，或者是第n个呢？

因为我的列表比较大，所以我也希望能尽可能高效地找到这个信息。任何帮助都非常感谢！

Answer 1

如果速度很重要（比如你有一种情况是“创建一次，频繁查找”，而且没有重复的条目（如果有重复的话可以用set）），那么我建议你在创建列表的时候，建立一个字典，把每个项目当作键，索引当作值。这样的话，无论字典有多长，你查找的时间始终都是O(1)，也就是非常快。不过这里有很多“如果”的情况...

Answer 2

要在一个列表中找到某个元素的位置，你可以使用 l.index(某个东西)。

http://docs.python.org/library/stdtypes.html#typesseq

Answer 3

如果你想在一个没有排序的列表中找到最小的 n 个值，可以看看 heapq.nsmallest() 这个方法。如果 n 的值不是太大，这个方法可能会更高效。要找到最小值的位置，可以试试这个：

>>> from heapq import nsmallest
>>> from random import random
>>> values = [random() for i in range(20)]
>>> values
[0.012227103410989537, 0.9782624648209769, 0.9896111545377924, 0.9033620518745159, 0.6767780103989406, 0.4595455061820246, 0.39814471642551696, 0.6904798136040561, 0.8727083752258934, 0.6680153337266017, 0.606044647078923, 0.5644656135679249, 0.934351848916147, 0.05955628567745763, 0.7236000566917332, 0.8303865367817055, 0.9671576336593124, 0.3164892315873573, 0.8416372881413415, 0.5009057933309073]
>>> nsmallest(4, range(len(values)), key=lambda i: values[i])
[0, 13, 17, 6]

或者有一种更快但稍微不太清晰的方法：

>>> nsmallest(4, range(len(values)), key=values.__getitem__)
[0, 13, 17, 6]

对于你的列表，你可能想要类似这样的东西（代码未经测试）：

def indices():
    for k in range(47):
        for j in range(1000):
            for i in range(40):
                yield k, j, i
def keyfn(ind):
    k, j, i = ind
    return list_a[k][j][i]

print(nsmallest(4, indices(), key=keyfn))