विभिन्न numpy फैंसी इंडेक्सिंग विधियों का प्रदर्शन, numba

Question

के साथ भी, क्योंकि मेरे कार्यक्रम के लिए Numpy सरणी के तेज़ी से अनुक्रमण आवश्यक है और प्रदर्शन पर विचार करने के लिए फैंसी इंडेक्सिंग की अच्छी प्रतिष्ठा नहीं है, मैंने कुछ परीक्षण करने का फैसला किया। विशेष रूप से Numba तेजी से विकास कर रहा है, मैंने कोशिश की कि कौन सी विधियां numba के साथ अच्छी तरह से काम करती हैं।

आदानों मैं अपने लिए निम्नलिखित सरणियों का उपयोग कर के रूप में छोटे सरणियों परीक्षण:

import numpy as np 
import numba as nb 

x = np.arange(0, 100, dtype=np.float64) # array to be indexed 
idx = np.array((0, 4, 55, -1), dtype=np.int32) # fancy indexing array 
bool_mask = np.zeros(x.shape, dtype=np.bool) # boolean indexing mask 
bool_mask[idx] = True # set same elements as in idx True 
y = np.zeros(idx.shape, dtype=np.float64) # output array 
y_bool = np.zeros(bool_mask[bool_mask == True].shape, dtype=np.float64) #bool output array (only for convenience) 

और मेरे बड़े सरणियों परीक्षण के लिए निम्नलिखित सरणियों (y_bool से शिकार संख्या के साथ सामना करने के लिए यहाँ की जरूरत randint):

%timeit x[idx] 
#1.08 µs ± 21 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each) 
#large arrays: 129 µs ± 3.45 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each) 

%timeit x[bool_mask] 
#482 ns ± 18.1 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each) 
#large arrays: 621 µs ± 15.9 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each) 

%timeit np.take(x, idx) 
#2.27 µs ± 104 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each) 
# large arrays: 112 µs ± 5.76 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each) 

%timeit np.take(x, idx, out=y) 
#2.65 µs ± 134 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each) 
# large arrays: 134 µs ± 4.47 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each) 

%timeit x.take(idx) 
#919 ns ± 21.3 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each) 
# large arrays: 108 µs ± 1.71 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each) 

%timeit x.take(idx, out=y) 
#1.79 µs ± 40.7 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each) 
# larg arrays: 131 µs ± 2.92 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each) 

%timeit np.compress(bool_mask, x) 
#1.93 µs ± 95.8 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each) 
# large arrays: 618 µs ± 15.8 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each) 

%timeit np.compress(bool_mask, x, out=y_bool) 
#2.58 µs ± 167 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each) 
# large arrays: 637 µs ± 9.88 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each) 

%timeit x.compress(bool_mask) 
#900 ns ± 82.4 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each) 
# large arrays: 628 µs ± 17.8 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each) 

%timeit x.compress(bool_mask, out=y_bool) 
#1.78 µs ± 59.8 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each) 
# large arrays: 628 µs ± 13.8 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each) 

%timeit np.extract(bool_mask, x) 
#5.29 µs ± 194 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each) 
# large arrays: 641 µs ± 13 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each) 

012:

x = np.arange(0, 1000000, dtype=np.float64) 
idx = np.random.randint(0, 1000000, size=int(1000000/50)) 
bool_mask = np.zeros(x.shape, dtype=np.bool) 
bool_mask[idx] = True 
y = np.zeros(idx.shape, dtype=np.float64) 
y_bool = np.zeros(bool_mask[bool_mask == True].shape, dtype=np.float64) 

यह Numba का उपयोग किए बिना निम्नलिखित समय पैदावार

@nb.jit(nopython=True, cache=True, nogil=True) 
def fancy(x, idx): 
    x[idx] 

@nb.jit(nopython=True, cache=True, nogil=True) 
def fancy_bool(x, bool_mask): 
    x[bool_mask] 

@nb.jit(nopython=True, cache=True, nogil=True) 
def taker(x, idx): 
    np.take(x, idx) 

@nb.jit(nopython=True, cache=True, nogil=True) 
def ndtaker(x, idx): 
    x.take(idx) 

यह छोटे और बड़े सरणियों के लिए निम्नलिखित परिणाम प्राप्त होते हैं:

और numba साथ, nopython मोड, cach आईएनजी और nogil में jitting का उपयोग कर रहा अनुक्रमण के तरीके, जो numba द्वारा समर्थित हैं सजाया

