J'ai un horodatage de DateTime Python et un grand dict (index) où les clés sont des horodarestampes et que les valeurs sont d'autres informations qui m'intéressent.
Je dois trouver la dateTime (la clé) dans l'index qui est le plus proche de l'horodatage, aussi efficacement que possible.
pour le moment je fais quelque chose comme: qui fonctionne, mais prend trop de temps - mon index dict a des millions de valeurs et je Je fais la recherche des milliers de fois. Je suis flexible avec des structures de données et ainsi de suite - les horodaques sont appropriées, de sorte que je suis itération du premier aux derniers horodatages. De même, les horodatages dans le fichier texte que je charge dans les dicts sont séquentiels. Les idées d'optimisation seraient grandement appréciées.
3 Réponses :
Les dictionnaires ne sont pas organisés pour des recherches approfondies de Miss. Ils sont conçus pour des correspondances exactes (à l'aide d'un Table de hachage ).
Vous pouvez être meilleur- Off Maintenance d'une structure ordonnée rapide et interrogeable séparée. P>
Un moyen simple de démarrer est d'utiliser le Module de bisect pour les recherches rapides O (log n), mais plus lente O (n) insertions: p> une approche plus sophistiquée Convient aux dict-dicts non statiques et non statiques, seraient d'utiliser Blist qui emploie une structure d'arbres Pour les insertions et les recherches rapides. Vous n'avez besoin que si le dict va changer au fil du temps. P> Si vous souhaitez rester avec une approche basée sur le dictionnaire, envisagez une dict-de-listes qui clôturs entrées avec des horodatages proches: P> def get_closest_stamp(ts):
'Speed-up timestamp search by looking only at entries in the same hour'
hour = round_to_nearest_hour(ts)
cluster = daydict[hour] # return a list of entries
return min(cluster, key=lambda t: abs(ts - t))
Excellente réponse complète! (C'est bien de vous voir ici sur ce que, au fait, Raymond. :))
Pourquoi I + 2 en retour min (s [max (0, I-1): I + 2], clé = lambda T: ABS (TS - T))? Me semble comme ça pourrait être +1 et cela fonctionnerait toujours
Si votre liste est vraiment triée et non seulement "grossièrement séquentiel", vous pouvez utiliser une recherche binaire. Jetez un coup d'œil au BISECT Documentation du module pour plus d'informations.
Les objets DateTime sont comparables les uns aux autres. Faites donc une liste triée de votre clé / valeur de votre clé comme suit: pour chaque élément l'élément myPairs [i] code> , myPairs [I] [0] code> est la touche code> DateTime code> et MyPairs [i] [1] code> est la valeur. P> Vous pouvez rechercher cette liste efficacement en utilisant biseect_left code>: p> myPairs [i] code> est l'élément avec la dateTime la plus basse non plus tôt que cibleDateTime code>. Mais l'élément préalable (s'il y en a une) peut être plus proche à temps pour TargetDateTime code>. Ou cibleDateTime code> peut être ultérieurement supérieur à tout moment dans MyPairs code>. Vous devez donc vérifier: P> if i > 0 and i == len(myPairs):
i -= 1
elif i > 0 and targetDatetime - myPairs[i-1][0] < myPairs[i][0]- targetDatetime:
i -= 1
Est-ce que la grande dicte est relativement statique, ou vous ajoutez et supprimez-vous souvent des entrées?
La dicte est effectivement entièrement statique.
Merci beaucoup pour toutes les réponses utiles. J'ai eu un peu de jeu avec les suggestions et on dirait que je serai certainement en mesure de résoudre mon problème, les augmentations de vitesse sont énormes. À la maison maintenant, je vais donc avoir un peu plus de jeu demain et mettre à jour avec ma mise en œuvre finale.
Merci encore pour toutes les réponses, c'est une communauté aussi brillante. Parce qu'un dict a du sens dans le reste du code, je n'ai rien à voir pour cette recherche, j'ai fini par faire une liste des touches de dict, le triez, puis utilisez bisect_left pour la recherche, puis accédant aux valeurs de mon dict d'origine à l'aide de la clé de la liste. L'augmentation de la vitesse est insensée, comme 10k fois plus rapidement.