पुश कितने कुशल हैं!() और जूलिया में तरीकों को जोड़ना?

Question

this पृष्ठ पर यह कहता है कि push!() और append!() बहुत प्रभावी हैं।

मेरा सवाल यह है कि वे वास्तव में कितने कुशल हैं?

अर्थात्

यदि एक अंतिम सरणी के आकार को जानता है, यह अभी भी सरणी preallocate या यह संवर्द्धित बढ़ रही append!()/push!() का उपयोग कर बस के रूप में कुशल हो जाएगा करने के लिए तेजी से होता है?

अब इस मामले पर विचार करें जब एक अंतिम सरणी का आकार नहीं जानता है। उदाहरण के लिए, एकाधिक एरे को 1 बड़े सरणी में विलय करना (इसे A पर कॉल करें)। इस लक्ष्य को हासिल करने के लिए

दो तरीके:

1. append!()A करने के लिए प्रत्येक सरणी, जिसका आकार पूर्व आबंटित नहीं किया गया है आईएनजी।
2. मर्ज किए गए सरणी A के अंतिम आकार को खोजने के लिए प्रत्येक सरणी के पहले योग आयाम। फिर A प्रीलोकेट करें और प्रत्येक सरणी की सामग्री पर प्रतिलिपि बनाएँ।

इस मामले में कौन सा अधिक कुशल होगा?

Answer 1

इस तरह के एक प्रश्न का उत्तर आमतौर पर है: "यह निर्भर करता है"। उदाहरण के लिए, आप किस आकार सरणी को बनाने की कोशिश कर रहे हैं? सरणी का तत्व-प्रकार क्या है?

लेकिन यदि आप एक ह्युरिस्टिक के बाद हैं, तो एक साधारण गति परीक्षण क्यों नहीं चलाते? उदाहरण के लिए, निम्नलिखित स्निपेट:

function f1(N::Int) 
    x = Array(Int, N) 
    for n = 1:N 
     x[n] = n 
    end 
    return(x) 
end 

function f2(N::Int) 
    x = Array(Int, 0) 
    for n = 1:N 
     push!(x, n) 
    end 
    return(x) 
end 

f1(2) 
f2(2) 

N = 5000000000 
@time f1(N) 
@time f2(N) 

पता चलता है कि push! उपयोग के बारे में 6 बार पूर्व के आवंटन की तुलना में धीमी है। यदि आप कम चरणों के साथ बड़े ब्लॉक जोड़ने के लिए append! का उपयोग कर रहे थे, तो गुणक लगभग निश्चित रूप से कम होगा।

जब इन नंबरों की व्याख्या, "क्या !? 6 गुना धीमी !?" के घुटने झटका प्रतिक्रिया का विरोध। इस संख्या को संदर्भ में रखा जाना चाहिए कि आपके पूरे कार्यक्रम/फ़ंक्शन/सबराउटिन के लिए सरणी निर्माण कितना महत्वपूर्ण है। उदाहरण के लिए, यदि सरणी इमारत अपनी दिनचर्या का रन-टाइम का केवल 1% (सबसे विशिष्ट दिनचर्या के लिए, सरणी इमारत ज्यादा 1% से कम होंगे), तो 100 सेकंड के लिए अपनी दिनचर्या रन, 1 सेकंड खर्च कर रहा है, तो शामिल निर्माण सरणी 6 सेकंड प्राप्त करने के लिए 6 से गुणा करें। 99 सेकंड + 6 सेकंड = 105 सेकंड। इसलिए, प्री-आवंटन के बजाय push! का उपयोग करके आपके पूरे कार्यक्रम के रनटाइम को 5% तक बढ़ा दिया जाता है। जब तक आप उच्च आवृत्ति व्यापार में काम नहीं करते हैं, तो आप शायद इसके बारे में परवाह नहीं करेंगे।

अपने आप के लिए, मेरे सामान्य नियम यह है: अगर मैं कर सकते हैं पूर्व आवंटित आसानी से, तो मैं पहले से आवंटित। लेकिन अगर push! दिनचर्या बहुत कोड के लिए आसान, शुरू कीड़े के निचले संभावना के साथ, और कम उचित सरणी आकार पूर्व निर्धारित करने के लिए कोशिश कर रहा है चारों ओर खिलवाड़ करता है, तो मैं push! एक दूसरे सोचा के बिना उपयोग करें।

अंतिम नोट: यदि आप वास्तव में कैसे काम करता है push! की बारीकियों को देखने के लिए चाहते हैं, आप के बाद से julia source सिर्फ एक ccall लपेटता सी दिनचर्या में तल्लीन करने की आवश्यकता होगी।

