घटनाओं की गणना करने के लिए सबसे प्रभावी तरीका है?

Question

मैं प्रदर्शन-महत्वपूर्ण कोड में बड़ी संख्या में एंट्रॉपी और पारस्परिक जानकारी की गणना करना चाहता हूं। एक मध्यवर्ती कदम के रूप में, मुझे प्रत्येक मूल्य की घटनाओं की संख्या गिनने की आवश्यकता है। उदाहरण के लिए:

uint[] myArray = [1,1,2,1,4,5,2]; 
uint[] occurrences = countOccurrences(myArray); 
// Occurrences == [3, 2, 1, 1] or some permutation of that. 
// 3 occurrences of 1, 2 occurrences of 2, one each of 4 and 5. 

बेशक

स्पष्ट तरीके यह या तो एक साहचर्य सरणी का उपयोग कर रहे हैं या त्वरित तरह की तरह एक "मानक" छँटाई कलन विधि का उपयोग इनपुट सरणी छँटाई के द्वारा करने के लिए। बाइट्स जैसे छोटे पूर्णांक के लिए, कोड वर्तमान में एक सादे पुरानी सरणी का उपयोग करने के लिए विशिष्ट है।

क्या कोई हैश तालिका से अधिक कुशलता से ऐसा करने के लिए कोई चालाक एल्गोरिदम है या एक "मानक" सॉर्टिंग एल्गोरिदम ऑफ़र करेगा, जैसे एक एसोसिएटिव सरणी कार्यान्वयन जो सम्मिलन या सॉर्टिंग एल्गोरिदम पर अपडेट का समर्थन करता है जो आपके डेटा में चमकता है बहुत सारे रिश्तों?

नोट: गैर-स्पैस पूर्णांक संभावित डेटा प्रकार का केवल एक उदाहरण हैं। मैं यहां एक उचित जेनेरिक समाधान को लागू करने के लिए देख रहा हूं, हालांकि पूर्णांक वाले पूर्णांक और structs सामान्य मामले हैं, इसलिए यदि वे बेहद कुशल हैं तो मुझे इन समाधानों में रुचि होगी।

Answer 1

कृपया अपने डेटा के बारे में और बताएं।

• कितने आइटम हैं?
• कुल वस्तुओं के लिए अद्वितीय आइटमों का अपेक्षित अनुपात क्या है?
• आपके पूर्णांक के वास्तविक मूल्यों का वितरण क्या है? क्या वे आम तौर पर एक साधारण गिनती सरणी का उपयोग करने के लिए पर्याप्त छोटे होते हैं? या वे उचित रूप से संकीर्ण समूहों में क्लस्टर हैं? आदि

किसी भी मामले में, मैं निम्नलिखित विचार सुझाता हूं: एक विलय डुप्लिकेट गिनने के लिए संशोधित किया गया है।

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

आप [(x1,1), (x2,1), ...] से शुरू करते हैं और सामान्य रूप से एक विलय करते हैं, लेकिन जब आप एक ही मान से शुरू होने वाली दो सूचियों को मर्ज करते हैं, तो आप मान को मान देते हैं आउटपुट सूची उनके अवसरों के साथ। अपने उदाहरण में: घटना जोड़े है कि मूल तुलना में काफी छोटा है, लेकिन का योग:

[1:1,1:1,2:1,1:1,4:1,5:1,2:1] 
Split into [1:1, 1:1, 2:1] and [1:1, 4:1, 5:1, 2:1] 
Recursively process them; you get [1:2, 2:1] and [1:1, 2:1, 4:1, 5:1] 
Merge them: (first/second/output) 
[1:2, 2:1]/[1:1, 2:1, 4:1, 5:1]/[] - we add up 1:2 and 1:1 and get 1:3 
[2:1]/[2:1, 4:1, 5:1]/[1:3] - we add up 2:1 and 2:1 and get 2:2 
[]/[4:1, 5:1]/[1:3, 2:2] 
[1:3, 2:2, 4:1, 5:1] 

इस सरणी के एक प्रारंभिक कमी करने के लिए कुछ चतुर चाल का उपयोग करके काफी सुधार किया जा सकता है (मूल्य की एक सरणी प्राप्त प्रत्येक 'मान' के लिए 'अवसर' मूल सरणी में 'मान' के अवसरों की संख्या के बराबर है)। उदाहरण के लिए, सरणी को निरंतर ब्लॉक में विभाजित करें जहां मान 256 या 65536 से अधिक नहीं होते हैं और प्रत्येक ब्लॉक के अंदर अवसरों की गणना करने के लिए एक छोटी सी सरणी का उपयोग करते हैं। असल में यह चाल बाद में विलय चरणों में भी लागू की जा सकती है।

Answer 2

उदाहरण में पूर्णांक की एक सरणी के साथ, सबसे प्रभावशाली तरीका int एस की एक सरणी होगी और यह आपके मानों का उपयोग करके इंडेक्स होगा (जैसा कि आप पहले से ही कर रहे हैं)।

यदि आप ऐसा नहीं कर सकते हैं, तो मैं हैशपैप से बेहतर विकल्प के बारे में नहीं सोच सकता। आपको बस एक तेज़ हैशिंग एल्गोरिदम होना चाहिए। यदि आप अपने सभी डेटा का उपयोग करना चाहते हैं तो आप ओ (एन) प्रदर्शन से बेहतर नहीं हो सकते हैं। क्या यह आपके पास मौजूद डेटा के केवल एक हिस्से का उपयोग करने का विकल्प है?

(ध्यान दें कि छँटाई और गिनती asymptotically धीमी (O (n * लॉग (एन))) एक hashmap आधारित समाधान (ओ (एन)) का उपयोग करने से है।)

Answer 3

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

मामलों है कि वास्तविक जीवन काम का बोझ के प्रतिनिधि आप (स्पष्ट जोखिम है कि आप एक नमूना है कि वास्तव में क्या हुआ चुन सकते हैं के साथ सामना कर रहे हो करने के लिए उम्मीद कर रहे हैं की एक चयन पर बेंचमार्क के अलावा इस तरह की समस्याओं का समाधान करने के लिए कोई वास्तव में अच्छा तरीका उपलब्ध नहीं है पक्षपातपूर्ण/गैर-प्रतिनिधि बनें - यदि आप एक पुस्तकालय बनाने की कोशिश कर रहे हैं तो यह एक छोटा सा जोखिम नहीं है जिसका उपयोग आपके बाहरी नियंत्रण के बाहर कई बाहरी उपयोगकर्ताओं द्वारा किया जाएगा)।