Wie soll ich meine Graphenstruktur (sehr langsam insertion) ändern?

Question

Dieses Programm ich tue ist über ein soziales Netzwerk, das heißt, es gibt Benutzer und ihre Profile. Die Profile Struktur ist UserProfile.

Nun gibt es verschiedene mögliche Graph-Implementierungen, und ich glaube nicht, dass ich das beste bin mit. Ich habe eine Graph Struktur und innen, es gibt einen Zeiger auf eine verknüpfte Liste von Typ Vertex. Jedes Vertex Element hat einen Wert, einen Zeiger auf den nächsten Vertex und einen Zeiger zu einer verketteten Liste von Typ Edge. Jedes Edge Element hat einen Wert (so ich Gewichte definieren kann und was auch immer es gebraucht wird), einen Zeiger auf die nächste Edge und einen Zeiger auf den Vertex Besitzer.

Ich habe eine 2 Beispieldateien mit Daten zu verarbeiten (im CSV-Stil) und Einsatz in das Graph. Die erste ist der Benutzerdaten (ein Benutzer pro Zeile); die zweite ist die Benutzerbeziehungen (für den Graphen). Die erste Datei wird schnell in die grafische Darstellung eingefügt, weil ich immer an der Spitze einsetzen und es ist wie ~ 18000 Benutzer. Die zweite Datei dauert eine Ewigkeit, aber ich einfügen noch die Kanten an der Spitze. Die Datei hat etwa ~ 520000 Linien Benutzer Beziehungen und dauert zwischen 13-15mins in die Grafik eingefügt werden soll. Ich habe einen schnellen Test und Lesen der Daten ist ziemlich schnell, augenblicklich wirklich. Das Problem ist in der Insertion.

Dieses Problem besteht, weil ich ein Diagramm mit verknüpften Listen für die Eckpunkte umgesetzt. Jedes Mal, wenn ich brauche eine Beziehung einzufügen, muss ich für 2 Ecken nachzuschlagen, so dass ich sie miteinander verknüpfen können. Das ist das Problem ... Dadurch für ~ 520000 Beziehungen, dauert eine Weile.

Wie soll ich dieses Problem lösen?

Lösung 1) Einige Leute mir empfohlen, den Graph (der Scheitel Teil) als ein Array statt einer verknüpften Liste zu implementieren. Auf diese Weise habe ich den direkten Zugriff auf jede Ecke und das Einfügen wird wahrscheinlich erheblich gehen fallen. Aber ich weiß nicht, wie die Idee eine Reihe von Zuweisung mit [18000] Elementen. Wie praktisch ist das? Meine Beispieldaten haben ~ 18000, aber was, wenn ich brauche viel weniger oder viel mehr? Die verlinkte Liste Ansatz hat, dass die Flexibilität, kann ich, was Größe, die ich will, solange es dafür Gedächtnis ist. Aber das Array nicht, wie soll ich eine solche Situation bewältigen? Was sind Ihre Vorschläge?

verkettete Listen zu verwenden ist gut für die Platzkomplexität aber schlecht für die Zeitkomplexität. Und mit einem Array ist gut für die Zeitkomplexität, aber schlecht für die Platzkomplexität.

Alle Gedanken über diese Lösung?

Lösung 2) Dieses Projekt erfordert auch, dass ich eine Art von Datenstrukturen, die schnelle Suche ermöglicht auf Basis einen Namensindex und einen ID-Index. Dazu habe ich beschlossen, Hash-Tabellen zu verwenden. Meine Tabellen sind mit separaten Verkettungs als Kollisionsauflösung implementiert und wenn ein Ladefaktor von 0,70 zu erreichen ist, die ich normalerweise die Tabelle neu erstellen. Ich stütze die nächste Tabellengröße auf diesem http://planetmath.org/encyclopedia/GoodHashTablePrimes.html.