अद्यतन: ओपी टिप्पणी में push! के बीच का अंतर और MATLAB में array(end+1) = n की तरह एक ऑपरेशन पर सवाल उठाया। मैंने हाल ही में MATLAB में कोड नहीं किया है, लेकिन मैं अपनी मशीन पर एक प्रतिलिपि रखता हूं क्योंकि मेरे सभी पुराने कागजात के लिए कोड MATLAB में है। मेरा वर्तमान संस्करण R2014a है। मेरी समझ यह है कि MATLAB के इस संस्करण में, सरणी के अंत में जोड़ने से संपूर्ण सरणी को फिर से आवंटित किया जाएगा। इसके विपरीत, जूलिया में push! काम करता है, मेरे सर्वोत्तम ज्ञान के लिए, .NET में सूचियों की तरह। वेक्टर के आवंटित स्मृति को गतिशील रूप से ब्लॉक में जोड़ा जाता है क्योंकि वेक्टर के आकार बढ़ते हैं। यह बड़े आवंटन की मात्रा को बड़े पैमाने पर कम करता है जिसे करने की आवश्यकता है, हालांकि मेरी समझ यह है कि कुछ पुनः आवंटन अभी भी जरूरी है (मुझे इस बिंदु पर सही होने में खुशी है)। तो push! को मैटलैब में एक सरणी जोड़ने से अधिक काम करना चाहिए।

N = 10000000; 
tic 
x = ones(N, 1); 
for n = 1:N 
    x(n) = n; 
end 
toc 


N = 10000000; 
tic 
x = []; 
for n = 1:N 
    x(end+1) = n; 
end 
toc 

मैं:

Elapsed time is 0.407288 seconds. 
Elapsed time is 1.802845 seconds. 

5 बार मंदी के बारे में तो, तो हम निम्नलिखित MATLAB कोड चला सकते हैं। समय पद्धति में लागू चरम गैर-कठोरता को देखते हुए, कोई यह कहने का लुत्फ उठा सकता है कि यह जूलिया मामले के बराबर है। लेकिन प्रतीक्षा करें, अगर हम जूलिया में व्यायाम को N = 10000000 के साथ फिर से चलाते हैं, तो समय 0.01 और 0.07 सेकंड होते हैं। MATLAB संख्याओं के लिए इन संख्याओं की परिमाण में तीव्र अंतर मुझे हुड के तहत वास्तव में क्या हो रहा है, इस बारे में दावा करने के बारे में बहुत परेशान करता है, और क्या MATLAB में 5-बार की मंदी की तुलना में 6 गुना मंदी की तुलना करना वैध है या नहीं जूलिया। असल में, अब मैं अपनी गहराई से बाहर हूं। हो सकता है कि कोई ऐसा व्यक्ति जो मैडलब वास्तव में हुड के तहत करता है, और अधिक अंतर्दृष्टि प्रदान कर सकता है। जूलिया के बारे में, मैं सी-कोडर का अधिकतर नहीं हूं, इसलिए मुझे संदेह है कि मुझे स्रोत के माध्यम से देखने में बहुत अंतर्दृष्टि मिलेगी (जो सार्वजनिक रूप से उपलब्ध है, MATLAB के विपरीत)।

Answer 2

push! हमेशा एक पूर्व आवंटित सरणी में डालने, की तुलना में धीमी हो सकता है अगर कोई अन्य कारण से push! (1) तत्व सम्मिलित करता है, बस के रूप में जब आप ऐसा मैन्युअल रूप से करना, और (2) सरणी की लंबाई वृद्धि कर देता है के लिए । दो ऑपरेशन एक से अधिक तेज़ नहीं हो सकते हैं, जब कोई दो का हिस्सा होता है।

हालांकि, जैसा कि अन्य उत्तरों में बताया गया है कि अंतर अक्सर चिंतित होने के लिए इतना बड़ा नहीं होता है। आंतरिक रूप से (पिछली बार मैंने कोड की जांच की), जूलिया एक बढ़ती-ए-फैक्टर-ऑफ-2 रणनीति का उपयोग करती है, ताकि आपको केवल log2(N) पुनर्वितरण की आवश्यकता हो।

यदि आप पहले से ही सरणी का आकार जानते हैं, तो आप sizehint! का उपयोग करके पुनर्वितरण को खत्म कर सकते हैं। चूंकि आप आसानी से अपने लिए परीक्षण कर सकते हैं, यह एक प्रीलोकेटेड सरणी में सम्मिलन के सापेक्ष प्रदर्शन दंड को खत्म नहीं करता है, लेकिन यह इसे कम कर सकता है।