Bien le bonjour !
Dans le cadre d'un projet libre (dont je vous avais déjà parlé ici il y a quelques temps), je me gratte fort la tête pour trouver un manière optimale (dans le sens performance, l'occupation mémoire n'est pas une priorité pour le moment) d'organiser des données, en Python.
Et comme à force de gratter, l'épaisseur de ma boite crânienne commence à dangereusement tendre vers 0, je me permet d'en appeler aujourd'hui aux nombreux talents mytico-pythoniciens ici présents =D
voilà le problème :
Je cherche à stocker une liste d'évènements datés de 0 à +I (de immédiat à I itérations dans le futur).
Plusieurs évènements peuvent avoir lieu à la même date.
Les évènements sont des objets.
Je ne peux pas vraiment me permettre de parcourir plus d'éléments que strictement nécessaire aussi bien à la lecture qu'à l'écriture (c'est du "autant temps-réel que possible").
une fois un évènement passé, il doit dégager de la liste fissa (la mémoire n'est pas un problème, mais quand même, il va y avoir beaucoup d'évènements)
Cerise sur le gâteux : pour le moment je prototype en Python pour des raisons de simplicité, mais une réécriture en C++ est planifiée, donc un algo aussi agnostique que possible est bienvenu =D
D'avance merci beaucoup.
# Tu parles de performance mais ...
Posté par totof2000 . Évalué à 5. Dernière modification le 30 juin 2023 à 12:18.
… pour pouvoir proposer une structure de données performante, il faut savoir comment tu vas accéder aux données de cette structure (insertion/accès/suppression des données) pour les traiter.
Autrement dit, il n'y a que trop peu d'infos pour permettre de t'aider.
Personnellement, je partirai d'une simple liste dans un premier temps. Si les événements doivent être traités par ordre chronologique, je m'assurerais que la liste soit "ordonnée" par timestamp. Eventuellement, si plusieurs éléments peuvent avoir lieu à la même date, je ferais peut-être une double liste : une liste d'evenements associé à un timestamp, rangé dans une liste de timestamps. Ceà dit, ce n'est peut-être pas la meilleure façon de faire : tout dépend de comment tu traiteras tes évenements par la suite.
Désolé, j'ai un peu de mal à être précis dans ma description …
De mon point de vue, C++ et python sont tellements différents qu'un algo performant dans un langage ne le sera pas forcément dans l'autre.
[^] # Re: Tu parles de performance mais ...
Posté par Krunch (site web personnel) . Évalué à 2.
+1 pour mieux définir le problème. Si on ne sait pas quelles opérations doivent être performantes, on ne peut pas recommander une structure de données.
Il est vraisemblable qu'il soit préférable de s'en tenir aux types de base. Au besoin on peut aller voir dans la bibliothèque de base (collections notamment).
https://docs.python.org/3/tutorial/datastructures.html
https://docs.python.org/3/library/datatypes.html
pertinent adj. Approprié : qui se rapporte exactement à ce dont il est question.
# listes et dictionnaires
Posté par bobo38 . Évalué à 1.
Je ne fais que des trucs simples en python et j'essaie de rester sur les types de base que viennent avec la "standard library". La plupart des problèmes peuvent être résolus avec les listes et les dictionnaires. J'utilise toujours ça comme design pattern, si bien que je peux comprendre comment mes vieux codes fonctionnent.
Tu as une chiée d'évènements avec leurs structure de données, chacun ayant ses propres données. Pour ce genre de truc je fais un dictionnaire de dictionnaires : les données chaque évènements seraient un dictionnaire, je ferais donc un dictionnaire de ces dictionnaires avec pour clé un identifiant d'évènement. Voici pour la structure de données. Dans ton cas tu peux faire un dictionnaire d'objets.
Tu as besoin d'un ordre chronologique. Pour ça ma solution standard serait une bête liste de listes. L'élément de base est une liste (ou tuple si la date de l'évènement ne peut pas changer, pas sûr que ça influence les performances) [ ]. La propriété du la liste de tels évènements c'est que quand tu tries ça ça trier d'abord par ordre du premier élément puis pas . C'est très simple et efficace. Avec cette façon de faire, la liste chonologique de tuples/listes est toujours "triée", il s'agit jute de trouver la bonne place dans la liste à l'ajout d'évènement (ça peut potentiellement être optimisé pour un algo par dichotomie, pas sûr de ce que les algos de tris de listes font en standard).
Il est ensuite possible, sans trop se fouler, d'identifier périodiquement les évènements passés dans la liste. Et de les supprimer : dans la liste et dans le dictionnaire. Pour garder les données synchronisées.
Pour la clé de dictionnaire "identifiant d'évènement" il faut être un peu malin pour éviter les doublons. Un bête +1 par rapport à la dernière entrée peut provoquer des overflows en C si la clé est un entier n bits, c'est un truc à prévoir possiblement.
Voilà mes 2 cents, de ce que je fais pour mes développements simples sans grosses contraintes de performances. Tu peux essayer ça comme benchmark, en utilisant les fonctions standards associées à ces types de données, pour tester d'autres alternatives qui seraient plus performantes (en python et en C), que tu décides de jouer à l'échelle du type de données en créant un objet ou à l'échelle de fonction de tri.
[^] # Re: listes et dictionnaires
Posté par bobo38 . Évalué à 1. Dernière modification le 30 juin 2023 à 12:38.
il est sans doute possible de virer faire une liste chronologique plus optimisée
[ [ [event0_id event1_id …]] [ [event0_id event1_id …]] … ]
où les évènements sont directement tes objets évènements. Du coup le tri se ferait juste sur les dates et donnerait par date croissante tous les évènements dans l'ordre dans lequel ils ont été "append" à la liste d'évènements. Ça retire un niveau de tri potentiellement inutile et le dictionnaire d'évènements qui n'est pas nécessaire.
Il resterait à optimiser juste l'insertion de nouvelle date "si date pas dans la liste". Et la suppression de liste dans la liste chronologique quand la date est passée. L'exécution d'évènement peut se cloturer par la suppression de l'évènement dans la liste chronologique, et si c'est le dernier évènement pour la date, la suppression de la liste d'évènements de la liste chronologique. Avec ça tu aurais un truc asynchrone sympa
# en C
Posté par OLeave . Évalué à 1.
C'est pensé en mode "C", j'ai du mal à faire autrement, peut-être utilisable dans un autre langage, mais je n'en suis pas sûr.
Si I est connu et borné, je ferais un buffer circulaire de taille I dont chaque élément pointe vers une liste d’évènements rangés en files (de pointeurs vers les objets) de taille variable.
Il faut prévoir un pointeur "instant courant" sur le buffer circulaire qui bouge d'un cran à chaque itération.
Stoker un nouvel évènement se fait en deux pointeurs, celui du buffer pointe sur la liste, qui, elle, devra présenter un pointeur vers sa fin pour y rajouter un élément.
bon courage,
# Un tas
Posté par GuieA_7 (site web personnel) . Évalué à 3.
Si j'ai bien compris ton besoin (accéder aux évènements les plus proches rapidement) c'est un problème classique, et le tas (heap) est sûrement une bonne solution. C'est une façon de ranger des éléments dans une liste/tableau en fonction d'une priorité (la date dans ton cas) de manière à accéder rapidement à l'élément le plus prioritaire.
En Python regarde le module standard heapq.
Suivre le flux des commentaires
Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.