Efficacité de la détection Palindrome

Question

J'ai été curieux par Jon Limjap's interview mishap et j'ai commencé à chercher des moyens efficaces de détecter le palindrome. J'ai vérifié les réponses palindrome golf et il me semble que dans les réponses sont deux algorithmes seulement, en inversant la chaîne et en vérifiant de la queue et 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 sont utilisées dans la détection des palindromes exactes dans les séquences d'ADN énormes. J'ai regardé un peu autour et n'ai pas trouvé d'article gratuit sur ce que pourrait être un moyen très efficace. Un bon moyen pourrait être de paralléliser la première version dans une approche de division et de conquête, en assignant une paire de tableaux de caractères 1..n et longueur-1-n..length-1 à chaque thread ou processeur.

Quoi de mieux?

En connaissez-vous?

Answer 1

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

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

Supposons que vous divisiez une chaîne longue de 1000 char 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 matches, vous devrez les traiter. Cependant, vous pouvez ajouter tous les résultats que vous avez fait dans une paire de cartographie Hashtable à booléens:

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

etc ... cela prendra trop de mémoire, cependant.Pour les paires de 100 100, la carte de hachage aura 2 * 4^100 éléments. Dites que vous ne stockez que deux hachages 32 bits de chaînes comme la clé, vous aurez besoin de quelque chose comme 10^55 mégaoctets, ce qui est ridicule. Peut-être que si vous utilisez des chaînes plus petites, le problème peut être traitable. Ensuite, vous aurez une énorme hashmap, mais au moins palindrome pour disons que 10x10 paires prendront O (1), donc vérifier si une chaîne de 1000 est un palindrome prendra 100 consultations au lieu de 500 compare. Il est encore O (N), bien que ...

Answer 2

Il n'y a pas, sauf si vous faites une correspondance floue. Ce qui est ce qu'ils font probablement dans l'ADN (j'ai fait EST en recherchant dans l'ADN avec smith-waterman, mais cela est évidemment beaucoup plus difficile que de faire correspondre un palindrome ou un complément inverse dans une séquence).

Answer 3

Évidemment, vous n'allez pas pouvoir aller mieux que l'efficacité asymptotique O (n), puisque chaque caractère doit être examiné au moins une fois. Vous pouvez obtenir de meilleures constantes multiplicatives, cependant.

Pour un seul thread, vous pouvez obtenir une accélération en utilisant l'assemblage. Vous pouvez également faire mieux en examinant les données en morceaux plus gros qu'un octet à la fois, mais cela peut être difficile en raison de considérations d'alignement. Vous ferez encore mieux d'utiliser SIMD, si vous pouvez examiner des morceaux de 16 octets maximum à la fois.

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

Answer 4

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

Le pararellisme pourrait aider, mais il ne changerait pas le rang de l'algorithme de la classe Oh parce qu'il équivaut à l'exécuter sur une machine plus rapide.

Answer 5

Avec Python, le code court peut être plus rapide car il met la charge dans les entrailles de la machine virtuelle plus rapide (Et il y a toute la cache et d'autres choses)

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

Answer 6

Une autre variante de votre deuxième fonction. Nous n'avons pas besoin d'un contrôle égal aux parties droites des chaînes normales et inverses.

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

Answer 7

comparaison du centre est toujours beaucoup plus efficace puisque vous pouvez écoper tôt un échec mais il alwo vous permet de faire des recherches palindrome plus vite max, peu importe si vous cherchez le rayon maximal tout ou non - palindromes de recouvrement.

La seule vraie paralellisation est si vous avez plusieurs chaînes indépendantes à traiter. Diviser en morceaux va perdre beaucoup de travail pour chaque miss et il y a toujours beaucoup plus d'échecs que de coups.

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 la table/carte. Si vous vérifiez et trouvez l'élément qui est déjà dans la table, 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)"); 
     }