numpy.unique(return_inverse) और numpy.add.at से तेज ग्रुपिंग व समेकन

विरल व बड़े key-space पर numpy.bincount से बचें। numpy.unique(return_inverse) और numpy.add.at के साथ 2D ndarray को तेज़ी से group कर मानों का योग करें—मेमोरी कुशल समाधान।

जब आपके पास [curveLocations, distinctCrossings] जैसी जोड़ियों का ndarray हो और कुछ curveLocations दोहराए जाते हों, तो लक्ष्य है उसी कुंजी के आधार पर पंक्तियों को समेकित करना और संबंधित गणनाओं को जोड़ना। क्रमबद्ध करना आवश्यक नहीं, लेकिन तेज, वेक्टराइज़्ड ग्रुपिंग जरूर चाहिए। लोग अक्सर numpy.bincount की ओर मुड़ते हैं—आकर्षक दिखता है, पर विरल और बड़े मानों वाली कुंजियों पर नुकसानदेह हो सकता है। यहां बेहतर उपाय है numpy.unique को return_inverse के साथ लेना और numpy.add.at के जरिए scatter-add करना।

समस्या की रूपरेखा

इनपुट अनसॉर्टेड 2D ndarray है जिसमें unsigned integers हैं। पहली कॉलम में curveLocations (कुंजियाँ) होती हैं, दूसरी में distinctCrossings (जिन्हें जोड़ना है)। कोई कुंजी दोहरती है तो उसकी सभी वैल्यूज़ को समेकित करना होगा। आउटपुट को क्रमबद्ध होना जरूरी नहीं।

कुंजियाँ विरल हैं, और अधिकतम कुंजी बहुत बड़ी हो सकती है। जैसा कि दस्तावेज़ कहते हैं,

"The length of out is equal to np.amax(x)+1."

इसी वजह से numpy.bincount यहाँ उपयुक्त नहीं है: अधिकतम बढ़ते ही बिनों की संख्या फटकर बढ़ जाएगी, जबकि अधिकांश बिन खाली रहेंगे। संदर्भित मामले में अधिकतम कुंजी की सीमा curveLocationsMAXIMUM = 1 << (2 * n + 4) है। n = 25 होने पर यह करीब 2^54 बिन तक पहुँचता है — जाहिर है, यह व्यावहारिक नहीं।

समस्या दिखाने वाला कोड उदाहरण

नीचे दिया गया स्निपेट यूनिक कुंजियों के क्रमबद्ध सेट और प्रति पंक्ति अलग लुकअप चरण का उपयोग करके वेक्टराइज़्ड समेकन दिखाता है। यह उस तरीके को दोहराता है जिसमें कुंजियाँ निकालने के लिए numpy.unique और प्रत्येक मूल पंक्ति को उसके समूह इंडेक्स पर मैप करने के लिए numpy.searchsorted का सहारा लिया जाता है। नाम स्पष्टता के लिए चुने गए हैं; बर्ताव वही है जो प्रचलित पैटर्न में होता है।

import numpy as np
def pack_by_location(pairs2d: np.ndarray) -> np.ndarray:
    # pairs2d का आकार (N, 2) है: [:, 0] कुंजियाँ (curveLocations) हैं, [:, 1] मान (distinctCrossings) हैं
    unique_keys = np.unique(pairs2d[:, 0])
    # दो-स्तंभ वाला परिणाम तैयार करें: [key, sum]
    grouped = np.tile(unique_keys, (2, 1)).T
    grouped[:, 1] = 0
    # प्रत्येक इनपुट कुंजी को unique_keys में उसकी स्थिति पर मैप करें, फिर मानों को scatter-add करें
    idx_map = np.searchsorted(grouped[:, 0], pairs2d[:, 0])
    np.add.at(grouped[:, 1], idx_map, pairs2d[:, 1])
    return grouped

यह तरीका दो वेक्टराइज़्ड पास करता है: एक कुंजियाँ निकालकर उन्हें सॉर्ट करने के लिए, और दूसरा उन्हीं कुंजियों में प्रत्येक मूल पंक्ति का इंडेक्स खोजने के लिए। यह काम करता है, लेकिन प्रोफाइलिंग में दिखा कि numpy.unique और numpy.searchsorted का मिलाजुला खर्च रनटाइम पर हावी हो सकता है—aggregateCurveLocations में लागत का बड़ा हिस्सा इन्हीं फ़ंक्शनों को गया।

ऐसा क्यों होता है

