J'ai une liste de dictionnaires comme entrée: Je dois modifier le champ Ceci est pour un moteur de recherche et je vis des réponses les plus rapides possible, de sorte que la boucle sur plusieurs listes de 100+ valeurs de plus de 100 ans puisse trouver le bon dictionnaire peut prendre beaucoup de temps. En ce moment, la meilleure façon dont je puisse penser cela, est de conserver un enregistrement de l'index de chaque dictionnaire, je peux donc utiliser cela pour appeler un dictionnaire spécifique de la liste. Comme ceci: P> "sélectionné" code> de false code> à vrai code> dans l'un de ces dictionnaires, puis renvoyez-la. Je comprends que cela rendrait beaucoup plus de sens pour que cet objet soit un dictionnaire de dictionnaires avec les clés de chaque dictionnaire étant le champ "nom" code>, mais je ne contrôle pas cette entrée et ne peut pas changer le Schéma de la sortie. P> indexsOfOptions = {"<name>": <indexOfDictionary>, etc...}
listOfOptions[indexsOfOptions["<name>"]]["selected"] = True
4 Réponses :
Voici une solution de complexité de temps O (n) et je ne pense pas que cela puisse être une autre solution mieux en termes de complexité du temps, car vous devez itérer sur toute la liste:
[{'name': 'a', 'selected': True}, {'name': 'b', 'selected': False}]
Avancé votre réponse depuis quand tout est dit et un il fournit le meilleur timing des différents algorithmes.
a essayé diverses méthodes comme suit.
filter 36 ms ± 3.36 ms per loop (mean ± std. dev. of 7 runs, 10 loops each) for_loop 15.8 ms ± 780 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
Êtes-vous sûr qu'il n'y a qu'un seul dict avec la clé souhaitée?
@ Kederrac - Comme mes tests de synchronisation sont pour la clé à la fin de la liste, les résultats de la synchronisation ne changeront pas même s'il y a plusieurs dicts avec la même clé. Mais, en tant que question de mise en œuvre, nous changerons le code de sorte que cela ne s'est pas rompu de ses boucles en cas d'attente de multiples hits clés.
Mais vos tests ne sont pas pertinents car le code n'a aucun sens que si la clé souhaitée est une et est à la fin
Vous pouvez tester le pire des scénarios si vous voulez
@ Kederrac - Je fournis une comparaison des pires périodes (qui est courante pour la comparaison des algorithmes). Si la clé est, par exemple, sont au début de la liste (meilleur cas), les temps sont comparables.
Vous n'avez pas le pire des cas de scénario d'abord
Deuxièmement, toutes vos fonctions sont mal implémentées pour la sélection multi-dict
@ Kederrac - OK, je pourrais être incorrect sur le pire des cas et toutes mes fonctions pourraient être des "mauvaises implémentations". Pourriez-vous m'éclairer?
Le pire des cas du scénario sera lorsque tous les dicts sont les mêmes et que vous devez tous les changer
Étant donné que toutes vos fonctions ne recherchent qu'une seule valeur à modifier échouera pour tout scénario multi-dict
Et je ne dis pas que sont de mauvaises implémentations, uniquement pour le scénario multi-dict
@ Kederrac - merci pour la uppote. Voir mon test étendu que j'ai effectué. Il n'y avait pas de différence dans le résultat pour le filtre et pour_loop sur le test précédent. Cela serait attendu du péché si nous supposons que la plupart du temps est consommé, entraînant une transmission de la liste plutôt que d'assigner une valeur didiconaire à la vraie.
Beaucoup mieux imo
L'OP dit "J'ai besoin de changer le champ" sélectionné "de False sur TRUE dans TRUE dans tout un de ces dictionnaires" (mettre l'accent sur le mien) et dans les commentaires que l'OP a dit "@ Kederrac doit seulement changer le champ unique" sélectionné "dans n'importe quel 1 des nombreux dictionnaires" .
@ kaya3 - merci. Nous voyons que le pire timing est le même pour changer un ou plusieurs champs. Cependant, le temps moyen est le 1/2 du pire chronométrage si nous n'avons besoin que de trouver et de modifier un seul dictionnaire (c'est-à-dire que la moitié de l'emplacement moyen est au milieu).
pour D dans la liste (filtré) n'a pas de sens, pourrait simplement être pour D dans filtré .
listOfOptions = [
{"name": "a", "selected": False},
{"name": "b", "selected": False}
]
def change(x):
[i.update({'selected':True}) for i in listOfOptions if i['name'] is x]
A generator would be the fastest way I can think of. I added it to a method that takes a string value to update something with one of your keys.
en ce moment, la meilleure façon dont je peux penser à ce faire, est de garder un enregistrement de l'index de chaque dictionnaire ... peut vous tromper si l'ordre de la liste change d'une manière ou d'une autre.
Je pense que cela signifie que les clés généralement sont au même index qu'ils étaient sur la requête précédente pour la même clé, mais l'index d'une clé donnée n'est pas garanti. Dans ce cas, vous pouvez mettre en cache le dernier index que chaque touche a été découverte, mais testez si l'indice mis en cache est toujours valide la prochaine fois que la clé est interrogée. Si c'est le cas, alors vous n'avez pas besoin de chercher; Si ce n'est pas le cas, vous pouvez faire la recherche à nouveau.
Si l'indice mis en cache n'est plus valide, mais le nouvel indice est susceptible d'être proche de l'indice mis en cache, vous pouvez faire une recherche linéaire "à double sens" à partir de l'indice mis en cache. Fondamentalement, initialisez
i = cached_index - 1 etj = cached_index + 1 , puis recherchez aveci décrémentation etj incrémentation.Si les touches sont par ordre alphabétique dans la liste (comme elles sont dans votre exemple), vous pouvez effectuer une recherche binaire au lieu d'une recherche linéaire.
Tout cela dit, il convient de comparer ces solutions, car le moyen le plus rapide de faire quelque chose dans Python est souvent de laisser les fonctions / méthodes intégrées implémentées dans C faire autant que possible le travail possible, même si Ils sont théoriquement plus lents selon la grande notation.
Une autre idée à faire avant une nouvelle recherche: disons que la clé était à l'index 900 avant. Maintenant, ce n'est pas là, mais il y a plutôt Key2 maintenant. Recherchez-vous là où Key2 était auparavant. Disons que c'était à l'index 897 avant. Ensuite, la clé pourrait avoir de bonnes chances d'être à l'index 903 maintenant.
juste itérer sur la liste
@Mayur j'ai mentionné cela. Oui, je peux le faire, mais cela augmente considérablement le temps de réponse. Je sais comment faire cela lentement. J'essaie juste de comprendre s'il y a un moyen de le faire bien, et avec une vitesse au moins similaire à la manière dont cela pourrait être fait avec les «options» étant un dictionnaire au lieu d'une liste.
Vous n'avez qu'un seul champ sélectionné pour changer ou plus?
Il semble une meilleure façon de créer
listofoptions comme dict commelistofoptions = {"A": {"nom": "A", "Sélectionné": FALSE}, "B": {"Nom ":" B "," Sélectionné ": false}}@KeDarrac doit seulement changer le champ unique "sélectionné" dans n'importe quel 1 des nombreux dictionnaires.
@Mayur Ouais j'ai mentionné ça aussi. Je ne peux pas changer le schéma pour la réponse d'entrée / sortie. J'ai demandé à cela de changer comme ça, mais même si le schéma est changé, ce sera un peu de temps et je devrai encore le faire pour la compatibilité en arrière.
Outre le commentaire où vous mentionnez de maintenir un index qui correspond à l'entrée de la liste Il n'y a pas d'autre moyen rapide d'y parvenir simplement en raison de la structure de données utilisée ici pour stocker les données
D'une manière ou d'une autre, le contenu des dictionnaires doit être examiné. Cela peut être fait "à la volée" ou via des tables de recherche pré-compilées contenant toutes les possibilités et sont calculées à l'avance. Les deux approches prennent du temps et si l'un ou le "meilleur" dépendra de la fréquence à laquelle il doit être utilisé et éventuellement de la manière dont la mémoire est consommée pour stocker toutes les tables de recherche. Le faire de manière dynamique, en moyenne, nécessiter uniquement le contenu de la moitié des dictionnaires à examiner.
Avez-vous pensé d'utiliser uniquement des fonctions intégrées qui feraient la boucle en interne (c'est-à-dire en C) plutôt que d'utiliser la boucle Python? Un exemple serait d'utiliser la fonction de filtrage pour rechercher le bon dictionnaire (basé sur la clé de nom) dont la valeur doit être modifiée.
@Darryig Ok, merci. Je vais donner cela un coup et voir comment cela se compare.
@Darrylg meh,
filtre n'est pas particulièrement plus performant qu'une boucle directe.@martineau OK. Je vais tester 3 solutions, à l'aide d'une table de recherche (je pense à simplement utiliser un dict pour cela), itération juste sur elle avec une boucle à boucle, puis en utilisant une fonction intégrée (C) comme une personne mentionné. Je vais comparer les différences de temps et voir qui en vaut la peine. À votre santé.
@MaxHarrison Votre meilleure option est d'accéder à votre approche d'index. Rien ne va battre cela en termes de vitesse et faire un index n'est pas vraiment un piratage, c'est ainsi que vous faites des choses performantes en général.
@maxharison mec, ça ne sera pas de concours. Aller avec la table de recherche. Si vous enveloppez la boucle dans une fonction, il sera pratiquement comme performant (ou mieux) que
filtre .@Darrylg en fait, le testant sur une liste de 2 000 000 La-boucle est terminée deux fois plus vite.
@ Juanpa.arrivillaga - True et vérifie avec ma simulation de différentes méthodes que j'ai postées dans une réponse.