2009-10-02 11 views
37

list.size()>0 जावा में list.isEmpty() से धीमा क्यों है? दूसरे शब्दों पर isEmpty()size()>0 से अधिक बेहतर है?जावा में list.isEmpty() से list.size()> 0 धीमी क्यों है?

जब मैं ArrayList में कार्यान्वयन को देखो, तो यह गति की तरह दिखता है एक ही होना चाहिए:

ArrayList.size()

/** 
    * Returns the number of elements in this list. 
    * 
    * @return the number of elements in this list 
    */ 
    public int size() { 
     return size; 
    } 

ArrayList.isEmpty()

/** 
    * Returns <tt>true</tt> if this list contains no elements. 
    * 
    * @return <tt>true</tt> if this list contains no elements 
    */ 
    public boolean isEmpty() { 
     return size == 0; 
    } 

यदि हम समय लेने के लिए बस एक साधारण कार्यक्रम लिखते हैं वाई दोनों विधियों, उस मामले size() सभी मामलों में isEmpty() ले जाएगा, ऐसा क्यों?

यहां मेरा टेस्टकोड है;

import java.util.List; 
import java.util.Vector; 

public class Main { 
    public static void main(String[] args) { 
     List l=new Vector(); 
     int i=0; 
     for(i=0;i<10000;i++){ 
      l.add(new Integer(i).toString()); 
     } 
     System.out.println(i); 
     Long sTime=System.nanoTime(); 
     l.size(); 
     Long eTime=System.nanoTime(); 
     l.isEmpty(); 
     Long eeTime=System.nanoTime(); 
     System.out.println(eTime-sTime); 
     System.out.println(eeTime-eTime); 
    } 
} 

यहां सभी मामलों में eTime-sTime>eeTime-eTime। क्यूं कर?

उत्तर

46

आपका परीक्षण कोड त्रुटिपूर्ण है।

बस ऑर्डर को उलट दें, यानी कॉल पहले और आकार> 0 सेकंड है और आपको विपरीत परिणाम मिलेगा। यह वर्ग लोडिंग, कैशिंग, आदि के कारण है

+1

@JLR: हां मैं आपके बिंदु को स्वीकार करता हूं, जैसा कि दोष था 2 अलग-अलग परियोजनाओं में दोनों तरीकों का परीक्षण किया गया और दोनों बहुत ही समान परिणाम दे रहे हैं। मेरी संदेह –

1

किसी लिंक की गई सूची में आइटमों की गणना करना बहुत धीमा हो सकता है।

+0

@spdenme: लेकिन इसकी गिनती नहीं, इसकी सिर्फ एक मूल्य लौटने? –

+0

आपके उदाहरण में आपके पास एक * ArrayList * –

+0

सूची एक इंटरफ़ेस है। यह कैसे लागू किया जाता है उन दो तरीकों के सापेक्ष प्रदर्शन को प्रभावित करता है। चूंकि आकार() को अक्सर एक बार कहा जाता है, अधिकांश कार्यान्वयन का निर्धारण होता है कि आकार के क्षेत्र को बनाए रखने की लागत सार्थक है। –

66

के लिए ArrayList एस, हाँ - आप सही हैं कि ऑपरेशन एक ही समय में (लगभग) लेते हैं।

सूची के अन्य कार्यान्वयन के लिए - बेवकूफ लिंक्ड सूचियां *, उदाहरण के लिए - आकार की गिनती बहुत लंबा समय ले सकती है, जबकि आप केवल वास्तव में देखभाल करते हैं कि यह शून्य से अधिक है या नहीं।

तो यदि आप पूरी तरह से जानते हैं कि सूची ArrayList का कार्यान्वयन है और कभी भी कभी नहीं बदलेगी तो इससे वास्तव में कोई फर्क नहीं पड़ता; लेकिन:

  1. यह एक विशिष्ट कार्यान्वयन के लिए स्वयं को टालने के लिए वैसे भी खराब प्रोग्रामिंग अभ्यास है।
  2. बातें कोड पुनर्गठन के साथ लाइन नीचे कुछ साल बदलते हैं, तो परीक्षण दिखाएगा कि "यह काम करता है" लेकिन बातों से पहले
  3. यहां तक ​​कि सबसे अच्छा मामले में, size() == 0 अभी भी से isEmpty() तेजी से नहीं है कम कुशलता से चल रहे हैं , इसलिए पूर्व का उपयोग करने के लिए कोई अनिवार्य कारण नहीं है।
  4. isEmpty यह एक स्पष्ट परिभाषा है कि आप वास्तव में किस चीज की परवाह करते हैं और परीक्षण कर रहे हैं, और इसलिए आपका कोड थोड़ा अधिक समझ में आता है।

