python - 将唯一 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]

不幸的是，list 不可散列，因此在将它们存储为映射键时必须将它们转换为 tuple。

---

注意使用 defaultdict 的技巧, 和 count().__next__提供唯一的递增 ID。在 python2 上，您必须将 .__next__ 替换为 .next。

defaultdict 将在找不到键时分配一个默认值。默认值是通过调用构造函数中提供的函数获得的。 在这种情况下，count() 生成器的 __next__ 方法会产生递增的数字。

作为一种更便携的替代方案，您可以这样做:

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 秒。