Discussion :

[matthi]

Bonjour ^^
Je suis à la recherche d'une structure de données où :
- la recherche d'un élément dans la structure de données se fait en cout constant ( déterminer si '3' est dedans par exemple, sans notion d'ordre ou quoi que ce soit)
- la concaténation de deux instances de cette structure de données est constante aussi
Vous avez une idée ce que ca pourrais être ou à quoi ca ressemblerais?

Pour exemple :
- la recherche d'un élément dans une liste est linéaire en la taille de la liste, mais la concaténation de deux listes est en cout constant
- La recherche d'une clé dans un dictionnaire est en cout constant mais la concaténation de deux dictionnaires est linéaire en la taille du dictionnaire

Je suppose qu'une telle structure à forcement des defaults autre part, comme la suppression d'élément par exemple,
mais je n'ai pas vraiment trouvé d'idée qui permettrais d'implémenter une structure avec ces propriétés et est-ce seulement possible?

Merci d'avance pour votre aide ^^

[tbc92]

Ce que tu recherches n'existe pas.
Bon, on pourrait jouer sur les mots, on peut concevoir un truc qui serait à coût constant quelque soient les volumes. Quand on fait une recherche, si la recherche aboutit en moins d'une heure, alors on fait en sorte que le programme tourne dans le vide, pendant une heure, avant de dire qu'il a trouvé ce qu'on cherchait. Pareil pour la concaténation.
On est à coût constant sur ces 2 critères.
Très lent, mais à coût constant.

Même dans les cas de dictionnaires, on n'est pas vraiment à coût constant sur les recherches. Les temps augmentent quand les volumes augmentent. Ils augmentent très peu, mais ils augmentent.

[matthi]

Quand je parle de cout constant ici, je veux plutôt dire en O(1), c'est plutôt de l'ordre de grandeur dont je parle.
Pour ce qui est des dictionnaires, le cout de recherche d'une clé est considéré en O(1) puisque les clés sont rangées dans une table de hachage.
Il est vrai que, du fait que l'on doive redéfinir la taille de la table de hachage si jamais l'on y ajoute trop d'éléments, il arrive que le cout d'ajout d'un élément soit important, mais l'ajout de beaucoup d'élément amortie ce cout. C'est pourquoi l'ajout d'un élément est considéré comme en cout constant en moyenne. (d'autant que cela dépend de la mémoire alloué à la table de hachage au début)

Pour ce qui est de la recherche d'élément c'est pareil, le cout reste en O(1) ou si il dépend de n c'est de manière tellement faible qu'il faudrait manipuler un nombre de données gigantesque pour que l'impact soit réellement conséquent.

De plus, ce que je cherche est une structure de données* qui permettrait de mettre en œuvre le type abstrait ayant les propriétés que j'ai données au dessus. Je cherche une manière d'implémenter quelque chose avec de telles propriétés sans me préoccuper des couts éventuelles comme l'augmentation de l'espace mémoire, je suppose que je disposerais d'assez de mémoire à la base, je regarde seulement le nombre de comparaison.

Je prend cependant note qu'il est en effet probable que cela soit impossible, mais je n'ai pas l'impression que ce soit pour les raisons que vous citez? Ou peut-être vous ai-je mal compris?

Merci beaucoup pour votre réponse en tout cas

[Flodelarab]

Bonjour

Il me semble que tu confonds "concaténation" et "copie". 2 dictionnaires peuvent être concaténés sans être recopiés.

[WhiteCrow]

Hello,
ta recherche est inhabituelle, dans le sens où bien qu'elle transpire le «je voudrais le plus rapide dans tous les aspects» usuel elle semble un peu plus réfléchie bien qu'un peu confuse.
Une recherche, quelle que soit la recherche, d'un élément dans une collection sera toujours en O(log(n)) si la comparaison de deux éléments est en O(1) (je parle en complexité temporelle classique) à moins de confondre l'élément et une clé d'indexation. L'accès aléatoire à un index précis peut lui se faire en O(1).
Et franchement, log(n) c'est super bien … faut pas déconner 😇

La concaténation de deux collections est une autre paire de manche. Parfois le plus simple est de faire des recherches dans chaque collection, la recherche étant rapide.
Une autre approche serait d'associer à la collection un (ou plusieurs) filtre de bloom qui permettrait d'éviter certaines recherches. Mais bon, je pars du principe que les recherches sont plus courantes que les concaténations …

Maintenant si la concaténation est plus courante que la recherche alors pourquoi ne pas essayer de regarder à adapter une sd comme les tas de fibonacci ? ptêt une idée à creuser 🤔

Quand à trouver une bdd qui implémente ça … c'est encore plus confusant comme remarque.
Quel est ton but ?

[matthi]

Bonjour ^^
C'est vrai que deux dictionnaire peuvent être concaténer sans être recopié.
Mais une concaténation reviens entre autre à une recopie puisque l'on devra parcourir un dictionnaire pour l'ajouter élément par élément à l'autre dictionnaire. Le temps d'exécution reste du même ordre de grandeur (O(n) quand l'ajout d'élément est en O(1)).
L'espace mémoire utiliser est moindre par contre, mais ce n'est pas ce qui m'intéresse ici.

Ce que j'entend pas concaténation, c'est partir de 2 structures de données identiques e1 et e2 contenant respectivement les ensembles d'éléments E1 et E2 et crée une structure de données e0 identique à e1 et e2 et contenant les éléments (E1 U E2)

[matthi]

Hello WhiteCrow ^^

C'est vrai que c'est un peu ca xD,
C'est vraiment pour gagner en rapidité mais ca ne me dérange pas de sacrifier d'autres paramètres comme l'espace mémoire pas exemple.
Pour l'application que je veux en faire, il y a en effet beaucoup de concaténation d'ensembles (la structure que je peux modifier) c'est pour cela que j'ai vraiment besoin qu'elle soit en O(1)
Et l'idée serait de pouvoir s'épargner le parcours d'une liste en regardant si son premier élément appartient déjà à un ensemble donné (les mêmes que précédemment). La problématique que je me pose est donc est-ce plus rapide de parcourir ma liste ou de rechercher si son premier élément est dans un ensemble, il est clair que si la recherche peut se faire en O(1) comme dans une table de hachage je gagne.
C'est pour cela que me je posais la question de savoir si une telle structure pouvait exister sans me faire perdre sur les concaténations.

Je vais regarder les tas de Tas de Fibonacci si la recherche se fait en O(ln(n)) il y a des chances pour que j'y gagne, merci beaucoup ^^

ps : désolé je me suis trompé, c'est bien structure de données que je voulais marquer et non base de données