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

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

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

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

isPal(w[0:100],w[-100:]) and isPal(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), хотя...

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

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

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

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

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

Нет, если только вы не сделаете нечеткое совпадение. Это то, что они, вероятно, делают в ДНК (я провел поиск EST в ДНК со Смитом-Уотерманом, но это, очевидно, намного сложнее, чем сопоставление палиндрома или обратного дополнения в последовательности).

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

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

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

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

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

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

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

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

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), это можно сделать и с использованием потоков, но вычисления становятся беспорядочными, лучше избегать этого. это не проверяет специальные символы и чувствительно к регистру. У меня есть код, который это делает, но этот код можно легко изменить, чтобы справиться с этим.