हजारों वैक्टरों को संग्रहीत करने के लिए डेटा संरचना

Question

मेरे पास एक जगह में 10,000 यादृच्छिक रूप से स्थित बिंदु हैं और मुझे यह बताने में सक्षम होना चाहिए कि कर्सर किसी भी समय किस निकटतम है। कुछ संदर्भ जोड़ने के लिए, बिंदु वेक्टर ड्राइंग के रूप में होते हैं, इसलिए उन्हें उपयोगकर्ता द्वारा लगातार और जल्दी से जोड़ा और हटाया जा सकता है और संभावित रूप से कैनवास स्पेस में असंतुलित भी हो सकता है ..

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

Answer 1

के बाद प्रश्न

1. उपयोग दो Red-Black Tree या Skip_list नक्शे को अपडेट करें। दोनों कॉम्पैक्ट स्व-संतुलन डेटा संरचनाएं हैं जो आपको खोज, सम्मिलित करने और हटाने के लिए ओ (लॉग एन) समय देते हैं। एक नक्शा प्रत्येक बिंदु के लिए एक्स-समन्वय का उपयोग एक कुंजी के रूप में करेगा और बिंदु स्वयं को एक मान के रूप में और दूसरा वाई-समन्वय का उपयोग एक कुंजी के रूप में करेगा और बिंदु स्वयं मान के रूप में करेगा।

2. एक व्यापार-बंद के रूप में, मैं सलाह देता हूं कि शुरुआत में कर्सर के चारों ओर खोज क्षेत्र को एक वर्ग द्वारा प्रतिबंधित करें। सही मिलान के लिए वर्ग की तरफ कर्सर के चारों ओर अपने "संवेदनशीलता सर्कल" के व्यास के बराबर होना चाहिए। यदि आप कर्सर से 10 पिक्सेल त्रिज्या के भीतर केवल निकटतम पड़ोसी में रूचि रखते हैं तो स्क्वायर पक्ष को 20px होना चाहिए। वैकल्पिक विकल्प के रूप में , यदि आप निकटता के बावजूद निकटतम पड़ोसी के बाद हैं तो आप कर्सर के सापेक्ष फर्श और छत का मूल्यांकन करके सीमा को गतिशील रूप से ढूंढने का प्रयास कर सकते हैं।

3. फिर सीमाओं के भीतर वाले नक्शे से बिंदुओं के दो सबसेट पुनर्प्राप्त करें, दोनों उप सेटों के भीतर केवल अंक शामिल करने के लिए विलय करें।

4. परिणाम के माध्यम से लूप, प्रत्येक बिंदु (डीएक्स^2 + डीई^2, स्क्वायर रूट से बचें क्योंकि आप वास्तविक दूरी में रुचि नहीं रखते हैं, केवल निकटता), निकटतम पड़ोसी को ढूंढें।

5. निकटतम पड़ोसी से दूरी मापने के लिए निकटता आंकड़े से रूट वर्ग लें, देखें कि यह "संवेदनशीलता सर्कल" के त्रिज्या से अधिक है, यदि इसका मतलब है कि सर्कल के भीतर कोई बिंदु नहीं है।

6. मैं हर दृष्टिकोण कुछ बेंचमार्क करने का सुझाव देता हूं; अनुकूलन के साथ शीर्ष पर जाना दो आसान है। मेरे मामूली हार्डवेयर (डुओ कोर 2) पर 10k अंकों के भीतर निकटतम पड़ोसी की भद्दा एकल-थ्रेडेड खोज जावा में 350 मिलीसेकंड लेती है। जब तक कि संपूर्ण यूआई री-एक्शन टाइम 100 मिलीसेकंड के नीचे होता है, यह एक उपयोगकर्ता के लिए तत्काल प्रतीत होता है, यह ध्यान में रखते हुए भी भद्दा खोज आपको पर्याप्त तेज़ प्रतिक्रिया दे सकती है।

   • :

जेनेरिक समाधान

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

यदि समय एक साधारण 2 डी सरणी में 10K अंक संग्रहीत करने और हर बार भद्दा खोज करने में कोई समस्या नहीं है, यानी प्रत्येक बिंदु के माध्यम से लूपिंग और दूरी की गणना करना विकल्प को बनाए रखने के लिए एक अच्छा और सरल आसान हो सकता है। http://dimacs.rutgers.edu/Workshops/MiningTutorial/pindyk-slides.ppt

