एक उदाहरण का उपयोग करके द्वि-आयामी सरणी, या कम्प्यूटेशनल जटिलता में दोहराव के लिए खोजें

शुभ दिन, प्रिय प्रभामंडल।

जब मैंने अपने दूसरे या तीसरे वर्ष में संस्थान में अध्ययन किया (जो सामान्य तौर पर, बहुत पहले नहीं था), मेरे पास, दूसरों के बीच, एक विषय "एल्गोरिदम और डेटा स्ट्रक्चर्स" था। हालांकि, उन्होंने न केवल एल्गोरिदम और संरचनाओं के बारे में बताया, बल्कि "कम्प्यूटेशनल जटिलता" जैसी अवधारणा के बारे में भी बताया। मैं मानता हूँ, तब यह मुझे बहुत पसंद नहीं आया।

"निश्चित रूप से स्थानिक और लौकिक जटिलता के लिए एल्गोरिथ्म के अध्ययन के साथ परेशान करना आवश्यक है, जब या तो बहुत उच्च-प्रदर्शन / उच्च-लोडेड सिस्टम विकसित कर रहा हो, या जब वास्तव में बड़ी मात्रा में डेटा के साथ काम कर रहा हो," - लगभग ऐसे विचारों ने मुझे दौरा किया (और, शायद, न केवल मुझे)।

हालाँकि, हाल ही में मुझे एक आसान काम के कारण अपने दिमाग को बदलना पड़ा।

कार्य इस प्रकार था: कुछ (ज्यादातर संख्यात्मक) डेटा के साथ एक्सेल टेबल थे। ये डेटा, बिना विवरण में जाने, उपप्रणालियों में उपयोग किए जाने वाले पहचानकर्ता थे। तालिकाओं में दोहराए जाने वाले मूल्यों को खोजने के लिए आवश्यक था, और, विभिन्न कारकों के आधार पर, तय करें कि उनके साथ क्या करना है। इस बिंदु पर, आपके पास पहले से ही एक प्रश्न हो सकता है: "यह स्वचालित रूप से क्यों नहीं?" वास्तव में, वे डेटासेट जिनके साथ स्वचालित प्रणाली सामना नहीं कर सकती थी, और जिसके लिए मानव हस्तक्षेप की आवश्यकता थी, तालिकाओं में गिर गए।
स्वाभाविक रूप से, बड़ी मात्रा में डेटा के माध्यम से मैन्युअल रूप से सॉर्ट करना (औसतन 5-10 कॉलम और प्रति दस्तावेज़ 1000 लाइनें) एक कृतघ्न कार्य है, इसलिए मैंने पुनरावृत्ति खोजने के मामले में प्रक्रिया को थोड़ा सरल बनाने का फैसला किया।
चूंकि सख्त संगठन नियमों के कारण सी में एक अलग उपयोगिता लिखना असंभव था, इसलिए मुझे वीबीए (जो मुझे बिल्कुल नहीं पता था) के बारे में थोड़ा पढ़ना पड़ा और वीबीए मैक्रो के रूप में एक समाधान के साथ आया।

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

सरल उपाय

सबसे सरल, सबसे प्रत्यक्ष और प्राथमिक समाधान जो दिमाग में आता है वह सिर्फ एक बिंदु-दर-बिंदु तुलना है। VBA पर, यह कुछ इस तरह दिखता है:

Sub FindMatches() Dim sCol, sRow, cCol, cRow As Integer For sCol = 1 To 10 For sRow = 1 To 10 For cCol = sCol + 1 To 10 For cRow = 1 To 10 If Cells(sRow, sCol) = Cells(cRow, cCol) Then If Cells(sRow, sCol).Font.Color = RGB(0, 0, 0) Then Cells(sRow, sCol).Font.Color = RGB(0, 150, 0) End If Cells(cRow, cCol).Font.Color = RGB(150, 0, 0) End If Next cRow Next cCol Next sRow Next sCol End Sub 

इस प्रकार, हम तालिका के प्रत्येक सेल को लेते हैं, और इसके बाद होने वाली सभी कोशिकाओं के साथ तुलना करते हैं (यह ध्यान देने योग्य है कि उस कॉलम में जहां तत्व का प्रवेश पहली बार होता है, कोई पुनरावृत्ति नहीं हो सकती है, इसलिए हम अगले कॉलम से तुलना शुरू करते हैं), और अगर हमें संयोग मिलते हैं, तो उन्हें लाल रंग में रंगो। क्या यह सुविधाजनक है? यह है। हालांकि, यह वह जगह है जहां कम्प्यूटेशनल जटिलता से दांतों का पता चलता है। यहाँ समय है कि यह मेरी नहीं तो कमजोर मशीन पर कार्रवाई करने के लिए है:

