Trouver les deux plus grands des cinq petits entiers le plus rapidement possible

J'utilise une variation d'un filtre médian à 5 croix sur les données d'image sur un petit système embarqué, c'est-à-dire

    x
  x x x
    x

L'algorithme est vraiment simple: lire 5 valeurs entières non signées, obtenir les 2 plus élevées, faire des calculs sur celles-ci et réécrire le résultat entier non signé.

Ce qui est bien, c'est que les 5 valeurs d'entrée entières sont toutes dans la plage de 0 à 20. La valeur entière calculée est également dans la plage 0-20!

Grâce au profilage, j'ai compris que l'obtention des deux plus grands nombres est le goulot d'étranglement, donc je veux accélérer cette partie. Quelle est la manière la plus rapide d'effectuer cette sélection?

L'algorithme actuel utilise un masque de 32 bits avec 1 à la position donnée par les 5 chiffres et une fonction CLZ prise en charge par HW.
Je dois dire que le CPU est un processeur propriétaire, non disponible en dehors de mon entreprise. Mon compilateur est GCC mais fait sur mesure pour ce CPU.

J'ai essayé de comprendre si je peux utiliser une table de recherche, mais je n'ai pas réussi à générer une clé que je peux utiliser.

J'ai combinaisons pour l'entrée mais l'ordre n'est pas important, c'est -à- dire le même que .$21^5$[5,0,0,0,5][5,5,0,0,0]

Il se trouve que la fonction de hachage ci-dessous produit un hachage parfait sans collisions!

def hash(x):
    h = 0
    for i in x:
        h = 33*h+i
    return h

Mais le hachage est énorme et il n'y a tout simplement pas assez de mémoire pour l'utiliser.

Existe-t-il un meilleur algorithme que je peux utiliser? Est-il possible de résoudre mon problème en utilisant une table de correspondance et en générant une clé?

Dans mon autre réponse, je suggère que les sauts conditionnels pourraient être le principal obstacle à l'efficacité. Par conséquent, les réseaux de tri me viennent à l'esprit: ils sont indépendants des données, c'est-à-dire que la même séquence de comparaisons est exécutée quelle que soit l'entrée, seuls les swaps étant conditionnels.

$\hat{U}_2(5) = 6$

Le réseau qu'il donne dans les solutions (réécrit en tableaux à base zéro) est

$\qquad\displaystyle [0:4]\,[1:4]\,[0:3]\,[1:3]\,[0:2]\,[1:2]$

qui implémente - après avoir ajusté la direction des comparaisons - en pseudocode comme

def selMax2(a : int[])
  a.swap(0,4) if a[0] < a[4]
  a.swap(1,4) if a[1] < a[4]
  a.swap(0,3) if a[0] < a[3]
  a.swap(1,3) if a[1] < a[3]
  a.swap(0,2) if a[0] < a[2]
  a.swap(1,2) if a[1] < a[2]
  return (a[0], a[1])
end

Maintenant, les implémentations naïves ont toujours des sauts conditionnels (à travers le code d'échange). Selon votre machine, vous pouvez cependant les contourner avec des instructions conditionnelles. x86 semble être son soi habituel; ARM semble plus prometteur car apparemment la plupart des opérations sont conditionnelles en elles-mêmes. Si je comprends bien les instructions , le premier échange se traduit par ceci, en supposant que nos valeurs de tableau ont été chargées dans les registres R0via R4:

CMP     R0,R4
MOVLT   R5 = R0
MOVLT   R0 = R4
MOVLT   R4 = R6

^{Oui, oui, bien sûr, vous pouvez utiliser l' échange XOR avec EOR .}

J'espère juste que votre processeur a ceci, ou quelque chose de similaire. Bien sûr, si vous construisez la chose à cet effet, vous pouvez peut-être y connecter le réseau?

C'est probablement (peut-être?) Le meilleur que vous puissiez faire dans le domaine classique, c'est-à-dire sans faire usage du domaine limité et sans effectuer de méchantes magies intra-mots.

1. Tri et recherche par Donald E. Knuth; L'art de la programmation informatique Vol. 3 (2 e éd., 1998)
2. $\hat{W}_2(5) = 7$

Juste pour que ce soit sur la table, voici un algorithme direct:

// Sort x1, x2
if x1 < x2
  M1 = x2
  m1 = x1
else
  M1 = x1
  m1 = x2
end

// Sort x3, x4
if x3 < x4
  M2 = x4
  m2 = x3
else
  M2 = x3
  m2 = x4
end

// Pick largest two
if M1 > M2
  M3 = M1
  if m1 > M2
    m3 = m1
  else
    m3 = M2
  end
else
  M3 = M2
  if m2 > M1
    m3 = m2
  else
    m3 = M1
  end
end

// Insert x4
if x4 > M3
  m3 = M3
  M3 = x4
else if x4 > m3
  m3 = x4
end

Par une implémentation intelligente de if ... else, on peut se débarrasser de certains sauts inconditionnels qu'aurait une traduction directe.

C'est moche mais ça ne prend que

• cinq ou six comparaisons (c'est-à-dire des sauts conditionnels),
• neuf à dix affectations (avec 11 variables, toutes dans les registres) et
• aucun accès mémoire supplémentaire.

$W_2(5)$

Cependant, cela ne peut pas être rapide sur les machines avec pipelining; étant donné leur pourcentage élevé de sauts conditionnels, la plupart du temps serait probablement passé en décrochage.

Notez qu'une variante plus simple - trier x1et x2ensuite insérer les autres valeurs par la suite - prend quatre à sept comparaisons et seulement cinq à six affectations. Comme je m'attends à ce que les sauts soient plus coûteux ici, je suis resté avec celui-ci.

1. Tri et recherche par Donald E. Knuth; L'art de la programmation informatique Vol. 3 (2 e éd., 1998)

Cela pourrait être une excellente application et un cas de test pour le projet Souper . Souper est un superoptimiseur - un outil qui prend une courte séquence de code en entrée et essaie de l'optimiser autant que possible (essaie de trouver une séquence de code équivalente qui sera plus rapide).

Souper est open source. Vous pouvez essayer d'exécuter Souper sur votre extrait de code pour voir s'il peut faire mieux.

Voir aussi le concours de John Regehr sur l'écriture de code rapide pour trier 16 valeurs 4 bits ; il est possible que certaines de ces techniques soient utiles.

$21^3$

T[T[T[441*a+21*b+c]*21+d]*21+e]

$21^4$

$21^2$

$21^2$