लाइब्रेरी ट्रोव। जावा में आदिम प्रकार के संग्रह

मानक जावा लाइब्रेरी में आदिम प्रकार के संग्रह को संभालने की क्षमता का अभाव है, जैसे कि इंट, लॉन्ग इत्यादि। मानक तरीका यह है कि कक्षाओं की वस्तुओं का उपयोग किया जाए इंटेगर, लॉन्ग इत्यादि।

यह दृष्टिकोण कम संख्या में तत्वों पर अच्छी तरह से काम करता है, क्योंकि, सबसे पहले, ऑटोबॉक्सिंग / ऑटोऑनबॉक्सिंग किसी भी ऑपरेशन के दौरान होता है, और दूसरी बात, ढेर में वस्तुओं के संदर्भ संग्रह में संग्रहीत होते हैं। हीप में ऑब्जेक्ट न केवल मेमोरी से अतिरिक्त ओवरहेड का परिचय देते हैं, बल्कि जीसी पर लोड भी बनाते हैं।

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

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

संग्रह सेट में शामिल हैं:

• सूची - एरियरिस्ट और लिंक्डलिस्ट
• मानचित्र - हैशपॉइंट
• सेट - हैशसेट
• ढेर - ArrayStack

Jdk के विपरीत, ट्रोव हैश ओपन एड्रेसिंग टक्कर रिज़ॉल्यूशन विधि का उपयोग करता है।

नामकरण सिद्धांत T <टाइप> <CollectionType> है।
उदाहरण के लिए:
TIntList इंटरफ़ेस - int की सूची, TIntArrayList का कार्यान्वयन:

TIntList l = new TIntArrayList(); 

TLongLongMap - लंबी कुंजी और लंबे मूल्यों के साथ नक्शा इंटरफ़ेस, TLongLongHashMap कार्यान्वयन:

 TLongLongMap m = new TLongLongHashMap(); 

Jdk संग्रहों में, यदि आइटम नहीं मिला है, तो नल वापस आ गया है। "NoEntryValue" ट्रोव में लौटता है, डिफ़ॉल्ट 0. है। आप NoEntryValue सीख सकते हैं, संग्रह बनाते समय NoEntryValue सेट कर सकते हैं।