समेकन अपने-आप में सरल है: हर मूल पंक्ति को किसी समूह इंडेक्स पर मैप करें और उसका मान संबंधित बकेट में जोड़ दें। बारीकी यह है कि यह मैपिंग कुशलता से कैसे बने। numpy.bincount इसलिए नहीं चल सकता क्योंकि वह अधिकतम कुंजी तक आवंटन करता है—विरल और विस्तृत कुंजी-स्थान में यह बहुत बड़ा हो जाता है। पिछले स्निपेट का सर्च-आधारित तरीका सही है, लेकिन सॉर्टेड यूनिक कुंजियाँ बनाने के बाद द्विआधारी खोजों का एक अतिरिक्त पास लगाता है।

numpy.unique return_inverse के जरिए वही मैपिंग सीधे दे सकता है जिसकी ज़रूरत है। यह “inverse” ऐरे इनपुट के हर तत्व के लिए डीडुप्लिकेटेड कुंजियों में सीधा इंडेक्स देता है, जिससे अलग सर्च चरण की जरूरत नहीं रहती। जैसे ही आपके पास ये इंडेक्स आ जाएँ, numpy.add.at योग इकट्ठा करने के लिए प्रभावी scatter-add कर देता है।

समाधान

नीचे दी गई फ़ंक्शन numpy.unique(return_inverse=True) और numpy.add.at का उपयोग करके कुंजी के आधार पर समेकन करती है। यह अतिरिक्त numpy.searchsorted पास से बचती है, और मेमरी उपयोग को कुंजी के आकार से स्वतंत्र तथा कसकर रखती है।

import numpy as np
def collapse_pairs(pairs2d: np.ndarray) -> np.ndarray:
    # pairs2d का आकार (N, 2) है: [:, 0] कुंजियाँ (curveLocations) हैं, [:, 1] मान (distinctCrossings) हैं
    keys, rev_idx = np.unique(pairs2d[:, 0], return_inverse=True)
    totals = np.zeros_like(keys)
    np.add.at(totals, rev_idx, pairs2d[:, 1])
    return np.column_stack((keys, totals))

यह [curveLocations, summedDistinctCrossings] वाला दो-स्तंभी परिणाम देता है। डिफ़ॉल्ट रूप से numpy.unique कुंजियाँ सॉर्टेड क्रम में लौटाता है, जो यहाँ ठीक है क्योंकि आउटपुट को मूल क्रम बनाए रखने की आवश्यकता नहीं।

दो स्तंभों से आगे बढ़ना

समेकन के बाद यदि और स्तंभ चाहिए हों, तो उन्हें समूहित परिणाम पर ही निकालें। उदाहरण के लिए, groupZulu और groupAlpha जैसी बिटवाइज़ निकासी को पहले जैसे ही मास्क और शिफ्ट से समेकित curveLocations से प्राप्त किया जा सकता है। समेकन चरण उन गणनाओं से स्वतंत्र है और बस धीमे “खोज-आधारित समूह” रूटीन को बदल देता है।

यह तरीका आपके टूलकिट में क्यों होना चाहिए

कुंजी के अनुसार समूह बनाकर मानों का योग करना डेटा-प्रधान कोड का बुनियादी ऑपरेशन है, और इसे ndarray स्तर पर सही करना मायने रखता है। विरल कुंजी-स्थान में बिन-काउंटिंग तरकीबें बाहर हो जाती हैं; प्रति-पंक्ति Python लूप अस्वीकार्य हैं; बार-बार खोज करना ओवरहेड जोड़ता है। unique + inverse + add.at का पैटर्न संक्षिप्त है, भारी आवंटनों से बचता है और बड़े, अनसॉर्टेड इनपुट पर साफ़-सुथरे ढंग से स्केल करता है।

निष्कर्ष

NumPy में समेकन द्वारा डुप्लिकेट हटाने के लिए समस्या को यूँ सोचें: “हर पंक्ति का समूह इंडेक्स बनाओ, फिर scatter-add करो।” जब कुंजियाँ विरल और संभावित रूप से बहुत बड़ी हों, तो numpy.bincount छोड़ दें। समूह इंडेक्स एक ही बार में बनाने के लिए numpy.unique के return_inverse=True का उपयोग करें, और numpy.add.at से संचय करें। यदि आपकी पाइपलाइन में curveLocations से निकले पोस्ट-एग्रीगेशन फ़ील्ड शामिल हैं, तो उन्हें पहले की तरह ही समूहित परिणाम पर गणना करें।