python - 在python中获得排序唯一列表的最快方法？

Question

在python中获得排序的唯一列表的最快方法是什么？ (我有一个可散列的东西的列表，并且想要有一些我可以迭代的东西 - 无论列表是否被修改，或者我得到一个新列表，还是一个可迭代的。在我的具体用例中，我我使用一次性列表来执行此操作，因此在适当的位置会更节省内存。)

我见过类似的解决方案

input = [5, 4, 2, 8, 4, 2, 1]
sorted(set(input))

但在我看来，首先检查唯一性然后排序是浪费的(因为当您对列表进行排序时，您基本上必须确定插入点，从而获得唯一性测试作为副作用)。也许还有更多类似unix的东西

cat list | sort | uniq

这只是在已经排序的列表中挑选出连续的重复项？

---

注意问题' Fastest way to uniqify a list in Python ' 列表未排序，并且 ' What is the cleanest way to do a sort plus uniq on a Python list? ' 要求最干净/最 Pythonic 的方式，并且接受的答案建议 sorted(set(input))，我正在尝试改进。

Answer 1

我相信 sorted(set(sequence)) 是最快的方法。是的，set 迭代序列，但这是一个 C 级循环，比您在 python 级执行的任何循环都快很多。

请注意，即使使用 groupby 你仍然有 O(n) + O(nlogn) = O(nlogn) 最糟糕的是 groupby 将需要一个 python 级别的循环，这会显着增加该 O(n) 中的常量，因此最终您会得到最差的结果。

当谈到 CPython 时，优化事物的方法是在 C 级别尽可能多地做(参见 this 答案以获取另一个反直觉性能示例)。要获得更快的解决方案，您必须在 C 扩展中重新实现排序。即便如此，也祝你获得与 python 的 Timsort 一样快的东西!

“规范解决方案”与 groupby 解决方案的小比较:

>>> import timeit
>>> sequence = list(range(500)) + list(range(700)) + list(range(1000))
>>> timeit.timeit('sorted(set(sequence))', 'from __main__ import sequence', number=1000)
0.11532402038574219
>>> import itertools
>>> def my_sort(seq):
...     return list(k for k,_ in itertools.groupby(sorted(seq)))
... 
>>> timeit.timeit('my_sort(sequence)', 'from __main__ import sequence, my_sort', number=1000)
0.3162040710449219

你可以看到它慢了 3 倍。

jdm提供的版本其实更差:

>>> def make_unique(lst):
...     if len(lst) <= 1:
...         return lst
...     last = lst[-1]
...     for i in range(len(lst) - 2, -1, -1):
...         item = lst[i]
...         if item == last:
...             del lst[i]
...         else:
...             last = item
... 
>>> def my_sort2(seq):
...     make_unique(sorted(seq))
... 
>>> timeit.timeit('my_sort2(sequence)', 'from __main__ import sequence, my_sort2', number=1000)
0.46814608573913574

慢了将近 5 倍。请注意，使用 seq.sort() 然后 make_unique(seq) 和 make_unique(sorted(seq)) 实际上是同一件事，因为Timsort 使用 O(n) 空间你总是有一些重新分配，所以使用 sorted(seq) 实际上并不会改变太多的时间。

jdm 的基准测试给出不同的结果，因为他使用的输入太小，因此所有时间都被 time.clock() 调用占用。