使用唯一索引索引列表 [英] Indexing a list with an unique index

问题描述

我有一个列表说 l = [10,10,20,15,10,20] 。我想为每个唯一值指定一个索引来获得 [1,1,2,3,1,2] 。

I have a list say l = [10,10,20,15,10,20]. I want to assign each unique value a certain "index" to get [1,1,2,3,1,2].

这是我的代码：

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

结果证明非常慢。

l 有1M个元素和100K个唯一元素。我也尝试过使用lambda和排序的地图，这没有用。这样做的理想方法是什么？

l has 1M elements, and 100K unique elements. I have also tried map with lambda and sorting, which did not help. What is the ideal way to do this?

推荐答案

代码的缓慢是因为 a.index （x）执行线性搜索，并对 l 中的每个元素执行线性搜索。因此，对于您执行的每个1M项目（最多）100K比较。

The slowness of your code arises because a.index(x) performs a linear search and you perform that linear search for each of the elements in l. So for each of the 1M items you perform (up to) 100K comparisons.

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

The fastest way to transform one value to another is looking it up in a map. You'll need to create the map and fill in the relationship between the original values and the values you want. Then retrieve the value from the map when you encounter another of the same value in your list.

这是一个通过进行单次传递的示例升。可能有进一步优化的空间，以消除在追加时重复分配 res 的需要。

Here is an example that makes a single pass through l. There may be room for further optimization to eliminate the need to repeatedly reallocate res when appending to it.

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)

这篇关于使用唯一索引索引列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！