Python优化如何在lis中找到重复值和值索引

Question

我有一张有18000个唯一ID的名单。 ID是字母A, B, C, D的串联。 我编写了一个代码，将ID按ID[0:-1]分组，并给出重复ID的索引位置

这样做很好，但是要继续进行很长时间：大约110 secs对于18 000 ID。 你有没有办法加快我的代码速度？你知道吗

a = ['1CDABCABDA', '1CDABCABDB', '1CDABCABDD', '1BCABCCCAA', '1DDAABBBBA', '1BCABCCCAD']

startTime = time.time()
b = [i[0:-1] for i in a]
b = list(set(b))


result = range(len(b))
it = 0
for i in result:
    result[i] = [b[i], []]
    for j in xrange(len(a)):
        if b[i] == a[j][0:-1]:
            result[i][1].append(j)

endTime =  time.time()

print endTime - startTime, 'secs !'

输出：

>>> [['1CDABCABD', [0, 1, 2]], ['1DDAABBBB', [4]], ['1BCABCCCA', [3, 5]]]

Answer 1

不使用其他模块的替代解决方案：

grouped = {}
for i, j in enumerate(a):    
    itm = grouped.get(j[0:-1], [])
    itm.append(i)    
    grouped[j[0:-1]] = itm

print [[k, v] for k, v in grouped.items()] # [['1CDABCABD', [0, 1, 2]], ['1DDAABBBB', [4]], ['1BCABCCCA', [3, 5]]]

Answer 2

这就是python中的groupby有效地做到的：

from itertools import groupby
a = ['1CDABCABDA', '1CDABCABDB', '1CDABCABDD', '1BCABCCCAA', '1DDAABBBBA', '1BCABCCCAD']
key = lambda i: a[i][:-1]
indexes = sorted(range(len(a)), key=key)
result = [[x, list(y)] for x, y in groupby(indexes, key=key)]

输出：

[['1BCABCCCA', [3, 5]], ['1CDABCABD', [0, 1, 2]], ['1DDAABBBB', [4]]]

Answer 3

对于这类问题，使用^{}作为更具python风格的方法：

>>> from collections import defaultdict
>>> d=defaultdict(list)
>>> new=[i[:-1] for i in a]

>>> d=defaultdict(list)
>>> for i,j in enumerate(new):
...    d[j].append(i)
... 
>>> d
defaultdict(<type 'list'>, {'1CDABCABD': [0, 1, 2], '1DDAABBBB': [4], '1BCABCCCA': [3, 5]})
>>> d.items()
[('1CDABCABD', [0, 1, 2]), ('1DDAABBBB', [4]), ('1BCABCCCA', [3, 5])]

注意defaultdict是一个线性解，比itertools.groupby和sorted更有效。你知道吗

也可以使用dict.setdefault方法：

>>> d={}
>>> for i,j in enumerate(new):
...   d.setdefault(j,[]).append(i)
... 
>>> d
{'1CDABCABD': [0, 1, 2], '1DDAABBBB': [4], '1BCABCCCA': [3, 5]}

有关更多详细信息，请查看以下基准点，它的~4X速度更快：

s1="""
from itertools import groupby
a = ['1CDABCABDA', '1CDABCABDB', '1CDABCABDD', '1BCABCCCAA', '1DDAABBBBA', '1BCABCCCAD']
key = lambda i: a[i][:-1]
indexes = sorted(range(len(a)), key=key)
result = [[x, list(y)] for x, y in groupby(indexes, key=key)]
"""
s2="""
a = ['1CDABCABDA', '1CDABCABDB', '1CDABCABDD', '1BCABCCCAA', '1DDAABBBBA', '1BCABCCCAD']
new=[i[:-1] for i in a]
d={}
for i,j in enumerate(new):
   d.setdefault(j,[]).append(i)
d.items()
    """


print ' first: ' ,timeit(stmt=s1, number=100000)
print 'second : ',timeit(stmt=s2, number=100000)

结果：

 first:  0.949549913406
second :  0.250894069672