फ्लाई पर पेरेंटाइल की गणना

Question

मैं जावा में प्रोग्रामिंग कर रहा हूं। प्रत्येक 100 एमएस मेरे कार्यक्रम को एक नया नंबर मिलता है।

यह एक कैश पिछले n = 180 संख्या के इतिहास में शामिल है के साथ है। जब मुझे एक नया नंबर x मिलता है, तो मैं गणना करना चाहता हूं कि x से छोटे कैश में कितनी संख्याएं हैं। बाद में मैं कैश में सबसे पुराना नंबर हटाना चाहता हूं।

हर 100 एमएस मैं की गणना कर रहे हैं और सबसे पुराने नंबर को हटाना कितने छोटी संख्याओं की प्रक्रिया दोहराना चाहते हैं।

मुझे किस एल्गोरिदम का उपयोग करना चाहिए? मैं गणना को तेजी से बनाने के लिए अनुकूलित करना चाहता हूं क्योंकि यह एकमात्र चीज नहीं है जो उन 100 एमएस पर गणना की जाती है।

Answer 1

व्यावहारिक कारणों और n की उचित मूल्यों आप आदिम int रों (सबसे पुरानी प्रविष्टि का ट्रैक रखने के) की एक अंगूठी बफर साथ का सबसे अच्छा कर रहे हैं के लिए, और कितने मूल्यों का निर्धारण करने के लिए एक रैखिक स्कैन छोटे होते हैं x से अधिक।

O(log n) में होने के लिए आपको Guavas TreeMultiset जैसे कुछ उपयोग करना होगा। यहां एक रूपरेखा है कि यह कैसा दिखाई देगा।

class Statistics { 

    private final static int N = 180; 
    Queue<Integer> queue = new LinkedList<Integer>(); 
    SortedMap<Integer, Integer> counts = new TreeMap<Integer, Integer>(); 

    public int insertAndGetSmallerCount(int x) { 

     queue.add(x);        // O(1) 
     counts.put(x, getCount(x) + 1);    // O(log N) 

     int lessCount = 0;       // O(N), unfortunately 
     for (int i : counts.headMap(x).values())  // use Guavas TreeMultiset 
      lessCount += i;       // for O(log n) 

     if (queue.size() > N) {      // O(1) 
      int oldest = queue.remove();    // O(1) 
      int newCount = getCount(oldest) - 1;  // O(log N) 
      if (newCount == 0) 
       counts.remove(oldest);    // O(log N) 
      else 
       counts.put(oldest, newCount);  // O(log N) 
     } 

     return lessCount; 
    } 

    private int getCount(int x) { 
     return counts.containsKey(x) ? counts.get(x) : 0; 
    } 

} 

मेरे 1 पर।8 गीगाहर्ट्ज लैपटॉप, यह समाधान लगभग 13 सेकंड पर 1,000,000 पुनरावृत्तियों का प्रदर्शन करता है (यानी एक पुनरावृत्ति लगभग 0.013 एमएस लेता है, अच्छी तरह से 100 एमएस से कम)।

Answer 2

अपनी संख्याओं को एक सूची में जोड़ें। यदि आकार> 180, पहले नंबर को हटा दें। गिनती सिर्फ 180 तत्वों पर फिर से चल रही है जो शायद पर्याप्त तेज़ है। प्रदर्शन के अनुसार हरा करना मुश्किल है।

Answer 3

कैश एक सूची हो, तो आप शुरू में डालने और सबसे पुराने अंत में हो सकता है और हटाया जा कर सकते हैं।

तो हर प्रविष्टि के बाद बस पूरी सूची स्कैन और नंबर आप की जरूरत की गणना।

Answer 4

आप एक लिंक्डलिस्ट कार्यान्वयन का उपयोग कर सकते हैं।

इस संरचना के साथ

, आप आसानी से पहले और सूची के अंतिम तत्वों में हेरफेर कर सकते हैं। (addFirst, removeFirst, ...) एल्गोरिथ्म के लिए (लगता है कि कितने नंबर दिए गए हैं कम/अधिक से अधिक), सूची में एक सरल पाश के लिए पर्याप्त है, और एक 180 के तत्व सूची में कम से कम 100ms में आप परिणाम दे देंगे।

Answer 5

आप 180 नंबर की एक सरणी रखने के लिए और इतनी है कि जब एक नया नंबर आप में आता है सबसे पुराने सूचकांक में संख्या के ऊपर लिख और सूचकांक सापेक्ष 180 को बढ़ा (यह थोड़ा और अधिक जटिल है सबसे पुराना करने के लिए एक सूचकांक को बचा सकता है इससे पहले कि आपको पहले 180 नंबरों के लिए विशेष व्यवहार की आवश्यकता है)।

की गणना कितने संख्या के लिए के रूप में छोटे मैं जानवर बल रास्ता (सभी नंबरों पुनरावृति और गिनती) का प्रयोग करेंगे रहे हैं।

---

