Hiệu suất phát hiện Palindrome

Question

Tôi đã tò mò theo số Jon Limjap's interview mishap và bắt đầu tìm kiếm các cách hiệu quả để phát hiện palindrome. Tôi đã kiểm tra các câu trả lời palindrome golf và có vẻ như với tôi rằng trong câu trả lời là hai thuật toán duy nhất, đảo ngược chuỗi và kiểm tra từ đuôi và đầu.

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] 

Tôi nghĩ rằng không có phương pháp nào trong số này được sử dụng để phát hiện chính xác palindromes trong chuỗi ADN lớn. Tôi nhìn xung quanh một chút và không tìm thấy bất kỳ bài viết miễn phí về những gì một cách cực kỳ hiệu quả cho điều này có thể được.

Cách tốt nhất có thể là song song phiên bản đầu tiên theo cách tiếp cận phân chia và chinh phục, gán một cặp mảng char 1..n và length-1-n..length-1 cho mỗi luồng hoặc bộ xử lý.

Điều gì sẽ là cách tốt hơn?

Bạn có biết không?

Answer 1

Chỉ cho một palindrome, bạn sẽ phải thực hiện nó trong O (N), vâng. Bạn có thể nhận được hiệu quả hơn với đa bộ vi xử lý bằng cách tách chuỗi như bạn đã nói.

Bây giờ, bạn muốn thực hiện đối sánh DNA chính xác. Những chuỗi này dài hàng nghìn ký tự và chúng rất lặp đi lặp lại. Điều này cho chúng ta cơ hội để tối ưu hóa.

Giả sử bạn chia chuỗi dài 1000 ký tự thành 5 cặp 100.100. Mã sẽ trông giống như sau:

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

vv ... Lần đầu tiên bạn thực hiện các kết quả phù hợp này, bạn sẽ phải xử lý chúng. Tuy nhiên, bạn có thể thêm tất cả các kết quả mà bạn đã thực hiện vào một cặp ánh xạ có thể bắt buộc thành booleans:

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

v.v ... sẽ mất quá nhiều bộ nhớ.Đối với các cặp 100.100, bản đồ băm sẽ có 2 * 4^100 phần tử. Giả sử bạn chỉ lưu trữ hai chuỗi 32 bit là khóa, bạn sẽ cần khoảng 10^55 megabyte, điều đó thật lố bịch.

Có thể nếu bạn sử dụng các chuỗi nhỏ hơn, vấn đề có thể có thể thực hiện được. Sau đó, bạn sẽ có một hashmap rất lớn, nhưng ít nhất palindrome cho chúng ta nói rằng 10x10 cặp sẽ mất O (1), vì vậy kiểm tra xem một chuỗi 1000 là palindrome sẽ mất 100 tra cứu thay vì 500 so sánh. Nó vẫn còn O (N), mặc dù ...

Answer 2

Không có, trừ khi bạn thực hiện một kết quả mờ. Đó là những gì họ có thể làm trong DNA (tôi đã thực hiện EST tìm kiếm trong DNA với smith-waterman, nhưng điều đó rõ ràng là khó khăn hơn nhiều sau đó phù hợp cho palindrome hoặc bổ sung đảo ngược theo trình tự).

Answer 3

Rõ ràng, bạn sẽ không thể đạt được hiệu quả tiệm cận tốt hơn O (n) vì mỗi ký tự phải được kiểm tra ít nhất một lần. Tuy nhiên, bạn có thể nhận được các hằng số nhân tốt hơn.

Đối với một chuỗi đơn, bạn có thể tăng tốc sử dụng lắp ráp. Bạn cũng có thể làm tốt hơn bằng cách kiểm tra dữ liệu theo khối lớn hơn một byte tại một thời điểm, nhưng điều này có thể khó khăn do cân nhắc căn chỉnh. Bạn sẽ làm tốt hơn để sử dụng SIMD, nếu bạn có thể kiểm tra các khối lớn đến 16 byte tại một thời điểm.

Nếu bạn muốn song song nó, bạn có thể chia chuỗi thành các phần N và có bộ xử lý i so sánh phân đoạn [i*n/2, (i+1)*N/2) với đoạn [L-(i+1)*N/2, L-i*N/2).

Answer 4

Cả hai đều ở dạng O (N) vì vậy tôi không nghĩ rằng có bất kỳ vấn đề hiệu quả cụ thể nào với bất kỳ giải pháp nào trong số này. Có lẽ tôi không sáng tạo đủ nhưng tôi không thể thấy làm thế nào nó có thể so sánh N yếu tố trong ít hơn N bước, vì vậy một cái gì đó như O (log N) chắc chắn là không thể IMHO.

Pararellism có thể hữu ích, nhưng nó vẫn không thay đổi thứ hạng lớn của thuật toán vì nó tương đương với việc chạy nó trên một máy nhanh hơn.

Answer 5

Với Python, mã ngắn có thể nhanh hơn vì nó đặt tải trọng hơn vào bên nhanh hơn của VM (Và có cả bộ nhớ cache và những thứ khác như vậy)

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

Answer 6

Một biến thể khác của hàm thứ hai của bạn. Chúng ta không cần kiểm tra bằng các phần bên phải của chuỗi bình thường và ngược lại.

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

Answer 7

So sánh từ trung tâm luôn luôn là hiệu quả hơn vì bạn có thể giải cứu sớm bỏ lỡ nhưng nó alwo cho phép bạn làm tìm kiếm palindrome max nhanh hơn, bất kể bạn đang tìm kiếm bán kính tối đa hoặc tất cả không -nhập lại palindromes.

Sự thực hiện song song duy nhất là nếu bạn có nhiều chuỗi độc lập để xử lý. Chia thành nhiều phần sẽ lãng phí rất nhiều công việc cho mỗi lần bỏ lỡ và luôn có nhiều lỗi hơn số lần truy cập.

Answer 8

Bạn có thể sử dụng thẻ bắt buộc phải đặt ký tự và có biến số lượt truy cập có giá trị tăng mỗi khi bạn tìm thấy phần tử không có trong bảng/bản đồ. Nếu bạn kiểm tra và tìm các phần tử đã có trong bảng, hãy giảm số lượng.

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