Ce que dit le titre. Je recherche une approche rapide et pythonique pour extraire les lignes du tableau d'extrémité A qui contient les éléments d'un autre tableau v
Un exemple simple de quoi Je veux réaliser est comme suit:
Entrée:
import numpy as np np.random.seed(0) size = 32000 base_arr = np.arange(size)*10 t1 = np.random.randint(0,6, size)+base_arr t2 = np.random.randint(5,10, size)+base_arr A = np.vstack((t1,t2)).T v = np.sort(np.random.randint(0,10,3*size)+np.repeat(base_arr,3))
Parce que A est un tableau de fin de pinte, ce qui signifie dans chaque ligne le premier élément et le deuxième élément représente le début et la fin d'un intervalle. Puisque seuls les intervalles de [20 28] , [31 37] et [43 43] contiennent les éléments en v (dans ce cas 26,31 et 43 sont contenus dans les intervalles créés par le tableau d'extrémité A ), la sortie souhaitée est:
[[20 28] [31 37] [43 43]]
Voici le code pour générer les tableaux d'entrée actuels:
A = [[ 4 9]
[15 19]
[20 28]
[31 37]
[43 43]]
v = [ 0 1 2 3 11 12 13 14 26 29 30 31 43]
Merci d'avance
EDIT : ajouté plus de détails à l'explication
4 Réponses :
Comparez le long d'une troisième dimension
import numpy as np
a = np.array([[ 4, 9],
[15, 19],
[20, 28],
[31, 37],
[43, 43]])
v = np.array([ 0, 1, 2, 3, 11, 12, 13, 14, 26, 29, 30, 31, 43])
between = np.logical_and(v >= a[:,0,None], v <= a[:,1,None])
print(a[between.any(-1)])
>>>
[[20 28]
[31 37]
[43 43]]
>>>
Malheureusement, le mien explose sur les plus grands tableaux avec un MemoryError
En fait, je l'ai remarqué aussi sur mon ordinateur. Je me demande s'il existe des moyens de le faire dans votre démarche sans créer de dimension supplémentaire. Si c'est possible, alors la fonction devrait être beaucoup moins gourmande en mémoire.
La dimension supplémentaire est nécessaire pour que cela fonctionne, elle permet la Broadcasting . Searchsorted est la voie à suivre. Je suis resté coincé et me suis trompé en lisant le terme vectorisé .
Approche # 1
Nous pouvons utiliser np.searchsorted pour obtenir les indices de position gauche et droit des éléments de début et de fin de chaque ligne par rapport aux valeurs v et recherchez ceux qui ne correspondent pas, ce qui indiquerait que la ligne particulière a au moins un élément dans ces limites. Par conséquent, nous pourrions simplement faire -
In [65]: %timeit A[np.searchsorted(v,A[:,0],'left')!=np.searchsorted(v,A[:,1],'right')]
2 ms ± 10.1 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
In [66]: %%timeit
...: idx = np.searchsorted(v,A[:,0],'left')
...: out = A[(idx<len(v)) & (v[idx.clip(max=len(v)-1)]<=A[:,1])]
1.32 ms ± 7.87 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
Approche # 2
Une autre façon serait d'utiliser les indices positionnés à gauche pour indexer dans v et voir ensuite s'ils sont inférieurs aux bons points de terminaison. Par conséquent, ce serait -
idx = np.searchsorted(v,A[:,0],'left') out = A[(idx<len(v)) & (v[idx.clip(max=len(v)-1)]<=A[:,1])]
Notez que cela suppose que v soit trié et entré sous forme de tableaux. Si v n'est pas déjà trié, nous devons le trier puis le nourrir.
Timings sur un plus grand ensemble de données à ma fin -
A[np.searchsorted(v,A[:,0],'left')!=np.searchsorted(v,A[:,1],'right')]
Merci pour votre réponse. De loin l'approche la plus rapide parmi les approches déjà bonnes
@Divakar Je viens de boucler les réponses sur range (400) , j'ai trouvé que for i in [5,29,130,139,146,150,156,178,295,313,315,337,342]: np.random.seed (i) , les sorties de l'approche 1 et de l'approche 2 sont différentes.
@Divakar, dans le terrain de test avec 400 itérations oui il pourrait y avoir des doublons. Mais aux endroits où je veux réellement appliquer ma fonction, non, il ne devrait pas y avoir de doublons. Et si c'est le cas, j'utiliserai v = np.unique (v) pour les supprimer.
@mathguy Yup, j'avais besoin de vérifier une condition là-bas. Application modifiée n ° 2.
@Divakar Je viens de le vérifier avec différents types de v , jusqu'ici tout va bien. J'apprécie vraiment votre suivi
Je ne considère pas cela comme entièrement pythonique, mais c'est au moins O (n).
def find_bounding_intervals(A, v):
rows = []
i = 0
for row in A:
while all(v[i] < row):
i += 1
if row[0] <= v[i] <= row[1]:
rows.append(row)
return np.array(rows)
A = np.array([[ 4, 9],
[15, 19],
[20, 28],
[31, 37],
[43, 43]])
v = np.array([ 0, 1, 2, 3, 11, 12, 13, 14, 26, 29, 30, 31, 43])
print(find_bounding_intervals(A, v))
Mon ordinateur portable bas de gamme élabore une solution en ~ 0,28 s pour les données beaucoup plus volumineuses défini dans votre question.
Merci pour votre réponse. Je ne savais pas que la fonction intégrée all () existe jusqu'à présent
Je viens d'utiliser votre code pour tester si une version numba -njitted de votre implémentation peut battre la version vectorisée. J'ai trouvé qu'en termes de performances, la version numba est la plus rapide. Je le posterai ci-dessous.
from numba import njit
@njit
def find_bounding_intervals(A, v):
rows_L = []
rows_R = []
i = 0
for row in range(A.shape[0]):
while v[i] < A[row,0] and v[i] < A[row,1]:
i += 1
if A[row,0] <= v[i] <= A[row,1]:
rows_L.append(A[row,0])
rows_R.append(A[row,1])
return np.array([rows_L, rows_R]).T
Although this implementation is technically not a vectorized function, it is indeed the fastest across almost all sizes of n.I should make it clear that the algorithm comes from @brentertainer
En relation: Rechercher si un tableau trié de flottants contient efficacement des nombres dans une certaine plage .