Java: Trouver des correspondances entre les chaînes

Question

Étant donné 2 chaînes, je veux trouver le premier match d'au moins quatre caractères.

C'est le code que j'ai actuellement pour le faire. Cela fonctionne correctement, mais je pense qu'il pourrait y avoir une meilleure façon de le faire. Y a-t-il des inefficacités criantes ou de mauvaises pratiques dans ce que je fais? Y a-t-il des bibliothèques communes, comme Apache Commons, dont je devrais profiter, mais je ne le suis pas?

Ne vous inquiétez pas pour la classe Gene - elle contient uniquement la chaîne en question. En outre, GeneMatch() signifie qu'aucune correspondance n'existe, tandis que le constructeur GeneMatch avec des arguments indique qu'une correspondance a été trouvée.

Constants.MIN_MATCH == 4, dans ce cas.

public static GeneMatch findMatch(Gene g0, Gene g1) { 

    String g0DNA = g0.getDNA(); 
    String g1DNA = g1.getDNA(); 

    if (g0DNA.equals("") || g1DNA.equals("")) { //there won't be a match if one is empty 
     return new GeneMatch(); 
    } 

    int g0Left = -1; 
    int g0Right = -1; 
    int g1Left = -1; 
    int g1Right = -1; 

    String window; 

    for (int inx = 0; inx <= g0DNA.length() - Constants.MIN_MATCH; inx++) { 
     window = g0DNA.substring(inx, inx + Constants.MIN_MATCH); 

     if (g1DNA.indexOf(window) != -1) { 

      g0Left = inx; 
      g0Right = inx + Constants.MIN_MATCH; 

      g1Left = g1DNA.indexOf(window); 
      g1Right = g1Left + Constants.MIN_MATCH; 

      /* grow the match to the right 
      * while the two right indices are less than the lengths of their respective strings, and the 
      * characters at the indices match, increment each index 
      */ 
      while (g0Right < g0DNA.length() && g1Right < g1DNA.length() && g0DNA.charAt(g0Right) == g1DNA.charAt(g1Right)) { 
       g0Right++; 
       g1Right++; 
      } 
      break; //we've already found a match, no need to continue sliding the window 
     } 
    } 

    //now that the indices are found, convert to Genes 
    if (g0Left == -1 || g0Right == -1 || g1Left == -1 || g1Right == -1) { //no match found 
     return new GeneMatch(); 
    } 

    Gene gL0 = new Gene(g0DNA.substring(0, g0Left)); 
    Gene gL1 = new Gene(g1DNA.substring(0, g1Left)); 

    Gene g0match = new Gene(g0DNA.substring(g0Left, g0Right)); 
    Gene g1match = new Gene(g1DNA.substring(g1Left, g1Right)); 

    Gene gR0 = new Gene(g0DNA.substring(g0Right)); 
    Gene gR1 = new Gene(g1DNA.substring(g1Right)); 

    //sanity check 
    assert g0DNA.equals(gL0.getDNA() + g0match.getDNA() + gR0.getDNA()) : "g0 didn't add up"; 
    assert g1DNA.equals(gL1.getDNA() + g1match.getDNA() + gR1.getDNA()) : "g1 didn't add up"; 

    return new GeneMatch(gL0, gR0, g0match, g1match, gL1, gR1); 

} 

Answer 1

approche actuelle

1. Double g1DNA.indexOf (fenêtre) appel - premier résultat d'appel peut être stocké et réutilisé plus tard;
2. objets chaîne inutile construction pendant fenêtre = g0DNA.substring (INX, INX + Constants.MIN_MATCH);
3. Inutile gL0, gL1, gR0, gR1 la construction dans l'affirmation de cas est off;
4. (si g0DNA.equals (« ») || g1DNA.equals (« »)) contrôle peut être améliorée afin de vérifier que les chaînes comporte au moins quatre symboles chacun;
5. Il toujours préférable d'appeler equals() sur constante, à savoir utiliser "" equals (arg). Il permet d'éviter les NPE possibles si arg est null. Il n'a pas beaucoup d'impact ici, juste une bonne politique de codage à appliquer;
6. Il est String.isEmpty() méthode qui peut être utilisé pour remplacer "".est égal à (arg);
7. Aucune vérification nulle n'est effectuée pour les chaînes d'ADN ;

Améliorations

1. Il est préférable de boucler la chaîne la plus courte, à savoir que vous devriez vérifier ADN1 et la longueur de dna2 et effectuer la boucle extérieure contre celle avec plus courte longueur . Cela permet de minimiser le nombre d'itérations ;
2. Vous pouvez éviter de créer de nouveaux objets de chaîne et opérer en termes de caractères. En outre, vous pouvez modifier l'algorithme afin de fonctionner avec toute implémentation java.lang.CharSequence;
3. Vous pouvez rappeler inégalés séquences, à savoir garder un ensemble de séquences omble qui ont été vérifiées et se sont avérés être inégalés afin de minimiser le temps de la boucle extérieure itération. Par exemple, vous itérez sur la chaîne qui contient de nombreux caractères 'b' caractères . Vous vérifiez que la deuxième chaîne ne contient pas ce char lors du premier traitement 'b'. Vous pouvez vous rappeler cela et arrêter ultérieures 'b' traitements avec impatience;
4. Lorsque vous utilisez String.indexOf() la recherche est effectuée à partir du début de la chaîne. Cela peut poser problème si la chaîne à rechercher est plutôt . Il peut être préférable de créer un index de caractères pour cela. C'est à dire. avant le match trouver, vous pouvez itérer tous les caractères de la chaîne cible et applications de construction comme « caractère » -> « ensemble des indices de leur présence dans la chaîne ». Cela permet de effectuer le contrôle de corps de la boucle beaucoup plus vite en cas de longues chaînes;

Considérations générales Il n'y a pas l'un meilleur algorithme ' parce que « le meilleur » sélection dépend du profil de données d'entrée et de la politique d'utilisation de l'algorithme. C'est à dire. Si l'algorithme est rarement exécuté et que son impact sur les performances est insignifiant, il ne sert à rien de consacrer beaucoup de temps à son optimisation et il vaut mieux écrire un code simple et facile à maintenir. Si les chaînes d'entrée sont plutôt courtes, il ne sert à rien de construire l'index des caractères etc. En général, essayez d'éviter l'optimisation préliminaire autant que possible et considérez soigneusement toutes les données d'entrée en choisissant l'algorithme résultant si vous y trouvez vraiment un goulot d'étranglement.

Answer 2

Ça me semble assez bien. Juste deux petites choses:

1. réutiliser le résultat de g1DNA.indexOf(window) au lieu de l'appeler deux fois (g1Left = g1DNA.indexOf(window);)

2. vous n'avez pas de vérifier les 4 vars pour être == -1 comme vous tous ensemble eux à la fois de toute façon.

Answer 3

Cela me semble bon. On peut aller de l'avant et optimiser micro en termes d'affectations, mais c'est le travail du compilateur JIT. Si vous pensez que l'algorithme est trop lent, essayez de le profiler.