एक तेज़ तरीका एक numpy सरणी

Question

में सबसे बड़ा एन तत्वों मैं जानता हूँ कि मैं तो वह ऐसा कर सकते हैं लगता है:

import numpy as np 
N=10 
a=np.arange(1,100,1) 
np.argsort()[-N:] 

हालांकि, यह बहुत धीमी गति से, क्योंकि यह एक पूर्ण तरह किया है।

मुझे आश्चर्य है कि numpy कुछ तरीकों को तेज़ी से प्रदान करता है या नहीं।

Answer 1

bottleneck मॉड्यूल में एक तेज़ आंशिक सॉर्ट विधि है जो सीधे अम्पी सरणी के साथ काम करती है: bottleneck.partition()।

ध्यान दें कि bottleneck.partition() रिटर्न वास्तविक मान हल कर, अगर आप क्रमबद्ध मूल्यों (क्या numpy.argsort() रिटर्न) आप bottleneck.argpartition() का उपयोग करना चाहिए की अनुक्रमित चाहते हैं।

मैं बेंचमार्क है:

• z = -bottleneck.partition(-a, 10)[:10]
• z = a.argsort()[-10:]
• z = heapq.nlargest(10, a)

जहां a एक यादृच्छिक 1000000-तत्व सरणी है।

• bottleneck.partition():

  समय इस प्रकार थे पाश

प्रति 25.6 एमएस
• np.argsort(): पाश
प्रति 198 एमएस
• heapq.nlargest(): पाश

Answer 2

शायद heapq.nlargest

import numpy as np 
import heapq 

x = np.array([1,-5,4,6,-3,3]) 

z = heapq.nlargest(3,x) 

परिणाम:

>>> z 
[6, 4, 3] 

आप इस्तेमाल कर सकते हैं आप n सबसे बड़ा bottleneck का उपयोग कर तत्वों का सूचकांक पता लगाना चाहते हैं bottleneck.argpartsort

>>> x = np.array([1,-5,4,6,-3,3]) 
>>> z = bottleneck.argpartsort(-x, 3)[:3] 
>>> z 
array([3, 2, 5] 

Answer 3

यदि नंबरों की सूची के रूप में सरणी भंडारण समस्याग्रस्त नहीं है, आप

import heapq 
heapq.nlargest(N, a) 

का उपयोग N सबसे बड़ा सदस्यों पाने के लिए कर सकते हैं।

Answer 4

में प्रत्येक ऋणात्मक चिह्न प्रति 358 एमएस प्रस्तावित बाधा समाधान

-bottleneck.partsort(-a, 10)[:10] 

डेटा की एक प्रति बनाता है।हम

bottleneck.partsort(a, a.size-10)[-10:] 

कर इसके अलावा प्रस्तावित numpy समाधान

a.argsort()[-10:] 

रिटर्न नहीं सूचकांक मूल्यों से प्रतियां निकाल सकते हैं।

a[a.argsort()[-10:]] 

दो टोंटी समाधान के सापेक्ष गति प्रारंभिक सरणी में तत्वों के आदेश पर निर्भर करता है, क्योंकि दो दृष्टिकोण विभिन्न बिंदुओं पर डेटा विभाजन: ठीक मूल्यों को खोजने के सूचकांक का प्रयोग है।

दूसरे शब्दों में, किसी एक विशेष यादृच्छिक सरणी के साथ समय या तो विधि तेज दिख सकता है।

1,000,000 तत्वों के साथ 100 यादृच्छिक सरणियों, प्रत्येक भर में समय के औसत,

-bn.partsort(-a, 10)[:10]: 1.76 ms per loop 
bn.partsort(a, a.size-10)[-10:]: 0.92 ms per loop 
a[a.argsort()[-10:]]: 15.34 ms per loop 

देता है जहां समय कोड इस प्रकार है:

import time 
import numpy as np 
import bottleneck as bn 

def bottleneck_1(a): 
    return -bn.partsort(-a, 10)[:10] 

def bottleneck_2(a): 
    return bn.partsort(a, a.size-10)[-10:] 

def numpy(a): 
    return a[a.argsort()[-10:]] 

def do_nothing(a): 
    return a 

def benchmark(func, size=1000000, ntimes=100): 
    t1 = time.time() 
    for n in range(ntimes): 
     a = np.random.rand(size) 
     func(a) 
    t2 = time.time() 
    ms_per_loop = 1000000 * (t2 - t1)/size 
    return ms_per_loop 

t1 = benchmark(bottleneck_1) 
t2 = benchmark(bottleneck_2) 
t3 = benchmark(numpy) 
t4 = benchmark(do_nothing) 

print "-bn.partsort(-a, 10)[:10]: %0.2f ms per loop" % (t1 - t4) 
print "bn.partsort(a, a.size-10)[-10:]: %0.2f ms per loop" % (t2 - t4) 
print "a[a.argsort()[-10:]]: %0.2f ms per loop" % (t3 - t4) 

Answer 5

numpy 1.8partition और argpartition कि आंशिक सॉर्ट (लागू करता है ओ (एन) समय में पूर्ण प्रकार के विरोध के रूप में ओ (एन) * लॉग (एन)) है।

import numpy as np 

test = np.array([9,1,3,4,8,7,2,5,6,0]) 

temp = np.argpartition(-test, 4) 
result_args = temp[:4] 

temp = np.partition(-test, 4) 
result = -temp[:4] 

परिणाम:

समय:

In [16]: a = np.arange(10000) 

In [17]: np.random.shuffle(a) 

In [18]: %timeit np.argsort(a) 
1000 loops, best of 3: 1.02 ms per loop 

In [19]: %timeit np.argpartition(a, 100) 
10000 loops, best of 3: 139 us per loop 

In [20]: %timeit np.argpartition(a, 1000) 
10000 loops, best of 3: 141 us per loop 

Answer 6

तुम भी numpy के प्रतिशतक फ़ंक्शन का उपयोग कर सकते हैं।)

