在Python中为列表中的列表分配唯一ID，其中重复项获得相同的ID

Question

在Python中为列表中的列表分配唯一ID，其中重复项获得相同的ID

8

我有一个列表，其中包含多个小列表（最多可能包含9万个元素）

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

我希望为每个元素分配一个唯一的ID，除非该项是重复的。因此对于上面的列表，我需要得到以下结果：

[0,1,0,1,2]

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

- jamborta

这些ID必须是连续的吗？如果不是，你很容易滥用列表的index方法：def get_ids(li): return [li.index(i) for i in li];，它会为[[1,2,3], [1,2,4], [1,2,3], [1,2,4], [1,2,5]]返回[0, 1, 0, 1, 4]。 - DeepSpace

1

@DeepSpace 这需要 O(N^2) 的时间。通过计算列表的排序副本并使用 bisect 来有效地将索引与其关联，可以改进它，使时间为 O(N log N)，这是使用比较解决此问题的下限。 - Bakuriu

3个回答

1

这是我处理它的方式：

from itertools import product
from random import randint
import time

t0 = time.time()
def id_list(lst):
    unique_set = set(tuple(x) for x in lst)
    unique = [list(x) for x in unique_set]
    unique.sort(key = lambda x: lst.index(x))

    result = [unique.index(i[1]) for i in product(lst, unique) if i[0] == i[1]]

    return result

seq = [[randint(1, 5), randint(1, 5), randint(1, 5)] for i in range(90000)]

print(id_list(seq))

t1 = time.time()

print("Time: %.4f seconds" % (t1-t0))

该代码会输出一系列的ID，以及计算一个包含在1和4之间的随机整数列表的序列所需的大约时间，共计90000次。

Time: 2.3397 seconds  # Will slightly differ from computation to computation

实际时间总是会稍微长一些，因为它需要在最后的打印语句中计算，但它不应该有太大的差异。

我还使用了time库来标记代码块开始和结束之间的时间间隔。

import time

t0 = time.time()

# code block here

t1 = time.time()

# Difference in time: t1 - t0

在代码片段中使用的itertools库以及product将加速计算。

- RoadRunner

0

这是一个与Bakuriu的解决方案略有不同的修改版，它仅适用于numpy数组，在内存占用和计算方面表现更佳（因为它不需要将数组转换为元组）：

from itertools import count
from collections import defaultdict
from functools import partial

def hashing_v1(seq):
    mapping = defaultdict(partial(next, count()))
    return [mapping[tuple(el)] for el in seq]

def hashing_v2(seq):
    mapping = defaultdict(partial(next, count()))
    result = []
    for le in seq:
        le.flags.writeable = False
        result.append(mapping[le.data])
    return result

In [4]: seq = np.random.rand(50000, 2000)

In [5]: %timeit hashing_v1(seq)
1 loop, best of 3: 14.1 s per loop

In [6]: %timeit hashing_v2(seq)
1 loop, best of 3: 1.2 s per loop

- jamborta

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Bakuriu · Accepted Answer

保留一个带有相关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秒。