एक क्रमबद्ध दो आयामी numpy सरणी

Question

अक्ष के साथ पहले गैर-शून्य मान ढूँढना मैं दो आयामी क्रमबद्ध सरणी की प्रत्येक पंक्ति के लिए पहले गैर-शून्य मान को खोजने का सबसे तेज़ तरीका ढूंढने का प्रयास कर रहा हूं। तकनीकी रूप से, सरणी में केवल मान शून्य और एक हैं, और यह "क्रमबद्ध" है।

उदाहरण के लिए, सरणी की तरह लग सकता है निम्नलिखित:

वी =

0 0 0 1 1 1 1 
0 0 0 1 1 1 1 
0 0 0 0 1 1 1 
0 0 0 0 0 0 1 
0 0 0 0 0 0 1 
0 0 0 0 0 0 1 
0 0 0 0 0 0 0 

मैं खोजने के लिए argmax समारोह

argmax(v, axis=1)) 

इस्तेमाल कर सकते हैं, जब यह शून्य से एक में परिवर्तन , लेकिन मेरा मानना ​​है कि यह प्रत्येक पंक्ति के साथ एक संपूर्ण खोज करेगा। मेरी सरणी उचित रूप से आकार (~ 2000x2000) होगी। क्या Argmax अभी भी लूप के भीतर प्रत्येक पंक्ति के लिए एक खोजशब्द दृष्टिकोण कर रहा है, या क्या कोई बेहतर विकल्प है?

इसके अलावा, सरणी हमेशा ऐसी होगी कि एक पंक्ति के लिए एक की पहली स्थिति हमेशा> = ऊपर की पंक्ति में एक की पहली स्थिति है (लेकिन यह गारंटी नहीं है कि इसमें एक होगा आखिरी कुछ पंक्तियां)। मैं इसे पिछली पंक्ति से पहले 1 की स्थिति के बराबर प्रत्येक पंक्ति के लिए एक लूप और "प्रारंभिक इंडेक्स वैल्यू" के साथ इसका फायदा उठा सकता हूं, लेकिन क्या मैं यह सोचने में सही हूं कि numpy argmax फ़ंक्शन अभी भी पाइथन में लिखे गए लूप को बेहतर प्रदर्शन करेगा ।

मैं केवल विकल्पों को बेंचमार्क कर दूंगा, लेकिन सरणी की किनार लंबाई काफी बदल सकती है (250 से 10,000 तक)।

Answer 1

यह यथोचित np.where उपयोग करने के लिए तेजी से होता है:

>>> a 
array([[0, 0, 0, 1, 1, 1, 1], 
     [0, 0, 0, 1, 1, 1, 1], 
     [0, 0, 0, 0, 1, 1, 1], 
     [0, 0, 0, 0, 0, 0, 1], 
     [0, 0, 0, 0, 0, 0, 1], 
     [0, 0, 0, 0, 0, 0, 1], 
     [0, 0, 0, 0, 0, 0, 0]]) 
>>> np.where(a>0) 
(array([0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 3, 4, 5]), array([3, 4, 5, 6, 3, 4, 5, 6, 4, 5, 6, 6, 6, 6])) 

कि 0.

तुम भी एनपी उपयोग कर सकते हैं की तुलना में अधिक मूल्यों के निर्देशांक के साथ tuples देता है।

def first_true1(a): 
    """ return a dict of row: index with value in row > 0 """ 
    di={} 
    for i in range(len(a)): 
     idx=np.where(a[i]>0) 
     try: 
      di[i]=idx[0][0] 
     except IndexError: 
      di[i]=None  

    return di  

प्रिंटों: जहां प्रत्येक उप सरणी का परीक्षण करने के

{0: 3, 1: 3, 2: 4, 3: 6, 4: 6, 5: 6, 6: None} 

यानी, पंक्ति 0: सूचकांक 3> 0; पंक्ति 4: सूचकांक 4> 0; पंक्ति 6: कोई सूचकांक 0 से अधिक

आपको संदेह के रूप में, argmax तेजी से हो सकता है:

def first_true2(): 
    di={} 
    for i in range(len(a)): 
     idx=np.argmax(a[i]) 
     if idx>0: 
      di[i]=idx 
     else: 
      di[i]=None  

    return di  
    # same dict is returned... 

आप सभी naughts की पंक्तियों के लिए एक None नहीं होने के तर्क के साथ सौदा कर सकते हैं, यह तेजी से अब भी है :

def first_true4(): 
    di={} 
    for i, ele in enumerate(np.argmax(a,axis=1)): 
     if ele==0 and a[i][0]==0: 
      di[i]=None 
     else: 
      di[i]=ele 

    return di   

:

def first_true3(): 
    di={} 
    for i, j in zip(*np.where(a>0)): 
     if i in di: 
      continue 
     else: 
      di[i]=j 

    return di  

और यहाँ एक संस्करण (के रूप में अपनी टिप्पणी में सुझाव दिया) argmax में अक्ष का उपयोग करता है

गति की तुलना (अपने उदाहरण सरणी पर) के लिए, मैं इस मिल:

  rate/sec usec/pass first_true1 first_true2 first_true3 first_true4 
first_true1 23,818 41.986   --  -34.5%  -63.1%  -70.0% 
first_true2 36,377 27.490  52.7%   --  -43.6%  -54.1% 
first_true3 64,528 15.497  170.9%  77.4%   --  -18.6% 
first_true4 79,287 12.612  232.9%  118.0%  22.9%   -- 

अगर मैं पैमाने पर एक 2000 x 2000 एनपी सरणी के लिए, यहाँ मैं क्या मिलता है:

  rate/sec usec/pass first_true3 first_true1 first_true2 first_true4 
first_true3  3 354380.107   --  -0.3%  -74.7%  -87.8% 
first_true1  3 353327.084  0.3%   --  -74.6%  -87.7% 
first_true2  11 89754.200  294.8%  293.7%   --  -51.7% 
first_true4  23 43306.494  718.3%  715.9%  107.3%   -- 

Answer 2

argmax() सी स्तर पाश उपयोग करें, यह अजगर पाश की तुलना में बहुत तेजी से है, तो मैं भी लगता है, यह मुश्किल argmax हरा() है, आप speedup करने Cython उपयोग कर सकते हैं आप अजगर में एक स्मार्ट एल्गोरिथ्म लिखें:

@cython.boundscheck(False) 
@cython.wraparound(False) 
def find(int[:,:] a): 
    cdef int h = a.shape[0] 
    cdef int w = a.shape[1] 
    cdef int i, j 
    cdef int idx = 0 
    cdef list r = [] 
    for i in range(h): 
     for j in range(idx, w): 
      if a[i, j] == 1: 
       idx = j 
       r.append(idx) 
       break 
     else: 
      r.append(-1) 
    return r 

2000x2000 मैट्रिक्स के लिए मेरे पीसी पर, यह 100us बनाम 3ms है।