java - जावा संग्रह फ्रेमवर्क कार्यान्वयन के लिए बिग-ओ सारांश?




collections big-o (3)

मैं जल्द ही "जावा क्रैश-कोर्स" पढ़ रहा हूं। हालांकि यह संभवतः यह मानना ​​सुरक्षित है कि दर्शकों के सदस्यों को बिग-ओ नोटेशन पता चलेगा, शायद यह मानना ​​सुरक्षित नहीं है कि वे जान लेंगे कि विभिन्न संग्रह कार्यान्वयन पर विभिन्न परिचालनों का क्रम क्या है।

मुझे सारांश मैट्रिक्स स्वयं उत्पन्न करने में समय लग सकता है, लेकिन अगर यह पहले से ही सार्वजनिक डोमेन में बाहर है, तो मैं निश्चित रूप से इसका पुन: उपयोग करना चाहूंगा (उचित क्रेडिट के साथ।)

किसी के पास कोई संकेतक है?


उपरोक्त लड़के ने हैश मैप / हैशसेट बनाम ट्रीमैप / ट्रीसेट के लिए तुलना की।

मैं ArrayList बनाम LinkedList के बारे में बात करेंगे:

सारणी सूची:

  • ओ (1) get()
  • amortized ओ (1) add()
  • यदि आप ListIterator.add() या Iterator.remove() का उपयोग करके मध्य में किसी तत्व को सम्मिलित या हटाते हैं, तो यह निम्नलिखित सभी तत्वों को स्थानांतरित करने के लिए ओ (एन) होगा

लिंक्ड सूची:

  • ओ (एन) get()
  • ओ (1) add()
  • यदि आप ListIterator.add() या Iterator.remove() का उपयोग कर बीच में तत्व को सम्मिलित या हटाते हैं, तो यह ओ (1) होगा

प्रत्येक संग्रह वर्ग के लिए सूर्य से जावाडॉक्स आम तौर पर आपको वही बताएंगे जो आप चाहते हैं। HashMap , उदाहरण के लिए:

यह कार्यान्वयन बुनियादी परिचालनों (प्राप्त करने और रखे) के लिए निरंतर समय का प्रदर्शन प्रदान करता है , मानते हैं कि हैश फ़ंक्शन बाल्टी के बीच तत्वों को सही तरीके से फैलता है। संग्रह दृश्यों पर इटरेशन के लिए हैश मैप इंस्टेंस (बाल्टी की संख्या) की "क्षमता" के साथ-साथ इसके आकार (कुंजी-मूल्य मैपिंग की संख्या) की "क्षमता" के समान समय की आवश्यकता होती है।

TreeMap :

यह कार्यान्वयन, केके, प्राप्त, रख और संचालन को हटाने के लिए गारंटीकृत लॉग (एन) समय लागत प्रदान करता है।

TreeSet :

यह कार्यान्वयन मूल संचालन के लिए गारंटीकृत लॉग (एन) समय लागत प्रदान करता है (जोड़ें, निकालें और इसमें शामिल है)।

(जोर मेरा)


जावा जेनरिक और कलेक्शन पुस्तक में यह जानकारी है (पेज: 188, 211, 222, 240)।

सूची कार्यान्वयन:

                      get  add  contains next remove(0) iterator.remove
ArrayList             O(1) O(1) O(n)     O(1) O(n)      O(n)
LinkedList            O(n) O(1) O(n)     O(1) O(1)      O(1)
CopyOnWrite-ArrayList O(1) O(n) O(n)     O(1) O(n)      O(n)

कार्यान्वयन सेट करें:

                      add      contains next     notes
HashSet               O(1)     O(1)     O(h/n)   h is the table capacity
LinkedHashSet         O(1)     O(1)     O(1) 
CopyOnWriteArraySet   O(n)     O(n)     O(1) 
EnumSet               O(1)     O(1)     O(1) 
TreeSet               O(log n) O(log n) O(log n)
ConcurrentSkipListSet O(log n) O(log n) O(1)

नक्शा कार्यान्वयन:

                      get      containsKey next     Notes
HashMap               O(1)     O(1)        O(h/n)   h is the table capacity
LinkedHashMap         O(1)     O(1)        O(1) 
IdentityHashMap       O(1)     O(1)        O(h/n)   h is the table capacity 
EnumMap               O(1)     O(1)        O(1) 
TreeMap               O(log n) O(log n)    O(log n) 
ConcurrentHashMap     O(1)     O(1)        O(h/n)   h is the table capacity 
ConcurrentSkipListMap O(log n) O(log n)    O(1)

कतार कार्यान्वयन:

                      offer    peek poll     size
PriorityQueue         O(log n) O(1) O(log n) O(1)
ConcurrentLinkedQueue O(1)     O(1) O(1)     O(n)
ArrayBlockingQueue    O(1)     O(1) O(1)     O(1)
LinkedBlockingQueue   O(1)     O(1) O(1)     O(1)
PriorityBlockingQueue O(log n) O(1) O(log n) O(1)
DelayQueue            O(log n) O(1) O(log n) O(1)
LinkedList            O(1)     O(1) O(1)     O(1)
ArrayDeque            O(1)     O(1) O(1)     O(1)
LinkedBlockingDeque   O(1)     O(1) O(1)     O(1)

java.util पैकेज के लिए जावाडोक के नीचे कुछ अच्छे लिंक हैं:





big-o