Comment feriez-vous cette déclaration d'échange le plus rapidement possible ?

Question

MISE À JOUR DU 2009-12-04 : Pour les résultats du profilage d'un certain nombre de suggestions postées ici, voir ci-dessous !

---

La question

Considérez la méthode suivante, très inoffensive et très simple, qui utilise un fichier switch pour retourner une valeur d'énumération définie :

public static MarketDataExchange GetMarketDataExchange(string ActivCode) {
    if (ActivCode == null) return MarketDataExchange.NONE;

    switch (ActivCode) {
        case "": return MarketDataExchange.NBBO;
        case "A": return MarketDataExchange.AMEX;
        case "B": return MarketDataExchange.BSE;
        case "BT": return MarketDataExchange.BATS;
        case "C": return MarketDataExchange.NSE;
        case "MW": return MarketDataExchange.CHX;
        case "N": return MarketDataExchange.NYSE;
        case "PA": return MarketDataExchange.ARCA;
        case "Q": return MarketDataExchange.NASDAQ;
        case "QD": return MarketDataExchange.NASDAQ_ADF;
        case "W": return MarketDataExchange.CBOE;
        case "X": return MarketDataExchange.PHLX;
        case "Y": return MarketDataExchange.DIRECTEDGE;
    }

    return MarketDataExchange.NONE;
}

Aujourd'hui, mon collègue et moi avons échangé quelques idées sur la manière de rendre cette méthode plus rapide. Nous avons proposé quelques modifications intéressantes qui ont permis d'améliorer les performances de manière significative (proportionnellement, bien sûr). J'aimerais savoir si d'autres personnes ont des idées d'optimisation qui ne nous sont pas venues à l'esprit.

Tout de suite, laissez-moi vous donner un petit avertissement : c'est pour amusant y pas pour alimenter tout le débat "optimiser ou ne pas optimiser". Cela dit, si vous comptez parmi ceux qui croient dogmatiquement que "l'optimisation prématurée est la racine de tous les maux", sachez que je travaille pour une société de trading à haute fréquence, où tout doit fonctionner le plus rapidement possible, qu'il y ait ou non un goulot d'étranglement. Donc, même si je poste ceci sur SO pour amusant il ne s'agit pas non plus d'une énorme perte de temps.

Une dernière remarque rapide : deux types de réponses m'intéressent : celles qui supposent que chaque entrée est un ActivCode valide (une des chaînes de caractères dans le champ "ActivCode") et celles qui supposent que chaque entrée est un code d'activation. switch ci-dessus), et ceux qui ne le font pas. Je suis presque Je suis certain que le fait de faire la première hypothèse permet d'améliorer encore la vitesse ; en tout cas, c'est ce qui s'est passé pour nous. Mais je sais que des améliorations sont possibles dans les deux cas.

---

Les résultats

