我可以建立一个清单，并在同一时间进行排序吗？

我正在编写一段软件的脚本，它并没有真正让我直接访问我需要的数据。相反，我需要询问我需要的每一条信息，并建立我得到的数据列表。由于各种原因，我需要对列表进行排序。一次构建列表非常简单，然后对其进行排序，然后对其进行排序。但是，我认为运行一次的速度会更快，而不是构建列表然后对其进行排序。我可以建立一个清单，并在同一时间进行排序吗？

因此，在现阶段，我已经基本上得到了这个：

my_list = [] 

for item in "query for stuff": 
    my_list.append("query for %s data" % item) 

my_list.sort() 

do_stuff(my_list)

的“查询东西”位与软件，这将给我一个迭代查询界面。 my_list需要包含来自所述迭代的内容的数据列表。通过这样做，我查询了第一个列表，然后遍历它以提取数据并将其放入my_list。然后我正在整理它。最后，我正在用do_stuff（）方法来处理它，它会遍历它并为每个项目执行一些操作。

问题是，我不能do_stuff（）它排序之前，因为列表顺序是重要的各种原因。我不认为我可以避免重复列表两次 - 一次建立列表，一次为其中的每个项目执行任务，因为我们事先不知道最近在位置N添加的项目是否会在我们添加下一个项目之后停留在位置N - 但是以分类的方式插入每个项目似乎更简洁，而不是在最后添加它们。有点像这样：

for item in "query for stuff": 
    my_list.append_sorted(item)

是否值得打扰尝试做这样的，或者我应该只是坚持建立列表，然后排序呢？

谢谢！

来源

2011-11-05 Simon Lundberg

简短的回答是：这不值得。

看看insertion sort。最坏的情况下运行时间是O(n^2)（平均情况也是二次的）。另一方面，Python's sort（也称为Timsort）在最坏的情况下将采取O(n log n)。

是的，它确实“看起来”更干净，以保持列表排序，因为你插入，但这是一个谬误。它没有真正的好处。唯一一次考虑使用插入排序的方式是每次插入后需要显示排序列表。

来源

2011-11-05 15:59:04 misha

这是错误的。如果正确执行，则将元素插入到已排序的列表中为O（log（n））。如果您需要每个插入之间的排序列表，比保留排序列表效率更高。 –

您正在考虑抽象清单。 Python列表是作为数组实现的。这意味着平均情况下的插入成本O（n），无论您插入的位置如何。请参阅https://wiki.python.org/moin/TimeComplexity。 – misha

这两种方法是渐近等价的。排序是O（n lg n）（默认情况下Python使用Timsort，除了非常小的数组外），并且在排序列表中插入O（lg n）（使用二分搜索），您必须执行此操作n次。

实际上，一种方法或另一种方法可能会稍快一些，这取决于您的数据已经排序了多少。

编辑：我认为在排序列表中的中间插入你找到后插入点是固定的时间（即表现得像一个链表，这是的数据结构，你会列表用于这样的算法）。正如Sven所指出的，Python列表可能并非如此。这将使得“保持列表排序”方法O（n^2），即插入排序。

我说“可能”是因为列表增长时列表实现从数组切换到链表，最显着的例子是CoreFoundation/Cocoa中的CFArray/NSArray。 Python可能会或可能不会这样。

来源

2011-11-05 16:01:32

在已排序（Python）列表中插入的是O（n），而不是O（log n）。 Python列表以数组存储。 –

@SvenMarnach你是对的，我相应地更新了我的答案。 –

你会如何查找链接列表？您使用的数据结构是某种平衡树。 –

查看bisect模块。它为您提供维护列表顺序的各种工具。在你的情况下，你可能想要使用bisect.insort。

for item in query_for_stuff(): 
    bisect.insort(my_list, "query for %s data" % item)

来源

2011-11-05 16:05:16 poke

我可以建立一个清单，并在同一时间进行排序吗？

回答

相关问题