Cette question est liée à ceci: Premier index de liste Python supérieur à x?
J'ai une liste (triée) de flottants, et je veux trouver le premier index qui dépasse chaque valeur d'une deuxième liste
par exemple
[1, 2]
si m était un flottant, j'utiliserais ceci:
[bisect.bisect_left(l,i) for i in m]
Mais pour le cas où m est une liste ceci échoue, et je ne peux que penser à employer une compréhension de liste:
bisect.bisect_left(l,m)
qui donne:
l=[0.2,0.3,0.7,0.9] m=[0.25,0.6]
qui fonctionne, mais Je veux l'accélérer pour les grandes listes dans mon exemple réel en évitant la compréhension de la liste car mes tests ont montré que c'était l'opération "goulot d'étranglement" (j'ai dit plus tôt que je soupçonnais qu'elle était trop lente). Existe-t-il un moyen de le faire efficacement en utilisant une fonction vectorisée par ex. numpy ou un algorithme amélioré (car une seule traversée de la liste est requise)?
3 Réponses :
Eh bien, il y a de fortes chances que bisect_left soit une opération O (logN) (recherche binaire) donc votre opération globale serait O (KlogN) où N correspond à la taille de l et K à la taille de m .
Si la deuxième liste m était également triée, vous pourriez en faire un O (N) simplement en exécutant un index sur les deux listes simultanément.
Mais, concernant votre commentaire "Je suspecte que c'est lent", votre premier mouvement devrait toujours être de tester la solution la plus simple avec le plus grand ensemble de données attendu. Si cela est réalisable, arrêtez-vous là! Ce n'est que s'il est insuffisant que vous commencez à penser à l'optimisation.
Par exemple, considérons le programme suivant:
import timeit
import random
import bisect
haystack = []
for _ in range(1000000):
haystack.append(random.random())
haystack.sort()
needles = []
for _ in range(10000):
needles.append(random.random())
print(timeit.timeit('[bisect.bisect_left(haystack, needle) for needle in needles]', setup = 'from __main__ import bisect, haystack, needles', number = 1000))
Cela crée une botte de foin de 1 000 000 éléments et un La liste d'aiguilles de 10000 éléments utilise ensuite votre compréhension de la liste bisect pour faire le travail. L'exécution sur mon bureau (pas particulièrement grognon) avec time montre:
real 0m0.738s # < 3/4 of a second elapsed user 0m0.578s sys 0m0.109s
Et ceci inclut le temps nécessaire pour construire les listes, trier la grande et imprimer les résultats.
Utiliser timeit pour se débarrasser de tout ce temps de configuration peut être fait avec: p >
import random
import bisect
haystack = []
for _ in range(1000000):
haystack.append(random.random())
haystack.sort()
needles = []
for _ in range(10000):
needles.append(random.random())
result = [bisect.bisect_left(haystack, needle) for needle in needles]
print(result)
Le résultat est 12.27 pour les mille itérations, ce qui signifie que vous pouvez le faire environ 75 fois par seconde sans transpirer.
De plus: l'opération globale serait K log (N); c'est-à-dire que cela dépend de la façon dont la taille de m se compare à la taille de l . Dans les cas où le l est grand mais m est petit, il serait préférable de rechercher binaire chaque élément de m , plutôt que de faire la type d'itération que vous décrivez.
Vous devez vous souvenir de la dernière valeur trouvée pour l'utiliser comme point de départ de la prochaine recherche binaire, donc au lieu de la compréhension de liste, vous devez utiliser une boucle for:
result = [bisect.bisect_left(l,m[0]),]
for i in m[1:] :
result.append( bisect.bisect_left(l,i,result[-1]))
Ceci devrait fonctionner plus vite qu'une simple compréhension.
J'ai donc trouvé qu'il y avait une fonction numpy pour effectuer cette tâche, np.searchsorted . ce qui est beaucoup plus rapide que l'utilisation de la compréhension de liste.
python3 -m timeit -s "import numpy as np" -s "import bisect" -s "h=np.sort(np.random.uniform(size=10000))" -s "n=np.sort(np.random.uniform(size=1000))" "r=np.searchsorted(h,n)"
Voici les horaires des différentes solutions:
1. Compréhension de liste standard:
c'était ma première tentative de solution
python3 -m timeit -s "import numpy as np" -s "import bisect" -s "h=np.sort(np.random.uniform(size=10000))" -s "n=np.sort(np.random.uniform(size=1000))" "r=[bisect.bisect_left(h,n[0])]" "for i in n[1:]:" " r.append(bisect.bisect_left(h,i,r[-1]))"
200 boucles, le meilleur de 5: 1,61 msec par boucle
2. Recherche raccourcie dans la boucle for
C'était la solution aimablement fournie par @lenik
python3 -m timeit -s "import numpy as np" -s "import bisect" -s "h=np.sort(np.random.uniform(size=10000))" -s "n=np.sort(np.random.uniform(size=1000))" "r=[bisect.bisect_left(h,i) for i in n]"
200 boucles, le meilleur des 5: 1,6 ms par boucle
A peine différent de la compréhension de liste dont j'ai été quelque peu surpris ...
3. Numpy searchsorted
result=np.searchsorted(searchlist,newindices)
10000 boucles, meilleur de 5: 33,6 usec par boucle
De loin le plus rapide .
à quoi ressemblerait la sortie finale et la deuxième liste est-elle également triée?
la deuxième liste est également triée dans mon application, une sortie ajoutée et des excuses pour une erreur de virgule
"Je soupçonne que c'est lent pour les grandes listes". Pourquoi? Pensez-vous à une amélioration algorithmique particulière?
@KarlKnechtel car il utilise la recherche binaire sur toute la liste
l, mais comme les listes sont triées, nous pouvons facilement restreindre la zone de recherche en se souvenant du dernier index trouvé, voir ma réponse ci-dessous.@KarlKnechtel - Je ne suis pas très expérimenté avec un python efficace, mais dans mon problème précédent ici stackoverflow.com/questions/59147730/... quand j'ai trouvé une solution en utilisant la compréhension de liste alors elle était 100 fois plus lent que l'utilisation des inserts intégrés, et il semblait qu'une solution plus efficace pouvait être trouvée en utilisant un seul balayage. J'ai essayé sans succès de trouver une fonction / un algorithme approprié dans numpy, d'où la question.
? Les compréhensions de liste sont intégrées; numpy n'est pas . Et bien sûr, vous constaterez de mauvaises performances en essayant d'utiliser des outils intégrés sur des données numpy, car les intégrées ne peuvent tirer parti d'aucune des optimisations numpy - c'est pourquoi numpy existe. C'est complètement différent du problème ici.
Oui, excusez-moi de ne pas utiliser la terminologie correcte, je veux dire une fonction standard (également dans un package) qui permet de l'exécuter de manière vectorisée pour la vitesse. Il s'avère que np.searchsorted était la fonction que je recherchais et qu'elle est en effet beaucoup plus rapide. Merci encore pour votre aide.