código C - acceso a la memoria/apropiación

Question

he escrito un fragmento de código en el que un dato:

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

añado seguridad de los datos I/P por cada 3 bytes contiguos y almacenar los ans. ex: temp [4096]; temp [0] = buf [0] + buf [1] + buf [2]; ... hasta 4096

A continuación, se genera un histograma de los resultados de la temperatura utilizando el código:

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

está ordenada El histograma (ordenamiento de burbuja) y luego de arriba se toman 8 valores más recurrentes. El código se ejecuta en el kernel de Linux (2.6.35)

El problema que estoy enfrentando es que si elimino la parte de clasificación, el tiempo necesario para ejecutar el código es muy rápido (6 microsec en mi computadora portátil, medido usando gettimeofday func). Pero después de introducir la clasificación, el proceso se ralentiza en gran medida (44 microsec). La función de clasificación en sí toma 20 microsegundos, no puedo entender por qué el tiempo está aumentando tanto. Hice un análisis de memoria usando Cachegrind, los resultados son normales e incluso intenté desactivar la preferencia, pero aún no muestra ninguna diferencia. Si alguien puede ayudarme aquí. ¡Gracias!

Answer 1

La clasificación de burbuja es lenta ... O (N^2) complejidad ... si desea un rendimiento más rápido, utilice una estructura de datos como un montón o ejecute el algoritmo de ordenación rápida en su matriz, ambos de los cuales le dará complejidad O (N log N) para el proceso de clasificación. Además, ambos métodos también funcionarán muy bien en arreglos de longitud fija.

Answer 2

La clasificación de burbuja es lenta, compara y cambia sus valores hasta 4096 * 4096 = 16,777,216 veces. Si solo necesita los 8 mejores valores, una selección de 1 barrido es con certeza más rápida. Somaturándose así.

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. */ }}

Con eso, se comparan los valores de una sola vez y el costo de la memmove es insignificante porque la matriz de selección es pequeña. No hay necesidad de ordenar la matriz, este algo es O (n), el mejor tipo sería O (n.log2 n)

EDITAR: He añadido la matriz para el índice. EDIT2: Introducido en segundo lugar para corregir el error fundamental que tuve en primera instancia. EDIT3: Comentario: memmove con el tamaño 0 está permitido y es básicamente un nop.