回文检测效率

如果只有一个回文,你必须在o(n)中做,是的。如您所说,通过拆分字符串,多处理器可以获得更高的效率。

现在假设你想做精确的DNA匹配。这些字符串有数千个字符长,它们是非常重复的。这给了我们优化的机会。

假设您将1000个字符长的字符串拆分为5对100100。代码如下:

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

等。。。第一次进行这些匹配时,必须对它们进行处理。但是,您可以将所做的所有结果添加到哈希表映射对中,以映射布尔值:

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

等。。。不过,这会占用太多的内存。对于100100对,哈希图将有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)渐近效率更好的结果。不过,你可以得到更好的乘法常数。

对于单个线程,可以使用assembly加速。通过一次检查大于一个字节的数据块,您也可以做得更好,但由于对齐方面的考虑,这可能很难做到。如果一次可以检查16个字节的块,那么使用simd会更好。

如果你想把它并行化,你可以把这个字符串分成N段,并有处理器。 i 比较该段 [i*n/2, (i+1)*N/2) 与细分市场 [L-(i+1)*N/2, L-i*N/2) .

没有,除非你做一个模糊匹配。这就是他们在DNA中可能做的(我做过EST 搜索 在与SmithWaterman的DNA中,这显然比在序列中匹配回文或反向补码要困难得多。

它们都在O(N)中,所以我认为这些解决方案中没有任何特别的效率问题。也许我没有足够的创造力,但我不知道如何在少于n步的时间内比较n个元素,所以像o(log n)这样的东西绝对不可能imho。

pararelism可能会有所帮助,但它仍然不会改变算法的大oh等级,因为它相当于在更快的机器上运行它。

从中间比较总是更有效的,因为你可以在错过的时候提前退出,但它总是允许你做更快的最大回文搜索,无论你是在寻找最大半径还是所有不重叠的回文。

唯一真正的平行化是如果有多个独立的字符串要处理。每一次失误都会浪费大量的工作,而且总是会有比命中更多的失误。

使用python,短代码可以更快,因为它将负载放入了更快的vm内部(还有整个缓存和其他类似的东西)。

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

您可以使用hashtable来放置字符,并有一个计数器变量,每当您发现不在表/映射中的元素时,该变量的值都会增加。如果您检查并查找表中已经存在的元素,则减少计数。

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) 这也可以使用线程来完成,但是计算会变得混乱,最好避免它。这不测试特殊字符,并且区分大小写。我有这样做的代码,但是可以修改这个代码来轻松地处理它。