Частичная сортировка малого массива в частной памяти OpenCL

Задача состоит в том, чтобы найти N наибольших элементов в массиве. Массив довольно мал (~ 40 предметов). Я использую этот алгоритм:Частичная сортировка малого массива в частной памяти OpenCL

float max1 = -inf; 
    int max1I = -1; 
    float max2 = -inf; 
    int max2I = -1; 
    float max3 = -inf; 
    int max3I = -1; 
    float max4 = -inf; 
    int max4I = -1; 
    float max5 = -inf; 
    int max5I = -1; 
    float performances[MAX_NUMBER_OF_SELECTIONS]; 
    for (int i = 0; i < numberOfSelections; ++i) { 
     float performance = /*some calculations*/; 
     performances[i] = performance; 
     if (performance > max1) { 
      max5 = max4; max5I = max4I; 
      max4 = max3; max4I = max3I; 
      max3 = max2; max3I = max2I; 
      max2 = max1; max2I = max1I; 
      max1 = performance; max1I = i; 
     } else if (performance > max2) { 
      max5 = max4; max5I = max4I; 
      max4 = max3; max4I = max3I; 
      max3 = max2; max3I = max2I; 
      max2 = performance; max2I = i; 
     } else if (performance > max3) { 
      max5 = max4; max5I = max4I; 
      max4 = max3; max4I = max3I; 
      max3 = performance; max3I = i; 
     } else if (performance > max4) { 
      max5 = max4; max5I = max4I; 
      max4 = performance; max4I = i; 
     } else if (performance > max5) { 
      max5 = performance; max5I = i; 
     } 
    }

подход был достаточно хорош, но теперь мне нужно, чтобы сделать его TOP10 вместо TOP5. Должен ли я скопировать этот шаблон? Или, может быть, есть что-то лучше?

источник

2016-02-03 Dmitry Galchinsky

Вы ищете, чтобы код был простым, быстрым или малым? В большинстве случаев я бы, вероятно, использовал структуру [heap] (https://en.wikipedia.org/wiki/Heap_ (data_structure)) для чего-то подобного. –

Я ищу самое быстрое решение на GPU. –

Является ли эта часть более крупного алгоритма? Вам нужно найти значения top10 ouf 40 значений в каждом потоке? Должен ли каждый блок найти топ10 из 40? Или это единственное, что должно делать это ядро? –

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

Я хотел бы сделать что-то вроде:

//Init 
float maxs[10+1]; 
for(int i=0; i<10+1; i++){ 
    maxs[i] = -inf; 
} 

for(int i=0; i<size; i++){ 
    //Is it higher than the element 0? 
    if(data[i] > maxs[0]){ 
     maxs[0] = data[i]; 
     for(int j=0; j<10; j++){ 
      if(maxs[j] > maxs[j+1]) 
       swap(maxs[j], maxs[j+1]); 
      else break; 
     } 
    } 
}

Теперь у вас есть массив из 11 элементов, упорядоченных от мала до высокой, просто взять последние 10 элементов.

Код может быть дополнительно оптимизирован, но это очень просто.

источник

2016-02-05 16:41:08 DarkZeros

Спасибо. Я сделаю сравнительный тест, чтобы сравнить наши подходы, чтобы проверить, что лучше. –

Я только что проверил производительность. Он работает немного быстрее, чем решение для копирования-вставки. Еще раз спасибо. –

Частичная сортировка малого массива в частной памяти OpenCL

ответ

Смежные вопросы