Python中从含重复元素的超大列表中为每个唯一元素随机选取代表索引的高效实现方法

嘿，这个问题我太熟了！处理百万级别的大列表，效率可是重中之重，我来给你捋捋怎么高效解决～

首先先明确下你的需求：你有一个可能超过100万元素的大列表，里面有大量重复元素，现在要为每个唯一元素随机挑选一个它出现过的索引，最终选出来的索引对应的元素得覆盖所有唯一值，而且索引数量要和唯一元素的数量完全一致对吧？

你给出的那个numpy方案虽然能实现功能，但真的不适合超大列表——因为你每循环一个唯一元素，就要用np.where(lst==e)全量扫描一次数组，要是唯一元素有上万个，那就是上万次全量扫描，百万级数据下这速度会慢到让你怀疑人生。

更高效的实现思路（普通Python版本，首选！） #

核心思路就是只遍历原列表一次，把每个元素对应的所有索引先存起来，之后再从每个元素的索引列表里随机挑一个就行，这样时间复杂度只有O(n)（n是列表长度），比多次全扫高效太多：

import random

# 示例超大列表（这里用小例子演示，实际可以是1M+元素的列表）
lst = ['b', 't', 'm', 'a', 'c', 'k', 'm', 't', 'm', 'l']

# 第一步：用字典记录每个元素对应的所有出现索引
elem_to_indices = {}
for idx, val in enumerate(lst):
    if val not in elem_to_indices:
        elem_to_indices[val] = []
    elem_to_indices[val].append(idx)

# 第二步：给每个唯一元素随机选一个索引
selection = [random.choice(indices) for indices in elem_to_indices.values()]

如果习惯用numpy的高效实现 #

要是你更倾向于用numpy处理，也可以用np.unique的分组功能，避免多次全量扫描：

import numpy as np

lst = np.array(['b', 't', 'm', 'a', 'c', 'k', 'm', 't', 'm', 'l'])

# 先通过unique得到唯一元素，以及原列表每个位置对应的唯一元素索引
unique_elems, inverse_idx = np.unique(lst, return_inverse=True)
# 生成原列表的索引数组
all_indices = np.arange(len(lst))
# 按唯一元素分组，得到每个元素对应的所有索引
grouped_indices = [all_indices[inverse_idx == i] for i in range(len(unique_elems))]
# 随机挑选索引
selection = [np.random.choice(grp) for grp in grouped_indices]

为什么这两种方法更高效？ #

你原来的方案时间复杂度是O(k*n)（k是唯一元素的数量），当k很大的时候（比如上万），这开销直接翻上万倍；而我推荐的两种方法，都是只需要遍历原列表一次（或者numpy内部批量处理），之后的随机选择都是O(k)的小开销，对于1M+的超大列表来说，效率提升可不是一星半点。

你可以自己测试下，用100万元素的列表跑一遍，原方案和新方案的速度差会非常明显～

备注：内容来源于stack exchange，提问作者Michael