Python能有效地找到排序列表中的某个地方吗？

Question

我有一个清单：

x = ['c', 'a', 'e']

我可以排序此列表：

x_sorted = sorted(x)

x_sorted现在是['a', 'c', 'e']

现在假设我有一个新变量y = 'd'

我想找出这个新变量在x_sorted中的位置。在本例中，新变量y包含字符串'd'，因此它将作为['a', 'c', 'd', 'e']放置在列表的索引2中。我希望尽可能有效地找出这个索引号（因为我必须重复这个过程很多次）。你知道吗

下面是我编写的一个函数，它非常简单：

def f(x_sorted, y):
    new_list = x_sorted[:] + [y]
    return sorted(new_list).index(y)

这给了我正确的答案。你知道吗

我想知道是否有更好更有效的方法来做这件事，因为f将被称为100000+次。你知道吗

提前谢谢！你知道吗

Answer 1

这肯定不是您在问题中演示的有效方法，在这种情况下，您每次都对其进行排序，因此如果执行此操作m倍，复杂性将是O(m*n*log(m))，因此首选方法是对其排序一次，然后简单地遍历列表以查找索引，这可以在O(n)中完成，但是最好的方法是使用二进制搜索，现在您的时间复杂度将降到O(log(n))。对于这类问题来说，这是最小的复杂性。你知道吗

Answer 2

你可以使用bisect

from bisect import bisect

l = ['a', 'c', 'e']

print(bisect(l,"d"))
2

要将其添加到列表中：

from bisect import insort


l = ['a',"b", 'c', 'e']

insort(l, "d")
print(l)
insort(l, "f")
print(l)

['a', 'b', 'c', 'd', 'e']
['a', 'b', 'c', 'd', 'e', 'f']

如果希望更快地插入，可以使用blist，其中使用insort维护排序列表是：

O(log**2 n)  vs  O(n)

从对分导入

from blist import blist

b = blist(["a", "b", "c", "e"])
insort(b, "f")
insort(b, "d")
print(b)
blist(['a', 'b', 'c', 'd', 'e', 'f'])

还有一个blist.sortedlist列表，您可以在其中使用.add：

from blist import sortedlist

l = ['b',"a", 'c', 'e']
b = sortedlist(l)

b.add("f")
print(b)
sortedlist(['a', 'b', 'c', 'e', 'f'])

还有一个sortedcontainers库具有sortedlist实现。你知道吗

Answer 3

如果x没有改变，或者很少改变，您可以对它进行预排序，然后在排序的列表上使用二进制搜索。这将导致每次排序的O(n logn)成本加上每次后续查找的O(logn)。你知道吗

如果x变化很大，可以使用线性搜索：

>>> x = ['c', 'a', 'e']
>>> y = 'd'
>>> sum(y > el for el in x)
2

这具有O(n)查找复杂性。你知道吗