लूपिंग बीट इंडेक्सिंग क्यों यहां है?

Question

कुछ साल पहले, पर सक्रिय प्रयोजन व्यंजनों तुलनात्मक उद्देश्यों के लिए, तीन पायथन/न्यूमपी कार्यों; इनमें से प्रत्येक ने एक ही तर्क स्वीकार कर लिया और उसी परिणाम को वापस कर दिया, दूरी मैट्रिक्स।

इनमें से दो प्रकाशित स्रोतों से लिया गया था; वे दोनों हैं - या वे मुझे - idiomatic numpy कोड होने के लिए दिखाई देते हैं। दूरी मैट्रिक्स बनाने के लिए आवश्यक दोहराव की गणना numpy के सुरुचिपूर्ण इंडेक्स सिंटैक्स द्वारा संचालित होती है। यहाँ उनमें से एक है:

from numpy.matlib import repmat, repeat 

def calcDistanceMatrixFastEuclidean(points): 
    numPoints = len(points) 
    distMat = sqrt(sum((repmat(points, numPoints, 1) - 
      repeat(points, numPoints, axis=0))**2, axis=1)) 
    return distMat.reshape((numPoints,numPoints)) 

तीसरे दूरी मैट्रिक्स बनाया एकल लूप (जो, जाहिर दिया पाशन कि सिर्फ 1,000 2 डी अंक की दूरी मैट्रिक्स, एक लाख प्रविष्टियां हैं की एक बहुत कुछ है) का उपयोग कर। पहली नज़र में इस समारोह ने मुझे उस कोड की तरह देखा जो मैं लिखने के लिए इस्तेमाल करता था जब मैं न्यूम्पी सीख रहा था और मैं पहले पायथन कोड लिखकर न्यूमपी कोड लिखता था और फिर इसे लाइन से लाइन करता था।

सक्रिय राज्य पोस्ट के कई महीनों के बाद, तीनों की तुलना में प्रदर्शन परीक्षणों के परिणाम पोस्ट किए गए और न्यूमपी मेलिंग सूची पर thread में चर्चा की गई।

वास्तव में पाश के साथ समारोह में काफी से बेहतर प्रदर्शन किया अन्य दो:

: सूत्र में

from numpy import mat, zeros, newaxis 

def calcDistanceMatrixFastEuclidean2(nDimPoints): 
    nDimPoints = array(nDimPoints) 
    n,m = nDimPoints.shape 
    delta = zeros((n,n),'d') 
    for d in xrange(m): 
    data = nDimPoints[:,d] 
    delta += (data - data[:,newaxis])**2 
    return sqrt(delta) 

एक भागीदार (Keir Mierle) एक कारण है कि यह सच हो सकता है की पेशकश की मुझे संदेह है कि यह है कि इसमें बेहतर इलाका है, पर गणना करने से पहले अपेक्षाकृत छोटे काम करने वाले सेट को पूरी तरह से पूरा करने से पहले एक। एक लाइनर संभावित रूप से बड़ी एमएक्सएन सरणी प्रोसेसर में बार-बार खींचना है।

इस पोस्टर के अपने खाते से, उनकी टिप्पणी केवल एक संदेह है, और ऐसा नहीं लगता है कि इस पर चर्चा की गई थी।

इन परिणामों के लिए कैसे खाता है इसके बारे में कोई अन्य विचार?

विशेष रूप से, क्या एक उपयोगी नियम है - लूप और कब सूचकांक के बारे में - जिसे इस उदाहरण से निकाला जा सकता है, numpy code लिखने में मार्गदर्शन के रूप में?

उन लोगों के लिए जो NumPy से परिचित नहीं हैं, या जिन्होंने कोड को नहीं देखा है, यह तुलना किनारे के मामले पर आधारित नहीं है - यह निश्चित रूप से मेरे लिए यह दिलचस्प नहीं होगा। इसके बजाए, इस तुलना में एक ऐसा फ़ंक्शन शामिल है जो मैट्रिक्स गणना में एक सामान्य कार्य करता है (यानी, दो पूर्ववर्ती दिए गए परिणाम सरणी बनाना); इसके अलावा, प्रत्येक कार्य बदले में सबसे आम numpy अंतर्निर्मित के बीच शामिल है।

Answer 1

