Structure de données pour les relations

Question

Je suis en train de convertir un VB6 en C# et je veux rendre ma structure de données qui détient des valeurs et des relations plus efficaces. Dans VB j'ai une collection de valeurs et une autre collection de relations entre ces valeurs avec des priorités pour ces relations. J'ai aussi un algorithme qui quand un ensemble de valeurs est passé à lui toutes les relations requises pour joindre ces valeurs ensemble est retourné. Par exemple, supposons que la collecte de valeurs contient de 1 à 10 et la collection de relations contient

1,2
3,2
5,2
2,8
8,10
9,10

Si l'entrée a été 1,9,10 les relations de retour serait -

1,2
2,8
8,10Comme il peut y avoir plusieurs chemins, le plus petit nombre de relations serait renvoyé mais il y a une mise en garde des priorités de relation. Si une relation a une priorité plus élevée, cette relation sera ajoutée et le reste des relations sera ajouté à partir de là. Je pense à utiliser un Disjoint-set data structure mais je ne suis pas sûr.

Des idées?

Merci

Plus d'informations -

Le nombre de valeurs serait normalement inférieur à 100 et les relations moins de 500. Les collections sont statiques et l'algorithme seront utilisés encore et encore à trouver des chemins. Aussi, je n'ai pas demandé cela, mais l'algorithme de Disjoint-set data structure serait-il le plus efficace?

Answer 1

Cela ressemble à ce que vous avez est un Graph. C'est une structure avec des nœuds et des arêtes. Il y a many many libraries et des outils qui traitent des graphiques. Microsoft même mis un document sur la façon de traiter avec eux. Je pense que les graphiques sont excellents et extrêmement utiles dans de nombreuses situations.

Un gros avantage avec les graphes est la possibilité d'assigner des priorités aux arêtes entre les nœuds. Ensuite, quand vous voulez trouver le chemin entre deux nœuds, boom, le graphique peut choisir le chemin avec la priorité idéale.

Dans votre situation, vos valeurs sont les nœuds et vos relations sont les arêtes.

Answer 2

Vous devez vous demander (et nous dire) quel type d'utilisation vous attendez. Est-ce que ces relations sont ajoutées dans l'ordre ou de manière aléatoire, vos requêtes viennent dans l'ordre (comme vous les montrez) ou au hasard, et est-ce essentiellement un processus par lots - les charger, lire les requêtes - ou pensez-vous faire est-il "en ligne" dans le sens où vous pouvez en ajouter, en interroger quelques-uns, puis en ajouter d'autres et en interroger d'autres? Savez-vous combien vous voulez stocker à l'avance, et combien prévoyez-vous de stocker? Douzaines? Milliers? Des dizaines de millions?

Voici quelques suggestions:

• si vous savez d'avance combien vous comptez stocker, ce n'est pas vraiment grand nombre, vous ne vous attendez pas à ajouter les après le premier chargement jusqu'à, il ne sont pas des doublons dans la côté gauche de la paire, et ils sont raisonnablement « dense » dans le sens qu'il n'y a pas de grands écarts entre les chiffres dans la main gauche un de la paire , alors vous voulez probablement a n tableau L'insertion est O (1), l'accès est O (1), mais ne peut pas avoir des index en double et l'étendre après que vous l'ayez construit est une douleur.
• si le nombre est vraiment grand, comme> 10 , vous avez probablement besoin d'un type de base de données. Les bases de données sont relativement très lentes - 4 à 5 ordres de de magnitude supérieure à celles des structures de données en mémoire - mais gèrent des données très volumineuses.
• Si vous avez des insertions après la première charge , et vous vous souciez de l'ordre , vous allez vouloir un peu sorte d'arbre, comme un arbre 2-3. Insertion et accéder à la fois O (lg n). Vous trouverez probablement un implmentation sous un nom comme « liste ordonnée » (je ne suis pas un gars C#.)
• La plupart tous les autres cas, vous avez probablement veulent un hachage. L'insertion moyenne et accès à la fois O (1), comme un tableau; pire des cas [que vous ne frapperez pas avec ces données] est O (n)