विभिन्न निकटतम पड़ोसी खोज एल्गोरिदम के लिए अच्छा विस्तृत सामग्री की एक गुच्छा:

दोनों के बीच व्यापार गत के एक नंबर के लिए, यहाँ उपलब्ध विभिन्न निकटतम पड़ोसी खोजें विकल्पों पर एक अच्छी प्रस्तुति है http://simsearch.yury.name/tutorial.html, बस एक चुनना है कि आपकी जरूरतों के अनुरूप सबसे अच्छा है।

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

नमूना जावा कार्यान्वयन

import java.util.*; 
import java.util.concurrent.ConcurrentSkipListMap; 

class Test 
{ 

    public static void main (String[] args) 
    { 

     Drawing naive = new NaiveDrawing(); 
     Drawing skip = new SkipListDrawing(); 

     long start; 

     start = System.currentTimeMillis(); 
     testInsert(naive); 
     System.out.println("Naive insert: "+(System.currentTimeMillis() - start)+"ms"); 
     start = System.currentTimeMillis(); 
     testSearch(naive); 
     System.out.println("Naive search: "+(System.currentTimeMillis() - start)+"ms"); 


     start = System.currentTimeMillis(); 
     testInsert(skip); 
     System.out.println("Skip List insert: "+(System.currentTimeMillis() - start)+"ms"); 
     start = System.currentTimeMillis(); 
     testSearch(skip); 
     System.out.println("Skip List search: "+(System.currentTimeMillis() - start)+"ms"); 

    } 

    public static void testInsert(Drawing d) 
    { 
     Random r = new Random(); 
     for (int i=0;i<100000;i++) 
      d.addPoint(new Point(r.nextInt(4096),r.nextInt(2048))); 
    } 

    public static void testSearch(Drawing d) 
    { 
     Point cursor; 
     Random r = new Random(); 
     for (int i=0;i<1000;i++) 
     { 
      cursor = new Point(r.nextInt(4096),r.nextInt(2048)); 
      d.getNearestFrom(cursor,10); 
     } 
    } 


} 

// A simple point class 
class Point 
{ 
    public Point (int x, int y) 
    { 
     this.x = x; 
     this.y = y; 
    } 
    public final int x,y; 

    public String toString() 
    { 
     return "["+x+","+y+"]"; 
    } 
} 

// Interface will make the benchmarking easier 
interface Drawing 
{ 
    void addPoint (Point p); 
    Set<Point> getNearestFrom (Point source,int radius); 

} 


class SkipListDrawing implements Drawing 
{ 

    // Helper class to store an index of point by a single coordinate 
    // Unlike standard Map it's capable of storing several points against the same coordinate, i.e. 
    // [10,15] [10,40] [10,49] all can be stored against X-coordinate and retrieved later 
    // This is achieved by storing a list of points against the key, as opposed to storing just a point. 
    private class Index 
    { 
     final private NavigableMap<Integer,List<Point>> index = new ConcurrentSkipListMap <Integer,List<Point>>(); 

     void add (Point p,int indexKey) 
     { 
      List<Point> list = index.get(indexKey); 
      if (list==null) 
      { 
       list = new ArrayList<Point>(); 
       index.put(indexKey,list); 
      } 
      list.add(p); 
     } 

     HashSet<Point> get (int fromKey,int toKey) 
     { 
      final HashSet<Point> result = new HashSet<Point>(); 

      // Use NavigableMap.subMap to quickly retrieve all entries matching 
      // search boundaries, then flatten resulting lists of points into 
      // a single HashSet of points. 
      for (List<Point> s: index.subMap(fromKey,true,toKey,true).values()) 
       for (Point p: s) 
       result.add(p); 

      return result; 
     } 

    } 

    // Store each point index by it's X and Y coordinate in two separate indices 
    final private Index xIndex = new Index(); 
    final private Index yIndex = new Index(); 

    public void addPoint (Point p) 
    { 
     xIndex.add(p,p.x); 
     yIndex.add(p,p.y); 
    } 


