कितना समय लगता है एक सरणी आवंटित करने के लिए (जावा में) ले करता है सरणी आवंटन, मुख्य रूप से जावा में लेकिन मुझे लगता है कि यह सब प्रोग्रामिंग भाषाओं के लिए प्रासंगिक है के बारे में

Question

बस एक सामान्य प्रश्न:

में कितना समय लगता स्मृति को आबंटित करने ले करता है आकार एन की एक सरणी के लिए [ओ (एन) के संदर्भ में]? मैं एक कार्यान्वयन की कल्पना कर सकता हूं जहां स्मृति आवंटन निरंतर समय में होता है: यदि आपके पास बड़ी मात्रा में रिक्त स्मृति है तो आप केवल नई सरणी के पहले और अंतिम सूचकांक में सूचक बना सकते हैं, लेकिन यह है कि स्मृति को आम तौर पर आवंटित किया जाता है? (साथ ही, जावा में कम से कम, यदि आप पूर्णांक की सरणी प्रारंभ करते हैं, तो सरणी में सभी मान प्रारंभ में 0 पर सेट किए जाते हैं; इसका मतलब यह है कि सरणी में प्रत्येक इंडेक्स अलग-अलग 0 के बराबर सेट होते हैं, जो होगा ऑपरेशन ओ (एन) बनाओ?)

धन्यवाद।

Answer 1

मैं सिर्फ हॉटस्पॉट पर एक micro benchmark दौड़ा - पोस्ट JIT संकलन, एक सरणी (एक i7 पर) का आवंटन लेता है:

• लगभग 10 एनएस आकार 1 की एक सरणी के लिए
• चारों ओर के लिए 400 एनएस आकार की एक सरणी के लिए आकार 10,000
• की एक सरणी 300,000 एनएस आसपास 1.000.000

तो अपने सवाल का जवाब देने, यह अनुभवजन्य प्रतीत होता है कि यह ओ (एन) हॉटस्पॉट पर है।

विस्तृत परिणाम:

Benchmark        Mode Thr Cnt Sec   Mean Mean error Units 
c.a.p.ArrayVsList.createArray1   avgt 1  5 2  12.293  0.867 nsec/op 
c.a.p.ArrayVsList.createArray10000  avgt 1  5 2  428.369  9.997 nsec/op 
c.a.p.ArrayVsList.createArray1M  avgt 1  5 2 342972.975  7253.989 nsec/op 

• जावा में एक वस्तु बनाने, यदि आपका ढेर काफी बड़ी है, लगभग मुक्त है
• (यह मोटे तौर पर एक सूचक offsetting में होते हैं), लेकिन JVM बेसब्री से करने लगता है समय सरणी
• अन्य JVMs बनाई गई है एक lazier प्रारंभ प्रदर्शन कर सकती है पर (एक आदिम के लिए या 0) null सभी आइटम आरंभ

Answer 2

आपने पहले से ही प्रश्न का उत्तर दिया है, यह जावा में O(n) है क्योंकि तत्व प्रारंभ किए गए हैं, जबकि ऐसी भाषाएं हैं जहां यह ऑपरेशन O(1) है क्योंकि प्रारंभिकरण नहीं है।

और बस सुनिश्चित

public class ArrayTest { 

    public static void main(String[] args) { 
    int[] var = new int[5]; 
    } 

} 

public class ArrayTest extends java.lang.Object{ 
public ArrayTest(); 
    Code: 
    0: aload_0 
    1: invokespecial #1; //Method java/lang/Object."<init>":()V 
    4: return 

public static void main(java.lang.String[]); 
    Code: 
    0: iconst_5 
    1: newarray int 
    3: astore_1 
    4: return 

} 

पैदा करता है और प्रलेखन कहते हैं होने के लिए के बारे में newarray:

एक नई सरणी जिसका घटकों प्रकार atype की और लंबाई के होते हैं गिनती एकत्रित ढेर से आवंटित गिनती है। पर एक संदर्भ सरणी यह ​​नया सरणी ऑब्जेक्ट ऑपरेंड स्टैक में धक्का दिया जाता है। प्रत्येक नए सरणी के तत्व सरणी के प्रकार (§2.5.1) के लिए डिफ़ॉल्ट प्रारंभिक मान में प्रारंभ किया गया है।

Answer 3

AFAIK, सरणी आवंटन हमेशा आपके पास अधिकतम आकार तक ओ (एन) होता है। ऐसा इसलिए है क्योंकि स्मृति को शून्य करने की लागत ओ (एन) भी है। इस गति को तेज करने के लिए सिस्टम कुछ चाल कर सकता है। यानी यह प्रत्येक बाइट को शून्य करने की आवश्यकता नहीं है, यह कुछ वर्चुअल मेमोरी चाल का उपयोग करके पूरे पृष्ठों को शून्य कर सकता है, लेकिन यहां तक ​​कि यह ओ (एन) भी है।