टीएल; डीआर उपरोक्त दूसरा कोड केवल बिंदुओं के आयामों की संख्या (3 डी बिंदुओं के लिए लूप के माध्यम से 3 गुना) पर लूपिंग है, इसलिए लूपिंग बहुत अधिक नहीं है। उपरोक्त दूसरे कोड में असली गति-अप यह है कि अंक के बीच मतभेदों को ढूंढते समय कुछ अतिरिक्त मैट्रिक्स बनाने से बचने के लिए यह बेहतर ढंग से नम्पी की शक्ति का उपयोग करता है। इससे स्मृति का उपयोग और कम्प्यूटेशनल प्रयास कम हो जाता है।

अधिक व्याख्या की मुझे लगता है कि calcDistanceMatrixFastEuclidean2 समारोह शायद अपने पाश के साथ आप को धोखा दे रहा है। यह केवल अंक के आयामों की संख्या पर लूपिंग है। 1 डी बिंदुओं के लिए, लूप केवल 2 डी, दो बार, और 3 डी के लिए, तीन बार निष्पादित करता है। यह वास्तव में बहुत लूपिंग नहीं है।

चलिए कोड को थोड़ा सा विश्लेषण करने के लिए विश्लेषण करते हैं कि एक दूसरे की तुलना में तेज़ क्यों है। calcDistanceMatrixFastEuclidean मैं fast1 और calcDistanceMatrixFastEuclidean2 पर कॉल करूंगा fast2 होगा।

fast1repmap फ़ंक्शन द्वारा प्रमाणित चीजों को करने के मैटलैब तरीके पर आधारित है। repmap फ़ंक्शन इस मामले में एक सरणी बनाता है जो केवल मूल डेटा बार-बार दोहराया जाता है। हालांकि, अगर आप फ़ंक्शन के लिए कोड देखते हैं, तो यह बहुत अक्षम है। यह करने के लिए यह कई नकली कार्यों (3 reshape एस और 2 repeat एस) का उपयोग करता है। repeat फ़ंक्शन का उपयोग उस सरणी को बनाने के लिए भी किया जाता है जिसमें प्रत्येक डेटा आइटम के साथ मूल डेटा होता है। यदि हमारा इनपुट डेटा [1,2,3] है तो हम [1,1,1,2,2,2,3,3,3] से [1,2,3,1,2,3,1,2,3] घटा रहे हैं। Numpy को Numpy के सी कोड चलाने के बीच में कई अतिरिक्त matrices बनाना पड़ा था जो से बचा जा सकता था।

fast2 न्यूम्पी कॉल के बीच कई मैट्रिक्स बनाने के बिना नम्पी के भारी उठाने का अधिक उपयोग करता है। fast2 अंक के प्रत्येक आयाम के माध्यम से loops, घटाव करता है और प्रत्येक आयाम के बीच वर्ग अंतर का एक कुल कुल रखता है। केवल अंत में वर्ग रूट किया जाता है। अब तक, यह fast1 जितना कुशल नहीं हो सकता है, लेकिन fast2repmat सामग्री को Numpy के अनुक्रमण का उपयोग करके सामान से बचाता है। आइए सादगी के लिए 1 डी केस देखें। fast2 डेटा की 1 डी सरणी बनाता है और डेटा के 2 डी (एन x 1) सरणी से इसे घटा देता है। यह repmat और repeat का उपयोग किए बिना प्रत्येक बिंदु और अन्य सभी बिंदुओं के बीच अंतर मैट्रिक्स बनाता है और इस प्रकार बहुत सारे अतिरिक्त सरणी बना देता है। यह वह जगह है जहां वास्तविक गति अंतर मेरी राय में निहित है। fast1fast2 के बीच मतभेदों को खोजने के लिए मैट्रिस के बीच बहुत अधिक अतिरिक्त बनाता है (और वे बड़े पैमाने पर कम्प्यूटेशनल रूप से बनाए जाते हैं) इन से बचने के लिए नम्पी की शक्ति को बेहतर बनाता है।

def calcDistanceMatrixFastEuclidean3(nDimPoints): 
    nDimPoints = array(nDimPoints) 
    n,m = nDimPoints.shape 
    data = nDimPoints[:,0] 
    delta = (data - data[:,newaxis])**2 
    for d in xrange(1,m): 
    data = nDimPoints[:,d] 
    delta += (data - data[:,newaxis])**2 
    return sqrt(delta) 

अंतर यह है कि हम अब एक शून्य मैट्रिक्स के रूप में डेल्टा का निर्माण कर रहे है:

वैसे, यहाँ एक छोटा सा तेजी से fast2 का संस्करण है।

Answer 2

मनोरंजन के लिए dis:

dis.dis(calcDistanceMatrixFastEuclidean)

