algorithm - sinonimo - Eficiencia de detección de Palindrome

palindromo sinonimo

Question

Sentí curiosidad por el percance de la entrevista de Jon Limjap y comencé a buscar formas eficientes de detectar el palíndromo. Comprobé las respuestas de golf palídrico y me parece que en las respuestas solo hay dos algoritmos, invirtiendo la secuencia y comprobando desde la cola y la cabeza.

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]

Creo que ninguno de estos métodos se usa en la detección de palíndromes exactos en grandes secuencias de ADN. Miré un poco y no encontré ningún artículo gratuito sobre la manera ultraeficiente para esto.

Una buena forma podría ser paralelizar la primera versión en un enfoque de dividir y vencer, asignando un par de arreglos de caracteres 1..n y longitud-1-n..length-1 a cada hilo o procesador.

¿Cuál sería una mejor manera?

¿Conoce alguna?

Answer 1

Ambos están en O (N), así que no creo que haya ningún problema de eficiencia particular con ninguna de estas soluciones. Tal vez no soy lo suficientemente creativo pero no veo cómo sería posible comparar N elementos en menos de N pasos, por lo que algo como O (log N) definitivamente no es posible en mi humilde opinión.

El pararellismo podría ayudar, pero aún no cambiaría el rango de Oh del algoritmo, ya que es equivalente a ejecutarlo en una máquina más rápida.

Answer 2

Dado un solo palíndromo, tendrá que hacerlo en O (N), sí. Puede obtener más eficiencia con multiprocesadores dividiendo la cadena como dijo.

Ahora diga que quiere hacer una coincidencia exacta de ADN. Estas cadenas tienen miles de caracteres de largo, y son muy repetitivas. Esto nos da la oportunidad de optimizar.

Supongamos que divide una cadena larga de 1000 caracteres en 5 pares de 100.100. El código se verá así:

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

etc ... La primera vez que haga estas coincidencias, tendrá que procesarlas. Sin embargo, puede agregar todos los resultados que haya realizado en una tabla de asignación de tabla hash a booleanos:

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

etc ... esto tomará demasiada memoria, sin embargo. Para pares de 100.100, el mapa hash tendrá 2 * 4 ^ 100 elementos. Digamos que solo almacena dos hashes de cadenas de 32 bits como clave, necesitará algo así como 10 ^ 55 megabytes, lo cual es ridículo.

Tal vez si usa cadenas más pequeñas, el problema puede ser manejable. Entonces tendrás un hashmap enorme, pero al menos palindrome, digamos que 10x10 pares tomarán O (1), por lo que si compruebas si una cadena 1000 es un palíndromo necesitarás 100 búsquedas en lugar de 500 búsquedas. Todavía es O (N), aunque ...

Answer 3

No lo hay, a menos que haga un partido difuso. Que es lo que probablemente hacen en el ADN (he hecho EST buscando en el ADN con smith-waterman, pero obviamente es mucho más difícil que encontrar un palíndromo o un complemento inverso en una secuencia).

Answer 4

Obviamente, no podrá obtener una eficacia asintótica superior a O (n), ya que cada personaje debe examinarse al menos una vez. Sin embargo, puedes obtener mejores constantes multiplicativas.

Para un único hilo, puede obtener una aceleración usando el ensamblaje. También puede hacerlo mejor examinando datos en fragmentos más grandes que un byte a la vez, pero esto puede ser complicado debido a consideraciones de alineación. Hará aún mejor utilizar SIMD, si puede examinar trozos de hasta 16 bytes a la vez.

Si quisieras paralelizarlo, podrías dividir la cuerda en N pedazos, y hacer que el procesador compare el segmento [i*n/2, (i+1)*N/2) con el segmento [L-(i+1)*N/2, Li*N/2) .

Answer 5

Otra variante de tu segunda función. No necesitamos verificación igual a las partes correctas de las cadenas normales e inversas.

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

Answer 6

Con Python, el código corto puede ser más rápido ya que coloca la carga en el interior más rápido de la máquina virtual (y está toda la memoria caché y otras cosas similares)

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

Answer 7

Comparar desde el centro siempre es mucho más eficiente, ya que puedes rescatar temprano en una falla, pero también te permite hacer búsquedas de palíndromo máximo más rápidas, independientemente de si buscas el radio máximo o todos los palíndromos que no se superponen.

La única paralelización real es si tiene múltiples cadenas independientes para procesar. Dividirse en pedazos desperdiciará mucho trabajo por cada falla y siempre hay más errores que éxitos.

Answer 8

Puede usar una tabla hash para poner el carácter y tener una variable de contador cuyo valor aumenta cada vez que encuentra un elemento que no está en la tabla / mapa. Si comprueba y encuentra el elemento que ya está en la tabla, disminuya el recuento.

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