    public Set<Point> getNearestFrom (Point origin,int radius) 
    { 


      final Set<Point> searchSpace; 
      // search space is going to contain only the points that are within 
      // "sensitivity square". First get all points where X coordinate 
      // is within the given range. 
      searchSpace = xIndex.get(origin.x-radius,origin.x+radius); 

      // Then get all points where Y is within the range, and store 
      // within searchSpace the intersection of two sets, i.e. only 
      // points where both X and Y are within the range. 
      searchSpace.retainAll(yIndex.get(origin.y-radius,origin.y+radius)); 


      // Loop through search space, calculate proximity to each point 
      // Don't take square root as it's expensive and really unneccessary 
      // at this stage. 
      // 
      // Keep track of nearest points list if there are several 
      // at the same distance. 
      int dist,dx,dy, minDist = Integer.MAX_VALUE; 

      Set<Point> nearest = new HashSet<Point>(); 

      for (Point p: searchSpace) 
      { 
      dx=p.x-origin.x; 
      dy=p.y-origin.y; 
      dist=dx*dx+dy*dy; 

      if (dist<minDist) 
      { 
        minDist=dist; 
        nearest.clear(); 
        nearest.add(p); 
      } 
      else if (dist==minDist) 
      { 
       nearest.add(p); 
      } 


      } 

      // Ok, now we have the list of nearest points, it might be empty. 
      // But let's check if they are still beyond the sensitivity radius: 
      // we search area we have evaluated was square with an side to 
      // the diameter of the actual circle. If points we've found are 
      // in the corners of the square area they might be outside the circle. 
      // Let's see what the distance is and if it greater than the radius 
      // then we don't have a single point within proximity boundaries. 
      if (Math.sqrt(minDist) > radius) nearest.clear(); 
      return nearest; 
    } 
} 

// Naive approach: just loop through every point and see if it's nearest. 
class NaiveDrawing implements Drawing 
{ 
    final private List<Point> points = new ArrayList<Point>(); 

    public void addPoint (Point p) 
    { 
     points.add(p); 
    } 

    public Set<Point> getNearestFrom (Point origin,int radius) 
    { 

      int prevDist = Integer.MAX_VALUE; 
      int dist; 

      Set<Point> nearest = Collections.emptySet(); 

      for (Point p: points) 
      { 
      int dx = p.x-origin.x; 
      int dy = p.y-origin.y; 

      dist = dx * dx + dy * dy; 
      if (dist < prevDist) 
      { 
        prevDist = dist; 
        nearest = new HashSet<Point>(); 
        nearest.add(p); 
      } 
      else if (dist==prevDist) nearest.add(p); 

      } 

      if (Math.sqrt(prevDist) > radius) nearest = Collections.emptySet(); 

      return nearest; 
    } 
} 

Answer 2

क्या अंक समान रूप से वितरित किए गए हैं?

आप एक निश्चित गहराई तक एक क्वाड-पेड़ बना सकते हैं, कहें, 8. शीर्ष पर आपके पास एक पेड़ नोड है जो स्क्रीन को चार चतुर्भुज में विभाजित करता है। प्रत्येक नोड पर स्टोर:

• ऊपरी बाएँ और नीचे सही
• से चार प्वाइंटर बच्चे नोड्स, जो चार चतुर्थ भाग

8 की गहराई तक पेड़ बिल्ड में नोड विभाजित समन्वय , कहें, और पत्ती नोड्स पर, उस क्षेत्र से जुड़े बिंदुओं की एक सूची संग्रहित करें। वह सूची आप रैखिक रूप से खोज सकते हैं।

यदि आपको अधिक बारीकी से आवश्यकता है, तो चौड़ाई के लिए चौकोर-पेड़ का निर्माण करें।

Answer 3

सबसे कुशल डेटा संरचना एक केडी पेड़ link text

Answer 4

यह अद्यतन और क्वेरी की आवृत्ति पर निर्भर करता है हो सकता है। तेजी से पूछताछ के लिए, धीमे अपडेट, एक क्वाड्री (जो 2-डी के लिए जेडी-पेड़ का एक रूप है) शायद सबसे अच्छा होगा। Quadtree भी गैर वर्दी बिंदु के लिए बहुत अच्छे हैं।

यदि आपके पास कम रिज़ॉल्यूशन है तो आप पूर्व-गणना वाले मानों की चौड़ाई x ऊंचाई की कच्ची सरणी का उपयोग करने पर विचार कर सकते हैं।