संपादित करें: मैं इसे देखना हास्यास्पद है कि "optimized" version पांच बार इस तुच्छ कार्यान्वयन की तुलना में धीमी (विश्लेषण के लिए @Eiko करने के लिए धन्यवाद) चलाता है पाते हैं। मुझे लगता है कि यह इस तथ्य के कारण है कि जब आप पेड़ों और मानचित्रों का उपयोग करते हैं तो आप डेटा इलाके खो देते हैं और कई मेमोरी दोष होते हैं (स्मृति आवंटन और कचरा संग्रह का उल्लेख नहीं करते हैं)।

Answer 6

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

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

import java.util.*; 

class SortedLinkedList { 

    public static class SortedLL<T> 
    { 
    public class SortedNode<T> 
    { 
     public SortedNode(T value) 
     { 
     _value = value; 
     } 

     T _value; 

     SortedNode<T> prev; 
     SortedNode<T> next; 

     SortedNode<T> sortedPrev; 
     SortedNode<T> sortedNext; 
    } 

    public SortedLL(Comparator comp) 
    { 
     _comp = comp; 
     _head = new SortedNode<T>(null); 
     _tail = new SortedNode<T>(null); 
     // Setup the pointers 
     _head.next = _tail; 
     _tail.prev = _head; 
     _head.sortedNext = _tail; 
     _tail.sortedPrev = _head; 
     _sortedHead = _head; 
     _sortedTail = _tail;  
    } 

    int insert(T value) 
    { 
     SortedNode<T> nn = new SortedNode<T>(value); 

     // always add node at end 
     nn.prev = _tail.prev; 
     nn.prev.next = nn; 
     nn.next = _tail; 
     _tail.prev = nn; 

     // now second insert sort through.. 
     int count = 0; 
     SortedNode<T> ptr = _sortedHead.sortedNext; 
     while(ptr.sortedNext != null) 
     { 
     if (_comp.compare(ptr._value, nn._value) >= 0) 
     { 
      break; 
     } 
     ++count; 
     ptr = ptr.sortedNext; 
     } 

     // update the sorted pointers.. 
     nn.sortedNext = ptr; 
     nn.sortedPrev = ptr.sortedPrev; 
     if (nn.sortedPrev != null) 
     nn.sortedPrev.sortedNext = nn; 
     ptr.sortedPrev = nn; 

     return count;    
    } 

    void trim() 
    { 
     // Remove from the head... 
     if (_head.next != _tail) 
     { 
     // trim. 
     SortedNode<T> tmp = _head.next; 
     _head.next = tmp.next; 
     _head.next.prev = _head; 

     // Now updated the sorted list 
     if (tmp.sortedPrev != null) 
     { 
      tmp.sortedPrev.sortedNext = tmp.sortedNext; 
     } 
     if (tmp.sortedNext != null) 
     { 
      tmp.sortedNext.sortedPrev = tmp.sortedPrev; 
     } 
     } 
    } 

    void printList() 
    { 
     SortedNode<T> ptr = _head.next; 
     while (ptr != _tail) 
     { 
     System.out.println("node: v: " + ptr._value); 
     ptr = ptr.next; 
     }  
    } 

    void printSorted() 
    { 
     SortedNode<T> ptr = _sortedHead.sortedNext; 
     while (ptr != _sortedTail) 
     { 
     System.out.println("sorted: v: " + ptr._value); 
     ptr = ptr.sortedNext; 
     }  
    } 

    Comparator _comp; 

    SortedNode<T> _head; 
    SortedNode<T> _tail;  

    SortedNode<T> _sortedHead; 
    SortedNode<T> _sortedTail;  

    } 

    public static class IntComparator implements Comparator 
    { 
    public int compare(Object v1, Object v2){ 
     Integer iv1 = (Integer)v1; 
     Integer iv2 = (Integer)v2; 
     return iv1.compareTo(iv2); 
    } 
    } 


    public static void main(String[] args){ 

    SortedLL<Integer> ll = new SortedLL<Integer>(new IntComparator()); 
    System.out.println("inserting: " + ll.insert(1)); 
    System.out.println("inserting: " + ll.insert(3)); 
    System.out.println("inserting: " + ll.insert(2)); 
    System.out.println("inserting: " + ll.insert(5)); 
    System.out.println("inserting: " + ll.insert(4)); 
    ll.printList(); 
    ll.printSorted();  

    System.out.println("inserting new value"); 
    System.out.println("inserting: " + ll.insert(3)); 
    ll.trim(); 
    ll.printList(); 
    ll.printSorted();  
    } 
} 

Answer 7

DescriptiveStatistics class (Percentile.java) की commons-math कार्यान्वयन पर एक नजर डालें

Answer 8

180 मूल्यों कई और नहीं एक साधारण सरणी जो एक जानवर बल खोज और System.arraycopy() से अधिक तेजी से 1 सूक्ष्म होना चाहिए -सेकंड (1/1000 मिली-सेकंड) और कोई जीसी नहीं है। यह तेजी से हो सकता है कि अधिक जटिल संग्रह के साथ खेल रहा है।

मेरा सुझाव है कि आप इसे सरल रखें और माप लें कि आपको इसे अनुकूलित करने की आवश्यकता होने से पहले कितनी देर लगती है।