将唯一ID分配给python中的列表列表,其中重复项获得相同的id

Question

我有一个列表列表(最多可包含90k个元素)

[[1,2,3], [1,2,4], [1,2,3], [1,2,4], [1,2,5]]

我想为每个元素分配一个id,其中id是唯一的,除非项目是重复的.所以对于上面的列表,我需要这个:

[0,1,0,1,2]

这样做最有效的方法是什么？

Answer 1

使用关联的ID保留已经看到的元素的映射.

from itertools import count
from collections import defaultdict


mapping = defaultdict(count().__next__)
result = []
for element in my_list:
    result.append(mapping[tuple(element)])

你也可以使用列表理解:

result = [mapping[tuple(element)] for element in my_list]

不幸的是,lists不可清除,因此您必须将它们转换为将它们tuple存储为映射的键.

注意使用的技巧defaultdict,并count().__next__提供独特的增加ID.在python2上你必须替换.__next__为.next.

该defaultdict会指定一个默认值时,它不能找到一把钥匙.通过调用构造函数中提供的函数获取默认值.在这种情况下,发电机的__next__方法count()产生越来越多的数字.

作为一种更便携的替代方案,您可以:

from functools import partial

mapping = defaultdict(partial(next, count()))

如评论中所提出的另一种解决方案是将索引用作唯一ID:

result = [my_list.index(el) for el in my_list]

但这是实现:

• 它需要O(N ^ 2)时间而不是O(N)
• ID是唯一的,增加但不连续(可能是也可能不是问题)

有关两种解决方案的比较,请参阅:

In [1]: from itertools import count
   ...: from collections import defaultdict

In [2]: def hashing(seq):
   ...:         mapping = defaultdict(count().__next__)
   ...:         return [mapping[tuple(el)] for el in seq]
   ...: 

In [3]: def indexing(seq):
   ...:    return [seq.index(i) for i in seq]
   ...: 

In [4]: from random import randint

In [5]: seq = [[randint(1, 20), randint(1, 20), randint(1, 20)] for _ in range(90000)]

In [6]: %timeit hashing(seq)
10 loops, best of 3: 37.7 ms per loop

In [7]: %timeit indexing(seq)
1 loop, best of 3: 26 s per loop

请注意,对于90k元素列表,映射解决方案需要的时间少于40 毫秒,而索引解决方案需要26 秒.