• bottleneck.partsort (:

  import timeit 
  import bottleneck as bn 
  
  N,M,K = 10,1000000,100 
  
  start = timeit.default_timer() 
  for k in range(K): 
      a=np.random.uniform(size=M) 
      tmp=-bn.partsort(-a, N)[:N] 
  stop = timeit.default_timer() 
  print (stop - start)/K 
  
  start = timeit.default_timer() 
  perc = (np.arange(M-N,M)+1.0)/M*100 
  for k in range(K): 
      a=np.random.uniform(size=M) 
      tmp=np.percentile(a,perc) 
  stop = timeit.default_timer() 
  print (stop - start)/K 
  

  पाश प्रति औसत समय: 59 एमएस

• np.percentile(): मेरे मामले में यह थोड़ा तेज तो bottleneck.partsort() था 54 एमएस

Answer 7

के बाद से इस सवाल का 5 साल पुराना है मैं इस समस्या थी और,, मैं सभी मानक फिर से करना और टोंटी की वाक्य रचना बदलना पड़ा (वहाँ अब और कोई partsort, यहहै 210 अब)।

मैंने पुनर्प्राप्त तत्वों की संख्या को छोड़कर, kwgoodman के रूप में एक ही तर्क का उपयोग किया, जो मैंने 50 तक बढ़ाया (मेरी विशेष स्थिति में बेहतर फिट करने के लिए)।

bottleneck 1: 01.12 ms per loop 
bottleneck 2: 00.95 ms per loop 
pandas  : 01.65 ms per loop 
heapq  : 08.61 ms per loop 
numpy  : 12.37 ms per loop 
numpy 2  : 00.95 ms per loop 

तो, bottleneck_2 और numpy_2 (adas के समाधान) बंधे गया:

मैं इन परिणामों मिला है। लेकिन, np.percentile (numpy_2) का उपयोग करके आपके पास पहले से सॉर्ट किए गए शीर्ष शीर्ष तत्व हैं, जो अन्य समाधानों के मामले में नहीं हैं। दूसरी तरफ, यदि आप उन तत्वों की अनुक्रमणिका पर भी रुचि रखते हैं, तो प्रतिशत उपयोगी नहीं है।

मैंने पांडा भी जोड़ा, जो उपलब्ध होने पर बाधा का उपयोग करता है (http://pandas.pydata.org/pandas-docs/stable/install.html#recommended-dependencies)।यदि आपके पास पहले से ही एक पांडा श्रृंखला या डेटाफ्रेम है, तो आप अच्छे हाथों में हैं, बस nlargest का उपयोग करें और आप कर चुके हैं।

बेंचमार्क के लिए इस्तेमाल किया कोड के रूप में (अजगर 3, कृपया) इस प्रकार है:

import time 
import numpy as np 
import bottleneck as bn 
import pandas as pd 
import heapq 

def bottleneck_1(a, n): 
    return -bn.partition(-a, n)[:n] 

def bottleneck_2(a, n): 
    return bn.partition(a, a.size-n)[-n:] 

def numpy(a, n): 
    return a[a.argsort()[-n:]] 

def numpy_2(a, n): 
    M = a.shape[0] 
    perc = (np.arange(M-n,M)+1.0)/M*100 
    return np.percentile(a,perc) 

def pandas(a, n): 
    return pd.Series(a).nlargest(n) 

def hpq(a, n): 
    return heapq.nlargest(n, a) 

def do_nothing(a, n): 
    return a[:n] 

def benchmark(func, size=1000000, ntimes=100, topn=50): 
    t1 = time.time() 
    for n in range(ntimes): 
     a = np.random.rand(size) 
     func(a, topn) 
    t2 = time.time() 
    ms_per_loop = 1000000 * (t2 - t1)/size 
    return ms_per_loop 

t1 = benchmark(bottleneck_1) 
t2 = benchmark(bottleneck_2) 
t3 = benchmark(pandas) 
t4 = benchmark(hpq) 
t5 = benchmark(numpy) 
t6 = benchmark(numpy_2) 
t0 = benchmark(do_nothing) 

print("bottleneck 1: {:05.2f} ms per loop".format(t1 - t0)) 
print("bottleneck 2: {:05.2f} ms per loop".format(t2 - t0)) 
print("pandas  : {:05.2f} ms per loop".format(t3 - t0)) 
print("heapq  : {:05.2f} ms per loop".format(t4 - t0)) 
print("numpy  : {:05.2f} ms per loop".format(t5 - t0)) 
print("numpy 2  : {:05.2f} ms per loop".format(t6 - t0)) 

की