• 100 सेल (10x10) - 70 मिलीसेकंड
• 200 कोशिकाएं (10x20) - 240 मिलीसेकंड
• 400 कोशिकाएं (10x40) - 920 मिलीसेकंड
• 2000 सेल (20x100) - 23535 मिलीसेकंड

सामान्य तौर पर, हम यह कह सकते हैं कि इनपुट n समय पर तत्वों की संख्या में वृद्धि के साथ, ऑपरेटिंग समय n ² गुना बढ़ जाएगा। बेशक, इस तरह का निर्णय मेरे लिए अस्वीकार्य था।

थोड़ा कम सरल उपाय

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

सामान्य रूप से संचालन की संख्या को कम करने के लिए, मैंने प्रत्येक अद्वितीय मान को एक अलग सरणी में लिखने का फैसला किया, और केवल इस तत्व के अद्वितीय तत्वों के साथ तुलना करें। यह कुछ इस तरह दिखता है:

 Sub FindMatches() Dim row As Integer //  Dim col As Integer //  Dim Values(5000, 5) As Integer //   Dim DistinctValues() As Integer //  Dim DistinctCount As Integer //   Dim i As Integer // Dim IsUnique As Boolean //  //        ReDim DistinctValues(0 To 0) DistinctCount = 0 //   Values   . For col = 1 To 5 For row = 1 To 5000 Values(row, col) = Cells(row, col) Next row Next col // . For col = 1 To 5 For row = 1 To 5000 //    Values  .            DistinktValues. IsUnique = True For i = 0 To DistinctCount - 1 If DistinctValues(i) = Values(row, col) Then //  ,       . IsUnique = False Cells(row, col).Font.Color = RGB(255, 75, 75) Exit For End If Next i //  ,      ,       DistinctValues,      If IsUnique = True Then DistinctCount = DistinctCount + 1 ReDim Preserve DistinctValues(0 To DistinctCount) DistinctValues(DistinctCount - 1) = Values(row, col) Cells(row, col).Font.Color = RGB(75, 175, 75) End If Next row Next col End Sub 

इसलिए, हमने पहले से ही सामना किए गए अद्वितीय तत्वों के साथ तुलना करके तत्व तुलना संचालन की संख्या को काफी कम कर दिया है। हमने शीट पर कोशिकाओं के संचालन की संख्या को दो तक कम कर दिया (पहला सरणी में सेल के मूल्य को बचाने के लिए है, दूसरा सेल को चित्रित करने के लिए है)। काम का समय कितना कम?

दुर्भाग्य से, इस एल्गोरिथ्म की गति इनपुट डेटा की एन्ट्रापी पर अत्यधिक निर्भर है। चूंकि हम अद्वितीय तत्वों की एक सरणी के साथ तुलना कर रहे हैं, तो यह सरणी जितनी बड़ी होगी, उतने ही अधिक समय की आवश्यकता होगी। दूसरे शब्दों में, इनपुट में जितने अधिक अद्वितीय तत्व हैं, उतने ही धीमे एल्गोरिथ्म काम करेंगे। मैंने 25,000 कोशिकाओं (5 कॉलम और 5,000 पंक्तियों) के लिए दो परीक्षण किए। पहले परीक्षण में, सभी कोशिकाओं को एक ही मूल्य (1) से भरा गया था, दूसरे में, इसके विपरीत, वे पुनरावृत्ति के बिना विभिन्न मूल्यों से भरे हुए थे।
पहले मामले के लिए, एल्गोरिथ्म ने 816 मिली सेकेंड लिया, और दूसरे के लिए, लगभग 19 सेकंड । और फिर भी, यह हमारी पहली पूर्ण थकावट खोज की तुलना में काफी तेज है, जो एक लुभावनी 58 मिनट में 25,000 कोशिकाओं को पचा सकती है।

हालांकि, सर्वश्रेष्ठ का पीछा कोई सीमा नहीं जानता है। कुछ विचार के बाद, मैंने पहिया को फिर से मजबूत नहीं करने का फैसला किया, लेकिन साबित एल्गोरिदम का उपयोग करने के लिए। मेरी पसंद त्वरित सॉर्ट एल्गोरिथ्म पर गिर गई, जो, जैसा कि आप जानते हैं, की जटिलता ओ (एन लॉग एन) है।

जल्दी ठीक करो

