Быстрое копирование выделенных элементов массива в C?

Question

Это может быть очень простой вопрос, но он меня действительно беспокоит.В основном я пытаюсь скопировать элементы старого вектора в новый вектор, используя C.

Копия основана на индексном векторе, где каждый элемент в этом векторе представляет индекс элемента встарый векторИндексный вектор не отсортирован.

Например, старый вектор A = [3.4, 2.6, 1.1].

индексный вектор B = [1, 1, 3, 3, 2, 1, 2].

После копирования я ожидаю, что новый вектор будет C = [3.4, 3.4, 1.1, 1.1, 2.6, 3.4, 2.6].

Самый брутальныйРешение, которое я могу придумать, состоит в том, чтобы запустить цикл через B и скопировать соответствующий элемент из A в C. Но когда вектор слишком велик, его стоимость невыносима.

У меня вопрос, есть ли быстрее/ умный способ сделать копию в C в этом случае?

Первоначально код написан на Джулии, и у меня не было проблем с этим.В Юлии я просто использую 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 и прочитайте ее один раз;иначе у вас есть алгоритм Шлемеля-маляра.

Я думаю, что лучшее, что мы можем сделать, это Устройство Даффа или петлевое развертывание.Я также сделал несколько тривиальных оптимизаций, которые обычно может выполнять компилятор, но я вспоминаю, что развертывание цикла компилятора не вполне так хорошо, как устройство Даффа.Мои знания могут быть устаревшими, и оптимизатор компилятора мог догнать их.

Может потребоваться исследование для определения оптимального числа развертывания.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);
}

С этим большим объемом я не могу справиться лучше, но с большим объемом может существовать лучший выбор, включающий изменение структуры данных.