Palindrome efficacité de détection

Je suis curieuse par Jon Limjap l'interview de mésaventure et a commencé à chercher des moyens efficaces pour faire palindrome de détection. J'ai vérifié le palindrome de golf réponses et il me semble que dans les réponses sont deux algorithmes seulement, l'inversion de la chaîne et de la vérification 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 sont utilisées dans la détection exacte des palindromes dans d'énormes séquences d'ADN. J'ai regardé un peu autour de lui et n'ai pas trouvé libres d'article sur ce qu'est un ultra efficace pour ce qui pourrait être.

Une bonne façon peut-être de la parallélisation de la première version dans un divide-and-conquer approche, l'affectation d'une paire de tableaux de char 1..n et la longueur-1-n..longueur-1 pour chaque thread ou le processeur.

Ce serait une meilleure façon?

Savez-vous tout?

source d'informationauteur Vinko Vrsalovic

  1. 5

    Donné qu'un palindrome, vous devrez le faire en O(N), oui. Vous pouvez obtenir plus d'efficacité avec des multi-processeurs par fractionnement de la chaîne, comme vous l'avez dit.

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

    Vous dire diviser un 1000-char à longue chaîne dans 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 matchs, vous aurez à traiter. Toutefois, vous pouvez ajouter tous les résultats que vous avez fait dans une table de hachage de la cartographie des paires de booléens:

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

    etc... cela va prendre beaucoup trop de mémoire. Pour les paires de 100,100, le hachage carte 2*4^de 100 éléments. Dire que vous gardez uniquement les deux 32-bit les hachages des chaînes comme la clé, vous aurez besoin de quelque chose comme 10^55 méga-octets, ce qui est ridicule.

    Peut-être que si vous utilisez de plus petites chaînes, le problème peut être traitable. Ensuite, vous aurez un énorme table de hachage, mais au moins palindrome, disons 10x10 paires prendra O(1), afin de vérifier si un 1000 chaîne est un palindrome prendra 100 recherches au lieu de 500 compare. Il est toujours en O(N), bien que...

  2. 2

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

    Pour un thread unique, vous pouvez obtenir une accélération à l'aide de l'assemblée. Vous pouvez aussi faire mieux en examinant les données en blocs plus gros qu'un octet à la fois, mais cela peut être difficile en raison de considérations d'alignement. Vous allez faire encore mieux à l'utilisation SIMD, si vous pouvez examiner des morceaux de 16 octets à la fois.

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

  3. 1

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

    Pararellism pourrait aider, mais il ne change pas le big-Oh rang de l'algorithme, car il est équivalent à l'exécution sur une machine plus rapide.

  4. 1

    Il n'y a pas, sauf si vous avez une correspondance floue. Qui est ce que probablement ils ne l'ADN (j'ai fait HNE recherche dans l'ADN avec smith-waterman, mais qui est évidemment beaucoup plus difficile alors d'appariement pour un palindrome ou d'inversion de complément dans une séquence).

  5. 1

    Une autre variante de la deuxième fonction. Nous n'avons pas besoin de vérifier égale du droit des parties de la normale et inverse les chaînes.

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

    Comparant à partir du centre est toujours beaucoup plus efficace puisque vous pouvez renflouer le début sur une miss mais il alwo vous permet de faire plus rapidement max palindrome de recherche, peu importe si vous êtes à la recherche pour le maximum de rayon et de tous les non-cumul des palindromes.

    La seule vraie paralellization est si vous avez de multiples indépendants des chaînes de processus. Diviser en morceaux de déchets beaucoup de travail pour chaque miss et il y a toujours beaucoup plus de justesse que les succès.

  7. 0

    Avec Python, le code court peut être plus rapide car il met la charge dans le plus rapide de l'intérieur de la VM (Et là est toute la mémoire cache et d'autres choses)

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

    Vous pouvez utiliser une table de hachage pour mettre le personnage et avoir une variable de compteur dont la valeur augmente à chaque fois que vous trouvez un élément non dans le tableau/la carte. Si u rechercher et de trouver de l'élément c'est déjà dans le tableau de diminuer le nombre de.

    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)");
        }