तो, आप मेरी समस्या को हल करने के लिए क्विकॉर्ट का उपयोग कैसे कर सकते हैं?

 // ,  . Type MyCell row As Long col As Long Value As Long End Type //  ,            . Sub QSort(sortArray() As MyCell, ByVal leftIndex As Long, _ ByVal rightIndex As Long) Dim compValue As MyCell Dim i As Long Dim J As Long Dim tempNum As MyCell i = leftIndex J = rightIndex compValue = sortArray(CLng((i + J) / 2)) //  . Do Do While (sortArray(i).Value < compValue.Value And i < rightIndex Or _ (sortArray(i).Value = compValue.Value And sortArray(i).col < compValue.col) Or _ (sortArray(i).Value = compValue.Value And sortArray(i).col = compValue.col And sortArray(i).row < compValue.row)) i = i + 1 Loop Do While (compValue.Value < sortArray(J).Value And J > leftIndex Or _ (sortArray(J).Value = compValue.Value And sortArray(J).col > compValue.col) Or _ (sortArray(J).Value = compValue.Value And sortArray(J).col = compValue.col And sortArray(J).row > compValue.row)) J = J - 1 Loop If i <= J Then tempNum = sortArray(i) sortArray(i) = sortArray(J) sortArray(J) = tempNum i = i + 1 J = J - 1 End If Loop While i <= J If leftIndex < J Then QSort sortArray(), leftIndex, J If i < rightIndex Then QSort sortArray(), i, rightIndex End Sub Sub FindMatches() //   Dim myRange As Range Set myRange = Selection //      Dim ColCount, RowCount As Integer ColCount = myRange.Columns.Count RowCount = myRange.rows.Count Dim FirstCol, FirstRow As Integer FirstCol = myRange.Column FirstRow = myRange.row //   ,       . Dim MyCells() As MyCell ReDim MyCells(ColCount * RowCount) Dim col, row As Integer Dim i As Long For col = FirstCol To FirstCol + ColCount - 1 For row = FirstRow To FirstRow + RowCount - 1 MyCells(CLng((col - FirstCol) * RowCount + row - FirstRow)).row = row MyCells(CLng((col - FirstCol) * RowCount + row - FirstRow)).col = col MyCells(CLng((col - FirstCol) * RowCount + row - FirstRow)).Value = CLng(Val(Cells(row, col))) Next row Next col //      Call QSort(MyCells, 0, ColCount * RowCount - 1) // . Cells(1, 1).Font.Color = RGB(0, 255, 0) For i = 1 To ColCount * RowCount - 1 If MyCells(i).Value <> MyCells(i - 1).Value Then Cells(MyCells(i).row, MyCells(i).col).Font.Color = RGB(0, 255, 0) Else Cells(MyCells(i).row, MyCells(i).col).Font.Color = RGB(255, 0, 0) End If Next i Cells(MyCells(firstOccurance).row, MyCells(firstOccurance).col).Font.Color = RGB(0, 255, 0) End Sub 

खुद को छाँटने के अलावा, मैंने शीट पर चयनित क्षेत्र के प्रसंस्करण को भी जोड़ा, क्योंकि यह अधिक सुविधाजनक है।

इस एल्गोरिथ्म के संचालन का सिद्धांत बहुत सरल है। हम एक डेटा संरचना बनाते हैं जो सेल (पंक्ति और स्तंभ संख्या) के पते और उसके मूल्य को संग्रहीत करता है। फिर इन संरचनाओं से एक सरणी बनाई जाती है जिसमें शीट से सभी डेटा दर्ज किया जाता है। एरियर को त्वरित सॉर्ट किया जाता है।
उसके बाद, तत्वों को रंगते हुए, एक बार सॉर्ट किए गए सरणी के माध्यम से जाने के लिए पर्याप्त है: समान मूल्यों वाले समूह में पहला तत्व हरा है, बाकी सभी लाल हैं।

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

उत्पादकता में लाभ कितना बड़ा था? यह एल्गोरिथ्म 4.2 सेकंड में यादृच्छिक मान के साथ 100,000 कोशिकाओं के साथ एक शीट को संसाधित करता है, जो, मेरी राय में, एक काफी स्वीकार्य परिणाम है।

तो, इस सब से क्या निष्कर्ष निकाला जा सकता है?

1. सबसे पहले, एल्गोरिथ्म के कम्प्यूटेशनल जटिलता की समस्या सभी प्रतीत होता है सरल कार्यों के लिए भी प्रासंगिक है, और इसे मुठभेड़ करने के लिए कुछ पूरी तरह से अविश्वसनीय मात्रा में डेटा के साथ काम करना आवश्यक नहीं है;
2. दूसरे, पहिया को सुदृढ़ करने की कोशिश न करें। कई मामलों में, सबसे अच्छा विकल्प एक विशिष्ट कार्य के लिए सिद्ध क्लासिक एल्गोरिदम को अनुकूलित करना होगा।

  PS चूंकि <source> टैग वीबीए हाइलाइटिंग का समर्थन नहीं करता है, कम से कम टिप्पणियों को उजागर करने के लिए, मुझे सी हाइलाइटिंग और सी-स्टाइल टिप्पणियों का उपयोग करना पड़ा।