Эффективность обнаружения палиндрома

Question

Мне стало любопытно неудача с интервью Джона Лимджапа и я начал искать эффективные способы обнаружения палиндрома. Я проверил ответы палиндром гольф , и мне кажется, что в ответах есть только два алгоритма: перевернуть строку и проверить хвост и голову.

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]

Я думаю, что ни один из этих методов не используется для обнаружения точных палиндромов в огромных последовательностях ДНК. Я немного осмотрелся и не нашел бесплатной статьи о том, каким может быть ультра-эффективный способ для этого.

Хорошим способом может быть распараллеливание первой версии в подходе «разделяй и властвуй», назначая пару массивов символов 1..n и length-1-n..length-1 для каждого потока или процессора.

Что было бы лучше?

Вы знаете кого-нибудь?

Answer 1

Учитывая только один палиндром, вам придется сделать это за O (N), да. Вы можете добиться большей эффективности с несколькими процессорами, разделив строку, как вы сказали.

Теперь скажите, что хотите точно сопоставить ДНК. Эти строки длиной в тысячи символов, и они очень повторяются. Это дает нам возможность оптимизировать.

Допустим, вы разбили строку длиной 1000 символов на 5 пар по 100 100. Код будет выглядеть так:

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

и т. Д. В первый раз, когда вы делаете эти совпадения, вам нужно будет их обработать. Тем не менее, вы можете добавить все результаты, которые вы сделали, в пары сопоставления хеш-таблицы для логических значений:

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

и т.д ... это займет слишком много памяти. Для пар 100,100 хэш-карта будет иметь 2 * 4 ^ 100 элементов. Скажем, вы храните в качестве ключа только два 32-битных хэша строк, вам потребуется что-то вроде 10 ^ 55 мегабайт, что смешно.

Может быть, если вы используете меньшие строки, проблема может быть устранена. Тогда у вас будет огромная хэш-карта, но, по крайней мере, палиндром, скажем, для пар 10x10 потребуется O (1), поэтому для проверки, является ли строка 1000 палиндромом, потребуется 100 поисков вместо 500 сравнений. Это все еще O (N), хотя ...

Answer 2

Еще один вариант вашей второй функции. Нам не нужно проверять равенство правых частей нормальной и обратной строк.

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

Answer 3

Очевидно, что вам не удастся добиться лучшей асимптотической эффективности, чем O (n), поскольку каждый символ должен быть проверен хотя бы один раз. Вы можете получить лучшие мультипликативные константы.

Для одного потока, вы можете получить ускорение с помощью сборки. Вы также можете добиться большего успеха, рассматривая данные порциями размером больше байта за раз, но это может быть непросто из-за соображений выравнивания. Вы сможете использовать SIMD еще лучше, если сможете одновременно анализировать блоки размером до 16 байт.

Если вы хотите распараллелить ее, вы можете разделить строку на N частей, и процессор i сравнит сегмент [i*n/2, (i+1)*N/2) с сегментом [L-(i+1)*N/2, L-i*N/2).

Answer 4

Нет, если вы не делаете нечеткий матч. Это то, что они, вероятно, делают в ДНК (я сделал EST , ища в ДНК с кузнецом, но это, очевидно, намного сложнее, чем поиск палиндрома или обратного комплемента в последовательности). *

Answer 5

Они оба в O (N), поэтому я не думаю, что есть какие-либо конкретные проблемы с эффективностью любого из этих решений. Может быть, я недостаточно креативен, но не понимаю, как можно было бы сравнить N элементов менее чем за N шагов, поэтому что-то вроде O (log N) определенно невозможно, ИМХО.

Парарелизм может помочь, но он все равно не изменит ранг алгоритма с большим значением Oh, поскольку он эквивалентен запуску его на более быстрой машине.

Answer 6

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 
    }
}

хотя мы делаем n / 2 вычислений, это все равно O (n) это может быть сделано также с использованием потоков, но вычисления становятся запутанными, лучше всего избегать этого. это не проверяет специальные символы и учитывает регистр. У меня есть код, который делает это, но этот код может быть изменен, чтобы справиться с этим легко.

Answer 7

Вы можете использовать хеш-таблицу для размещения символа и иметь переменную-счетчик, значение которой увеличивается каждый раз, когда вы находите элемент, отсутствующий в таблице / карте. Если вы проверите и найдете элемент, который уже есть в таблице, уменьшите счет.

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 8

Сравнение по центру всегда намного эффективнее, так как вы можете выручить рано при промахе, но это также позволяет быстрее выполнять поиск максимального палиндрома, независимо от того, ищете ли вы максимальный радиус или все непересекающиеся палиндромы.

Единственная реальная паралеллизация - это если у вас есть несколько независимых строк для обработки. Разбиение на куски будет тратить много работы на каждую промах, а промахов всегда намного больше, чем попаданий.

Answer 9

С Python короткий код может быть быстрее, поскольку он помещает нагрузку на более быстрые внутренние компоненты виртуальной машины (и есть весь кэш и другие подобные вещи)

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