Eh bien, il s'avère que la solution la plus rapide jusqu'à présent (que j'ai testée) est venue de João Angelo, dont la suggestion était en fait très simple, mais extrêmement intelligente. La solution que mon collègue et moi avons élaborée (après avoir essayé plusieurs approches, dont beaucoup ont été imaginées ici aussi) est arrivée en deuxième position ; j'allais la poster, mais il s'avère que Mark Ransom a eu exactement la même idée, alors allez voir sa réponse !

Depuis que j'ai effectué ces tests, d'autres utilisateurs ont posté des messages de même nature. plus récent des idées... Je les testerai en temps voulu, lorsque j'aurai quelques minutes de plus à ma disposition.

J'ai effectué ces tests sur deux machines différentes : mon ordinateur personnel à la maison (un Athlon double cœur avec 4 Go de RAM sous Windows 7 64 bits) et ma machine de développement au travail (un Athlon double cœur avec 2 Go de RAM sous Windows XP SP3). Évidemment, les temps étaient différents ; cependant, les relatif Les temps, c'est-à-dire la façon dont chaque méthode se compare à toutes les autres, étaient les mêmes. C'est-à-dire que le plus rapide était le plus rapide sur les deux machines, etc.

Maintenant, les résultats. (Les heures que j'affiche ci-dessous proviennent de mon ordinateur personnel).

Mais d'abord, pour référence, la déclaration originale de l'interrupteur :
1000000 passages : 98,88 ms
Moyenne : 0,09888 microseconde

Les optimisations les plus rapides jusqu'à présent :

1. L'idée de João Angelo d'attribuer des valeurs aux enums en se basant sur les codes de hachage des chaînes ActivCode, puis de les caser directement ActivCode.GetHashCode() a MarketDataExchange :
   1000000 passages : 23,64 ms
   Moyenne : 0,02364 microseconde
   Augmentation de la vitesse : 329.90%

2. L'idée de mon collègue et moi de faire un casting ActivCode[0] à un int et de récupérer les MarketDataExchange à partir d'un tableau initialisé au démarrage (cette même idée a été suggérée par Mark Ransom) :
   1000000 passages : 28,76 ms
   Moyenne : 0,02876 microseconde
   Augmentation de la vitesse : 253.13%

3. l'idée de l'auteur de commuter sur la sortie de ActivCode.GetHashCode() au lieu de ActivCode :
   1000000 passages : 34,69 ms
   Moyenne : 0,03469 microseconde
   Augmentation de la vitesse : 185.04%

4. L'idée, suggérée par plusieurs utilisateurs dont Auraseer, tster, et kyoryu, d'allumer ActivCode[0] au lieu de ActivCode :
   1000000 passages : 36,57 ms
   Moyenne : 0,03657 microseconde
   Augmentation de la vitesse : 174.66%

5. L'idée de Loadmaster d'utiliser le hachage rapide, ActivCode[0] + ActivCode[1]*0x100 :
   1000000 passages : 39,53 ms
   Moyenne : 0,03953 microseconde
   Augmentation de la vitesse : 153.53%

6. L'utilisation d'une table de hachage ( Dictionary<string, MarketDataExchange> ), comme cela a été suggéré par beaucoup :
   1000000 passages : 88,32 ms
   Moyenne : 0,08832 microseconde
   Augmentation de la vitesse : 12.36%

7. En utilisant une recherche binaire :
   1000000 passages : 1031 ms
   Moyenne : 1,031 microsecondes
   Augmentation de la vitesse : aucune (les performances se sont dégradées)

Permettez-moi de dire que c'était vraiment cool de voir combien d'idées différentes les gens avaient sur ce problème simple. C'était très intéressant pour moi, et je suis très reconnaissant à tous ceux qui ont contribué et fait une suggestion jusqu'à présent.

Answer 1

En supposant que chaque entrée sera une entrée valide ActivCode que vous pouvez modifier les valeurs de l'énumération et fortement couplées à l'option GetHashCode mise en œuvre :

enum MarketDataExchange
{
    NONE,
    NBBO = 371857150,
    AMEX = 372029405,
    BSE = 372029408,
    BATS = -1850320644,
    NSE = 372029407,
    CHX = -284236702,
    NYSE = 372029412,
    ARCA = -734575383,
    NASDAQ = 372029421,
    NASDAQ_ADF = -1137859911,
    CBOE = 372029419,
    PHLX = 372029430,
    DIRECTEDGE = 372029429
}

public static MarketDataExchange GetMarketDataExchange(string ActivCode)
{
    if (ActivCode == null) return MarketDataExchange.NONE;

    return (MarketDataExchange)ActivCode.GetHashCode();
}

Answer 2

Je créerais ma propre fonction de hachage rapide et j'utiliserais une instruction switch entière pour éviter les comparaisons de chaînes :

int  h = 0;  

// Compute fast hash: A[0] + A[1]*0x100
if (ActivCode.Length > 0)
    h += (int) ActivCode[0];
if (ActivCode.Length > 1)
    h += (int) ActivCode[1] << 8;  

// Find a match
switch (h)
{
    case 0x0000:  return MarketDataExchange.NBBO;        // ""
    case 0x0041:  return MarketDataExchange.AMEX;        // "A"
    case 0x0042:  return MarketDataExchange.BSE;         // "B"
    case 0x5442:  return MarketDataExchange.BATS;        // "BT"
    case 0x0043:  return MarketDataExchange.NSE;         // "C"
    case 0x574D:  return MarketDataExchange.CHX;         // "MW"
    case 0x004E:  return MarketDataExchange.NYSE;        // "N"
    case 0x4150:  return MarketDataExchange.ARCA;        // "PA"
    case 0x0051:  return MarketDataExchange.NASDAQ;      // "Q"
    case 0x4451:  return MarketDataExchange.NASDAQ_ADF;  // "QD"
    case 0x0057:  return MarketDataExchange.CBOE;        // "W"
    case 0x0058:  return MarketDataExchange.PHLX;        // "X"
    case 0x0059:  return MarketDataExchange.DIRECTEDGE;  // "Y"
    default:      return MarketDataExchange.NONE;
}

Mes tests montrent que c'est à peu près 4,5 fois plus rapide que le code original.

Si le C# avait un préprocesseur, j'utiliserais une macro pour former les constantes de casse.

Cette technique est plus rapide que l'utilisation d'une table de hachage et certainement plus rapide que l'utilisation de comparaisons de chaînes de caractères. Elle fonctionne pour des chaînes de quatre caractères maximum avec des ints 32 bits, et jusqu'à 8 caractères avec des longs 64 bits.

Answer 3

Si vous savez à quelle fréquence les différents codes apparaissent, les plus courants devraient être placés en tête de liste, ce qui réduit le nombre de comparaisons. Mais supposons que vous n'ayez pas cette information.

Le fait de supposer que le code d'activation est toujours valide accélère bien sûr les choses. Vous n'avez pas besoin de tester pour null ou la chaîne vide, et vous pouvez supprimer un test à la fin du switch. C'est-à-dire, testez tout sauf Y, et retournez DIRECTEDGE si aucune correspondance n'est trouvée.

Au lieu d'allumer toute la chaîne, allumez sa première lettre. Pour les codes qui ont plus de lettres, mettez un deuxième test à l'intérieur du cas de commutation. Quelque chose comme ça :

switch(ActivCode[0])
{
   //etc.
   case 'B':
      if ( ActivCode.Length == 1 ) return MarketDataExchange.BSE; 
      else return MarketDataExchange.BATS;
      // etc.
}

Il serait préférable que vous puissiez revenir en arrière et modifier les codes pour qu'ils soient tous à un seul caractère, car vous n'auriez alors jamais besoin de plus d'un test. Il serait encore mieux d'utiliser la valeur numérique de l'énumération, de sorte que vous puissiez simplement effectuer un casting au lieu de devoir changer/traduire en premier lieu.

Answer 4

J'utiliserais un dictionnaire pour les paires clé-valeur et profiterais du temps de recherche O(1).

Answer 5

Avez-vous des statistiques sur les cordes les plus courantes ? Pour pouvoir les vérifier en premier ?