%timeit fancy(x, idx) 
#686 ns ± 25.1 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each) 
# large arrays: 84.7 µs ± 1.82 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each) 

%timeit fancy_bool(x, bool_mask) 
#845 ns ± 31 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each) 
# large arrays: 843 µs ± 14.2 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each) 

%timeit taker(x, idx) 
#814 ns ± 21.1 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each) 
# large arrays: 87 µs ± 1.52 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each) 

%timeit ndtaker(x, idx) 
#831 ns ± 24.5 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each) 
# large arrays: 85.4 µs ± 2.69 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each) 

---

सारांश

जबकि numba के बिना numpy के लिए यह स्पष्ट है कि छोटे सरणी Boolean मास्क (ndarray.take(idx) की तुलना में एक कारक 2 के बारे में) के साथ सबसे अच्छी तरह से अनुक्रमित हैं, बड़े arrays ndarray.take(idx) के लिए सबसे अच्छा प्रदर्शन करेंगे, इस मामले में बूलियन अनुक्रमण से लगभग 6 गुना तेजी से । ब्रेकवेन-पॉइंट लगभग 1000 कोशिकाओं के सरणी आकार के साथ है और 20 कोशिकाओं के सूचकांक-सरणी आकार के साथ है।
1e5 तत्वों के साथ सरणी और 5e3 इंडेक्स सरणी आकार, ndarray.take(idx) लगभग लगभग 10 गुना तेज बूलियन मास्क इंडेक्सिंग से अधिक होगा। तो ऐसा लगता है कि बूलियन इंडेक्सिंग सरणी आकार के साथ काफी धीमी लगती है, लेकिन कुछ सरणी-आकार-थ्रेसहोल्ड तक पहुंचने के बाद थोड़ी सी पकड़ लेती है।

numba jitted कार्यों के लिए बूलियन मास्क इंडेक्सिंग को छोड़कर सभी अनुक्रमण कार्यों के लिए एक छोटी गति है। सरल फैंसी इंडेक्सिंग यहां सबसे अच्छा काम करता है, लेकिन अभी भी जूलिंग के बिना बुलियन मास्किंग से धीमा है।
बड़े सरणी के लिए बूलियन मास्क इंडेक्सिंग अन्य विधियों की तुलना में बहुत धीमी है, और गैर-जूट संस्करण से भी धीमी है। तीन अन्य विधियां सभी गैर-बुने हुए संस्करण की तुलना में काफी अच्छी और लगभग 15% तेज प्रदर्शन करती हैं।

मेरे आकार के लिए विभिन्न आकारों के कई सरणी के साथ, numba के साथ फैंसी इंडेक्सिंग जाने का सबसे अच्छा तरीका है। शायद कुछ अन्य लोग इस काफी लंबी पोस्ट में कुछ उपयोगी जानकारी भी पा सकते हैं।

संपादित करें:
मुझे खेद है कि मैं अपने प्रश्न पूछना भूल गया, जो वास्तव में मेरे पास है। मैं बस अपने कार्यदिवस के अंत में इसे तेजी से टाइप कर रहा था और इसे पूरी तरह से भूल गया था ... ठीक है, क्या आप परीक्षण किए गए लोगों की तुलना में किसी भी बेहतर और तेज विधि को जानते हैं? सिथॉन का उपयोग करना मेरा समय नुंबा और पायथन के बीच था।
चूंकि इंडेक्स सरणी को एक बार पूर्वनिर्धारित किया जाता है और लंबे पुनरावृत्तियों में बदलाव किए बिना उपयोग किया जाता है, तो इंडेक्सिंग प्रक्रिया को पूर्व-परिभाषित करने का कोई भी तरीका बहुत अच्छा होगा। इसके लिए मैंने कदमों का उपयोग करने के बारे में सोचा। लेकिन मैं कदमों के एक कस्टम सेट को पूर्व परिभाषित करने में सक्षम नहीं था। क्या तारों का उपयोग कर स्मृति में पूर्वनिर्धारित दृश्य प्राप्त करना संभव है?

संपादित करें 2:
मुझे लगता है मैं पूर्वनिर्धारित लगातार सूचकांक सरणियों जो एक ही मान सरणी पर इस्तेमाल किया जाएगा के बारे में मेरे सवाल स्थानांतरित करेंगे करने के लिए पुनरावृत्ति में कुछ लाख बार के लिए (जहां केवल मूल्यों को बदल लेकिन आकार नहीं) एक नया और अधिक विशिष्ट सवाल। यह सवाल बहुत सामान्य था और शायद मैंने इस प्रश्न को थोड़ा भ्रामक बना दिया। जैसे ही मैंने नया प्रश्न खोला, मैं यहां लिंक पोस्ट करूंगा!
Here is the link to the followup question.