Derzeit halten beide Hash Tables einen Zeiger auf die UserProfile statt Vervielfältigung des Benutzerprofils selbst. Das wäre dumm, Ändern von Daten würden drei Änderungen erfordern und es ist wirklich dumm, es so zu tun. So spare ich nur den Zeiger auf die UserProfile. Der gleiche Benutzerprofil Zeiger wird auch als Wert in jedem Graph Vertex gespeichert.

Also, ich habe 3-Datenstrukturen, Graph und zwei Hash Tables und jeder einzelne von ihnen auf die gleiche genaue UserProfile zeigen. Die Struktur Graph wird dem Zweck dienen, den kürzesten Weg zu finden und Sachen wie, dass, während die Hash-Tabellen dienen als schnell Index mit Namen und ID.

Was ich denke, mein Graph Problem zu lösen ist, anstatt den Hash Tables Wert Punkt zum UserProfile zu haben, ich es mit dem entsprechenden Vertex zeigen. Es ist immer noch ein Zeiger, nicht mehr und nicht weniger Raum verwendet wird, ich just ändern, was ich darauf zu.

Wie diese kann ich einfach und schnell Nachschlag für jeden Vertex ich brauche, und verknüpfen sie zusammen. Dies wird die ~ 520000 Beziehungen ziemlich schnell ein.

Ich dachte, dieser Lösung, weil ich bereits die Hash-Tabellen haben und ich brauche sie haben, dann, warum nicht nutzen sie für die Indizierung der Graph Eckpunkte statt des Benutzerprofils? Es ist im Grunde das gleiche, ich immer noch die UserProfile ziemlich schnell zugreifen können, gehen Sie einfach auf die Vertex und dann auf die UserProfile.

Aber, sehen Sie keine Nachteile auf dieser zweiten Lösung gegen die erste? Oder nur Profis, dass Überwältigen der Vor- und Nachteile auf der ersten Lösung?

Andere Solution) Wenn Sie eine andere Lösung haben, bin ich ganz Ohr. Aber bitte die Vor- und Nachteile dieser Lösung gegenüber dem vorangegangenen 2. erkläre ich wirklich nicht viel Zeit damit zu verschwenden, gerade jetzt, ich brauche mit diesem Projekt zu bewegen, so, wenn ich tue, so zu tun, eine Änderung, muß ich genau verstehen, was die Art und Weise zu ändern, und wenn es das ist wirklich zu gehen.

Hoffentlich niemand schlief das Lesen und schloß den Browser, sorry für das große Testament. Aber ich wirklich brauchen, um zu entscheiden, was ist, dies zu tun, und ich wirklich eine Änderung vornehmen müssen.

P. S:. Wenn meine vorgeschlagenen Lösungen zu beantworten, bitte aufzählen sie wie ich, damit ich weiß genau, was Sie reden und nicht zu verwechseln mich selbst mehr, als ich schon bin

Answer 1

Der erste Ansatz ist das Da das Hauptproblem hier Geschwindigkeit ist, würde ich den Array Ansatz bevorzugen.

Sie sollten natürlich, halten die Hash-Tabelle für die Namen-Index-Suche.

Wenn ich richtig verstanden habe, nur Sie die Daten gleichzeitig verarbeiten. So gibt es keine dynamische Einfügen von Daten.

mit der Raumzuweisung Problem umgehen, würde ich empfehlen:

. 1 - Lesen Sie einmal die Datei, die Anzahl der Scheitelpunkt zu bekommen

2 - zuweisen, dass der Raum

Wenn Sie Daten dynamisch ist, können Sie einige einfache Methode implementieren, um die Array-Größe in Schritten von 50% zu erhöhen.

3 - In den Kanten, Sie ersetzen verknüpfte Liste für ein Array. Dieses Array sollte dynamisch mit Schritten von 50% erhöht werden.

Auch mit dem „Extra“ Platz zugewiesen, wenn Sie die Größe mit Schritten von 50% erhöht, die Gesamtgröße der Anordnung verwendet wird, sollte nur geringfügig größer sein als mit der Größe der verknüpften Liste.

Ich hoffe ich konnte helfen.