Laden eine doppelt verkettete Liste aus einer SQL-Datenbank

Question

so ist es das, was ich habe ...

QueueList

{Id,Queue_Instance_ID, Parent_Queue_Instance_ID, Child_Queue_Instance_ID}

was der effizienteste Weg, dies ein LinkedList<QueueList> in stopfen? im Grunde denken Sie, ich kann tiefer gehen als o(n^2)?

danke.

Answer 1

Wenn du ein bisschen darüber nachdenkst, kannst du es in O (n) Zeit machen, auch wenn es etwas zusätzliches Zeug braucht, das etwas Overhead bringt. (Immernoch an)).

Sie könnten eine Art universelles Hash-Schema verwenden, damit Sie eine gute Hashtable erstellen können. Im Wesentlichen Hash durch die Instanz-ID.

-Nehmen Sie jede Warteschlange und werfen Sie sie in einen doppelt verbundenen Knoten irgendeiner Art. - Fügen Sie jeden Knoten in die Hashtabelle ein. - Wenn Sie einfügen, überprüfen Sie, ob die Eltern und/oder Kinder in der Hashtabelle sind und verknüpfen Sie sie entsprechend. _ Wenn du fertig bist, beginne am Kopf (was du im ersten Durchgang herausfinden kannst), gehe die Liste durch und füge sie zu deiner LinkedList hinzu oder verwende einfach die doppelt verknüpfte Liste.

Dies dauert einen Durchgang, der O (n) ist, und die Hashtabelle nimmt O (n) zu initialisieren und Einsätze sind O (1).

Das Problem, das für Sie übrig bleibt, ist die Auswahl einer guten Hashtabellen-Implementierung, die Ihnen diese Ergebnisse liefert.

Außerdem müssen Sie den Speicheraufwand berücksichtigen, da ich nicht weiß, wie viele Ergebnisse Sie erwarten. Hoffentlich genug, um in Erinnerung zu bleiben.

Ich weiß nicht oder denke, dass es eine SQL-Abfrage-basierte Lösung gibt, aber meine SQL-Kenntnisse sind sehr begrenzt.

Hoffe, das hilft!

Answer 2

O (n) ist besser als O (n^2), oder? ;)

Ich nehme an, dass die Eltern- und Kind-ID tatsächlich die vorherige und nächste ID in der Liste sind.

Zuerst legen Sie die Elemente in ein Wörterbuch, so dass Sie leicht auf der QueueInstanceId nachschlagen können. In dieser Schleife finden Sie auch das erste Element. Dann fügen Sie einfach die Elemente zur verknüpften Liste hinzu und verwenden das Wörterbuch, um das nächste Element zu erhalten. Beispiel in 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)); 

Elemente zu einem Wörterbuch Hinzufügen und bekommen sie durch Schlüssel sind O (1) Operationen, und jede Schleife ist die Länge der Quellenliste, so dass es alle ein O (n) Betrieb.