यदि आपके पास बहुत कम अंक या तेज़ अपडेट हैं, तो एक साधारण सरणी पर्याप्त है, या एक साधारण विभाजन हो सकता है (जो क्वाड्री की तरफ जाता है)।

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

Answer 5

मैं (के रूप में मैं this सवाल को दिया था मूल रूप से एक ही answer) एक Voronoi Diagram और एक Trapezoidal Map बनाने का सुझाव देना चाहूंगा। Voronoi Diagram बहुभुज में स्थान का विभाजन करेगा। प्रत्येक बिंदु में बहुभुज होगा जो सभी बिंदुओं का वर्णन करता है जो इसके सबसे नज़दीक हैं। अब जब आप किसी बिंदु की क्वेरी प्राप्त करते हैं, तो आपको यह पता लगाना होगा कि यह किस बहुभुज में है। इस समस्या को Point Location कहा जाता है और Trapezoidal Map का निर्माण करके हल किया जा सकता है।

Voronoi DiagramFortune's algorithm का उपयोग करके बनाया जा सकता है जो ओ (एन लॉग एन) कम्प्यूटेशनल चरणों और लागत ओ (एन) स्पेस लेता है। This website आपको दिखाता है कि ट्रैपेज़ॉयडल मानचित्र कैसे बनाएं और इसे कैसे पूछें। तुम भी कुछ सीमा पा सकते हैं:

• अपेक्षित निर्माण के समय: O (n लॉग ऑन एन)
• अपेक्षित अंतरिक्ष जटिलता: हे (एन) लेकिन
• सबसे महत्वपूर्ण बात, उम्मीद क्वेरी समय: हे (लॉग एन)।
  (यह (सैद्धांतिक) हे की तुलना में बेहतर (√ केडी-पेड़ के एन) है।)
• अद्यतन कर रहा है रैखिक हो जाएगा (ओ (एन)) मुझे लगता है।

मेरा स्रोत (उपरोक्त लिंक के अलावा) है: Computational Geometry: algorithms and applications, अध्याय छः और सात।

वहां आपको दो डेटा संरचनाओं (विस्तृत प्रमाण सहित) के बारे में विस्तृत जानकारी मिल जाएगी। Google पुस्तकें संस्करण में केवल आपके लिए आवश्यक चीज़ों का एक हिस्सा है, लेकिन अन्य लिंक आपके उद्देश्य के लिए पर्याप्त होना चाहिए। अगर आप उस तरह की चीज़ में रुचि रखते हैं तो बस किताब खरीदें (यह एक अच्छी किताब है)।

Answer 6

आपने अपने अंक के आयाम निर्दिष्ट नहीं किए हैं, लेकिन यदि यह 2 डी लाइन ड्राइंग है तो एक बिटमैप बाल्टी - एक क्षेत्र में बिंदुओं की सूचियों की एक 2 डी सरणी, जहां आप एक कर्सर के पास और उसके आस-पास की बाल्टी स्कैन करते हैं बहुत अच्छा प्रदर्शन कर सकते हैं। अधिकांश सिस्टम 100x100 से 1000x1000 ऑर्डर के बिटमैप बाल्टी को खुशी से संभाल लेंगे, जिसमें से छोटा अंत एक बाल्टी प्रति बिंदु का मतलब रखेगा। हालांकि एसिम्प्टोटिक प्रदर्शन ओ (एन) है, वास्तविक दुनिया का प्रदर्शन आम तौर पर बहुत अच्छा होता है। बाल्टी के बीच अलग-अलग बिंदुओं को स्थानांतरित करना तेज हो सकता है; यदि आप ऑब्जेक्ट्स को अंक के बजाए बाल्टी में डालते हैं तो चारों ओर चलती वस्तुओं को भी तेजी से बनाया जा सकता है (इसलिए 12 पॉइंट्स का बहुभुज 12 बाल्टी से संदर्भित किया जाएगा; इसे बाल्टी सूची में सम्मिलन और हटाने की लागत 12 गुणा हो जाती है; बाल्टी ऊपर 2 डी सरणी में निरंतर समय है)। यदि कैनवास आकार कई छोटे कूदों में बढ़ता है तो प्रमुख लागत सब कुछ पुनर्गठित कर रही है।

Answer 7

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