производительности тяги :: reduce_by_key с несколькими ключевыми повторениями

Question

я должен сделать в привязке сокращения массивов с разными ключами, которые повторяются только один раз в то время:

keys = {1,2,3,3,4,5,6,7,7, 8, 9, 9,10,11,...} 
array = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,...} 

// after reduction 
result = {1,2,7,5,6,7,17,10,23,13,14} 

Использование thrust::reduce_by_key (или любой другой сегментированным методом редукции) является не самый быстрый вариант здесь, поскольку большинство операций на самом деле являются просто копиями из одного массива в другой.

Что было бы лучшим подходом к этой проблеме?

Answer 1

Фактически, reduce_by_key: соответствующий алгоритм для использования здесь. Дело в том, что текущая реализация в Thrust не так быстро, как может быть. Чтобы уточнить, нет ничего, что могло бы предотвратить выполнение reduce_by_key со скоростью memcpy, и я считаю, что other implementations уже достигнет этого уровня. Наш предварительный план Thrust v1.7 включает в себя повышение производительности до reduce_by_key и других алгоритмов на основе сканирования с использованием кодов в соответствующем проекте back40computing.

Обратите внимание, что если сегменты либо (1) длинны, либо (2) равномерной длины, то можно сделать лучше, чем reduce_by_key. Например, в какой-то момент экономичнее использовать дескриптор сегмента на основе смещения, чем ключи или головные флаги. Однако, когда сегменты являются короткими (как в вашем случае) или сильно переменной длиной, оптимальная реализация reduce_by_key действительно является лучшим инструментом для работы.