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将被称为100,000+次.

提前致谢!

Answer 1

你可以使用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)

来自bisect import insort

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实现.