Answer 1

आपका सारांश पूरी तरह से सही नहीं है, आप पहले से ही अलग तरह से आकार सरणियों लेकिन एक बात है कि आप अनुक्रमित तत्वों की संख्या को बदलने के लिए था नहीं किया साथ परीक्षण किया था।

मैं शुद्ध अनुक्रमण के लिए यह प्रतिबंधित है और take छोड़े गए और compress और extract (जो प्रभावी रूप से पूर्णांक सरणी अनुक्रमण है) (क्योंकि ये प्रभावी रूप से बूलियन सरणी अनुक्रमण हैं)। इनके लिए एकमात्र अंतर निरंतर कारक हैं। विधियों take और compress के लिए निरंतर कारक numpy फ़ंक्शंस np.take और np.compress के लिए ओवरहेड से कम होगा, लेकिन अन्यथा प्रभाव उचित रूप से आकार वाले सरणी के लिए उपेक्षित होंगे।

बस मुझे विभिन्न संख्या के साथ प्रस्तुत करते हैं:

# ~ every 500th element 
x = np.arange(0, 1000000, dtype=np.float64) 
idx = np.random.randint(0, 1000000, size=int(1000000/500)) # changed the ratio! 
bool_mask = np.zeros(x.shape, dtype=np.bool) 
bool_mask[idx] = True 

%timeit x[idx] 
# 51.6 µs ± 2.02 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each) 
%timeit x[bool_mask] 
# 1.03 ms ± 37.1 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each) 


# ~ every 50th element 
idx = np.random.randint(0, 1000000, size=int(1000000/50)) # changed the ratio! 
bool_mask = np.zeros(x.shape, dtype=np.bool) 
bool_mask[idx] = True 

%timeit x[idx] 
# 1.46 ms ± 55.1 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each) 
%timeit x[bool_mask] 
# 2.69 ms ± 154 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) 


# ~ every 5th element 
idx = np.random.randint(0, 1000000, size=int(1000000/5)) # changed the ratio! 
bool_mask = np.zeros(x.shape, dtype=np.bool) 
bool_mask[idx] = True 

%timeit x[idx] 
# 14.9 ms ± 495 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) 
%timeit x[bool_mask] 
# 8.31 ms ± 181 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) 

तो यहाँ क्या हुआ? यह आसान है: इंटीजर सरणी अनुक्रमण केवल इंडेक्स-सरणी में मानों के रूप में कई तत्वों तक पहुंचने की आवश्यकता है। इसका मतलब है कि अगर कुछ मैच हैं तो यह बहुत तेज़ होगा लेकिन धीमे हो जाएंगे यदि कई इंडेक्स हैं। बूलियन सरणी अनुक्रमण, हालांकि, हमेशा पूरे बूलियन सरणी के माध्यम से चलने और "सत्य" मानों की जांच करने की आवश्यकता होती है। इसका मतलब है कि यह सरणी के लिए लगभग "स्थिर" होना चाहिए।

लेकिन, प्रतीक्षा करें, यह वास्तव में बूलियन सरणी के लिए स्थिर नहीं है और पूर्णांक सरणी अनुक्रमण को लंबे समय तक (अंतिम मामला) क्यों लेता है, भले ही इसे 5 गुना कम तत्वों को संसाधित करना पड़े?

यही वह जगह है जहां यह अधिक जटिल हो जाता है। इस मामले में बूलियन सरणी में True यादृच्छिक स्थानों पर था जिसका अर्थ है कि यह शाखा भविष्यवाणी विफलताओं के अधीन होगा। True और False में समान घटनाएं होंगी लेकिन यादृच्छिक स्थानों पर ये अधिक संभावना होगी। यही कारण है कि बूलियन सरणी अनुक्रमण धीमा हो गया - क्योंकि True से False का अनुपात अधिक बराबर और इस प्रकार अधिक "यादृच्छिक" हो गया। अगर True एस भी अधिक समय लेता है तो परिणाम सरणी बड़ी होगी।

इस शाखा भविष्यवाणी बात के लिए एक उदाहरण के रूप (/ compilers अलग प्रणाली के साथ अलग हो सकता है) उदाहरण के रूप में इस का उपयोग करें:

