एडोब साक्षात्कार: कुछ परिचालनों को तेजी से करने के लिए हजारों अंक (x, y) को संग्रहीत करने के लिए उपयोग करने के लिए डेटा संरचना का उपयोग

Question

हमें उस बिंदु के रंग के लिए हजारों अंक (x, y, c) c स्टोर करना होगा। मुख्य रूप से यह स्क्रीन पर पिक्सेल से संबंधित है। हमें संचालन करना है: दिए गए x = i, हमें x = i वाले सभी बिंदुओं का रंग बदलना होगा। सिमिलरी, दिया गया y = i, हमें y = i वाले सभी बिंदुओं का रंग बदलना होगा।

मैंने 2 डी-मैट्रिक्स का समाधान प्रस्तावित किया। फिर एक्स और वाई निर्देशांक के लिए अलग हैश तालिका। फिर उसने मुझसे बेहतर समाधान के लिए भी पूछा। हम डेटा संरचनाओं का बेहतर संयोजन कैसे उपयोग कर सकते हैं?

Answer 1

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

Answer 2

यदि कोई पुनर्प्राप्ति wrt एक समन्वय नहीं है: तो आप हैशिंग एक्स, y निर्देशांक के जोड़े का प्रस्ताव दे सकते हैं। पोस्ट कम ध्रुव के साथ कुछ हैश का प्रस्ताव है, जैसा कि hash = (y << 16)^x; करता है।

लेकिन आप एक्स या वाई के लिए अपने डेटा wrt value तक पहुंच बनाना चाहते हैं। बिंदुओं को स्टोर करने और कुशलतापूर्वक संचालन करने के लिए संरचना एक बिंदु QTree या क्वाड ट्री है। See here।

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

एक बिंदु quadtree का एक नोड बड़ा अंतर किया जा रहा है यह चार संकेत है कि (एक-एक वृत्त का चतुर्थ भाग के लिए) के बजाय दो ("छोड़" और "सही") के साथ एक द्विआधारी पेड़ की एक नोड के समान है, एक साधारण बाइनरी पेड़ में। इसके अलावा एक कुंजी आमतौर पर दो भागों में विघटित होती है, जो x और y निर्देशांक का जिक्र करती है। इसलिए एक नोड में निम्नलिखित जानकारी होती है: 4 पॉइंटर्स: क्वाड ['एनडब्ल्यू'], क्वाड ['एनई'], क्वाड ['एसडब्ल्यू]], और क्वाड [' एसई '] बिंदु; जो बदले में है: कुंजी; आमतौर पर एक्स, वाई निर्देशांक मान के रूप में व्यक्त किया जाता है; उदाहरण के लिए एक नाम

फिर, आप एएबीबी रेंज के भीतर सभी बिंदुओं की पूछताछ के लिए एक पुनरावर्ती कार्य कर सकते हैं। आप QueryRange()

class QuadTree 
{ 
    function queryRange(AABB range) 
    { 
    Array of XY pointsInRange; // Prepare an array of results 

    // Check objects at this quad level 
    for (int p := 0; p < points.size; p++) 
    { 
     if (range.containsPoint(points[p])) 
     pointsInRange.append(points[p]); 
    } 

    pointsInRange.appendArray(northWest->queryRange(range)); 
    pointsInRange.appendArray(northEast->queryRange(range)); 
    pointsInRange.appendArray(southWest->queryRange(range)); 
    pointsInRange.appendArray(southEast->queryRange(range)); 

    return pointsInRange; 
    } 
}