Алгоритм: извлечение каждого 4-го элемента массива

Question

У меня есть два огромных массива (int source [1000], dest [1000] в коде ниже, но в действительности есть миллионы элементов). Исходный массив содержит ряд int с которой я хочу, чтобы скопировать 3 из каждых 4

Например, если исходный массив является:

int source[1000] = {1,2,3,4,5,6,7,8....}; 
int dest[1000]; 

Вот мой код:

for (int count_small = 0, count_large = 0; count_large < 1000; count_small += 3, count_large +=4) 
    { 
     dest[count_small] = source[count_large]; 
     dest[count_small+1] = source[count_large+1]; 
     dest[count_small+2] = source[count_large+2]; 
    } 

В конце концов, Dest консольный вывод будет:

1 2 3 5 6 7 9 10 11... 

Но это Алгоритм Построения m так медленно! Есть ли алгоритм или функция с открытым исходным кодом, которую я могу использовать/включить?

Спасибо :)

Edit: Фактическая длина моего массива будет составлять около 1 млн (640 * 480 * 3)

Edit 2: Обработка это цикл занимает около 0,98 секунды до 2,28 секунды , в то время как другой код только занять 0.08 секунд 0,14 секунды, так что устройство использует по крайней мере 90% времени центрального процессора только для цикла

Answer 1

Вы можете попробовать memcpy вместо индивидуальных заданий:

memcpy(&dest[count_small], &source[count_large], sizeof(int) * 3); 

Answer 2

Ну, асимптотическая сложность там так же хороша, как и она. Возможно, вы сможете добиться немного лучшей производительности, загрузив значения в виде четырех четырехсторонних SIMD-целых чисел, перетасовывая их в три 4-позиционных SIMD-целых числа и записывая их обратно, но даже это вряд ли будет намного быстрее.

С учетом сказанного, однако, время обработки 1000 элементов (Edit: или один миллион элементов) будет совершенно тривиальным. Если вы считаете, что это узкое место в вашей программе, вы ошибаетесь.

Answer 3

Прежде чем вы сделаете гораздо больше, попробуйте профилировать ваше приложение и определите, является ли это лучшим местом для проведения вашего времени. Затем, если это горячее пятно, определите, насколько это быстро, и как быстро вам это нужно/может достичь? Затем проверьте альтернативы; накладные расходы на потоки или OpenMP могут даже замедлить его (, особенно, как вы уже отметили, если вы работаете на одном основном процессоре - в этом случае это вообще не поможет). Для одиночной резьбы я бы посмотрел на memcpy в соответствии с ответом Шона.

@Sneftel также имеет ссылку other options ниже с участием SIMD integers.

Один из вариантов - попытаться параллельно обработать цикл и посмотреть, поможет ли это. Вы можете попробовать использовать стандарт OpenMP (см. Wikipedia link here), но вам придется попробовать его для конкретной ситуации и посмотреть, помогло ли это. Я использовал это недавно в реализации ИИ, и это очень помогло нам.

#pragma omp parallel for 
for (...) 
{ 
    ... do work 
} 

Кроме этого, вы ограничены собственными оптимизациями компилятора.

Вы также можете посмотреть на недавней поддержке многопоточности в С11, хотя вы могли бы быть лучше, используя заранее Реализуемый рамочные инструменты, такие как parallel_for (доступно в new Windows Concurrency Runtime through the PPL в Visual Studio, если это то, что вы используете), чем загибайте своя.

parallel_for(0, max_iterations, 
    [...] (int i) 
    { 
     ... do stuff 
    } 
); 

Внутри цикла for у вас все еще есть другие возможности. Вы можете попробовать цикл for, который выполняет итерацию и пропускает все, вместо того, чтобы делать 3 копии на итерацию (просто пропустить, когда (i+1) % 4 == 0), или сделать блок memcopy операций для групп из 3 целых чисел по Seans answer. Вы можете добиться немного разных оптимизаций компилятора для некоторых из них, но это маловероятно (memcpy, вероятно, так же быстро, как вы получите).

for (int i = 0, int j = 0; i < 1000; i++) 
{ 
    if ((i+1) % 4 != 0) 
    { 
    dest[j] = source[i]; 
    j++; 
    } 
} 

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

Answer 4

Является ли ваш массив размером всего 1000? Если да, то как это медленно? Это должно быть сделано в кратчайшие сроки! Пока вы создаете новый массив и однопоточное приложение, это единственный удаленный AFAIK.

Однако, если массивы данных огромны, вы можете попробовать многопоточное приложение.

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

Answer 5

Если у вас есть карта Nvidia, вы можете использовать CUDA. Если это не так, вы можете попробовать другие методы и среды параллельного программирования.