J'ai une grande piscine d'objets avec numéro de départ et numéro de fin. Par exemple: supposant que les intervalles ne se chevauchent pas les uns avec les autres. Et j'écris une fonction qui prend un numéro et localisez l'objet qui (bas, élevé) le contient. Dites données 333, je veux les 3ème objets sur la liste. Y a-t-il une façon que je puisse le faire aussi efficacement que possible, à court de recherche linéaire? Je pensais à une recherche binaire, mais j'ai des difficultés à faire face à la vérification de la gamme.
4 Réponses :
Pensez si cela vaut la peine de trier les données.
Si vous souhaitez rechercher beaucoup de fois, vous devez tout d'abord trier, puis rechercher à l'aide de la recherche binaire. Ce sera Ainsi, le tri, puis la recherche doit être effectué uniquement si PS Vous pouvez utiliser une autre approche pour trier et rechercher, comme proposé dans d'autres réponses, de toutes manières, la conclusion reste: le faire uniquement si
Si vous voulez seulement rechercher quelques fois, cela ne devrait pas - et vous ne pouvez pas éviter la recherche linéaire. La complexité totale de vos recherches sera O (n * k) , où n est le nombre d'éléments et k est le nombre de recherches.
O (nlogn) pour le tri et O (klogn) pour la recherche K fois, vous obtenez donc le total de O ((n + k) logn) .
k> = logn
k> = logn
Oui, bien que la piscine d'objets soit corrigée, je m'attends à faire de la recherche à plusieurs reprises, alors le tri semble justifié. Merci.
Tout d'abord, il n'est pas du tout clair que la recherche binaire est justifiée ici. Il se peut que la recherche linéaire soit plus rapide lorsque le nombre d'intervalles est petit.
Si vous êtes préoccupé par la performance, la chose prudente à faire est de profiler le code et peut-être de comparer les deux méthodes sur vos entrées typiques. < / p>
Avertissement de côté, la recherche binaire pourrait être mise en œuvre en triant les intervalles une fois, puis à l'aide de la dans ce qui précède, je suppose que les intervalles ne se chevauchent pas et que l'intervalle inclut à la fois ses points de départ et d'extrémité. Enfin, pour améliorer les performances, on peut envisager une factorisation biseect module pour effectuer la recherche: [intervalle [1] pour intervalles d'intervalle] hors de la fonction et le faire juste une fois au début.
Vous pouvez utiliser le module BISECT: http://docs.python.org/library/bisect .html
Vous devez trier vos données une fois, puis utiliser BISECT: P>
import bisect data=None tuples=[(0, 128, None), (235, 865, None), (999, 2333, None)] tuples.sort() print tuples print bisect.bisect(tuples, (-1,)) # 0 print bisect.bisect(tuples, (1,)) # 1 print bisect.bisect(tuples, (333,)) # 2 print bisect.bisect(tuples, (3333,)) # 3
Merci pour la suggestion de bisiger, ce qui semble être le consensus commun dans ce cas.
Si la vitesse de recherche est de la plus haute importance, vous pouvez créer une table de recherche (comme déjà commenté par S.Lott). Cela prendra la mémoire o em> ( r em>) (où r em> est la taille de la plage), o em> ( r em>) temps de pré-traitement et o em> (1) temps de recherche fort>. Créez un tableau de la taille de la plage et remplissez chaque élément avec un pointeur sur les données ou null. lookup = {}
for low, high, data in source_ranges:
for i in range(low,high): # or maybe high+1 if the ranges are inclusive
lookup[i] = data
Est-ce "vaut" le tri pour utiliser une recherche binaire? [Si vous envisagez de rechercher quelques fois, il ne "vaut pas", si vous envisagez de rechercher beaucoup de fois, c'est]
Les objets devraient être triés.
Quelle est la limite supérieure et inférieure absolue de ces chiffres? Vous pourrez peut-être élargir les gammes dans un «index mappé sur le bit» approprié où vous énumérez simplement toutes les valeurs de la gamme.