Efficacité de la détection palindrome

Question

La entrevue de Jon Limjap a provoqué une curiosité et a commencé à rechercher des moyens efficaces de faire la détection palindrome. J'ai vérifié les réponses golf palindrome et il me semble que, dans les réponses, il n'y a que deux algorithmes, l'inversion de la chaîne et vérifier à partir de la queue et de la tête.

def palindrome_short(s):
    length = len(s)
    for i in xrange(0,length/2):
        if s[i] != s[(length-1)-i]: return False
    return True

def palindrome_reverse(s):
    return s == s[::-1]

Je pense qu'aucune de ces méthodes n’est utilisée dans la détection de palindromes exacts dans d’énormes séquences d’ADN. J'ai jeté un coup d'œil autour de moi et je n'ai trouvé aucun article gratuit sur ce que pourrait être un moyen ultra-efficace.

Une bonne façon de procéder consiste peut-être à paralléliser la première version selon une approche diviser pour mieux régner, en attribuant une paire de tableaux de caractères 1..n et longueur-1-n..longueur-1 à chaque thread ou processeur.

Quelle serait une meilleure solution?

En connaissez-vous?

Answer 1

Etant donné un seul palindrome, vous devrez le faire en O (N), oui. Vous pouvez obtenir plus d'efficacité avec les multi-processeurs en scindant la chaîne comme vous l'avez dit.

Maintenant, dites que vous voulez faire une correspondance exacte de l'ADN. Ces chaînes contiennent des milliers de caractères et sont très répétitives. Cela nous donne l'occasion d'optimiser.

Supposons que vous scindiez une chaîne longue de 1000 caractères en 5 paires de 100,100. Le code ressemblera à ceci:

isPal(w[0:100],w[-100:]) and isPail(w[101:200], w[-200:-100]) ...

etc ... La première fois que vous faites ces correspondances, vous devrez les traiter. Cependant, vous pouvez ajouter tous les résultats que vous avez obtenus dans une paire de mappage de table de hachage à des booléens:

isPal = {("ATTAGC", "CGATTA"): True, ("ATTGCA", "CAGTAA"): False}

etc ... cela prendra beaucoup trop de mémoire, cependant. Pour des paires de 100,100, la carte de hachage aura 2 * 4 ^ 100 éléments. Dites que vous ne stockez que deux clés de hachage 32 bits comme clé; vous aurez besoin de quelque chose comme 10 ^ 55 Mo, ce qui est ridicule.

Peut-être que si vous utilisez des chaînes plus petites, le problème peut être résolu. Ensuite, vous aurez une énorme hashmap, mais au moins un palindrome pour 10 paires de 10x10 prendra O (1), donc vérifier si une chaîne de caractères 1000 est un palindrome prendra 100 consultations au lieu de 500 comparaisons. C'est toujours O (N), bien que ...

Answer 2

Une autre variante de votre deuxième fonction. Nous n’avons besoin d’aucune vérification égale des bonnes parties des chaînes normales et inverses.

def palindrome_reverse(s):
  l = len(s) / 2
  return s[:l] == s[l::-1]

Answer 3

Évidemment, vous ne pourrez pas améliorer l'efficacité asymétrique de O (n), car chaque personnage doit être examiné au moins une fois. Vous pouvez cependant obtenir de meilleures constantes multiplicatives.

Pour un seul thread, vous pouvez accélérer le processus en utilisant assembly. Vous pouvez également faire mieux en examinant des données dans des morceaux de plus d'un octet à la fois, mais cela peut être délicat à cause des considérations d'alignement. Vous ferez encore mieux d’utiliser SIMD si vous pouvez examiner des blocs d’une taille maximale de 16 octets à la fois.

Si vous souhaitez le paralléliser, vous pouvez diviser la chaîne en N morceaux et demander au processeur i de comparer le segment [i * n / 2, (i + 1) * N / 2) avec le segment [L- (i + 1) * N / 2, Li * N / 2) .

