Ich arbeite an einem akademischen Projekt: eine Bibliothek schreiben, um den kürzesten Pfad auf großen, gewichteten, gerichteten Graphen zu finden.Beste Datenstruktur für große Graphen in cpu/speichergebundener Umgebung
Spezifikationen sind:
Das Beispiel Datensatz ein Graph von 1500 Vertices mit einem Durchschnitt von 5,68 Flanken pro Knoten ist. Die Spezifikation kann bis zu 20.000 Knoten variieren.
Außerdem arbeite ich in einer cpu/memory gebundenen Umgebung: Android.
Kantengewicht ist nicht trivial, noch costant. Es hängt von variablen Zuständen des Graphen ab.
Wir müssen offline arbeiten.
ich Gesicht einige Schwierigkeiten:
ich eine effiziente Art und Weise müssen zu speichern, retrive und Aktualisierungsdaten des Graphen. Sollte ich ein SQLite-Objekt mit Abfragen von den Java-Klassen verwenden, ein großes benutzerdefiniertes Java-Objekt auf dem Heap, oder was? Ich denke, das ist der performancekritischste Aspekt.
Ich brauche eine effiziente Möglichkeit, eine Art von Short-Path-Algorithmus zu implementieren. Da alle Gewichte positiv sind, sollte ich den Dijikstra-Algorithmus mit einer ArrayList als Container der besuchten Knoten anwenden?
Ist dies ein guter Fall, den NDK zu verwenden? Die Aufgabe ist CPU-intensiv, aber sie macht auch häufigen Zugriff auf den Speicher, also denke ich nicht, aber ich bin offen für Beiträge.
Immer daran denken, dass Ressourcen knapp sind, Ram ist unzureichend, Festplatte ist langsam, CPU ist wertvoll (Batterie - weise).
Jede Beratung ist willkommen, cheers :)
Wie oft wird die Struktur (im Gegensatz zu nur den Gewichten) Ihres Diagramms aktualisiert? Werden Sie einmal ein Diagramm erstellen und dann viel daran arbeiten, bevor Sie es erneut ändern? –
Weder die Struktur noch die Gewichtungen werden zur Laufzeit aktualisiert. Die Grafik enthält mehrere vorgeschlagene Gewichte, und die Bibliothek sollte das tatsächliche Gewicht aus den vorgeschlagenen schätzen. – Mascarpone