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已经排序并包含了从最小值开始的list_a数值。让我们假设它如下所示：

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

那么2.3是最小值，但我如何知道它是在list_a中的第8个元素还是第15个元素或第n个元素呢？

由于我的列表非常大，所以我也需要尽可能高效地完成这项任务。感谢任何帮助。

- Mandeep

---

list_a_sorted的目的只是为了实现高效的搜索吗？我这么问是因为，最高效的排序算法的复杂度是O(n log n)，而最糟糕的查找（逐个遍历元素）的复杂度是O(n)。如果list_a_sorted仅用于帮助查找元素，则在未排序的列表内查找会更具性能优势。 - c-ram

那是个好观点。最终，我需要在已排序的列表中找到n个最小值，因此我认为排序列表会使查找这些值更容易。 - Mandeep

Answer 1

要在列表中找到元素的位置，您可以使用l.index(something)。 http://docs.python.org/library/stdtypes.html#typesseq

- Gryphius

---

这是正确的，但每次查找都是O(n)，他说列表非常大，所以效率不高。而且，如果任何值是重复的，你只会得到相同的索引，而不是两个值。 - Duncan

Answer 2

如果你想在未排序的列表中找到前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))

- Duncan

---

这看起来很有用。对于我的列表，即：list_a = [[[0 for i in range(40)] for j in range(1000)] for k in range(47)]，我该如何在k维度中找到nsmallest？ - Mandeep

我已经扩展了我的答案，以找到 nsmallest。你可以从中挑选出 k 个值，但可能会出现重复。如果您不想要重复的 k 值，则可能希望在嵌套列表上使用 min()，并仅在外部级别使用 nsmallest()。 - Duncan

感谢您，重复的内容也没问题：） - Mandeep

Answer 3

如果速度很重要（例如，“创建一次，经常查找”），并且没有重复项（如果有，请使用set），那么我建议您在创建列表时创建一个字典，其中每个项目作为键，其索引作为值。在这种情况下，无论字典的长度如何，您始终具有O（1）的查找时间。有许多“如果”的情况...

- Fredrik Pihl

Answer 4

回答评论中的问题...

如果L是数字列表，这将返回n个最小项的索引

[j for i,j in sorted((j,i) for i,j in enumerate(L))[:n]]

这里有另一种方法，稍微有点棘手

sorted(range(len(L)), key=L.__getitem__)[:n]

哪个更有效率留给读者练习 :)

- John La Rooy