Algorithme le plus rapide Résolu

Question

Bonjour les amis,

je cherche l'algorithme le plus rapide en C++ pour obtenir de la fonction suivante

inline int fonction (char* a) {


}

les résultats suivants:
entrée        Sortie
  A              3
  E              4
  C              9
  K              10
  L              40
  autre          0

Il existe apparemment un algorithme plus rapide que le switch/case

Merci

cptpingu · Accepted Answer

switch case n'est pas un algorithme.
Ce que tu recherches est une manière technique de faire les choses, pas un algorithme.

Je ne vois pas vraiment comment aller plus vite qu'un switch case !

A moins de faire de la métaprog, mais si les données sont acquises à l'exécution, ce ne sera pas possible.

(Ou peut être peut-on trouver une astuce à base de masque de bit, mais c'est un peu tiré par les cheveux).

cs_cogno · Answer

Et Pingu tes la seule personne active du forum? mdr

Merci en tout cas.
Moi j'ai répondu switch/case. Il m'a dit que c'était le second choix.

Il m'a dit qu'il pouvait avoir besoin de cette fonction 300 000 fois par seconde lol

En effet j'ai pas explorer la piste des masques binaires, c'est bien vu!

je peux malheureusement pas le faire maintenant car je ne suis plus sur des valeurs numériques..

cptpingu · Answer

La seule solution qui me vient à l'esprit pour être plus rapide que switch case, c'est de calculer la logique à la compilation: #include template struct Func { static const int member = 0; }; template <> struct Func<'A'> { static const int member = 3; }; template <> struct Func<'E'> { static const int member = 4; }; template <> struct Func<'C'> { static const int member = 9; }; template <> struct Func<'K'> { static const int member = 10; }; template <> struct Func<'L'> { static const int member = 40; }; int main(void) { std::cout << "Q = " << Func<'Q'>::member << std::endl; std::cout << "A = " << Func<'A'>::member << std::endl; std::cout << "E = " << Func<'E'>::member << std::endl; std::cout << "C = " << Func<'C'>::member << std::endl; std::cout << "K = " << Func<'K'>::member << std::endl; std::cout << "L = " << Func<'L'>::member << std::endl; return 0; }

cs_cogno · Answer

En effet, ca peut etre ca, mais ou ets ce que tu fais la comparaison avec le char*a ?

cptpingu · Answer

Je ne le fais pas, puisque tout est à la compilation. C'est pour cela que j'ai précisé que c'était le seul moyen de vraiment aller plus vite, mais que ça ne résolvait pas le problème dans le cas ou les valeurs n'étaient connues qu'à l'exécution.

cs_cogno · Answer

Lui me demandait de remplir la fonction
inline int fct (char a*) {

.?.

}

Mais en effet, c'etait peut etre un "piège", dans le sens où il attendait que je propose une solution plus statique..

cptpingu · Answer

J'ai finalement une solution, mais je ne pense pas qu'elle soit plus rapide qu'un switch case, et c'est un peu tiré par les cheveux:

#include 

int fonction(char* a)
{
  return
    ((!!!(*a ^ 0b1000001)) * 3) +
    ((!!!(*a ^ 0b1000101)) * 4) +
    ((!!!(*a ^ 0b1000011)) * 9) +
    ((!!!(*a ^ 0b1001011)) * 10) +
    ((!!!(*a ^ 0b1001100)) * 40);
}

int main()
{
  std::cout << "Q " << fonction("Q") << std::endl;
  std::cout << "A " << fonction("A") << std::endl;
  std::cout << "E " << fonction("E") << std::endl;
  std::cout << "C " << fonction("C") << std::endl;
  std::cout << "K " << fonction("K") << std::endl;
  std::cout << "L " << fonction("L") << std::endl;

  return 0;
}

cs_cogno · Answer

A méditer sur le secret de tes masques :)

