Étant donné un tableau, a , de valeurs triées et un tableau de plages, bins , quel est le moyen le plus efficace de compter combien de valeurs dans a appartiennent à chaque plage, rng , dans bins ?
Actuellement, je fais ce qui suit:
array([3., 4., 3., 3., 4., 4., 3., 3., 3., 3., 3.])
Ce qui renvoie le tableau attendu
def sliding_count(a, end, window, start=0, step=1):
bins = [(x, x + window) for x in range(start, (end + 1) - window, step)]
counts = np.zeros(len(bins))
for i, rng in enumerate(bins):
count = len(a[np.where(np.logical_and(a>=rng[0], a<=rng[1]))])
counts[i] = count
return counts
a = np.array([1, 5, 8, 11, 14, 19])
end = 20
window = 10
sliding_count(a, end, window)
Mais j'y sens doit être un moyen plus efficace de le faire?
3 Réponses :
Le nombre d'éléments dans un bac b est le nombre d'éléments <= b.end moins le nombre d'éléments
Ainsi, vous pouvez créer un tableau démarre des bacs triés par début, et fins tableau de bacs triés par fin. Parcourez ensuite les 3 tableaux à l'étape. Lorsque vous avancez au-delà de chaque x dans a , avancez au-delà des débuts avec x à partir du décompte de ce bac. Passez ensuite aux extrémités avec x <= b.end et ajoutez position_in_a au décompte de ce bac.
La complexité totale est O (N log N), dominée par le tri des tableaux de début et de fin. Parcourir les 3 tableaux et ajuster les nombres est O (N).
Dans votre code, vous générez le tableau de bacs déjà triés, donc si vous pouvez le faire, vous pouvez sauter l'étape de tri et la complexité totale est O (a.length + bin_count). Je ne prendrais même pas la peine de générer ce tableau car vous pouvez facilement calculer les valeurs de début et de fin à partir de l'index.
import perfplot
def make_array(N):
a = np.random.randint(10, size=N)
a = a.cumsum()
return a
def using_sliding(a):
return sliding_count(a, end, window)
def using_alt(a):
return alt(a, end, window)
perfplot.show(
setup=make_array,
kernels=[using_sliding, using_alt],
n_range=[2**k for k in range(22)],
logx=True,
logy=True,
xlabel='len(a)')
Quelque chose comme ça (?):
def sliding_count(a, nx0, nx1, window):
bin0 = np.arange(nx0,nx1,1)
bin1 = bin0 + window
count = np.zeros((nx1-nx0), dtype=int)
for j in range(nx1-nx0):
count[j] = np.sum(a<=bin1[j]) - np.sum(a<bin0[j])
return count
#---- main ---------------
nx0, nx1, window = 0, 11, 10
a = np.array([1, 5, 8, 11, 14, 19])
sliding_count(a, nx0, nx1, window)
array([3, 4, 3, 3, 4, 4, 3, 3, 3, 3, 3])
Je n'ai pas vérifié le code pour nx0> 0 et step> 1 dans bin0 = np.arange (nx0, nx1,1) . La longueur de la boucle for doit donc être modifiée dans de tels cas.
Imho c'est assez efficace. Cherchez-vous un moyen plus efficace?
saviez-vous que
rangerenvoie un objet sur lequel vous pouvez fairex in range (...)et obtenir un vrai / faux?@Nullman oui, mais cela signifierait que je devrais itérer
binsune fois pour chaque élément dansaLa fenêtre sera-t-elle toujours un multiple de l'étape?