我有一个列表,其中包含多个小列表(最多可能包含9万个元素)
[[1,2,3], [1,2,4], [1,2,3], [1,2,4], [1,2,5]]
我希望为每个元素分配一个唯一的ID,除非该项是重复的。因此对于上面的列表,我需要得到以下结果:
[0,1,0,1,2]
什么是最有效的方法来做这个?
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]
这很简单,但有以下几点需要注意:
想要比较两种解决方案,请参考:
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
operator.itemgetter(*map(tuple, my_list))(mapping)
。 - Mazdakdefaultdict
兼容2.6+版本,您可以使用 defaultdict(lambda c=count(): next(c))
,而不是依赖于实际的方法名称或使用 functools.partial
... - Jon Clementspartial
和next
内置函数在Python 2.6中都可用,所以它们已经兼容Python 2.6了。 - Bakuriumap()
返回一个迭代器,比列表消耗更少的内存。而解包只是将项目传递给 itemgetter()
。 - Mazdakfrom 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
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
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]
。 - DeepSpacebisect
来有效地将索引与其关联,可以改进它,使时间为 O(N log N),这是使用比较解决此问题的下限。 - Bakuriu