Python优化：如何在列表中查找重复值及其索引

Question

我有一个包含18,000个唯一ID的列表。 ID是字母A，B，C，D的连接。 我编写了一段代码，通过ID [0：-1]将ID分组，并给出重复ID的索引位置。

这很有效，但处理时间很长：对于18,000个ID，需要大约110秒。 你有什么想法可以加快我的代码吗？

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]]]

- Guilhain

---

你能展示一下你代码的输出吗？ - Mazdak

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

- Guilhain

你需要更详细地解释你的代码和输出，例如['1DDAABBBB'，[4]]中的4代表什么？ - Mazdak

它是在一个索引位置上。 - Guilhain

Answer 1

这是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]]]

- JuniorCompressor

---

@Guilhain 可以尝试一下 Kasra 的解决方案。 - JuniorCompressor

Answer 2

作为解决此类问题的更Pythonic的方法，使用{{link1：collections.defaultdict}}：

>>> 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]}

更多细节请查看以下基准测试，它比原来快约4倍：

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

- Mazdak

---

0.11秒内处理18,000个ID！ - Guilhain

@Guilhain，所以请放心并接受答案吧 ;) - Mazdak

s2是我做的最佳解决方案，我进行了10,000次迭代，使用18,000个ID，并使用timeit计时，总共花费了16.46秒。恭喜！ - Guilhain

Answer 3

一种不使用其他模块的替代方案：

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]]]

- Nir Alfasi

---

0.05秒！非常感谢！ - Guilhain

@Guilhain 如果你喜欢，请举手，鼓掌两次，点赞并接受！:D - Nir Alfasi

等等，你需要返回索引...只是一个技术细节...但不知道时间会受到什么影响... - JuniorCompressor

@JuniorCompressor 你的意思是 print grouped.keys() 吗？ - Nir Alfasi

你应该返回类似于 [['1CDABCABD', [0, 1, 2]]... 的东西。 - JuniorCompressor

@JuniorCompressor 你的意思是这个吗：[[k, v] for k, v in grouped.items()]？ - Nir Alfasi

Answer 4

你在找这个吗：

>>> d = {}
>>> for ind, elem in enumerate(a):
    ... d.setdefault(elem[0:-1], []).append(ind)
>>> print d
{'1CDABCABD': [0, 1, 2], '1DDAABBBB': [4], '1BCABCCCA': [3, 5]}

这个解决方案与Kasra的优化代码非常相似，但速度略微更快。区别在于切片的位置，尽管不确定为什么一个比另一个表现稍好:

s1 = """
a = ['1CDABCABDA', '1CDABCABDB', '1CDABCABDD', '1BCABCCCAA',
      '1DDAABBBBA', '1BCABCCCAD']
d = {}
for ind, elem in enumerate(a):
    d.setdefault(elem[0:-1], []).append(ind)
"""

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)
"""

print 'Kasra's time/my time: %s' % (str(timeit(stmt=s2, number=100000)/timeit(stmt=s1, number=100000))

Kasra's time/my time: 1.24058060531 

- Saksham Varma