Structure de données

[MattOPI]

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
- 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 ^^
-----

[Jack]

C'est destiné à un langage particulier?

PS: j'espère que tu témoigneras davantage de gratitude à ceux qui t'ont répondu que la dernière fois.

[MattOPI]

Je me posais la question afin de mettre en place cette structure de données en python.
Mais en soit cette question ressemble plus à la recherche d'une structure de données qui met en œuvre le type abstrait qui à les propriétés données au dessus.
Je ne sais pas si il y a déjà des structures de données qui répondent à ces critères dans certains langages, mais du coup, si c'est faisable je me demandais comment cela pourrais être implémenté.
Peut-être avec une table de hachage où quelque chose dans le genre. Et la méthode pour implémenter cela n'est pas dépendante d'un langage en particulier à priori

ps : Désolé Jack si j'ai pu me montrer 'ingrat' lors de ma première question, ce n'est pas une excuse en soit mais c'était la première fois que j'était amené à utiliser un forum et je n'ai pas particulièrement fait attention. Je serais plus vigilant à l'avenir

[Jack]

ps : Désolé Jack si j'ai pu me montrer 'ingrat' lors de ma première question, ce n'est pas une excuse en soit mais c'était la première fois que j'était amené à utiliser un forum et je n'ai pas particulièrement fait attention. Je serais plus vigilant à l'avenir

Tout va bien alors

Je te laisse dans les mains des spécialistes de python et de modélisation de données.

[A voir en vidéo sur Futura]

[Merlin95]

Pourrais tu traduire ça en termes concrets ?
Par exemple en quoi la recherche séquentielle ne répond pas au problème en étant entièrement explicite.

Après je pourrais chercher d'après ce que je connais.

[pm42]

- la recherche d'un élément dans la structure de données se fait en cout constant
- la concaténation de deux instances de cette structure de données est constante aussi

Il n'y a pas beaucoup de structure de données où la recherche se fait en coût constant.
Donc on arrive aux tables de hachage mais leur concaténation n'est pas en coût constant : elle est en n ne serait que parce qu'il faut bien gérer les éventuels doublons.
Ce sujet des doublons va compliquer la concaténation en temps constant pour toute structure à accès en temps constant puisqu'elles sont basées sur des index.

Quand je tombe sur ce genre de problème, typiquement en datascience avec des gros jeux de données, je retravaille un peu l'algo pour pouvoir utiliser à chaque étape une structure adaptée.
Mais je ne connais de pas de solution générale et je ne suis pas sur qu'elle existe : en tout cas, je n'en vois pas dans les librairies habituelles.

[MattOPI]

Le problème de la recherche séquentielle c'est que tu doit parcourir les éléments de la liste, savoir si un entier donné est dans la liste prendra en moyenne n comparaisons (moins en réalité mais c'est l'ordre de grandeur)
Donc si tu as une liste d'entier vraiment grande par exemple, savoir si un entier donné appartient à cette liste peut être 'long'
Dans une table de hachage en revanche, la construction est telle que si veut savoir si une entier dans stocké dans la table cela ne te coute que quelques opérations quelque soit l'entier ou sa position dans la table
Le cout de recherche est donc constant et ne dépend pas de la taille de la table ou du nombre d'éléments stockés dedans

[MattOPI]

D'accord, merci beaucoup pm42, j'ai posé cette même question sur d'autre forums en parallèle mais je ne reçois que très peu de réponses donc il y a en effet peu de chances pour que ce soit réalisable.
La question n'est pas là depuis longtemps donc peut-être que quelqu'un avec une solution miracle apparaitra?
Mais sinon, je vais suivre ton conseil et repenser mon algo pour éviter d'avoir à me confronter à ce genre de problématique ^^

[pm42]

La question n'est pas là depuis longtemps donc peut-être que quelqu'un avec une solution miracle apparaitra?

Il est possible qu'elle existe et que je l'ignore. Mais j'ai fait quelques recherches avant de répondre pour vérifier que je n'avais pas raté une nouvelle structure sans rien trouver.
Si la solution en question existe, je suis intéressé.

