小编RCa*_*107的帖子

从列表中多次（> 1M）提取随机值的最佳（最快）方法是什么？

我目前的情况是，我有一个表示为邻接列表的图，其内部列表的长度可以有很大不同（在范围 [2，可能是 100k] 内）。

我需要迭代这个列表来生成随机游走，所以我当前的解决方案是沿着

1. 获取随机节点
2. 从该节点的邻接列表中选择一个随机索引
3. 移动到新节点
4. 转到2
5. 重复直到随机游走达到所需的长度
6. 转到1

当图不太大时，这种方法就足够好了，但是现在我正在处理一个包含 >440k 节点的图，每个节点所具有的边数差异非常大。

我目前用来提取随机索引的函数是

node_neighbors[int(random.random() * number_neighbors_of_node)]

与我之前的实现相比，这加快了计算速度，但对于我的目的来说，它仍然慢得令人无法接受。

一个节点的邻居数量可以从 2 个到数万个，我无法删除小节点，我必须在这个环境中生成数万个随机游走。

从分析代码来看，大部分生成时间都花在寻找这些索引上，因此我正在寻找一种可以减少这样做所需时间的方法。然而，如果可以通过修改算法来完全避开它，那就太好了。

谢谢！

编辑：出于好奇，我使用测试了同一代码的三个变体timeit，结果如下：

setup='''
import numpy as np
import random

# generate a random adjacency list, nodes have a number of neighbors between 2 and 10000

l = [list(range(random.randint(2, 10000))) for _ in range(10000)]
'''

for _ in range(1000):    
    v = l[random.randint(0, 10000-1)] # Get a random node adj list 
    vv = v[random.randint(0, len(v)-1)] …