(इसके अलावा, मैं शून्य के उपयोग आपके सवाल का शीर्षक में संशोधन चाहते हैं; सवाल ही है, और ये कार्यवाही, के साथ किसी भी वस्तु के संदर्भ अशक्त हैं कि क्या लेना देना नहीं है।)

* मैं मूल रूप से LinkedList लिखा, जो कि java.util.LinkedList का संदर्भ दे रहा है, हालांकि यह विशेष कार्यान्वयन इसकी लंबाई को स्पष्ट रूप से स्टोर करता है, आकार() को ओ (1) ऑपरेशन यहां बना देता है। एक और बेवकूफ लिंक्ड सूची ऑपरेशन ऐसा नहीं कर सकता है, और अधिक सामान्य अर्थ में सूची के कार्यान्वयन पर कोई दक्षता गारंटी नहीं है।

+5

"" 'LinkedList' (' java.util.LinkedList' a.k.a) भी इसके आकार को संग्रहीत करता है तो 'आकार()' कॉल बस के रूप में तेजी से 'ArrayList' के लिए के रूप में है, लेकिन सामान्य बात अभी भी बहुत ही वैध है। –

+0

@dtszzs: रन टाइम, एक ही नहीं है thats मैं क्या परीक्षण किया है और सिर्फ मुझे असहज बना .. –

+4

@Sam रूडोल्फ: आप इसे कैसे परीक्षण किया? ऐसे microbenchmarks गलत पाने के हजारों तरीके हैं। –

2

उन दो कार्यान्वयनों को देखते हुए, गति एक जैसी होनी चाहिए, यह सच है।

लेकिन इन तरीकों के लिए अब तक केवल एक ही संभावित कार्यान्वयन नहीं है। उदाहरण के लिए एक प्राइमेटेड लिंक्ड लिस्ट (एक जो आकार को अलग से स्टोर नहीं करता है) isEmpty()size() कॉल से बहुत तेज़ उत्तर दे सकता है।

इससे भी महत्वपूर्ण बात: isEmpty(), वास्तव में अपने इरादे का वर्णन करता है, जबकि size()==0 अनावश्यक रूप से जटिल है (बेशक बेहद नहीं जटिल है, लेकिन किसी भी अनावश्यक जटिलता बिल्कुल परहेज किया जाना चाहिए)।

+0

but6 अगर आप वहां कार्यान्वयन देखते हैं, तो वे बहुत ही सरल दिखते हैं? –

+0

जिन्हें आप देखते हैं, हां। लेकिन जैसा कि @ dtsazza ने बहुत अच्छी तरह से समझाया: कार्यान्वयन एकमात्र महत्वपूर्ण बात नहीं है, इरादा और पठनीयता भी महत्वपूर्ण है। और अन्य कलेक्टन कार्यान्वयन हो सकते हैं जहां 'आकार()' को इतनी आसानी से कार्यान्वित नहीं किया जा सकता है ('कमजैश मैप' या अन्य गतिशील संग्रह)। –

5

तुमने कहा था:

सभी मामलों क्यों में

यहाँ eTime-sTime>eeTime-eTime?

सबसे पहले, यह शायद आपके परीक्षण कोड के कारण है। आप l.size() और l.isEmpty() को एक ही समय में कॉल करने की गति का परीक्षण नहीं कर सकते हैं, क्योंकि वे दोनों एक ही मान पूछते हैं। सबसे अधिक संभावना है l.size() ने आपके सीपीयू कैश में अपनी सूची का आकार लोड किया है और परिणामस्वरूप l.isEmpty() को कॉल करना बहुत तेज है।

आप l.size बुला() लाख बार और l.isEmpty() दो अलग-अलग कार्यक्रमों लेकिन सिद्धांत रूप में में लाख बार के एक जोड़े की एक जोड़ी संकलक केवल आपके जाएं, क्योंकि वे सभी कॉल्स दूर का अनुकूलन सकता है 'की कोशिश कर सकते वास्तव में परिणाम के साथ कुछ भी नहीं कर रहे हैं।

