Skuteczność wykrywania palindromu

Question

Zaciekawił mnie Jon Limjap's interview mishap i zacząłem szukać skutecznych sposobów na wykrywanie palindromu. Sprawdziłem odpowiedzi palindrome golf i wydaje mi się, że w odpowiedziach są tylko dwa algorytmy, odwracając ciąg i sprawdzając od ogona i głowy.

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] 

Myślę, że żadna z tych metod nie jest używana do wykrywania dokładnych palindromów w ogromnych sekwencjach DNA. Rozejrzałem się trochę i nie znalazłem żadnego darmowego artykułu na temat tego, jaki może być ultra wydajny sposób.

Dobrym sposobem może być zrównoleglenie pierwszej wersji w podejściu dziel i rządź, przypisując parę znaków z tablic 1..n i długość-1-n..length-1 do każdego wątku lub procesora.

Jaki byłby lepszy sposób?

Czy znasz jakieś?

Answer 1

Biorąc pod uwagę tylko jeden palindrom, musisz to zrobić w O (N), tak. Możesz uzyskać większą wydajność dzięki procesorom wieloprocesorowym, dzieląc łańcuch tak, jak powiedziałeś.

Teraz powiedz, że chcesz dokładnie dopasować DNA. Łańcuchy te mają tysiące znaków i są bardzo powtarzalne. Daje nam to możliwość optymalizacji.

Załóżmy, że dzielisz łańcuch o długości 1000 znaków na 5 par po 100,100. Kod będzie wyglądał następująco:

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

itp ... Po raz pierwszy te dopasowania będą musiały zostać przetworzone. Jednakże, można dodać wszystkie wyniki zrobiłeś w hashtable parami mapowania do wartości logicznych:

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

etc ... to zajmie zbyt dużo pamięci, choć.Dla par 100,100 mapa hash będzie miała 2 * 4^100 elementów. Powiedzmy, że jako klucz przechowujesz tylko 32-bitowe skróty ciągów, potrzebujesz czegoś w rodzaju 10^55 megabajtów, co jest śmieszne.

Może, jeśli używasz mniejszych ciągów, problem może być trudny. Będziesz miał ogromną mieszankę, ale przynajmniej palindrom, powiedzmy 10x10 par, zajmie O (1), więc sprawdzenie, czy 1000 łańcuchów jest palindromem, spowoduje 100 wyszukiwań zamiast 500 porównań. To wciąż O (N), choć ...

Answer 2

Nie ma, chyba że robisz rozmyte dopasowanie. Co prawdopodobnie robią w DNA (zrobiłem EST szukając w DNA z smith-watermanem, ale jest to oczywiście o wiele trudniejsze niż dopasowanie do palindromu lub dopełnienia wstecznego w sekwencji).

Answer 3

Oczywiście, nie da się osiągnąć lepszej skuteczności niż asymptotyczna (O), ponieważ każda postać musi zostać zbadana co najmniej raz. Możesz jednak uzyskać lepsze stałe multiplikatywne.

Dla pojedynczego wątku można uzyskać przyspieszenie za pomocą złożenia. Można również zrobić lepiej, analizując dane w porcjach większych niż bajty w tym samym czasie, ale może to być trudne ze względu na kwestie wyrównania. Jeszcze lepiej użyjesz SIMD, jeśli możesz zbadać porcje o wielkości 16 bajtów na raz.

Jeśli chcesz zrównoleglić go, możesz podzielić ciąg na N części, a procesor i porównać segment [i*n/2, (i+1)*N/2) z segmentem [L-(i+1)*N/2, L-i*N/2).

Answer 4

Oba są w O (N), więc nie sądzę, że istnieje jakiś szczególny problem z wydajnością w przypadku któregokolwiek z tych rozwiązań. Może nie jestem wystarczająco kreatywny, ale nie widzę, jak byłoby możliwe porównywanie elementów N w mniej niż N krokach, więc coś takiego jak O (log N) zdecydowanie nie jest możliwe IMHO.

Pararellizm może pomóc, ale nadal nie zmieniłby rangi algorytmu big-Oh, ponieważ jest równoważny uruchomieniu go na szybszej maszynie.

Answer 5

z Pythona, krótki kod może być szybsze, ponieważ stawia obciążenie do szybszych wewnętrzne VM (i nie jest cały cache i inne takie rzeczy)

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

Answer 6

Kolejny wariant drugiej funkcji. Nie potrzebujemy sprawdzania równych prawych części normalnych i wstecznych ciągów.

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

Answer 7

Porównując od centrum zawsze jest dużo bardziej efektywne, ponieważ można wyskoczyć na początku miss ale ALWO pozwala wykonać szybciej max przeszukiwanie palindrom, niezależnie od tego, czy szukasz maksymalnego promienia lub wszystkich nie - nakładające się na siebie palindromy.

Jedyną prawdziwą paralelizacją jest, jeśli masz wiele niezależnych ciągów do przetworzenia. Podział na kawałki zmarnuje dużo pracy dla każdej miss i zawsze jest o wiele więcej błędów niż trafień.

Answer 8

Możesz użyć tablicy by umieścić znak i mieć zmienną licznika, której wartość zwiększa się za każdym razem, gdy znajdziesz element, który nie znajduje się w tabeli/mapie. Jeśli sprawdzisz i znajdziesz element, który już znajduje się w tabeli, zmniejszy liczbę.

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