"adaptiver" Algorithmus

[Blue-Tiger]

Hi!
Ich less grad Segdewick's "Algorithmen in C++". Allerdings versteh ich nicht, was der Unterschied zwischen adaptiven und nichtadaptiven Algorithmen sein soll, und werd aus des Autors Erklaerung auch nicht schlauer

Also: was ist der Unterschied?

[volkard]

Blue-Tiger schrieb:

Hi!
Ich less grad Segdewick's "Algorithmen in C++". Allerdings versteh ich nicht, was der Unterschied zwischen adaptiven und nichtadaptiven Algorithmen sein soll, und werd aus des Autors Erklaerung auch nicht schlauer

Also: was ist der Unterschied?

adaptive sind welche, die zur laufzeit aus den reinkommenden daten ihre tabellen, bäume etc. erstellen.
nichtadaptive sind welche, die entweder feste nehmen oder erstmal einen durchlauf durch die daten machen und die tabellen oder bäume erstellen und dann mit der/dem tabelle/baum nochmal durchgehen.

[Blue-Tiger]

volkard schrieb:

Blue-Tiger schrieb:

Hi!
Ich less grad Segdewick's "Algorithmen in C++". Allerdings versteh ich nicht, was der Unterschied zwischen adaptiven und nichtadaptiven Algorithmen sein soll, und werd aus des Autors Erklaerung auch nicht schlauer

Also: was ist der Unterschied?

adaptive sind welche, die zur laufzeit aus den reinkommenden daten ihre tabellen, bäume etc. erstellen.
nichtadaptive sind welche, die [...] erstmal einen durchlauf durch die daten machen und die tabellen oder bäume erstellen und dann mit der/dem tabelle/baum nochmal durchgehen.

Versteh ich deas so richtig:
adaptive erstellen zur Laufzeit aus den reinkommenden Daten ihre Datenstrukturen.
nichtadaptive erstellen (u. U.) ebenfalls Datenstrukturen, aber laeufen vorher einmal ueber die Daten drueber?

Was bitte soll so eine Unterscheidung bringen?

[volkard]

Blue-Tiger schrieb:

Was bitte soll so eine Unterscheidung bringen?

stell dir einfach mal ne huffman-codierung vor. ich will ein saugroßes file mit huffman packen.
nu hab ich zwei alternativen:
a) ich lese das file erstmal komplett durch und zähle die häufigkeiten aller buchstaben und baue dann einen huffman-tree und dann lese ich das file nochmal komplett und setze jedes gelesene zeichen anhand des huffman-trees um.
b) ich behaupte am anfang, jedes zeichen kam genau einmal vor. und baue den entsprechenden huffman-tree. und lese vom file 8192 bytes und setze die anhand des trees um. aber dabei zähle ich gleichzeitig die häufigkeiten der eingangsdaten und alle 8192 bytes berechne ich einen neuen huffman-tree.

a) hat den vorteil der besten packrate, wenn die wahrscheinlichkeitsverteilung auch über das ganze file gleich bleibt. also wenn ich "mypacker *.txt" aufrufe, wird das schon so sein. aber hat den nachteil, daß erst die ganzen eingangsdaten mal gelesen werden müssen. nun gut, sie stehen ja nach dem ersten lesen in plattencache. also null problemo. a) ist also gut, wenn die eingangsdaten kelienr sind als das frei ram. aber wenn nicht, nimmt man vielleicht gerne b) in kauf, weil ein plattenzugriff so teuer ist wie 100000 ramzugriffre und will halt nicht 30 minuten warten, wenn es mit 2% schlechterer packrate auch in 30 sekunden ginge.

b) hat aber noch einen gewaltigen vorteil in manchen pack-situationen. ich mache "mypacker ." und der packer sortiert erstmal nach dateinamenerweiterungen, also erst alle *.txt, dann alle *.doc, dann alle *.exe. und den adaptiven machen wir so, daß er alte statistiken vergisst. daß er nur sagen wir mal das letze megabyte kennt. der kann sich dadurch auch neue gegebenehitan anpassen und ist am schluss stärker als a). natürlich nur bei so fällen, wo nacheinander große brocken mit unterschiedlichen wahrscheinlichkeitsverteilungen kommen.

Blue-Tiger schrieb:

Was bitte soll so eine Unterscheidung bringen?

naja, die haben schon durchaus echt andere vorzüge und nachteile. und wenn man drüber reden will, ist es gut, for a) und b) eigene worte zu haben.

[Blue-Tiger]

Hmm.... nur nochmal zur Sicherheit: "adaptiv" heisst dann also, dass sich der Algorithmus nicht immer gleich verhaelt, sondern sich den Eingangsdaten "anpasst" (bzw. abhaengig von denen anders arbeitet)?