22

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

我见过像这样的解决方案

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

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

cat list | sort | uniq

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

请注意问题“在 Python 中对列表进行 uniqify 的最快方式 ”中的列表未排序，以及“在 Python 列表中进行排序加 uniq 的最简洁方法是什么？' 要求最干净/最 Pythonic 的方式，并且接受的答案表明sorted(set(input))，我正在努力改进。

4

5 回答 5

28

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

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

当谈到 CPython 时，优化事物的方法是在 C 级别尽可能多地做（请参阅此答案以获取另一个反直觉性能的示例）。要获得更快的解决方案，您必须在 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()and then make_unique(seq)andmake_unique(sorted(seq))实际上是一回事，因为 Timsort 使用O(n)空间，你总是有一些重新分配，所以 usingsorted(seq)实际上并没有改变太多的时间。

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

于 2012-11-28T12:58:01.700 回答
5

也许这不是您正在寻找的答案，但无论如何，您应该考虑到这一点。

基本上，您在列表中有 2 个操作：

unique_list = set(your_list)       # O(n) complexity
sorted_list = sorted(unique_list)  # O(nlogn) complexity

现在，你说“在我看来，首先检查唯一性然后排序是浪费的”，你是对的。但是，这个多余的步骤到底有多糟糕？取 n = 1000000：

# sorted(set(a_list))
O(n) => 1000000
o(nlogn) => 1000000 * 20 = 20000000
Total => 21000000

# Your fastest way
O(nlogn) => 20000000
Total: 20000000

速度增益：(1 - 20000000/21000000) * 100 = 4.76 %

对于 n = 5000000，速度增益：~1.6 %

现在，这种优化值得吗？

于 2012-11-28T11:35:29.200 回答
3

这只是我在几分钟内完成的事情。该函数在原地修改列表，并删除连续重复：

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

一些有代表性的输入数据：

inp = [
(u"Tomato", "de"), (u"Cherry", "en"), (u"Watermelon", None), (u"Apple", None),
(u"Cucumber", "de"), (u"Lettuce", "de"), (u"Tomato", None), (u"Banana", None),
(u"Squash", "en"), (u"Rubarb", "de"), (u"Lemon", None),
]

确保两种变体都按要求工作：

print inp
print sorted(set(inp))
# copy because we want to modify it in place
inp1 = inp[:]
inp1.sort()
make_unique(inp1)
print inp1

现在进行测试。我没有使用 timeit，因为我不想为列表的复制计时，而只想对排序计时。time1是sorted(set(...),之后是,time2是Avinash Y的解。list.sort()make_uniquetime3itertools.groupby

import time
def time1(number):
    total = 0
    for i in range(number):
        start = time.clock()
        sorted(set(inp))
        total += time.clock() - start
    return total

def time2(number):
    total = 0
    for i in range(number):
        inp1 = inp[:]
        start = time.clock()
        inp1.sort()
        make_unique(inp1)
        total += time.clock() - start
    return total

import itertools 

def time3(number): 
    total = 0 
    for i in range(number): 
        start = time.clock() 
        list(k for k,_ in itertools.groupby(sorted(inp))) 
        total += time.clock() - start 
    return total

sort + make_unique大约和 一样快sorted(set(...))。我必须再做几次迭代才能看到哪一个可能更快，但在变体中它们非常相似。itertools版本有点慢。

# done each 3 times
print time1(100000)
# 2.38, 3.01, 2.59
print time2(100000)
# 2.88, 2.37, 2.6
print time3(100000)
# 4.18, 4.44, 4.67

现在有一个更大的列表（这+ str(i)是为了防止重复）：

old_inp = inp[:]
inp = []
for i in range(100):
    for j in old_inp:
        inp.append((j[0] + str(i), j[1]))

print time1(10000)
# 40.37
print time2(10000)
# 35.09
print time3(10000)
# 40.0

请注意，如果列表中有很多重复项，则第一个版本要快得多（因为它的排序较少）。

inp = []
for i in range(100):
    for j in old_inp:
        #inp.append((j[0] + str(i), j[1]))
        inp.append((j[0], j[1]))

print time1(10000)
# 3.52
print time2(10000)
# 26.33
print time3(10000)
# 20.5
于 2012-11-28T12:56:27.070 回答
3 
import numpy as np
np.unique(...)

np.unique函数返回一个唯一的 ndarray，并根据类似数组的参数进行排序。这将适用于任何 numpy 类型，但也适用于可排序的常规 python 值。

如果您需要常规的 python 列表，请使用np.unique(...).tolist()

于 2013-11-03T02:24:28.700 回答
1 
>>> import itertools
>>> a=[2,3,4,1,2,7,8,3]
>>> list(k for k,_ in itertools.groupby(sorted(a)))
[1, 2, 3, 4, 7, 8]
于 2012-11-28T11:50:50.313 回答