c++ - 从另一个数组 C++ 复制随机元素到数组中的最快方法

Question

标题几乎说明了一切，但我将举例说明：假设您有一个字符数组 a 和另一个字符数组 b。有没有更好的方法只放入位于 b 中主要位置的字符？假设我们有一个包含素数位置的数组。现在我的天真代码看起来像这样。

for(i = 0; i < n; i++)
 a[i] = b[j + prime[i]];

这里 prime[i] 存储了 b 的素数位置，b 远大于 a，j 是 b 中的任意位置（不会出现越界问题，因为 j+prime[i] 不超过 b 的边界） .

Answer 1

什么是更好的？一种方法是：如果在编译时知道 prime[] 位置，那么我们可以添加一个预取来提前获取缓存行。

这使得内存访问时间更好。

Answer 2

您可以在将值读取（或复制）到数组中时执行此操作，使用素数函数告诉您一个数字是否为素数。

我快速绘制的一种方法是生成素数，直到它们达到您的数组容量，然后简单地遍历它们并从数组中复制所需的元素。我可以想到几种优化方法，例如在程序中使用“预处理”函数生成素数，这样你就可以重用列表。

质数列表将被缓存，并且访问时间会减少很多（您不太可能拥有非常庞大的质数列表）

Answer 3

让我们从算法的角度来看这个。

您想对数组 A 中的每个条目执行哈希函数。假设您对数组 A 中的项目的状态一无所知，那么算法的运行时间下限为 O(n)，线性时间。您必须遍历每个成员，因为您没有更多信息可以帮助您“跳过”某些元素或优化流程。

也就是说，挑战变成了将算法保持在 O(n)。您演示的代码会执行此操作，假设您随后以相同的方式复制非质数。因此，对于复制步骤，从算法的角度来看，没有办法让它更快。但这并不意味着您执行散列步骤的方式不会影响速度。