Answer 4

Il n'y en a pas, sauf si vous faites une correspondance approximative. C’est ce qu’ils font probablement dans l’ADN (j’ai fait EST avec une recherche dans ADN avec Smith-Waterman, mais c’est évidemment beaucoup plus difficile que de rechercher un palindrome ou un complément inverse dans une séquence).

Answer 5

Ils sont tous les deux en O (N), je ne pense donc pas que l’une de ces solutions pose un problème d’efficacité particulier. Peut-être que je ne suis pas assez créatif mais je ne vois pas comment il serait possible de comparer N éléments en moins de N étapes, alors quelque chose comme O (log N) n’est définitivement pas possible à mon humble avis.

Le pararellisme pourrait aider, mais cela ne changerait pas le classement big-Oh de l'algorithme, car cela revient à l'exécuter sur une machine plus rapide.

Answer 6

La comparaison à partir du centre est toujours beaucoup plus efficace, car vous pouvez vous en tirer plus tôt mais cela vous permet toujours de faire une recherche max plus rapide du palindrome, que vous recherchiez le rayon maximal ou tous les palindromes ne se chevauchant pas.

La seule véritable paralellisation est si vous avez plusieurs chaînes indépendantes à traiter. Le fractionnement en morceaux gaspillera beaucoup de travail pour chaque coup manqué et il y aura toujours beaucoup plus de ratés que de coups.

Answer 7

Avec Python, le code court peut être plus rapide puisqu'il place la charge dans les éléments internes les plus rapides de la machine virtuelle (et qu'il y a tout le cache, etc.)

def ispalin(x):
   return all(x[a]==x[-a-1] for a in xrange(len(x)>>1))

Answer 8

Vous pouvez utiliser une table de hachage pour mettre le caractère et avoir une variable de compteur dont la valeur augmente chaque fois que vous trouvez un élément qui n'est pas dans table / map. Si vous vérifiez et trouvez l’élément déjà présent dans le tableau, diminuez le nombre.

For odd lettered string the counter should be back to 1 and for even it should hit 0.I hope this approach is right.

See below the snippet.
s->refers to string
eg: String s="abbcaddc";
Hashtable<Character,Integer> textMap= new Hashtable<Character,Integer>();
        char charA[]= s.toCharArray();
        for(int i=0;i<charA.length;i++)
        {

            if(!textMap.containsKey(charA[i]))
            {   
                textMap.put(charA[i], ++count);

            }
            else
                {
                textMap.put(charA[i],--count);


        }
        if(length%2 !=0)
        {
            if(count == 1)
            System.out.println("(odd case:PALINDROME)");
            else
                System.out.println("(odd case:not palindrome)");
        }
        else if(length%2==0)    
        {
            if(count ==0)
                System.out.println("(even case:palindrome)");
            else
                System.out.println("(even case :not palindrome)");
        }

Answer 9

public class Palindrome{
    private static boolean isPalindrome(String s){
        if(s == null)
            return false;   //unitialized String ? return false
        if(s.isEmpty())     //Empty Strings is a Palindrome 
            return true;
        //we want check characters on opposite sides of the string 
        //and stop in the middle <divide and conquer>
        int left = 0;  //left-most char    
        int right = s.length() - 1; //right-most char

        while(left < right){  //this elegantly handles odd characters string 
            if(s.charAt(left) != s.charAt(right)) //left char must equal 
                return false; //right else its not a palindrome
            left++; //converge left to right 
            right--;//converge right to left 
        }
        return true; // return true if the while doesn't exit 
    }
}

bien que nous fassions n / 2 calculs c'est toujours O (n) cela peut également être fait en utilisant des threads, mais les calculs sont compliqués, mieux vaut les éviter. cela ne vérifie pas les caractères spéciaux et est sensible à la casse. J'ai un code qui le fait, mais ce code peut être modifié pour le gérer facilement.