अजगर/NumPy: चल रहे योग को लागू करने (लेकिन काफी नहीं)

Question

को देखते हुए समान अवधि की दो सरणियों, एक होल्डिंग डेटा, एक परिणाम पकड़े लेकिन शुरू में शून्य पर सेट है, जैसे हैं:

a = numpy.array([1, 0, 0, 1, 0, 1, 0, 0, 1, 1]) 
b = numpy.array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0]) 

मैं था ए में तीन आसन्न तत्वों के सभी संभावित सबसेट्स की गणना की गणना करना। यदि योग 0 या 1 है, तो बी में तीन संबंधित तत्व अपरिवर्तित छोड़ दिए गए हैं; , ख है

for x in range(len(a)-2): 
    if a[x:x+3].sum() > 1: 
     b[x:x+3] = 1 

इस के बाद: केवल तभी योग 1 से अधिक है, ताकि बाद गणना ख

array([0, 0, 0, 1, 1, 1, 0, 1, 1, 1]) 

एक साधारण पाश यह पूरा होगा बन जाता है, 1 करने के लिए ख सेट में तीन इसी तत्व हैं वांछित रूप।

मुझे इसे बड़ी मात्रा में डेटा के लिए करना है, इसलिए गति एक मुद्दा है। ऊपर ऑपरेशन करने के लिए NumPy में एक तेज तरीका है?

(मुझे लगता है कि यह एक संकल्प के समान है, लेकिन काफी समान नहीं है)।

Answer 1

तुम एक घुमाव के साथ शुरू कर सकते, मूल्यों है कि 1 से अधिक चुनें और अंत में एक "फैलाव" का उपयोग करें:

b = numpy.convolve(a, [1, 1, 1], mode="same") > 1 
b = b | numpy.r_[0, b[:-1]] | numpy.r_[b[1:], 0] 

के बाद से इस अजगर पाश से बचा जाता है, यह तेजी से अपने दृष्टिकोण से किया जाना चाहिए, लेकिन मैं समय नहीं किया

एक वैकल्पिक फैलने के लिए एक दूसरी घुमाव के उपयोग करने के लिए है:

kernel = [1, 1, 1] 
b = numpy.convolve(a, kernel, mode="same") > 1 
b = numpy.convolve(b, kernel, mode="same") > 0 

आप SciPy उपलब्ध है, तो अभी तक फैलाव के लिए एक और विकल्प

b = numpy.convolve(a, [1, 1, 1], mode="same") > 1 
b = scipy.ndimage.morphology.binary_dilation(b) 

संपादित है: some timings करने से, मैंने पाया कि यह समाधान बड़े सरणी के लिए सबसे तेज़ प्रतीत होता है:

b = numpy.convolve(a, kernel) > 1 
b[:-1] |= b[1:] # Shift and "smearing" to the *left* (smearing with b[1:] |= b[:-1] does not work) 
b[:-1] |= b[1:] # … and again! 
b = b[:-2] 

एक मिलियन प्रविष्टियों की एक सरणी के लिए, यह मेरी मशीन पर आपके मूल दृष्टिकोण से 200 गुना तेज था। जैसा कि टिप्पणियों में ईओएल द्वारा इंगित किया गया है, इस समाधान को थोड़ा नाजुक माना जा सकता है, हालांकि, यह न्यूम्पी के कार्यान्वयन विवरण पर निर्भर करता है।

Answer 2

आप के साथ एक कुशल तरीके से "घुमाव" रकम की गणना कर सकते हैं:

>>> a0 = a[:-2] 
>>> a1 = a[1:-1] 
>>> a2 = a[2:] 
>>> a_large_sum = a0 + a1 + a2 > 1 

अपडेट करना b तो कुछ का मतलब है कि लिख कर कुशलता से किया जा सकता है "तीन पड़ोसी a_large_sum मूल्यों के कम से कम एक सच है कि" : आप पहली बार आप a_large_sum सरणी वापस तत्वों की एक ही नंबर के लिए a के रूप में (दाएं से, बाईं ओर और सही करने के लिए बाईं ओर, और उसके बाद) का विस्तार:

