在Python中,从列表中删除重复项的最快算法是什么,以便所有元素都是唯一的*同时保留顺序*？

例如:

>>> x = [1, 1, 2, 'a', 'a', 3]
>>> unique(x)
[1, 2, 'a', 3]

假设列表元素是可清除的.

澄清:结果应该保留列表中的第一个副本.例如,[1,2,3,2,3,1]变为[1,2,3].

1> Terhorst..：

---

def unique(items):
    found = set([])
    keep = []

    for item in items:
        if item not in found:
            found.add(item)
            keep.append(item)

    return keep

print unique([1, 1, 2, 'a', 'a', 3])

---

set()优于set([]).

---

这是一个旧线程,但是如果你在add()和append()方法中使用局部函数(在循环之前放入`add = found.add`和`app = keep.append`然后使用`add(item)`和`app(item)`,这是迄今为止最快的.字典使用速度更快的原因是它不需要为每个添加和附加进行属性查找.只需要我的两分钱.

2> John Fouhy..：

---

使用:

lst = [8, 8, 9, 9, 7, 15, 15, 2, 20, 13, 2, 24, 6, 11, 7, 12, 4, 10, 18, 13, 23, 11, 3, 11, 12, 10, 4, 5, 4, 22, 6, 3, 19, 14, 21, 11, 1, 5, 14, 8, 0, 1, 16, 5, 10, 13, 17, 1, 16, 17, 12, 6, 10, 0, 3, 9, 9, 3, 7, 7, 6, 6, 7, 5, 14, 18, 12, 19, 2, 8, 9, 0, 8, 4, 5]

并使用timeit模块:

$ python -m timeit -s 'import uniquetest' 'uniquetest.etchasketch(uniquetest.lst)'

对于其他各种功能(我以他们的海报命名),我有以下结果(在我的第一代英特尔MacBook Pro上):

Allen:                  14.6 µs per loop [1]
Terhorst:               26.6 µs per loop
Tarle:                  44.7 µs per loop
ctcherry:               44.8 µs per loop
Etchasketch 1 (short):  64.6 µs per loop
Schinckel:              65.0 µs per loop
Etchasketch 2:          71.6 µs per loop
Little:                 89.4 µs per loop
Tyler:                 179.0 µs per loop

[1]请注意,Allen修改了列表 - 我相信这会缩短时间,因为timeit模块运行代码100000次,其中99999次使用无欺骗列表.

---

总结:使用套装的直接实施胜过令人困惑的单行:-)

3> jfs..：

---

这是目前为止最快的解决方案(以下输入):

def del_dups(seq):
    seen = {}
    pos = 0
    for item in seq:
        if item not in seen:
            seen[item] = True
            seq[pos] = item
            pos += 1
    del seq[pos:]

lst = [8, 8, 9, 9, 7, 15, 15, 2, 20, 13, 2, 24, 6, 11, 7, 12, 4, 10, 18, 
       13, 23, 11, 3, 11, 12, 10, 4, 5, 4, 22, 6, 3, 19, 14, 21, 11, 1, 
       5, 14, 8, 0, 1, 16, 5, 10, 13, 17, 1, 16, 17, 12, 6, 10, 0, 3, 9, 
       9, 3, 7, 7, 6, 6, 7, 5, 14, 18, 12, 19, 2, 8, 9, 0, 8, 4, 5]
del_dups(lst)
print(lst)
# -> [8, 9, 7, 15, 2, 20, 13, 24, 6, 11, 12, 4, 10, 18, 23, 3, 5, 22, 19, 14, 
#     21, 1, 0, 16, 17]

字典查找比Python 3中的集合略快.

---

好时机,但错误的结论.时序只显示操作符访问,如``d [k] = v``比方法调用访问更快,例如``d .__ setitem __(k,v)``,即使后者已使用`预先绑定` `d_setitem = d .__ setitem__``然后定时``d_setitem(k,v)``.

4> Allen..：

---

什么是最快的取决于您的列表的重复百分比.如果它几乎都是重复项,只有很少的唯一项,那么创建新列表可能会更快.如果它主要是唯一的项目,将其从原始列表(或副本)中删除将更快.

这是一个用于修改列表的地方:

def unique(items):
  seen = set()
  for i in xrange(len(items)-1, -1, -1):
    it = items[i]
    if it in seen:
      del items[i]
    else:
      seen.add(it)

在索引上向后迭代可确保删除项不会影响迭代.

5> James Hopkin..：

---

这是我发现的最快的就地方法(假设有很大比例的重复):

def unique(l):
    s = set(); n = 0
    for x in l:
        if x not in s: s.add(x); l[n] = x; n += 1
    del l[n:]

这比Allen的实现快10%(基于timeit.repeat,由psyco编译的JIT).它保留了任何重复的第一个实例.

repton-infinity:如果你能证实我的时间,我会感兴趣的.

6> Constantin..：

---

强制性的基于发电机的变化:

def unique(seq):
  seen = set()
  for x in seq:
    if x not in seen:
      seen.add(x)
      yield x

7> Raymond Hett..：

---

这可能是最简单的方法:

list(OrderedDict.fromkeys(iterable))

从Python 3.5开始,OrderedDict现在用C语言实现,所以现在它是最短,最干净,最快的.

8> Tyler..：

---

一内胆:

new_list = reduce(lambda x,y: x+[y][:1-int(y in x)], my_list, [])