[Merlin95]

Ok pour ma recherche séquentielle, pour la table de hachage alors en quoi ça ne convient pas ?

[pm42]

Ok pour ma recherche séquentielle, pour la table de hachage alors en quoi ça ne convient pas ?

Parce que la concaténation de 2 tables de hachage impose une forme de réhachage qui n'est pas en temps constant mais en O(n).

[MattOPI]

La table de hachage ne semble pas convenir parce que si la recherche est en cout constant, la concaténation, elle, ne l'est pas, si je me donne deux tables de hachages et que je veux en crée une troisième contenant tout les éléments de la première et de la deuxième, je devrais par exemple parcourir toute la deuxième table et ajouter un à un ses éléments à la première table ce qui est a un cout linéaire par rapport à la taille de la deuxième table.

[MattOPI]

Re bonjour pm42

Du coup, je n'ai définitivement pas réussi à trouver une structure comme celle que j'espérais, mais le résultat le plus concluant que j'ai pu obtenir ce serais d'utiliser une structure du type 'Union-Find' tu connais peut-être déjà?
https://fr.wikipedia.org/wiki/Union-find et sinon il y a quelques vidéos qui explique bien

Merci pour ton aide en tout cas ^^

[pm42]

Du coup, je n'ai définitivement pas réussi à trouver une structure comme celle que j'espérais, mais le résultat le plus concluant que j'ai pu obtenir ce serais d'utiliser une structure du type 'Union-Find' tu connais peut-être déjà?
https://fr.wikipedia.org/wiki/Union-find et sinon il y a quelques vidéos qui explique bien

Sans savoir pour quel usage exact c'est, difficile à dire. C'est quand même assez spécialisé comme structure.
Comme tu ne parlais pas de classe d'équivalence et que l'union-find ne va te donner un accès temps-constant qu'après avoir aplati l'arbre sinon tu vas rester en O(log(n)).

[Shuffle777]

Bonsoir,

Je ne connais aucune structure "atomique" (non composée) qui réponde à ces critères. En revanche, une collection (tableau) de tables de hachage pourrait ressembler à une solution.

La recherche ne serait pas en temps constant, mais en O(N), où N serait le nombre de tables de hachage, ce qui reste tout de même extrêmement rapide si la fonction de hachage n'est pas trop complexe. La "concaténation" (ajout de la nouvelle table dans la collection) est en temps constant si le tableau est de taille fixe.

Peut-on savoir, ou au moins avoir un ordre d'idée du besoin ? Je suis toujours parmi les premiers à vouloir optimiser un maximum, mais il ne faut pas oublier qu'avec la puissance des machines actuelles, il est rarement justifié d'avoir des exigences aussi fortes que "j'ai besoin de tout en temps constant".

[Shuffle777]

edit : Après réflexion, un tableau de tables de hachages ne convient pas pour une concaténation en O(1). Je propose donc plutôt une liste chaînée de tables de hachage.

[pm42]

La recherche ne serait pas en temps constant, mais en O(N), où N serait le nombre de tables de hachage, ce qui reste tout de même extrêmement rapide si la fonction de hachage n'est pas trop complexe. La "concaténation" (ajout de la nouvelle table dans la collection) est en temps constant si le tableau est de taille fixe.

Cela marche dans certains cas, si le nombre d'entrée par structure individuelle est beaucoup plus grande que le nombre de structures. En gros, si on concatène peu de tables de hachages mais qu'elles contiennent beaucoup d'éléments.
Mais si on concatène des milliers de table de hachage contenant chacune 100 éléments, la complexité du temps d'accès redevient en O(n) où n est le nombre total d'éléments.
On perd également toute forme de contrôle d'unicité habituel des tables de hachage ce qui peut suivant le sujet être un problème ou pas.

edit : Après réflexion, un tableau de tables de hachages ne convient pas pour une concaténation en O(1). Je propose donc plutôt une liste chaînée de tables de hachage.

La liste chaînée est la plus simple et fonctionne ici en effet. Avec les librairies modernes, quand on veut les avantages des 2, on utilise une implémentation récente du Vecteur.