समय जटिलता या जावा में <Array Name> .length की छिपी लागत

मैं जावा में एक परियोजना को देख रहा था और एक for पाश जो नीचे की तरह लिखा गया था पाया:समय जटिलता या जावा में <Array Name> .length की छिपी लागत

for(int i=1; i<a.length; i++) 
{ 
    ........... 
    ........... 
    ........... 
}

मेरा प्रश्न है: यह महंगा गणना करने के लिए है a.length (यहां एक सरणी नाम है)? यदि नहीं, तो a.length को आंतरिक रूप से गणना कैसे की जा रही है (इसका मतलब है कि JVM कैसे सुनिश्चित करता है कि ओ (1) इस तक पहुंच)? जैसा है:

int length = a.length; 
for(int i=1; i<length; i++) 
{ 
    ........... 
    ........... 
    ........... 
}

यानी फ़ंक्शन के अंदर स्थानीय चर के मूल्य तक पहुंचने की तरह। धन्यवाद।

स्रोत

2013-08-01 Trying

समय स्थिर है लेकिन संभवतः यह एक स्टैक वैरिएबल में लंबाई को संग्रहीत करने से थोड़ा सा धीमा है। मुझे इस पर संदेह है क्योंकि जेवीएम को सरणी में जाना है और फिर लंबाई प्राप्त करना है। लेकिन यह सरणी तत्वों को स्कैन नहीं करता है और उन्हें गिनता है। –

देखें http://stackoverflow.com/questions/5950155/how-is-length-implemented-in-java-arrays – Shoe

'a.length'" गणना "नहीं हो रहा है, यह एक अंतिम क्षेत्र है। – arshajii

मेरा प्रश्न है: यह a.length गणना करने के लिए

नहीं, ये सरणी पर सिर्फ एक क्षेत्र है (JLS section 10.7 देखें) महंगा है। यह महंगा नहीं है, और जेवीएम जानता है कि यह कभी नहीं बदलेगा और लूप को उचित रूप से अनुकूलित कर सकता है। (दरअसल, मैं उम्मीद करता हूं कि एक अच्छा जेआईटी एक गैर-ऋणात्मक संख्या वाले चर को प्रारंभ करने के सामान्य पैटर्न को नोटिस करेगा, यह जांचें कि यह length से कम है और फिर सरणी तक पहुंच - यदि यह नोटिस करता है, तो यह सरणी सीमा जांच को हटा सकता है।)

स्रोत

2013-08-01 15:34:08

'यह सरणी पर सिर्फ एक फ़ील्ड है'। इसका क्या मतलब है?सरणी एक कंटेनर नहीं है जिसमें एक फ़ील्ड होगा। क्या आप समझा सकते हैं? आपके प्रयास के लिए धन्यवाद। – Trying

@ ट्राइंग क्या आपने लिंक खोला है और दूसरी पंक्ति पढ़ी है? – assylias

@assylias ya। और लाइन में संदेह है 'सरणी की लंबाई अंतिम उदाहरण परिवर्तनीय लंबाई के रूप में उपलब्ध है।' यह कैसे संभाला जाता है मेरा संदेह है। धन्यवाद। – Trying

a.length गणना नहीं है लेकिन केवल सरणी के भीतर आयोजित फ़ील्ड तक पहुंच है। उस तरह के पढ़ने का ऑपरेशन सुपर फास्ट है।

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

संभावित गति अंतर यहां नैनोसेकंड में है (संभवतः बिना "एस")।

स्रोत

2013-08-01 15:34:15 assylias

इसे 'jmh' के माध्यम से चलाएं :) –

मैंने इसे चलाया है, और आपका अनुमान लगभग सही था: यह * * * के साथ है, अर्थात् * शून्य नैनोसेकंड * :) –

@ मार्कोटोपॉलिक मेरी टिप्पणी जेआईटी से पहले प्रदर्शन पर थी! मुझे लगता है कि अगर आप ऊब महसूस करते हैं तो संकलन को रोकने के लिए कहीं भी एक विकल्प है! – assylias

जावा सरणी में तय किया गया है। एक बार जब आप इसे घोषित कर लेंगे तो आप स्मृति में उस सरणी के आकार को नहीं बदल सकते हैं (यदि आपने सरणी आकार बदलने की कोशिश की है तो यह स्मृति में एक नई सरणी बना देगा)।

इस वजह से हमें ओ (1) लंबाई लुकअप मिलता है। जैसा कि हम सरणी की स्मृति में कुल आकार जानते हैं। यदि हम पहली अनुक्रमणिका की स्मृति में आकार को भी देखते हैं तो हम ओ (1) गति पर लंबाई प्राप्त करने के लिए त्वरित गणना कर सकते हैं। कोई बात नहीं कितना बड़ा हमारे सरणी है के रूप में, अपने जाने वाले स्मृति में आकार देखने के लिए समय की एक ही राशि लेने के लिए और पहले सूचकांक के आकार

स्रोत

2013-08-01 15:34:58 zidsal

देखने एक सरणी में, lengthList.size() में के रूप में एक समारोह नहीं है। जब आप जावा में एक सरणी बनाते हैं, तो इसकी लंबाई स्थिर होती है। तो लागत कम से कम

स्रोत

2013-08-01 15:36:10

list.size() अधिकांश सूची कार्यान्वयन के लिए एक साधारण गेटर है। – assylias

आपकी सुविधा के लिए, मैंने इसे माइक्रोबेंमार्क किया है। कोड:

public class ArrayLength 
{ 
    static final boolean[] ary = new boolean[10_000_000]; 
    static final Random rnd = new Random(); 
    @GenerateMicroBenchmark public void everyTime() { 
    int sum = rnd.nextInt(); 
    for (int i = 0; i < ary.length; i++) sum += sum; 
    } 
    @GenerateMicroBenchmark public void justOnce() { 
    int sum = rnd.nextInt(); 
    final int length = ary.length; 
    for (int i = 0; i < length; i++) sum += sum; 
    } 
}

परिणाम:

Benchmark      Mode Thr Cnt Sec   Mean Mean error Units 
o.s.ArrayLength.everyTime thrpt 1  3 5 40215.790  1490.800 ops/msec 
o.s.ArrayLength.justOnce  thrpt 1  3 5 40231.192  966.007 ops/msec

सारांश: कोई पता लगाने योग्य परिवर्तन।

स्रोत

2013-08-01 16:05:27

@MarkoTopolnik प्रयास की सराहना करते हैं। धन्यवाद। +1। – Trying

समय जटिलता या जावा में <Array Name> .length की छिपी लागत

उत्तर

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