Her değerin kendisi için işlemden daha büyük saymanın etkili yolu

Question

Gerçek değerler içeren bir numpy vektörüne sahibim. Bu vektördeki her bir değer için, değerin kendisinden daha büyük olan değerlerin sayısını saymak istiyorum. Örneğin

:

# pandas 
df[column].apply(lambda x: (df[column] > x).sum()) 

# numpy equivalent 
[(arr>x).sum() for x in arr] 

Ama çok yavaş:

input: array([1.,2.,3.,1.,1.,0.,10.]) # numpy array 
output: array([3, 2, 1, 3, 3, 6, 0]) 

İlk fikirdi. Bunu yapmanın verimli bir yolu var mı?

Answer 1

Bunu yapmanın bir yolu, basit Python'un bisect modülü kullanarak gereğidir

: Bu daha sonra dizinin sıralanmış bir kopyasını oluşturur ve

import bisect 
array = [1.,2.,3.,1.,1.,0.,10.] 
n = len(array) 
sorted_array = sorted(array) 
print [n - bisect.bisect(sorted_array, val) for val in array] 

orijinalin her biri için, belirlemek için sıralı diziye ikili arama kullanır elemanlar, kaç değer daha büyüktür.

Algoritmada, orijinal kodun O(n^2) ile karşılaştırıldığında, O(n logn) zaman karmaşıklığı vardır. Karşılaştırma için 100K öğelerin bir giriş dizisinde test ettim ve 200x daha hızlıydı.

P.S. Her şey NumPy tek astar olarak yazılabilir: my 100K-eleman testi dizisinde

output = array.size - np.searchsorted(np.sort(array), array, side='right') 

, bu orijinalinden daha 1300X hızlıdır.