在numpy数组中反转随机选择的键

Question

我有一个由N个值组成的大型np.array，我需要随机选择其中10%的值:

choice=random.sample(range(N), int(N*percent))  # percent has values 0-1
newarr=arr[choice]

N可能有超过200万个值。

实际上，我也需要另外90%的值的数组。目前我使用以下代码，但运行非常缓慢：

def buildRevChoice(choice, nevents):
        revChoice=[]
        for i in range(N):
            if not i in choice:
                revChoice.append(i)
        return revChoice

你能想到一种加快这个过程的方法吗？

- user575736

---

快速优化：在 buildRevChoice 中，创建一个从 choice 到 set 的映射以加速查找。 - tobias_k

如果你需要更好的性能，就不要在大数组上使用Python循环。而是使用Python / NumPy的函数式编程和NumPy的向量化。 - Bruno Gelb

是的，我知道，但是我在谷歌上没有找到其他解决方案。想不出一个合理的搜索短语。 - user575736

Answer 1

你可以使用random.shuffle函数来打乱列表，然后根据需要进行分割。

def choice(N, percent):
    tmp = range(N)
    random.shuffle(tmp)
    cut = int(N * percent)
    return tmp[:cut], tmp[cut:]

你将获得两个列表，第一个包含所选的内容，第二个包含剩余的内容。

- Sufian Latif

---

不是一个坏的解决方案；尽管我对random.shuffle的性能有些谨慎。可能，random.permutation具有更好的性能。而且，根据其实现方式，np.argsort(random.randint())可能仍然是生成排列索引的更快速的方法。 - Eelco Hoogendoorn

@EelcoHoogendoorn 我没有使用过 numpy，所以我只知道基本的 Python :) O(n) Fisher Yates 洗牌算法是否是一个不错的选择？ - Sufian Latif

除非您计划编写C扩展，否则您自己实现的任何算法都不是一个好选择。请注意，我没有对洗牌进行基准测试；我只是想象最随机的原地洗牌算法不一定是最有效的。 - Eelco Hoogendoorn

Answer 2

如果你能接受一个掩码数组的内存开销，这种方法似乎比通过索引选择其他值更快，并且保留了are元素的顺序。下面是我在IPython笔记本中测试得到的结果：

N = 2000000
arr = random.random(N)
percent = 0.10

我的解决方案：

%% timeit
choice = random.choice(N, N*percent)
mask = zeros_like(arr, bool)   
mask[choice] = True
newarr = arr[mask]
revchoice = arr[~mask]

10次循环，3次中取最佳结果：每次循环耗时18.1毫秒。

0605002的解决方案：

tmp = range(N)
random.shuffle(tmp)
cut = int(N * percent)
newarr, revchoice = tmp[:cut], tmp[cut:]

1个循环，3次中的最佳结果：每个循环603毫秒

- chthonicdaemon

---

非常感谢，这是两个非常好的解决方案，我会检查哪一个更快。我不习惯内存问题。在什么情况下我不应该使用掩码？ - user575736

这个解决方案（以及由0605002提供的另一个解决方案）使用了一个与“arr”大小相同的数组。因此，如果您的数组只有可用内存的一半那么大，你将没有足够的空间来创建遮罩。如果避免构建遮罩，你只需要为索引数组增加10%的内存即可。但是200万个点并不算多。 - chthonicdaemon

我已经更新了我的答案并附上了时间。我的解决方案快了一个数量级。 - chthonicdaemon

相比我的第一个解决方案，这真的很快。非常感谢，这帮了我很多。我喜欢保留数组的顺序。另外：我必须执行那段代码几次（<10），所以解决方案之间的差异更加明显。 - user575736

在 Stack Overflow 上表达“谢谢，这帮了我很多”的最佳方式是接受答案 :-) - chthonicdaemon