c - 在 C 中快速复制数组的选定元素？

Question

这可能是一个非常基本的问题，但它确实让我很烦恼。我想做的基本上是使用 C 将旧 vector 中的元素复制到新 vector 中。

副本基于索引 vector ，该 vector 中的每个元素代表旧 vector 中元素的索引。索引 vector 未排序。

例如， 旧 vector A = [3.4, 2.6, 1.1]。

索引 vector B = [1, 1, 3, 3, 2, 1, 2]。

复制后，我希望新 vector 为 C = [3.4, 3.4, 1.1, 1.1, 2.6, 3.4, 2.6]。

我能想到的最残忍的解决方案是在B中运行一个循环，将A中对应的元素复制到C中。但是当 vector 太大时，成本是无法承受的。

我的问题是，此时是否有更快/更智能的方式在 C 中进行复制？

最初代码是用 Julia 编写的，我对此没有意见。在 Julia 中，我只使用 C = A[B] 并且速度很快。谁知道他们是怎么做到的？

添加C伪代码:

float *A = []; # old array
int *B = []; # index array
float *C;
for(i=0;i<length(B);i++)
{
   *(C+i) = *(A+*(B+i));
}

Answer 1

假设:length(B) 实际上不是一个函数，但您没有发布它是什么。如果是函数，则捕获到for循环外的局部变量中，并读取一次；否则你有一个 Schlemiel 画家的算法。

我认为我们能做的最好的是Duff's Device又名循环展开。我还做了一些编译器通常可以进行的微不足道的优化，但我记得编译器的循环展开不如 Duff 的设备好。我的知识可能已经过时，编译器的优化器可能已经跟上了。

可能需要进行探测以确定最佳展开数。 8 是传统的，但循环体内的代码比正常情况下大。

此代码对指针A 和B 具有破坏性。如果您再次需要它们，请保存它们。

float *A = []; # old array
int *B = []; # index array
float *C;
int ln = length(B);
int n = (ln + 7) % 8;
switch (n % 8) {
case 0: do { *C++ = A[*B++];
case 7:      *C++ = A[*B++];
case 6:      *C++ = A[*B++];
case 5:      *C++ = A[*B++];
case 4:      *C++ = A[*B++];
case 3:      *C++ = A[*B++];
case 2:      *C++ = A[*B++];
case 1:      *C++ = A[*B++];
    } while (--n > 0);
}

对于这么多的范围，我无法做得更好，但是对于更大的范围，可能存在更好的选择，包括重新设计您的数据结构。