替代python的.sort()(用于插入大型列表并保持其排序)

Question

我需要不断添加数字到预先排序的列表:

for num in numberList:
    list.append(num)
    list.sort()

每次迭代都很短,但是当给定的numberList包含数万个值时,此方法会减慢速度.是否有更高效的可用功能使列表保持不变并找出插入新数字的索引以保持正确的数字顺序？我尝试写的任何东西都需要比.sort()更长的时间

Answer 1

您可以使用该bisect.insort()函数将值插入已排序的列表中:

from bisect import insort

insort(list, num)

请注意,这仍然需要一些时间,因为插入点之后的所有元素都必须向上移动一步; 您可能想要考虑将列表重新实现为链接列表.

但是,如果要保持列表排序只是为了始终能够获得最小或最大的数字,则应该使用该heapq模块 ; 堆不是按严格的排序顺序保存的,但是在任何时候都能非常快速地为您提供最小值或最大值.

Answer 2

请参阅在列表上实现插入排序的原生bisect.insort(),这应该完全符合您的需求,因为复杂性最好是O(n)而最坏的是O(n ^ 2)而不是O(nlogn)与您当前的解决方案(插入后诉诸).

但是,有更快的替代方法来构建排序数据结构,例如跳过列表和二进制搜索树,这将允许插入最多的复杂度O(log n)和最坏的O(n),或甚至更好的B树,红色- 黑树,Splay树和AVL树,在最佳和最差情况下都具有复杂度O(log n).关于所有这些解决方案和其他解决方案的复杂性的更多信息可以在Eric Rowell 的伟大BigO CheatSheet中找到.但请注意,所有这些解决方案都要求您安装第三方模块,通常需要使用C编译器进行编译.

但是,有一个名为sortedcontainers的pure-python模块,声称与AVL树和B树实现的C编译Python扩展一样快或更快(此处可用基准测试).

我对几个解决方案进行了基准测试,看看哪个是最快的插入排序:

sortedcontainers: 0.0860911591881
bisect: 0.665865982912
skiplist: 1.49330501066
sort_insert: 17.4167637739

这是我用来进行基准测试的代码:

from timeit import Timer
setup = """
L = list(range(10000)) + list(range(10100, 30000))
from bisect import insort

def sort_insert(L, x):
    L.append(x)
    L.sort()

from lib.skiplist import SkipList
L2 = SkipList(allowDups=1)
for x in L:
    L2.insert(x)

from lib.sortedcontainers import SortedList
L3 = SortedList(L)
"""

# Using sortedcontainers.SortedList()
t_sortedcontainers = Timer("for i in xrange(10000, 10100): L3.add(i)", setup)
# Using bisect.insort()
t_bisect = Timer("for i in xrange(10000, 10100): insort(L, i)", setup)
# Using a Skip List
t_skiplist = Timer("for i in xrange(10000, 10100): L2.insert(i)", setup)
# Using a standard list insert and then sorting
t_sort_insert = Timer("for i in xrange(10000, 10100): sort_insert(L, i)", setup)

# Timing the results
print t_sortedcontainers.timeit(number=100)
print t_bisect.timeit(number=100)
print t_skiplist.timeit(number=100)
print t_sort_insert.timeit(number=100)

因此,结果表明排序的容器确实比bisect快了近7倍(我希望速度差距随着列表大小而增加,因为复杂性是一个数量级的不同).

更令人惊讶的是,跳过列表比bisect更慢,但可能是因为它没有像bisect一样优化,后者在C中实现并且可能使用一些优化技巧(注意我使用的skiplist.py模块是最快的 - Python Skip List我可以找到,pyskip模块要慢很多).

另外值得注意的是:如果您需要使用比列表更复杂的结构,则sortedcontainers模块提供SortedList,SortedListWithKey,SortedDict和SortedSet(而bisect仅适用于列表).此外,您可能会对这个有点相关的基准以及各种Python操作的复杂性备忘录感兴趣.