ट्रोव संग्रह का लाभ प्रसंस्करण विधियों - forEach,

  public static long troveEach() { final long [] rvalue = {0}; // troveMap - TLongLongHashMap // TLongProcedure      , //    false //     troveMap.forEachValue(new TLongProcedure() { @Override public boolean execute(long value) { rvalue[0] += value; return true; } }); return rvalue[0]; } 

grep , inverseGrep - सशर्त सूची संकलन (TList के लिए ...) और transformValues - संग्रह तत्वों पर inplace परिवर्तन का संचालन करते हैं।

एक उपयोगी विशेषता - एक वस्तु के रूप में एक वस्तु (एक वस्तु उत्तराधिकारी) के साथ एक हैशपॉप / हैशसेट के मामले में, आप अपने हैश फ़ंक्शन इंटरफ़ेस HशिंगStrategy <T> का उपयोग कर सकते हैं।

बेंचमार्किंग के लिए, हमने उत्कृष्ट बेंचमार्क टूल jhh का उपयोग किया।
यह बहुत अच्छा होगा अगर डेवलपर्स इसे मावेन रिपॉजिटरी में प्रकाशित करें।

स्वरूपण, एक ऑपरेशन - 1 मिलियन तत्वों ( पूरी रिपोर्ट यहां ) को बनाए रखने के लिए आउटपुट को थोड़ा संपादित करना पड़ा:

 $ java -version java version "1.7.0_21" Java(TM) SE Runtime Environment (build 1.7.0_21-b11) Java HotSpot(TM) 64-Bit Server VM (build 23.21-b01, mixed mode) $ java -server -XX:+AggressiveOpts -Xms2048m \ -Xmx2048m -jar microbenchmarks.jar ".*Trove.*" -prof gc -i 3 -r 5s 

 बेंचमार्क मोड थ्रू Cnt Sec मतलब मीन एरर यूनिट
 // सूची में डालें <Integer>
 IntListJdkInsert 1 1 3 5 104.950 6.756 ऑप्स / सेक
 // सूची की पूर्ण गणना <Integer>
 IntListJdkTraverse 1 1 5 5 774.100 71.809 ऑप्स / सेक

 // TIntArrayList में डालें
 IntListTroveInsert 1 3 5 424.556 28.239 ऑप्स / सेक
 // पूर्ण गणना TIntArrayList
 IntListTroveTraverse 1 1 5 5 3548.806 7.712 ऑप्स / सेक

 // HashMap <Long, Long> में डालें
 LongHashMapJdkInsert 1 3 5 24.683 1.994 ऑप्स / सेक
 // HashMap <long, Long> बारी में सभी तत्वों की खोज करें
 LongHashMapJdkSearch 1 1 5 5 67.789 1.119 ऑप्स / सेक
 // मूल्यों की विस्तृत खोज HashMap <लॉन्ग, लॉन्ग>
 LongHashMapJdkTraverse 1 3 5 99.761 0.882 ऑप्स / सेकंड का रोमांच

 // TLongLongMap में डालें
 LongHashMapTroveInsert 1 3 5 28.750 0.165 ऑप्स / सेक
 // बदले में TLongLongMap में सभी तत्वों की खोज करें
 LongHashMapTroveSearch 1 1 5 5 145.933 0.416 ऑप्स / सेकंड रोमांचित करें
 / / forong का उपयोग कर TLongLongMap मूल्यों की पूरी गणना
 LongHashMapTroveTraverse 1 3 5 318.528 0.980 ऑप्स / सेकंड का रोमांच

कब्जे वाली मेमोरी की मात्रा की गणना करना इतना आसान नहीं है, लेकिन जीसी गतिविधि से एक अप्रत्यक्ष निष्कर्ष निकाला जा सकता है:

  jd  List<Integer>: Iteration 1 (5s in 1 thread): 103,950 ops/sec GC | wall time = 5,002 secs, GC time = 0,331 secs, GC% = 6,62%, GC count = +24  Trove  TIntArrayList: Iteration 1 (5s in 1 thread): 428,400 ops/sec GC | wall time = 5,002 secs, GC time = 0,019 secs, GC% = 0,38%, GC count = +32 

यदि आप TIntArrayList के स्रोतों को देखते हैं, तो यह स्पष्ट हो जाएगा कि प्रदर्शन लाभ कहां से आता है - डेटा को एक सरणी के रूप में संग्रहीत किया जाता है:

 public class TIntArrayList implements TIntList, Externalizable { static final long serialVersionUID = 1L; /** the data of the list */ protected int[] _data; 

TLongLongMap खोज गति का उपयोग करके समझाया गया है - कोई अस्थायी वस्तु नहीं बनाई गई है और अनबॉक्सिंग को बाहर रखा गया है।

एक ही बेंचमार्क, लेकिन एक ऑपरेशन - 1 हजार तत्व:

 बेंचमार्क मोड थ्रू Cnt Sec मतलब मीन एरर यूनिट
 IntListJdkInsert 1 1 5 5 239478.011 871.469 ऑप्स / सेक
 IntListJdkTraverse 1 1 5 5 1326701.717 1649.389 ऑप्स / सेक

 IntListTroveInsert 1 1 3 5 315562.594 2483.415 ऑप्स / सेक
 IntListTroveTraverse 1 1 5 5 3630599.806 10822.903 ऑप्स / सेक

 LongHashMapJdkInsert 1 3 5 45315.689 47.630 ऑप्स / सेकंड का रोमांच
 LongHashMapJdkSearch थ्रीप 1 3 5 114759.789 424.996 ऑप्स / सेक
 LongHashMapJdkTraverse 1 1 5 5 210012.550 139.001 ऑप्स / सेक

 LongHashMapTroveInsert 1 3 5 33078.583 119.127 ऑप्स / सेक
 LongHashMapTroveSearch 1 1 5 5 148311.567 267.613 ऑप्स / सेक
 LongHashMapTroveTraverse 1 1 3 5 351955.550 901.902 ऑप्स / सेकंड का रोमांच

यह देखा जा सकता है कि संग्रह में तत्वों की संख्या में कमी के साथ, प्रदर्शन में अंतर गिर जाता है।

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

प्रोजेक्ट कोड GitHub पर उपलब्ध है ।

पुनश्च। संग्रह बनाते समय तत्वों की संख्या का मान जानबूझकर निर्धारित नहीं किया गया था।