nicht angemeldet
Hi Daniela,
Wonach sortierst du genau? Zuerst nach Thread, und dann?
Ich fände es schön wenn du eine Lösung findest das zu sortieren ohne
dass ein nachträglicher Sort nötig ist, aber ich weis keine
Möglichkeit.
ich weiß nicht, ob Du Dir bei Deiner Darstellung einen Gefallen damit tust, "Rekursion" als etwas 'Böses' darzustellen.
Ich versuche mal, eine hinreichend exakte Aufgabenstellung zu dem zu erfinden, was hier die gante Zeit als Lösungsansätze diskutiert wird, insbesondere die zugrundeliegenden stillschweigenden Annahmen explizit zu formulieren und darauf basierend eine komplexitätstheoretische Bewertung der beiden Lösungsansätze abzugeben.
Was passiert denn eigentlich mit den zu verarbeitenden Daten, den Postings eines Forums?
Im wesentlichen haben wir es mit zwei Operationen zu tun:
a) Einfügung neuer Knoten (nachfolgend "Schreiben" genannt)
b) Ausgabe von Mengen von Knoten (Thread etc, nachfolgend "Lesen" genannt)
Für den allgemeinen Anwendungsfall stelle ich zwei Thesen auf:
1. Es werden wesentlich weniger Knoten pro Operation geschrieben (nämlich einer) als gelesen (eine entsprechende Granularität der Datenspeicherung vorausgesetzt - das leistet die "ein Thread = eine Datei"-Form von XML technisch bereits nicht mehr, eine relationale Datenbank mit record locking würde es können).
2. Es werden wesentlich mehr Lese- (viele pro Thread) als Schreiboperationen (eine pro Posting) durchgeführt.
Wenn wir zu beiden Aussagen entsprechende Faktoren bestimmen können (aus einer statistischen Analyse der konkret vorliegenden Daten), würden wir ein Verhältnis zwischen Leseoperationen (1 * 1) und Schreiboperationen (x * y) bestimmen können.
Die Gesamtkosten für die Verarbeitung wären in diesem Falle also
(1 * Kosten_schreiben(n)) + (x*y * Kosten_lesen(n)),
wobei n die Menge der vorhandenen Daten beschreibt (hier die Anzahl Postings).
Irgendwie scheint dies nahezulegen, daß wir durchaus daran interessiert sein sollten, die Lesekosten niedrig zu halten, und zwar gerne auch auf Kosten höherer Schreibkosten.
Genau das leistet ein Indexbaum einer relationalen Datenbank im Vergleich zu einer sequentiellen Datenspeicherungsform (wie sie sowohl einer XML-Datei als auch der Archiv-Suche zugrunde liegt). Nehmen wir mal die Kostenrechnung für einen Suchvorgang:
- Bei der sequentiellen Anordnung sind die Kosten beim Schreiben in
der Größenordnung O(1) - es wird genau ein Datensatz geschrieben.
Die Kosten beim Lesen sind dagegen O(n) bei n Datensätzen, also
linear. - Bei der Indexstruktur ist das Schreiben viel teurer - jeder neue
Datensatz muß in einen sortierten Baum eingefügt werden! Das kostet
O(log (n)). Umgekehrt ist allerdings das gezielte Lesen sehr billig
- über den Sortierungsbaum kann mit ebenfalls O(log n) jeder ge-
wünschte Datensatz herausgesucht werden.
Ehrlicherweise muß man dazu sagen, daß die Indexverwaltung einen gewissen Overhead kostet. Aber wie Frank völlig richtig sagte: "Lineare Faktoren sind Schall und Rauch" - denn bei einer Vervielfachung der Datenmenge werden sie sehr schnell irrelevant. Das ist auch der Grund, weshalb die sequentielle Suche mit O(n) bewertet wird - der implizite Faktor von 0.5 (im Mittel brauchen wir nur die Hälfte der Dokumente zu durchsuchen, um ein bestimmtes zu finden) fällt bei großen Datenmengen einfach hinter die Heizung.
Die obige Modell-Rechnung dürfte klar machen, was die Indexierung genau leistet: Sie verlagert die Kosten vom Lesen auf das Schreiben, _weil_ die Aufgabenstellung postuliert, daß sehr selten geschrieben, aber sehr häufig gelesen wird.
Im Prinzip macht Daniela mit ihrer gespeicherten Thread-Adressierung ("thread.posting.posting.posting" etc.) genau dasselbe: Sie baut eine Indexstruktur auf.
Denn diese Struktur wird ja nicht nur dazu genutzt, ein Posting innerhalb des Threads eindeutig zu adressieren - das Posting wird beim Schreiben bereits an der korrekt sortierten Stelle abgelegt.
Auch hier ist das Schreiben verteuert worden (und zwar genau wie oben von O(1) auf O(log (n)), während das Lesen eines sortierten Threads verbilligt wird, nämlich von O(n * log(n)) für das Lesen plus externe Sortieren auf nur noch O(n) für das Lesen der bereits sortiert abgespeicherten Postings.
Viele Grüße
Michael