C код - доступ к памяти / приоритет - PullRequest
Новая
       13

C код - доступ к памяти / приоритет

6 голосов
/ 05 июля 2011

Я написал фрагмент кода, в котором данные: 

unsigned char buf[4096]; // data in chunks of size 4k
unsigned counter[256];

Я складываю данные i / p для каждых 3 смежных байтов и сохраняю ans. напр .: темп [4096]; temp [0] = buf [0] + buf [1] + buf [2]; ... до 4096

Затем гистограмма генерируется из результатов temp с использованием кода: 

for(i = 0; i < 4096; i++)
counter[temp[i]]++;

Гистограмма сортируется (пузырьковая сортировка), а затем берутся верхние 8 наиболее повторяющихся значений. Код запускается в ядре Linux (2.6.35)

Проблема, с которой я сталкиваюсь, заключается в том, что, если я удаляю часть сортировки, время, затрачиваемое на выполнение кода, очень быстро (6 мкс на моем ноутбуке, измеряется с помощью функции gettimeofday). Но после введения сортировки процесс значительно замедляется (44 мкс). Сама функция сортировки занимает 20 микросекунд, я не могу понять, почему время так сильно увеличивается. Я сделал анализ памяти, используя cachegrind, результаты нормальные, и я даже попытался отключить выгрузку, но все же это не показывает никакой разницы. Если кто-нибудь может помочь мне здесь. Спасибо!

Ответы [ 2 ]

2 голосов
/ 05 июля 2011

Пузырьковая сортировка медленная, она сравнивает и меняет ваши значения до 4096 * 4096 = 16 777 216 раз.Если вам нужны только 8 лучших значений, выбор из 1 развертки, безусловно, быстрее.Примерно так. 

 const uint_t n = 8;
 uint_t best[n] = {0};
 uint_t index[n] = {0};
 uint_t j;

 for(uint_t i=0; i<4096; i++) {

   if(counter[i] > best[n-1]) {
     for(j=n-2; j && counter[i] > best[j]; j--);           /* Find the insertion position, as our value might be bigger than the value at position n-1. */
     memmove(&best [j+1], &best[j] , (n-1 -j) * sizeof best[0]);      /* Shift the values beyond j up 1  */
     memmove(&index[j+1], &index[j], (n-1 -j) * sizeof index[0]);
     best[j] = counter[i];                                 /* Put the current best value at the top */
     index[j] = i;                                         /* Store the index in the second array to know where the best value was. */
   }
 }

При этом вы сравниваете свои значения только один раз, а стоимость memmove незначительна, потому что ваш массив выбора мал.Нет необходимости сортировать массив, этот алгоритм равен O (нм) с n размером вашего массива и m размером вашего выбора.Лучшая сортировка будет O ((n.log2 n) .m).Таким образом, если m мало, а n велико, это невозможно для любого универсального алгоритма сортировки.

EDIT : я добавил массив для индекса.

EDIT2 : введена секунда для исправления фундаментальной ошибки, которая была у меня в первой инстанции.

EDIT3 : Комментарий: memmove с размером 0 разрешен и по сути не имеет значения.

1 голос
/ 05 июля 2011

Пузырьковая сортировка медленная ... O (N ^ 2) сложность ... если вам нужна более высокая производительность, используйте структуру данных, например, кучу, или запустите алгоритм быстрой сортировки в вашем массиве, оба из которых будутдать вам O (N log N) сложность для процесса сортировки.Кроме того, оба метода также будут хорошо работать с массивами фиксированной длины.

...