[linux-l] mbox/Maildir/tar

[Oliver Bandel]

Zitat von Rocco Rutte <pdmef at gmx.net>:

> Hi,
>
> * Ivan F. Villanueva B. wrote:
> >Am Mi, Nov 28, 2007 10:42:14 +0100, Rocco Rutte schrieb:
> >> O(log(n))/O(1) statt O(n)
> >           ^^^^^
> >        das verstehe ich nicht
>
> Gute Hashtabellen (max. 50% voll, gute Hashfunktion mit guter
> Streuung)
> haben im Mittel keine Kollisionen, d.h. der Eintrag ist nach
> Berechnung
> der Hashsumme modulo Tabellengröße immer im Mittel sofort gefunden.
> Im
> worst-case kommt die Komplexität glaube ich auf das Verfahren zur
> Kollisionsauflösung an. Wenn man chaining (also verkettete Liste an
> der
> Stelle in der Tabelle) benutzt, kann man im schlechtesten Fall eine
> einfach verlinkte Liste haben, also O(n) (z.B. wenn die Tabelle nur 1
> Zeile hat). Bei linearem Auflösen (also Soll-Stelle je 1 Stelle
> weiter
> probieren) müsste man auch auf O(n) kommen. Für andere Verfahren
> weiss
> ich es nicht aus dem Kopf.
[...]

Was ich immer noch suche, ist die Antwort bzgl.
der Listen. Du meintest irgendwas mit Listen auf dem baum drauf oder so?
(Finde die Mail leider gerade nicht).

Und ich frage mich, wo denn da Listen sind.
Du schreibst hier was von hash; ich dachte es werden Bäume
in den Dateissystenmen eingesetzt.

Aber vielleicht wreden wir auch aneinander vorbei.

Mir ist vorhin, als ich mich kurz auf's Ohr (eigentlich auf's Auge)
gehauen habe so im Halbschlaf einen gedankeblitz gehabt: "Au weia,
ich habe ext3 gelesen, ext3 geschrieben, aber ich hatte immer
Reiser-FS im Hinterkopf".
Deswegen war das dann wohl alles Quark, was ich schrieb,
bezüglich ext3 sehr viel langsamer als ext2.




>
> Ist aber schon 'ne Weile her, dass das in der Uni dran war. IIRC gibt
> es
> für O(1) auch einen Beweis (zumindest denke ich dass der Prof mal
> sowas
> erwähnt hatte)...
[...]

Naja, muss ja irgendwas statistisches Sein.
Vermutlich Markoffketten und Grenzwert der Übergangsmatrix.


>
> Nachteil: Hashtabellen brauchen viel Pflege
[...]
immer schön giessen ;-)


Das Problem mit dem Suchen sieht da ja garnicht so schlimm aus.
log(n) ist doch ganz nett.
Deswegen denke ich auch, daß die Probleme von Maildir nicht
daher rühren. Klar: je weniger man auf dem Filesystem herum rödeln
muß, um so besser.

Andererseits denke ich, daß Performance-Probleme eher durch die
Verzögerungen bei den Zugriffen auf die I/O herrühren, und nicht
von algorithmischen Problemchen.
Man wird einfach bei den Zugriffen immer mit Wartezeiten konfrontiert,
da viele Zugriffe anstehen und die Hardware wie wild ackert.
Algorithmisch wäre das Problem schon gelöst, was den Aufwand angeht,
aber wenn bei jedem Zugriff gebremst wird, hat man ein Problem.

Vielleicht muß man das Filesystem selbst parallelisieren, so daß
mehrere Zugriffe abgearbeitet werden können, also irgendwie cahen.
oder mehrere Platten parallel schreiben, statt immer auf die
eine Platte zu warten.

Gruß,
   Oliver