13

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

dataList = [

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

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

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

]

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

我想当我想添加它们时我可以使用 insort 或 bisect ，但我不知道如何让它查看子列表的第二个元素。

这里有什么想法吗？我只是将数据附加到末尾，然后进行线性排序以稍后再查找内容。但是，在这里放入几十个数千个子列表，然后搜索 100k 个项目，这需要一段时间。

4

2 回答 2

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

这会按每个项目中的第二个元素对列表进行适当的排序。

正如评论中所指出的，只排序一次（最后）效率更高。Python 的内置排序方法已经过大量优化，可以快速运行。经过测试，在各种大小的列表中，内置排序似乎始终比使用另一个答案中建议的堆方法快 3.7 倍左右（我测试了高达 600000 的大小）。

于 2012-09-07T19:51:55.020 回答
8

取决于几件事，但首先想到的是使用 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)

于 2012-09-07T19:53:35.300 回答