>>> a_large_sum_0 = np.hstack([a_large_sum, [False, False]]) 
>>> a_large_sum_1 = np.hstack([[False], a_large_sum, [False]]) 
>>> a_large_sum_2 = np.hstack([[False, False], a_large_sum]) 

फिर आप 01 प्राप्त एक कुशल तरीके से:

>>> b = a_large_sum_0 | a_large_sum_1 | a_large_sum_2 

यह NumPy आंतरिक तेजी से छोरों का एक लाभ के माध्यम से परिणाम है कि आप प्राप्त देता है, लेकिन एक बहुत ही कुशल तरीके से,।

पीएस: यह दृष्टिकोण अनिवार्य रूप से स्वेन के पहले समाधान के समान ही है, लेकिन स्वेन के सुरुचिपूर्ण कोड से अधिक पैदल यात्री है; हालांकि, यह तेज़ है। स्वेन का दूसरा समाधान (डबल convolve()) और भी सुरुचिपूर्ण है, और यह दो गुना तेज है।

Answer 3

आप NumPy's stride_tricks पर भी एक नज़र डालना चाहेंगे। स्वेन के समय सेटअप (स्वेन के जवाब में लिंक देखें) का उपयोग करते हुए, मैंने पाया कि (बहुत) बड़े सरणियों के लिए, यह भी आप क्या चाहते हैं (a की अपनी परिभाषा के साथ यानी) करने के लिए एक तेजी से रास्ता है:

shape = (len(a)-2,3) 
strides = a.strides+a.strides 
a_strided = numpy.lib.stride_tricks.as_strided(a, shape=shape, strides=strides) 
b = np.r_[numpy.sum(a_strided, axis=-1) > 1, False, False] 
b[2:] |= b[1:-1] | b[:-2] 

संपादन के बाद (नीचे टिप्पणियां देखें) यह अब सबसे तेज़ तरीका नहीं है।

यह आपके मूल सरणी पर विशेष रूप से चरणबद्ध दृश्य बनाता है। a में डेटा कॉपी नहीं किया गया है, लेकिन इसे आसानी से एक नए तरीके से देखा जाता है। हम मूल रूप से एक नई सरणी बनाना चाहते हैं जिसमें अंतिम अनुक्रमणिका में उप-सरणी शामिल हों जिन्हें हम जोड़ना चाहते हैं (यानी वे तीन तत्व जिन्हें आप जोड़ना चाहते हैं)। इस तरह, हम अंतिम कमांड के साथ अंत में आसानी से योग कर सकते हैं।

इस नए आकार के अंतिम तत्व इसलिए 3 हो गया है, और पहले तत्व वर्ष a शून्य से 2 (क्योंकि हम केवल -2 nd तत्व को साथ जोड़ सकते हैं) की लंबाई हो जाएगा।

स्ट्रॉइड सूची में बाइट्स में स्ट्रिंग्स शामिल हैं, कि नई सरणी a_strided आकार के प्रत्येक आयाम में अगले तत्व को प्राप्त करने की आवश्यकता है। यदि आप इन बराबर सेट करते हैं, तो इसका मतलब है कि a_strided[0,1] और a_strided[1,0] दोनों a[1] होंगे, जो वही है जो हम चाहते हैं। एक सामान्य सरणी में यह मामला नहीं होगा (पहला चरण "आकार का पहला-आयाम समय लंबाई-का-सरणी-प्रथम-आयाम (= आकार [0])" होगा, लेकिन इस मामले में हम कर सकते हैं इसका अच्छा इस्तेमाल करें।

सुनिश्चित नहीं है कि मैंने यह सब वास्तव में अच्छी तरह से समझाया है, लेकिन केवल एक_स्ट्रैड प्रिंट करें और आप देखेंगे कि परिणाम क्या है और यह ऑपरेशन को कितना आसान बनाता है।