donc ce que je suis ...le chargement d'une double liste liée à partir d'une base de données SQL
QueueList
{Id,Queue_Instance_ID, Parent_Queue_Instance_ID, Child_Queue_Instance_ID}
ce sera le moyen le plus efficace pour farcir cela dans un LinkedList<QueueList>? fondamentalement pensez-vous que je peux aller plus bas que o(n^2)?
merci.
En y réfléchissant un peu, vous pouvez le faire en temps O (n), même si cela prendra un peu plus de choses qui ajouteront un peu de frais généraux. (Toujours sur)).
Vous pouvez utiliser un système de hachage universel afin de pouvoir créer une bonne table de hachage. Essentiellement, hachage par l'ID d'instance.
-Prenez chaque file d'attente et jetez-la dans un noeud doublement lié. - Insérez chaque noeud dans la table de hachage. - Lorsque vous insérez, vérifiez si le parent et/ou l'enfant sont dans la table de hachage et créez un lien en conséquence. _ Lorsque vous avez terminé, commencez en tête (ce que vous devriez savoir au premier passage), parcourez la liste et ajoutez-la à votre LinkedList ou utilisez simplement la liste double liée qui en résulte.
Ceci prend un passage qui est O (n), et la table de hachage prend O (n) pour initialiser et les insertions sont O (1).
Le problème qui vous reste est de choisir une bonne implémentation de hashtable qui vous donnera ces résultats.
En outre, vous devez tenir compte de la charge de mémoire, car je ne sais pas combien de résultats vous attendez. Espérons assez pour garder en mémoire.
Je ne connais pas ou ne pense pas qu'il existe une solution basée sur une requête SQL, mais mes connaissances SQL sont très limitées.
Espérons que cela aide!
O (n) est meilleur que O (n^2), non? ;)
Je suppose que les identifiants parent et enfant sont en fait les identifiants précédent et suivant dans la liste.
Placez d'abord les éléments dans un dictionnaire pour pouvoir les rechercher facilement sur le QueueInstanceId. Dans cette boucle, vous trouvez également le premier élément. Ensuite, vous ajoutez simplement les éléments à la liste liée et utilisez le dictionnaire pour obtenir l'élément suivant. Exemple en C#:
Dictionary<int, QueueList> lookup = new Dictionary<int, QueueList>();
QueueList first = null;
foreach (QueueList item in source) {
lookup.Add(item.QueueInstanceId, item);
if (item.ParentQueueInstanceId == -1) {
first = item;
}
}
LinkedList<QueueList> list = new LinkedList<QueueList>();
do {
list.AddLast(first);
} while (lookup.TryGetValue(first.ChildQueueInstanceId, out first));
Ajout d'éléments dans un dictionnaire et de les amener par la clé sont O (1) opérations, et chaque boucle est la longueur de la liste d'origine, il est donc tout une opération de O (n).
merci beaucoup, Guffa. Cela a tout à fait du sens. c'était la solution que je cherchais, mais parfois c'est dur à la fin de la journée de travail ... – countach16
Que voulez-vous faire de plus que simplement les mettre dans la liste chaînée? L'ajout d'un élément dans une LinkedList est une opération O (1), donc ajouter n éléments est une opération O (n). –
Guffa
Je veux les mettre dans le bon ordre. Je vais obtenir une liste dans un ordre aléatoire si je les sélectionne simplement dans la base de données. – countach16
Pourquoi les obtiendriez-vous dans un ordre aléatoire si vous les sélectionnez? Vous les obtiendrez sans aucun doute plus rapidement avec la base de données qu'avec le code, surtout si la table est indexée. –