devancer par tant d'exclamation...je me dis que si en effet cest ca, je suis fier de ne pas l'avoir trouvé héhé (j'ai économiser de la chute de cheveux)

mais a mon avis tu as raison, ya que le masquage qui reste comme solution

cptpingu · Answer

Simplifiable en:

#include 

int fonction(char* a)
{
  return
    (!(*a ^ 'A') * 3) +
    (!(*a ^ 'E') * 4) +
    (!(*a ^ 'C') * 9) +
    (!(*a ^ 'K') * 10) +
    (!(*a ^ 'L') * 40);
}

int main()
{
  std::cout << "Q " << fonction("Q") << std::endl;
  std::cout << "A " << fonction("A") << std::endl;
  std::cout << "E " << fonction("E") << std::endl;
  std::cout << "C " << fonction("C") << std::endl;
  std::cout << "K " << fonction("K") << std::endl;
  std::cout << "L " << fonction("L") << std::endl;

  return 0;
}

BruNews · Answer

Tout ce qui amènera vers le 'return valeur' depuis l'entrée de la fonction fait partie de l'algo, le 'switch case' y compris. On est ensuite dépendant de la qualité de l'optimiseur du compilo.
Dans tous les cas, switch case se résumera au maxi à 5 CMP et 1 seul JMP (le vilain goto), imbattable ici.

ciao...
BruNews, MVP VC++

cptpingu · Answer

Tout ce qui amènera vers le 'return valeur' depuis l'entrée de la fonction fait partie de l'algo, le 'switch case' y compris. On est ensuite dépendant de la qualité de l'optimiseur du compilo. 
Je ne suis pas tout à fait d'accord, ce n'est pas un algorithme, mais l'implémentation d'un algorithme. Un algorithme n'a rien à voir avec une quelconque technique, c'est juste une idée, une méthode de résolution.

Dans tous les cas, switch case se résumera au maxi à 5 CMP et 1 seul JMP (le vilain goto), imbattable ici. 
S'il n'y a pas plus rapide qu'un switch, alors pourquoi lui avoir posé la question ? Un piège ? Il y a une astuce qui m'a échappée ? S'il y a une meilleur solution que le switch case pour l'exemple énoncé, je serais très curieux de la connaître (parce que très honnêtement, je ne vois pas).

BruNews · Answer

J'espère aussi qu'on aura la réponse.

ciao...
BruNews, MVP VC++

cs_cogno · Answer

Attention, ne pas trop se focaliser sur cet exercice, car il y a peut etre une astuce en fonction des valeurs numériques choisies, et je ne suis pas sûr d'avoir les bonnes en tête...

En tout cas je ne pense pas qu'il y avait un piège car il a dit:

"on passe à la question suivante, mais cest deja bien, le switch case etait le second choix...."

Si cetait un pièg, jpense quil maurait laissé chercher en galérant..

katsankat · Answer

Salut, tu devrais mesurer le code si tu cherches vraiment le plus rapide. Avec une macro ou mieux avec de l'assembleur inline ça serait fait à mach2.

cs_cogno · Answer

merci Katsankat,

cependant le mec m'a dit que c'était possible en gardant le prototype

inline int fct (char*) ...

mais bon ca se trouve yavait une astuce de masquage de bit avec les valeurs numériques, donc j'ai relaché un peu le pb..

cptpingu · Answer

Avec une macro
Non, en C++ on préfère largement utiliser de la méta-prog à des macros. J'ai déjà proposé une telle technique sur la page précédente, mais ça ne résout pas le problème, les variables étant connu uniquement à l'exécution.

 ou mieux avec de l'assembleur inline ça serait fait à mach2.
Ce n'est pas parce que tu fais de l'assembleur, que ça va forcément plus vite. Les compilateurs modernes sont extrêmement astucieux, et génère très souvent des codes parfaitement optimisés.

Je serais tout de même curieux de voir ce que tu as à proposer en assembleur, parce qu'un switch case en assembleur ne serait pas plus rapide si codé en assembleur par tes soins, que généré astucieusement par un compilateur.

katsankat · Answer

Je n'ai rien d'autre à proposer que de mesurer le code au lieu de blablater.

cs_aardman · Answer

salut,
puisque des valeurs sont connues, pourquoi ne pas utiliser un tableau indexé par a qui contient toutes les valeurs ?

cs_cogno · Answer

j'l'ai proposé, un tableau a deux colonnes indéxé, il m'a dit pas plus rapide qu'un switch case..

cs_aardman · Answer

pourquoi deux colones ?
tu as un int tableau[256] qui contient toutes les valeurs et dans ta fonction tu as juste à retourner tableau[*a]

cs_cogno · Answer

deux colonnes car en entrée ya le char * a et en sortie le int, non?

cptpingu · Answer

tu as un int tableau[256] qui contient toutes les valeurs et dans ta fonction tu as juste à retourner tableau[*a]

J'y ai pensé mais plusieurs problèmes:
* Il ne connait pas les vrais valeurs, donc si il se tape un caractère étendu, la technique ne fonctionnera plus
* Prend de la place en mémoire, si il est sur un système embarqué, c'est peu être beaucoup trop place.

Sinon, si les contraintes sont celles posées à l'origine du problème, ça peut être une excellente idée. Mais à voir tout de même le réel gain, si gain il y a.

katsankat · Answer

Salut voici des codes en langage C pour mesurer le temps d'exécution d'une portion de code

Algorithme le plus rapide

23 réponses

Votre réponse

Discussions similaires