如何在创建列表时保持列表的排序

Question

我正在读取一个文件,并在Python中提取包含一些字符串和一些数字的数据.我将这些信息存储为列表列表,如下所示:

dataList = [

['blah', 2, 3, 4],

['blahs', 6, 7, 8],

['blaher', 10, 11, 12],

]

我想保持dataList按子列表的第二个元素排序:dataList [] [1]

当我想要添加它们时,我想我可以使用insort或bisect,但是我无法弄清楚如何让它看看子列表的第二个元素.

这有什么想法？我只是将数据附加到最后,然后进行线性排序以便稍后查找.但是,在这里抛出几十个数千个子列表,然后搜索10万个项目,这需要一段时间.

Answer 1

dataList.sort(key=lambda x: x[1])

这将按照每个项目中的第二个元素对列表进行排序.

正如评论中指出的那样,只排序一次(最后)效率更高.Python的内置排序方法已经过大量优化,可以快速工作.在测试之后,看起来内置排序的速度始终比使用其他答案中建议的堆方法快3.7倍,而不是各种大小的列表(我测试的大小高达600000).

Answer 2

取决于一些事情,但首先想到的是使用heapq模块:

import heapq
heap = []
for row in rows:
    heapq.heappush(heap, (row[1], row))

这将创建一个充满元组的堆,其中第一个元素是您要排序的元素,第二个元素是行.

从堆中读取它们的最简单方法是复制它然后弹出项:

new_heap = list(heap)
while new_heap:
    _, row = heapq.heappop(new_heap)
    print row

将每个项目插入堆中的运行时间是O(lg N),因此创建堆将需要O(N lg N)时间,并且从堆中弹出项目也需要O(lg N)时间,因此需要时间O(N lg N)来遍历它.

如果这些权衡不理想,你可以使用二进制搜索树(标准库中不存在,但很容易找到它们),或者像其他评论者建议的那样,在阅读后对行进行排序:rows.sort(key=lambda row: row[1]).

现在,实际上,除非你处理大量的行,否则在加载它之后对列表进行就地排序几乎肯定会更快(即,使用该.sort()方法)...所以尝试一些东西看看什么效果最好.

最后,这bisect是一个糟糕的主意,因为插入Python列表需要O(N)时间,因此插入带有bisect的项目需要每个项目的O(N lg N)时间,因此需要总时间.O((N lg N) * N) = O(N**2)