bool_mask = np.zeros(x.shape, dtype=np.bool) 
bool_mask[:1000000//2] = True # first half True, second half False 
%timeit x[bool_mask] 
# 5.92 ms ± 118 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) 

bool_mask = np.zeros(x.shape, dtype=np.bool) 
bool_mask[::2] = True # True and False alternating 
%timeit x[bool_mask] 
# 16.6 ms ± 361 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) 

bool_mask = np.zeros(x.shape, dtype=np.bool) 
bool_mask[::2] = True 
np.random.shuffle(bool_mask) # shuffled 
%timeit x[bool_mask] 
# 18.2 ms ± 325 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) 

तो True और False के वितरण गंभीर रूप बूलियन मास्क भले ही साथ क्रम को प्रभावित करेगा उनमें True की समान राशि होती है! compress-कार्यों के लिए एक ही प्रभाव दिखाई देगा।

पूर्णांक सरणी अनुक्रमण (और इसी तरह np.take) के लिए एक और प्रभाव दिखाई देगा: कैश इलाके। आपके मामले में सूचकांक यादृच्छिक रूप से वितरित किए जाते हैं, इसलिए आपके कंप्यूटर को "प्रोसेसर कैश" लोड में बहुत से "रैम" करना पड़ता है क्योंकि यह बहुत ही असंभव है कि दो सूचकांक एक दूसरे के पास होंगे।

इस की तुलना करें:

idx = np.random.randint(0, 1000000, size=int(1000000/5)) 
%timeit x[idx] 
# 15.6 ms ± 703 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) 

idx = np.random.randint(0, 1000000, size=int(1000000/5)) 
idx = np.sort(idx) # sort them 
%timeit x[idx] 
# 4.33 ms ± 366 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) 

सूचकांक संभावना बेहद वृद्धि हुई है कि अगले मूल्य पहले से ही कैश में होगा छँटाई करके और इस विशाल speedups हो सकता है। यह एक बहुत ही महत्वपूर्ण कारक है यदि आप जानते हैं कि सूचकांक क्रमबद्ध किए जाएंगे (उदाहरण के लिए यदि वे np.where द्वारा बनाए गए थे, तो उन्हें क्रमबद्ध किया गया है, जो np.where का परिणाम विशेष रूप से अनुक्रमण के लिए कुशल बनाता है)।

तो, ऐसा नहीं है कि पूर्ण सरणी इंडेक्सिंग छोटे सरणी के लिए धीमी है और बड़े सरणी के लिए तेज़ है यह अधिक कारकों पर निर्भर करता है। दोनों के पास उनके उपयोग-मामले हैं और परिस्थितियों के आधार पर एक दूसरे की तुलना में तेज़ (काफी) तेज हो सकता है।

---

मुझे numba कार्यों के बारे में थोड़ा सा बात करने दें। पहले कुछ सामान्य बयान:

• cache कोई फर्क नहीं पड़ता है, यह केवल फ़ंक्शन को पुन: संकलित करने से बचाता है। इंटरैक्टिव वातावरण में यह अनिवार्य रूप से बेकार है। यदि आप मॉड्यूल में फ़ंक्शंस को पैकेज करते हैं तो यह तेज़ है।
• nogil स्वयं ही कोई गति वृद्धि प्रदान नहीं करेगा। यह तेज़ होगा यदि इसे विभिन्न धागे में बुलाया जाता है क्योंकि प्रत्येक फ़ंक्शन निष्पादन जीआईएल को छोड़ सकता है और फिर एकाधिक कॉल समानांतर में चल सकते हैं।

अन्यथा मैं नहीं पता है कि कैसे Numba effectivly इन कार्यों को लागू करता है, लेकिन जब आप NumPy Numba में सुविधाओं का उपयोग यह धीमी या तेज हो सकता है - लेकिन भले ही वह तेज है यह बहुत तेजी से (शायद के लिए छोड़कर नहीं होगा छोटे सरणी)। क्योंकि अगर इसे तेजी से बनाया जा सकता है तो न्यूपी डेवलपर्स इसे भी लागू करेंगे। अंगूठे का मेरा नियम है: यदि आप इसे कर सकते हैं (वेक्टरिज्ड) NumPy के साथ numba से परेशान नहीं है। केवल अगर आप इसे वेक्टरकृत न्यूमपी फ़ंक्शंस के साथ नहीं कर सकते हैं या न्यूमपी बहुत अधिक अस्थायी सरणी का उपयोग करेगा तो numba चमक जाएगा!