किसी भी मामले में, दोनों के बीच प्रदर्शन अंतर नगण्य होगा, विशेष रूप से जब आप यह तुलना करने के लिए तुलना करते हैं कि सूची खाली है या नहीं (l.size() == 0)। सबसे अधिक संभावना उत्पन्न कोड लगभग पूरी तरह से समान दिखेंगे। जैसा कि कुछ अन्य पोस्टर ने नोट किया है, आप इस मामले में पठनीयता के लिए अनुकूलन करना चाहते हैं, गति नहीं।

संपादित करें: मैंने इसे स्वयं परीक्षण किया। यह काफी टॉस-अप है। size() और isEmpty()Vector पर प्रयुक्त लंबे समय तक अलग-अलग परिणाम दिए, न ही लगातार दूसरे को हराया। ArrayListsize() पर चलने पर तेज़ लग रहा था, लेकिन बहुत अधिक नहीं। यह संभवतः इस तथ्य के कारण है कि Vector तक पहुंच सिंक्रनाइज़ है, इसलिए इन तरीकों तक पहुंच को बेंचमार्क करने का प्रयास करते समय आप वास्तव में क्या देख रहे हैं सिंक्रनाइज़ेशन ओवरहेड है, जो बहुत संवेदनशील हो सकता है।

यहां ले जाने की बात यह है कि जब आप निष्पादन समय में कुछ नैनोसेकंड अंतर के साथ एक विधि कॉल को अनुकूलित करने का प्रयास कर रहे हैं, तो आप गलत कर रहे हैंLong एस का उपयोग करने की तरह, मूल रूप से मूल बातें प्राप्त करें, जहां आपको long का उपयोग करना चाहिए।

+0

वास्तव में नहीं, मैं सिर्फ अलग-अलग कार्यक्रमों में दो मामलों को चलाता हूं, केवल संदेह को साफ़ करने के लिए और परिणाम एक ही आकार() है() –

15

मुझे खेद है, लेकिन आपका बेंचमार्क त्रुटिपूर्ण है। बेंचमार्क तक पहुंचने के तरीके के बारे में सामान्य विवरण के लिए Java theory and practice: Anatomy of a flawed microbenchmark पर एक नज़र डालें।


अद्यतन: एक उचित बेंचमार्क के लिए आप Japex ध्यान देना चाहिए।

+0

Java.net समाशोधन के लिए Thanx अभी नीचे हो रहा है। –

0

सामान्य रूप से कहना असंभव है कि यह तेज़ है, क्योंकि यह इंटरफ़ेस List का कार्यान्वयन करने पर निर्भर करता है।

मान लीजिए कि हम ArrayList के बारे में बात कर रहे हैं। ArrayList के स्रोत कोड देखने, आप फ़ाइल अपने JDK स्थापना निर्देशिका में src.zip में पा सकते हैं। तरीकों isEmpty और size के रूप में लग रहा है के स्रोत कोड (Windows के लिए सूर्य JDK 1.6 अद्यतन 16) इस प्रकार है:

public boolean isEmpty() { 
    return size == 0; 
} 

public int size() { 
    return size; 
} 

आप आसानी से देख सकते हैं कि दोनों भाव isEmpty() और size() == 0 नीचे बिल्कुल वैसा ही बयान करने के लिए है, तो एक आ जाएगा निश्चित रूप से दूसरे की तुलना में तेज़ नहीं है।

यदि आप रुचि रखते हैं कि यह इंटरफ़ेस List के अन्य कार्यान्वयन के लिए कैसे काम करता है, तो स्रोत कोड को स्वयं देखें और पता लगाएं।

1

पीएमडी (स्थिर नियमसेट आधारित जावा स्रोत कोड विश्लेषक) के अनुसार है (लक्षण) पसंद है। आप पीएमडी नियम यहां पा सकते हैं। "UseCollectionIsEmpty" नियम के लिए खोजें।

http://pmd.sourceforge.net/rules/design.html

मेरे हिसाब से यह भी आकार() == 0 का उपयोग करके संपूर्ण स्रोत कोड संगत के बजाय() isEmpty का उपयोग कर लोगों को और बाकी के आधे रखने में मदद मिलती।

2

.size() को पूरी सूची को देखना है, जबकि .isEmpty() पहले पर रोक सकता है।

स्पष्ट रूप से कार्यान्वयन निर्भर है, लेकिन जैसा कि पहले कहा गया है, अगर आपको वास्तविक आकार जानने की आवश्यकता नहीं है, तो सभी तत्वों की गिनती क्यों परेशान करें?

संबंधित मुद्दे