Rechercher l’occurrence max / min dans un tableau de nombres entiers

Je viens de terminer l’écriture d’un algorithme qui trouve des valeurs dans un tableau d’entiers en entrée avec des occurrences max / min. Mon idée est de sortinger le tableau (toutes les occurrences sont maintenant en séquence) et d’utiliser une paire pour stocker pour chaque valeur le nombre d’occurrences correspondant.

La complexité devrait être O(nlogn) mais je pense qu’il existe des multiplicateurs constants. Que puis-je faire pour améliorer les performances?

 #include  #include  #include "e7_8.h" #define N 20 /*Structure for  pair*/ typedef struct { int value; int freq; } VAL_FREQ; void get_freq(int *v, int n, int *most_freq, int *less_freq) { int v_i, vf_i, current_value, current_freq; VAL_FREQ* sp = malloc(n*sizeof(VAL_FREQ)); if(sp == NULL) exit(EXIT_FAILURE); mergesort(v,n); vf_i = 0; current_value = v[0]; current_freq = 1; for(v_i=1; v_i<n+1; v_i++) { if(v[v_i] == current_value) current_freq++; else{ sp[vf_i].value = current_value; sp[vf_i++].freq = current_freq; current_value = v[v_i]; current_freq = 1; } } /*Finding max,min frequency*/ int i, max_freq_val, max_freq, min_freq_val, min_freq; max_freq = sp[0].freq; max_freq_val = sp[0].value; min_freq = sp[0].freq; min_freq_val = sp[0].value; for(i=1; i max_freq) { max_freq = sp[i].freq; max_freq_val = sp[i].value; } if(sp[i].freq < min_freq) { min_freq = sp[i].freq; min_freq_val = sp[i].value; } } *most_freq = max_freq_val; *less_freq = min_freq_val; free(sp); } 

Commençons par le fait que votre algorithme est déjà O (n * log (n)), chaque étape étant O (n) en dehors du sorting qui est O (n * log (n)). S’il peut être amélioré de manière significative, cela dépend du type de consortingbution attendu. Éditer: À moins que, et cela semble être le cas, il ne fait pas partie de l’exigence de sorting des valeurs (en tout cas par valeur, et non par nombre d’occurrences) à la fin du processus, auquel cas, ne manquez pas Oli. La réponse de Charlesworth.

Il y a 2 concept sur le terrain: le premier est le nombre d’échantillons que vous allez obtenir (n); la seconde est “quelle concentration” sont leurs valeurs, quelle est l’étendue ou la largeur de la plage où ces valeurs peuvent être réparties (w = MAX_VALUE – MIN_VALUE).

Si n est inférieur à w (vos valeurs sont donc minces), votre approche est déjà optimale et laisse peu de place à l’amélioration.

Mais si w est petit et n est grand, vous avez beaucoup à gagner avec la méthode suivante.

Disons que vous savez que vous ne pouvez obtenir aucune valeur inférieure à MIN_VALUE et aucune valeur supérieure à MAX_VALUE. Ensuite, vous pouvez utiliser value comme index pour un tableau dans lequel vous collectez vos fréquences. De cette façon, vous sautez l’étape de sorting (O (n * log (n))) et vous calculez vos fréquences dans O (n).

 int buffer_frequencies[MAX_VALUE - MIN_VALUE + 1]; //Now reset the array with some convenient function like memset int* value_frequencies = buffer_frequencies; value_frequencies -= MIN_VALUE; //Shift the beginning of the array, so that //you can use the value directly as the array index //You are allowed to use negative indexes for(v_i=0; v_i < n; v_i++) { value_frequencies[v[v_i]]++; } 

Ou même (peut-être une version légèrement plus rapide du cycle for, mais généralement un bon compilateur le convertira déjà dans la version la plus efficace):

 int* p_v = v; int* end_p_v = v+n; for(; p_v < end_p_v; p_v++) { value_frequencies[*p_v]++; } 

Veillez à ce que cette méthode (les deux versions) soit très délicate pour les valeurs d'entrée. En d'autres termes, vous casserez les limites de la mémoire si vous obtenez une valeur supérieure à MIN_VALUE ou MAX_VALUE.

Puis la deuxième partie de l'algorithme:

 //First cycle could be optimized, but it has no impact int i = MIN_VALUE; max_freq = value_frequencies[i]; max_freq_val = i; min_freq = value_frequencies[i]; min_freq_val = i; for(; i max_freq) ? i : max_freq_val; max_freq = (value_frequencies[i] > max_freq) ? value_frequencies[i] : max_freq; min_freq_val = (value_frequencies[i] < min_freq) ? i : min_freq_val; min_freq = (value_frequencies[i] < min_freq) ? value_frequencies[i] : min_freq; } } 

Utilisez une table de hachage pour implémenter une carte clé-valeur? Cela devrait vous donner O (n) le temps prévu. *


* Cependant, notez que c’est O (n 2 ) dans le pire des cas. Cela ne se produit que lorsque toutes les entrées sont dans le même seau et que vous finissez par rechercher une liste chaînée à chaque itération! Pour une implémentation décente de table de hachage, la probabilité que cela se produise est vraiment très faible.