Le moyen le plus rapide de déterminer le minimum non nul

Question

Ayant un tableau de par exemple 4 entiers, comment déterminer son minimum non nul - de la manière la plus rapide?

Answer 1

Il existe une solution parallèle à ce problème, mais cela n'en vaut probablement pas la peine.

Nous définissons d'abord une opération xchg(m, n) sur un tableau a :

xchg(m, n) => ((a[m] > a[n] && a[n] != 0) || a[m] == 0) ? swap(a[m],a[n])

Cette opération trie deux éléments 'm' et 'n' dans l'ordre croissant s'ils contiennent tous deux des valeurs non nulles, ou les échange si la valeur de l'élément 'm' est zéro.

Ensuite, nous exécutons un ensemble de cinq opérations de ce type comme suit:

xchg(0,2) xchg(1,3)
xchg(0,1) xchg(2,3)
xchg(1,2)

Les opérations appariées xchg peuvent être exécutées en parallèle, réduisant le coût en temps de 40% sur une exécution strictement séquentielle. Lorsque nous avons terminé, tous les éléments non nuls du tableau seront triés par ordre croissant. L'élément de plus petite valeur sera dans un [0]. Si cette valeur est zéro, il n'y a pas de valeurs différentes de zéro dans le tableau.

Cette solution tire parti du parallélisme inhérent fourni par le tri des réseaux ( http://en.wikipedia.org / wiki / Sorting_network ), mais une analyse séquentielle de 4 éléments n'utilise pas plus de trois opérations de comparaison, et nécessite essentiellement deux fois moins d'écritures de stockage en moyenne:

scan séquentiel

int v = a[0]
for (n = 1; n < 4; n++) {
   if ((a[n] < v && a[n] != 0 ) || v == 0) v = a[n]
} 

Answer 2

À moins que vous ne gardiez la valeur minimale lorsque des éléments sont ajoutés au tableau, ou que vous gardiez le tableau dans un ordre trié - je ne vois pas d'autre solution que d'itérer chaque membre pour déterminer la valeur minimale.

Il n'y a pas de moyen "rapide" de tester chaque membre.

En général, je suggère de ne pas optimiser quelque chose à moins qu'il ne se révèle réellement lent.L'ancienne règle de votre programme passe 90% de son temps dans 10% du code est généralement vraie.Il en va de même pour les règles selon lesquelles les programmeurs ont 99,99% de chances d'optimiser le code pas dans ces 10%.

Profil de votre code - profil de votre code - profil de votre code

Answer 3

Si nous pensons à des micro-optimisations, alors il pourrait être plus rapide de calculer min(min(a,b),min(c,d)) au lieu de min(min(min(a,b),c),d) sur un processeur moderne dans le désordre, en raison des dépendances moins séquentielles: dans le premier, le processeur peut calculer min(a,b) etmin(c,d) indépendamment en parallèle, s'il dispose d'unités d'exécution suffisantes.Cela suppose que le processeur a une instruction de déplacement conditionnelle, de sorte que le calcul du min ne nécessite pas de branchement.

Answer 4

Dépend de l'entrée.Si le tableau n'est pas trié, vous devrez parcourir le tableau complet.Si le tableau est trié, il vous suffit de faire une boucle jusqu'à ce que vous trouviez quelque chose qui n'est pas zéro - c'est beaucoup plus court.

Answer 5

Le moyen le plus rapide de le coder est le std::min({a,b,c,d}).

Sur une note plus sérieuse: si votre application est goulot d'étranglement sur quelque chose comme prendre le minimum d'un grand nombre de valeurs, une meilleure solution pourrait être de trouver un moyen de diviser cette tâche de recherche minimale en plusieurs parties et de l'envoyer au GPU (ouplusieurs threads), qui peuvent alors effectuer plusieurs calculs de recherche minimum en même temps.

Le parallélisme aiderait probablement plus que d'essayer d'écrire une fonction minimale dans l'assembly.