2   0 LOAD_GLOBAL    0 (len) 
       3 LOAD_FAST    0 (points) 
       6 CALL_FUNCTION   1 
       9 STORE_FAST    1 (numPoints) 

    3   12 LOAD_GLOBAL    1 (sqrt) 
      15 LOAD_GLOBAL    2 (sum) 
      18 LOAD_GLOBAL    3 (repmat) 
      21 LOAD_FAST    0 (points) 
      24 LOAD_FAST    1 (numPoints) 
      27 LOAD_CONST    1 (1) 
      30 CALL_FUNCTION   3 

    4   33 LOAD_GLOBAL    4 (repeat) 
      36 LOAD_FAST    0 (points) 
      39 LOAD_FAST    1 (numPoints) 
      42 LOAD_CONST    2 ('axis') 
      45 LOAD_CONST    3 (0) 
      48 CALL_FUNCTION   258 
      51 BINARY_SUBTRACT 
      52 LOAD_CONST    4 (2) 
      55 BINARY_POWER 
      56 LOAD_CONST    2 ('axis') 
      59 LOAD_CONST    1 (1) 
      62 CALL_FUNCTION   257 
      65 CALL_FUNCTION   1 
      68 STORE_FAST    2 (distMat) 

    5   71 LOAD_FAST    2 (distMat) 
      74 LOAD_ATTR    5 (reshape) 
      77 LOAD_FAST    1 (numPoints) 
      80 LOAD_FAST    1 (numPoints) 
      83 BUILD_TUPLE    2 
      86 CALL_FUNCTION   1 
      89 RETURN_VALUE 

dis.dis(calcDistanceMatrixFastEuclidean2)

2   0 LOAD_GLOBAL    0 (array) 
       3 LOAD_FAST    0 (nDimPoints) 
       6 CALL_FUNCTION   1 
       9 STORE_FAST    0 (nDimPoints) 

    3   12 LOAD_FAST    0 (nDimPoints) 
      15 LOAD_ATTR    1 (shape) 
      18 UNPACK_SEQUENCE   2 
      21 STORE_FAST    1 (n) 
      24 STORE_FAST    2 (m) 

    4   27 LOAD_GLOBAL    2 (zeros) 
      30 LOAD_FAST    1 (n) 
      33 LOAD_FAST    1 (n) 
      36 BUILD_TUPLE    2 
      39 LOAD_CONST    1 ('d') 
      42 CALL_FUNCTION   2 
      45 STORE_FAST    3 (delta) 

    5   48 SETUP_LOOP    76 (to 127) 
      51 LOAD_GLOBAL    3 (xrange) 
      54 LOAD_FAST    2 (m) 
      57 CALL_FUNCTION   1 
      60 GET_ITER 
     >> 61 FOR_ITER    62 (to 126) 
      64 STORE_FAST    4 (d) 

    6   67 LOAD_FAST    0 (nDimPoints) 
      70 LOAD_CONST    0 (None) 
      73 LOAD_CONST    0 (None) 
      76 BUILD_SLICE    2 
      79 LOAD_FAST    4 (d) 
      82 BUILD_TUPLE    2 
      85 BINARY_SUBSCR 
      86 STORE_FAST    5 (data) 

    7   89 LOAD_FAST    3 (delta) 
      92 LOAD_FAST    5 (data) 
      95 LOAD_FAST    5 (data) 
      98 LOAD_CONST    0 (None) 
      101 LOAD_CONST    0 (None) 
      104 BUILD_SLICE    2 
      107 LOAD_GLOBAL    4 (newaxis) 
      110 BUILD_TUPLE    2 
      113 BINARY_SUBSCR 
      114 BINARY_SUBTRACT 
      115 LOAD_CONST    2 (2) 
      118 BINARY_POWER 
      119 INPLACE_ADD 
      120 STORE_FAST    3 (delta) 
      123 JUMP_ABSOLUTE   61 
     >> 126 POP_BLOCK 

    8  >> 127 LOAD_GLOBAL    5 (sqrt) 
      130 LOAD_FAST    3 (delta) 
      133 CALL_FUNCTION   1 
      136 RETURN_VALUE 

मैं dis पर एक विशेषज्ञ नहीं हूँ, लेकिन ऐसा लगता है जैसे आप देखने के लिए होता है एफ पर अधिक उन कार्रवाइयां जिन्हें पहली बार यह जानने के लिए बुलाया जाता है कि वे थोड़ी देर क्यों लेते हैं। पाइथन के साथ एक प्रदर्शन प्रोफाइलर उपकरण भी है, cProfile।