एआरए: एक सीधी रेखा पर अधिकतम अंक खोजने के लिए एल्गोरिथ्म

हाल ही में, मुझे साक्षात्कार के लिए एक क्लासिक समस्या आई: एक सीधी रेखा (एक विमान, पूर्णांक निर्देशांक) पर खड़े होने वाले अधिकतम अंकों की खोज करना। संपूर्ण खोज का विचार तुरंत मेरे दिमाग में आया, जिसमें O (n ^ 2) में स्पष्ट समय की जटिलता है, लेकिन यह मुझे प्रतीत हुआ कि O में कुछ और होना चाहिए, कम से कम कुछ विकल्प तो (n * log (n)) । आधे घंटे के बाद, कुछ बेहतर भी मिला!



_{इनपुट-आउटपुट के उदाहरणों के साथ समस्या का अधिक विस्तृत विवरण GeeksForGeeks और LeetCode पर है}

पहले मैंने देखा कि आप केवल क्षैतिज या ऊर्ध्वाधर लाइनों के लिए समस्या को हल कर सकते हैं, शब्दकोश में प्रत्येक बिंदु के X / Y को जोड़ सकते हैं। और दूसरी रेखाओं में क्या अंतर है? बस एक ढलान? .. लेकिन यह ठीक है!

इस प्रकार, मैंने तय किया कि उन्हें घुमाकर अंक की पूरी सूची में कई बार जाना संभव था। और O (n) में समाधान प्राप्त होता है! हालांकि एक बड़े गुणांक के साथ। मैं वास्तव में आशा करता हूं कि मैंने साइकिल का आविष्कार नहीं किया है :)

# ***  *** #   #    = 180/ROT_COUNT  # #      12, #  180*4    (6% ), #  180*20   (0% ). # ó    . #     - . ROT_COUNT = 180*10 #  #        , #       1 / MULT_COEF. #    4  . #   MULT_COEF   ROT_COUNT. # ó    - . #     - . MULT_COEF = 2 ** 3 angles = list(map(lambda x: x*180.0/ROT_COUNT, range(ROT_COUNT))) def mnp_rotated(points, angle): """Returns Maximum Number of Points on the same line with given rotation""" #   rad = math.radians(angle) co = math.cos(rad) si = math.sin(rad) #      counts = {} for pair in points: #    nx = pair[0]*co - pair[1]*si #       , #      #       #      nx = int(nx * MULT_COEF) #   if nx in counts: counts[nx] += 1 else: counts[nx] = 1 #    return max(counts.values()) def mnp(points): """Returns Maximum Number of Points on the same line""" res = 0 best_angle = 0 #      for i in angles: current = mnp_rotated(points, i) #  ,     if current > res: res = current best_angle = i return res 

कल्पना, यह कुछ इस तरह दिखता है:
_{मेरा पहला घर-निर्मित GIF, कृपया डांटे नहीं :)}



यह ध्यान रखना दिलचस्प है कि बाद की विस्तृत खोज के कार्यान्वयन ने कोड की अधिक पंक्तियों को ले लिया।

मेरे घूर्णी एल्गोरिथ्म के रनटाइम के माप के साथ ग्राफ और अंकों की संख्या के आधार पर पूर्ण गणना है।


लगभग 150 अंक समय में रैखिक जटिलता का लाभ दिखाते हैं (ऊपर कोड में उपयोग किए गए गुणांक के साथ)। नतीजतन, इस एल्गोरिथ्म में निम्नलिखित नुकसान हैं:

• सटीकता निरपेक्ष नहीं है।
• अंकों के छोटे सेट पर रनटाइम लंबा है।
  _{सामान्य तौर पर, यह गुणांक के एक सक्षम चयन द्वारा आसानी से ठीक किया जाता है: सरल सेटों के लिए, 2000 के बजाय ROT_COUNT = 36 काफी पर्याप्त है, जो कोड को 50+ बार गति देता है।}

और ऐसे फायदे:

• यह आंशिक रूप से निर्देशांक के साथ शांति से काम करता है।
• समय जटिलता रैखिक है, जो बड़े डेटा सेटों पर ध्यान देने योग्य है।

माप के साथ एक तालिका यहां उपलब्ध है । दोनों एल्गोरिदम और विभिन्न चेक के साथ परियोजना का संपूर्ण स्रोत कोड GitHub पर है ।

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