पालिंड्रोम पहचान दक्षता

Question

मुझे Jon Limjap's interview mishap द्वारा उत्सुकता मिली और पालिंड्रोम पहचान करने के कुशल तरीकों की तलाश शुरू कर दी। मैंने palindrome golf उत्तरों की जांच की और मुझे लगता है कि उत्तर में केवल दो एल्गोरिदम हैं, स्ट्रिंग को उलटकर पूंछ और सिर से जांचना।

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..एन और लम्बाई -1-एन .. लम्बाई -1 की एक जोड़ी असाइन कर सकता है।

बेहतर तरीका क्या होगा?

क्या आप किसी को जानते हैं?

Answer 1

केवल एक पालिंड्रोम देखते हुए, आपको इसे ओ (एन), हाँ में करना होगा। जैसा कि आपने कहा था स्ट्रिंग को विभाजित करके आप बहु-प्रोसेसर के साथ अधिक दक्षता प्राप्त कर सकते हैं।

अब कहें कि आप सटीक डीएनए मिलान करना चाहते हैं। ये तार हजारों वर्ण लंबे हैं, और वे बहुत दोहराए गए हैं। यह हमें अनुकूलित करने का अवसर देता है।

कहें कि आप 1000-चार लंबी स्ट्रिंग को 100,100 के 5 जोड़े में विभाजित करते हैं। कोड इस तरह दिखेगा:

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

आदि ... पहली बार जब आप इन मैचों को करते हैं, तो आपको उन्हें संसाधित करना होगा। हालांकि, अगर आप आप बूलियन्स को एक hashtable मानचित्रण जोड़े में किया है सभी परिणाम जोड़ सकते हैं:

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

आदि ... इस तरह से बहुत अधिक स्मृति, हालांकि ले जाएगा।100,100 के जोड़े के लिए, हैश मानचित्र में 2 * 4^100 तत्व होंगे। कहें कि आप कुंजी के रूप में स्ट्रिंग के दो 32-बिट हैंश स्टोर करते हैं, आपको 10^55 मेगाबाइट्स की तरह कुछ चाहिए, जो हास्यास्पद है।

शायद यदि आप छोटे तारों का उपयोग करते हैं, तो समस्या ट्रैक्टेबल हो सकती है। फिर आपके पास एक बड़ा हैशप होगा, लेकिन कम से कम पालिंड्रोम कहें कि 10x10 जोड़े ओ (1) लेंगे, इसलिए जांच करें कि 1000 स्ट्रिंग एक पालिंड्रोम 500 तुलनाओं के बजाय 100 लुकअप लेगा। यह अभी भी हे (एन), हालांकि है ...

Answer 2

ऐसा नहीं है, जब तक कि आप एक अस्पष्ट मैच न करें। डीएनए में वे शायद यही करते हैं (मैंने ईएसटी को को स्मिथ-वॉटरमैन के साथ डीएनए में खोजा है, लेकिन यह स्पष्ट रूप से एक पहेली में पैलिंड्रोम या रिवर्स-पूरक के लिए मिलान करना बहुत मुश्किल है)।

Answer 3

जाहिर है, आप ओ (एन) एसिम्प्टोटिक दक्षता से बेहतर होने में सक्षम नहीं होंगे, क्योंकि प्रत्येक चरित्र को कम से कम एक बार जांच की जानी चाहिए। हालांकि, आप बेहतर गुणक स्थिरांक प्राप्त कर सकते हैं।

एक ही थ्रेड के लिए, आप असेंबली का उपयोग करके एक गति प्राप्त कर सकते हैं। आप एक समय में एक बाइट से बड़े हिस्से में डेटा की जांच करके बेहतर कर सकते हैं, लेकिन यह संरेखण विचारों के कारण मुश्किल हो सकता है। आप सिमड का उपयोग करने के लिए और भी बेहतर करेंगे, अगर आप एक समय में 16 बाइट्स के रूप में बड़े हिस्से की जांच कर सकते हैं।

यदि आप इसे समानांतर बनाना चाहते हैं, तो आप स्ट्रिंग को एन टुकड़ों में विभाजित कर सकते हैं, और प्रोसेसर i सेगमेंट [i*n/2, (i+1)*N/2) सेगमेंट [L-(i+1)*N/2, L-i*N/2) सेगमेंट की तुलना करें।

Answer 4

वे दोनों ओ (एन) में हैं इसलिए मुझे नहीं लगता कि इनमें से किसी भी समाधान के साथ कोई विशेष दक्षता समस्या है। हो सकता है कि मैं पर्याप्त रचनात्मक नहीं हूं लेकिन मैं नहीं देख सकता कि एन तत्वों से कम एन तत्वों की तुलना करना कैसे संभव होगा, इसलिए ओ (लॉग एन) जैसी कुछ निश्चित रूप से आईएमएचओ संभव नहीं है।

पैरालेलिज्म मदद कर सकता है, लेकिन यह अभी भी एल्गोरिदम के बड़े-ओह रैंक को नहीं बदलेगा क्योंकि यह इसे तेज मशीन पर चलाने के बराबर है।

Answer 5

अजगर के साथ

, लघु कोड तेजी से हो सकता है, क्योंकि यह वी एम के तेजी से आंतरिक में बोझ डालता है (और वहाँ पूरे कैश और अन्य ऐसी बातें है)

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

Answer 6

आपके दूसरे फ़ंक्शन का एक और संस्करण। हमें सामान्य और रिवर्स स्ट्रिंग के दाहिने हिस्सों के बराबर चेक की आवश्यकता नहीं है।

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

Answer 7

केंद्र से तुलना करना हमेशा बहुत अधिक कुशल है, क्योंकि आप एक याद आती है पर जल्दी जमानत सकता है लेकिन यह alwo आप तेजी से अधिकतम विलोमपद खोज करने के लिए, की परवाह किए बिना अनुमति देता है कि क्या आप अधिक से अधिक त्रिज्या या सभी गैर की तलाश में हैं - ओवरलैपिंग पालिंड्रोम।

एकमात्र वास्तविक पैरालाइलाइजेशन यह है कि यदि आपके पास प्रक्रिया करने के लिए कई स्वतंत्र तार हैं। टुकड़ों में विभाजित करने से हर मिस के लिए बहुत सारे काम बर्बाद हो जाएंगे और हिट से हमेशा ज्यादा याद आती है।

Answer 8

आप चरित्र को रखने और काउंटर वैरिएबल रखने के लिए हैशटेबल का उपयोग कर सकते हैं जिसका मूल्य हर बार जब आप तालिका/मानचित्र में कोई तत्व नहीं पाते हैं। यदि आप तालिका में पहले से मौजूद तत्व को चेक और ढूंढते हैं तो गिनती कम हो जाती है।

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