I.) Die MF-Regel:

Mache ein Element zum ersten Element der Liste,

(move-to-front)

nachdem auf das Element (als Ergebnis einer erfolgreichen Suche) zugegriffen wurde.

Die relative Anordnung der anderen Elemente bleibt dabei erhalten.

Anm.:

Der MF-Algorithmus ist 2 kompetitiv (siehe: Beweis); er ist ein "memoryless Algorithmus", benötigt also keinen zusätzlichen Speicher.

II.) Die T-Regel:

Vertausche ein Element mit dem unmittelbar Vorangehenden,

(Transpose)

nachdem auf das Element (als Ergebnis einer erfolgreichen Suche) zugegriffen wurde.

Anm.:

Der T-Algorithmus ist ein "memoryless Algorithmus".

III.) Die FC-Regel:

Ordne jedem Element einen Häufigkeitszähler (Counter) zu,

(Frequency Count)

der anfangs auf 0 steht und die Anzahl der Zugriffe auf das Element speichert.

Außerdem wird die Liste nach jedem Zugriff so neu geordnet,

dass die Häufigkeitszähler der Elemente in absteigender Reihenfolge sind.

Anm.:

Der FC-Algorithmus ist kein "memoryless Algorithmus".

a.)

Es gibt eine Reihe von experimentell ermittelten Messergebnissen für reale Daten, um zu ermitteln welche der drei Strategien am "optimalsten" ist.

So berichten Bently und McGeoch:

"Die T-Regel ist schlechter als die FC-Regel; die MF-Regel und die FC-Regel sind vergleichbar gut, die MF-Regel ist allerdings in manchen Fällen besser."

Anmerkung hierzu meinerseits:

Selbst wenn die MF- und die FC-Regel gleichgut wären, würde man eher die MF-Regel bevorzugen,

da diese ein "memoryless Algorithmus" ist und somit keinen zusätzlichen Speicher benötigt.

Bei der FC-Regel hingegen muss zu jedem Element der Counter immer noch mitgespeichert werden.

b.)

Die Arbeitsweise der FC-Regel lässt sich besonders gut beobachten, wenn die Zugriffshäufigkeit der Elemente sehr unterschiedlich ist.

c.)

Nachteile der einzelnen Regeln:

Nachteil der MF-Regel:

Das Vorziehen eines Elementes an den Listenanfang ist relativ dramatisch,

wird ein "seltenes" Element "irrtümlich" an den Listenanfang gesetzt,

so wird dieser "Fehler" erst allmählich korrigiert, wenn "lange" nicht mehr auf das Element zugegriffen wird.

Nachteil der T-Regel:

Wird in einer Anfragefolge immer nur auf die letzten beiden Elemente zugegriffen, so entstehen maximale Kosten.

Nachteil der FC-Regel:

Das "Mitschleppen" eines Counters für jedes Element hat einen nicht zu vernachlässigenden Speicheraufwand zur Folge!!

Falls man jedoch nicht ohnehin einen Counter für jedes Element benötigt, z.B. um eine Benutzerstatistik aufzustellen,

lohnt die Verwendung der FC-Regel normalerweise nicht.