Algorithme le plus rapide [Résolu]

Signaler
Messages postés
26
Date d'inscription
dimanche 6 décembre 2009
Statut
Membre
Dernière intervention
12 décembre 2009
-
Messages postés
571
Date d'inscription
vendredi 30 décembre 2005
Statut
Membre
Dernière intervention
12 juillet 2012
-
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

23 réponses

Messages postés
3820
Date d'inscription
dimanche 12 décembre 2004
Statut
Modérateur
Dernière intervention
1 décembre 2020
113
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).
Messages postés
26
Date d'inscription
dimanche 6 décembre 2009
Statut
Membre
Dernière intervention
12 décembre 2009

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..
Messages postés
3820
Date d'inscription
dimanche 12 décembre 2004
Statut
Modérateur
Dernière intervention
1 décembre 2020
113
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 <char c>
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;
}
Messages postés
26
Date d'inscription
dimanche 6 décembre 2009
Statut
Membre
Dernière intervention
12 décembre 2009

En effet, ca peut etre ca, mais ou ets ce que tu fais la comparaison avec le char*a ?
Messages postés
3820
Date d'inscription
dimanche 12 décembre 2004
Statut
Modérateur
Dernière intervention
1 décembre 2020
113
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.
Messages postés
26
Date d'inscription
dimanche 6 décembre 2009
Statut
Membre
Dernière intervention
12 décembre 2009

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..
Messages postés
3820
Date d'inscription
dimanche 12 décembre 2004
Statut
Modérateur
Dernière intervention
1 décembre 2020
113
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;
}
Messages postés
26
Date d'inscription
dimanche 6 décembre 2009
Statut
Membre
Dernière intervention
12 décembre 2009

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
Messages postés
3820
Date d'inscription
dimanche 12 décembre 2004
Statut
Modérateur
Dernière intervention
1 décembre 2020
113
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;
}
Messages postés
21042
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
24
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++
Messages postés
3820
Date d'inscription
dimanche 12 décembre 2004
Statut
Modérateur
Dernière intervention
1 décembre 2020
113
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).
Messages postés
21042
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
24
J'espère aussi qu'on aura la réponse.

ciao...
BruNews, MVP VC++
Messages postés
26
Date d'inscription
dimanche 6 décembre 2009
Statut
Membre
Dernière intervention
12 décembre 2009

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..
Messages postés
571
Date d'inscription
vendredi 30 décembre 2005
Statut
Membre
Dernière intervention
12 juillet 2012
3
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.
Messages postés
26
Date d'inscription
dimanche 6 décembre 2009
Statut
Membre
Dernière intervention
12 décembre 2009

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..
Messages postés
3820
Date d'inscription
dimanche 12 décembre 2004
Statut
Modérateur
Dernière intervention
1 décembre 2020
113
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.
Messages postés
571
Date d'inscription
vendredi 30 décembre 2005
Statut
Membre
Dernière intervention
12 juillet 2012
3
Je n'ai rien d'autre à proposer que de mesurer le code au lieu de blablater.
Messages postés
1905
Date d'inscription
mercredi 22 janvier 2003
Statut
Membre
Dernière intervention
17 septembre 2012
2
salut,
puisque des valeurs sont connues, pourquoi ne pas utiliser un tableau indexé par a qui contient toutes les valeurs ?
Messages postés
26
Date d'inscription
dimanche 6 décembre 2009
Statut
Membre
Dernière intervention
12 décembre 2009

j'l'ai proposé, un tableau a deux colonnes indéxé, il m'a dit pas plus rapide qu'un switch case..
Messages postés
1905
Date d'inscription
mercredi 22 janvier 2003
Statut
Membre
Dernière intervention
17 septembre 2012
2
pourquoi deux colones ?
tu as un int tableau[256] qui contient toutes les valeurs et dans ta fonction tu as juste à retourner tableau[*a]