使用唯一索引索引列表

Question

我有一个清单说l = [10,10,20,15,10,20].我想为每个唯一值分配一个特定的"索引"来获取[1,1,2,3,1,2].

这是我的代码:

a = list(set(l))
res = [a.index(x) for x in l]

结果证明非常慢.

l拥有1M个元素和100K独特元素.我也尝试过使用lambda和排序的地图,这没有用.这样做的理想方法是什么？

Answer 1

您可以O(N)使用a defaultdict和list comprehension 及时完成此操作:

>>> from itertools import count
>>> from collections import defaultdict
>>> lst = [10, 10, 20, 15, 10, 20]
>>> d = defaultdict(count(1).next)
>>> [d[k] for k in lst]
[1, 1, 2, 3, 1, 2]

在Python 3中使用__next__而不是next.

如果你想知道它是如何工作的？

传递给的default_factory(即count(1).next在这种情况下)defaultdict仅在Python遇到缺失键时被调用,因此对于10,该值将为1,然后对于接下来的10,它不再是缺失的键,因此使用先前计算的1,现在20又是一个缺失的密钥,Python将default_factory再次调用它来获取其值等等.

d 最后将看起来像这样:

>>> d
defaultdict(<method-wrapper 'next' of itertools.count object at 0x1057c83b0>,
            {10: 1, 20: 2, 15: 3})

Answer 2

代码的缓慢产生是因为a.index(x)执行线性搜索并对其中的每个元素执行线性搜索l.因此,对于每个1M项目,您执行(最多)100K比较.

将一个值转换为另一个值的最快方法是在地图中查找.您需要创建地图并填写原始值与所需值之间的关系.然后在列表中遇到另一个相同值时从地图中检索值.

这是一个通过单个传递的示例l.可能存在进一步优化的空间,以消除res在追加时重复重新分配的需要.

res = []
conversion = {}
i = 0
for x in l:
    if x not in conversion:
        value = conversion[x] = i
        i += 1
    else:
        value = conversion[x]
    res.append(value)

Answer 3

您的解决方案是缓慢的,因为它的复杂性是O(nm)与m正在独特的元素个数l:a.index()是O(m),你把它的每一个元素l.

为了实现它O(n),index()在字典中删除并存储索引:

>>> idx, indexes = 1, {}
>>> for x in l:
...     if x not in indexes:
...         indexes[x] = idx
...         idx += 1
... 
>>> [indexes[x] for x in l]
[1, 1, 2, 3, 1, 2]

如果l仅包含已知范围内的整数,则还可以将索引存储在列表中而不是字典中,以便更快地进行查找.

Answer 4

嗯,我想这取决于你是否希望它以特定的顺序返回索引.如果您希望该示例返回:

    [1,1,2,3,1,2]

然后你可以看看提交的其他答案.但是,如果您只关心为每个唯一编号获取唯一索引,那么我可以为您提供快速解决方案

    import numpy as np
    l = [10,10,20,15,10,20]
    a = np.array(l)
    x,y = np.unique(a,return_inverse = True)

对于这个例子,y的输出是:

    y = [0,0,2,1,0,2]

我测试了1,000,000个条目,它基本上立即完成.