सी # में सरणी के लिए आवृत्ति वितरण की गणना करने का सबसे तेज़ तरीका क्या है?

Question

मैं बस सोच रहा हूं कि उस गणना के लिए सबसे अच्छा तरीका क्या है। आइए मान लें कि मेरे पास मानों और सीमाओं की सरणी की एक इनपुट सरणी है - मैं सीमाओं सरणी में प्रत्येक सेगमेंट के लिए आवृत्ति वितरण की गणना/बकेटेट करना चाहता था।

क्या इसके लिए बाल्टी खोज का उपयोग करना अच्छा विचार है?

वास्तव में मुझे लगता है कि सवाल Calculating frequency distribution of a collection with .Net/C#

पाया लेकिन मुझे समझ में नहीं आता कि कैसे उस उद्देश्य के लिए बाल्टी का उपयोग करने के कारण प्रत्येक बकेट के आकार मेरी स्थिति में अलग अलग हो सकता है।

संपादित करें: सब चर्चा के बाद मैं आंतरिक/बाहरी पाश समाधान है, लेकिन अभी भी मैं एक शब्दकोश के साथ आंतरिक पाश समाप्त करने के लिए उस मामले में हे (एन) प्रदर्शन प्राप्त करना चाहते हैं अगर मैं सही ढंग से समझ में आ रहा इनपुट हैश करने के लिए की जरूरत है एक बाल्टी सूचकांक में मूल्य। तो हमें ओ (1) जटिलता के साथ किसी प्रकार का हैश फ़ंक्शन चाहिए? कोई विचार यह कैसे करना है?

Answer 1

बाल्टी सॉर्ट पहले से ही ओ (एन^2) सबसे खराब मामला है, इसलिए मैं यहां एक साधारण आंतरिक/बाहरी लूप करूँगा। चूंकि आपकी बाल्टी सरणी आपके इनपुट सरणी से जरूरी है, इसे आंतरिक लूप पर रखें। चूंकि आप कस्टम बाल्टी आकार का उपयोग कर रहे हैं, वास्तव में कोई गणितीय चाल नहीं है जो उस आंतरिक पाश को खत्म कर सकती है।

int[] freq = new int[buckets.length - 1]; 
foreach(int d in input) 
{ 
    for(int i = 0; i < buckets.length - 1; i++) 
    { 
     if(d >= buckets[i] && d < buckets[i+1]) 
     { 
      freq[i]++; 
      break; 
     } 
    } 
} 

यह भी O (n^2) सबसे खराब स्थिति है, लेकिन आप कोड सादगी हरा सकते हैं। मैं ऑप्टिमाइज़ेशन के बारे में चिंता नहीं करता जब तक कि यह वास्तविक समस्या न हो जाए। यदि आपके पास एक बड़ी बाल्टी सरणी है, तो आप किसी प्रकार की बाइनरी खोज का उपयोग कर सकते हैं। लेकिन, चूंकि आवृत्ति वितरण आमतौर पर < 100 तत्व होते हैं, मुझे संदेह है कि आपको बहुत सारे वास्तविक-विश्व प्रदर्शन लाभ दिखाई देंगे।

Answer 2

अपने इनपुट सरणी वास्तविक दुनिया डेटा (अपने पैटर्न के साथ) का प्रतिनिधित्व करता है और सीमाओं की सरणी यह ​​बार-बार पुनरावृति भीतरी पाश में आप निम्नलिखित दृष्टिकोण पर विचार कर सकते करने के लिए बड़ी है:

• सभी तरह सबसे पहले आपका इनपुट सरणी यदि आप असली दुनिया डेटा के साथ काम करते हैं तो मैं Timsort - Wiki पर विचार करने की सलाह दूंगा। यह वास्तविक दुनिया डेटा में देखे जा सकने वाले पैटर्न के लिए बहुत अच्छी प्रदर्शन गारंटी प्रदान करता है।

• अनुसार क्रमबद्ध सरणी के माध्यम से पार और सीमाओं की सरणी में पहली मूल्य से इसकी तुलना:

  • यदि इनपुट सरणी में मूल्य से कम सीमा है - इस सीमा के लिए वेतन वृद्धि आवृत्ति काउंटर
  • हैं में मूल्य इनपुट सरणी सीमा के बाद बड़ी है - सीमाओं की सरणी में अगले मान पर जाएं और नई सीमा के लिए काउंटर बढ़ाएं।

एक कोड यह इस तरह दिख सकता है:

Timsort(myArray); 
int boundPos; 
boundaries = GetBoundaries(); //assume the boundaries is a Dictionary<int,int>() 

for (int i = 0; i<myArray.Lenght; i++) { 
    if (myArray[i]<boundaries[boundPos]) { 
    boundaries[boubdPos]++; 
    } 
    else { 
    boundPos++; 
    boundaries[boubdPos]++; 
    } 
}