Skip Pointer < Sonstiges < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:26 Do 28.02.2008 | | Autor: | Bastiane |
Hallo zusammen!
Ich wüsste gerne, was ein Skip Pointer ist. In den Unterlagen finde ich dort nur folgende Folie:
[Dateianhang nicht öffentlich]
Es geht darum, die beiden Listen zu mergen bzw. die Elemente, die in beiden vorkommen, herauszufinden. Die Pfeile überspringen ja aber z. B. die 8 bzw. die 2, so dass ich nicht verstehe, was es mit den Pfeilen dort auf sich hat... ![[kopfkratz]](/images/smileys/kopfkratz.gif "[kopfkratz]")
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
Dateianhänge:
Anhang Nr. 1 (Typ: png) [nicht öffentlich]
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 12:34 Fr 29.02.2008 | | Autor: | felixf |
Hallo Bastiane
> Ich wüsste gerne, was ein Skip Pointer ist. In den
> Unterlagen finde ich dort nur folgende Folie:
>
> [Dateianhang nicht öffentlich]
>
> Es geht darum, die beiden Listen zu mergen bzw. die
> Elemente, die in beiden vorkommen, herauszufinden. Die
> Pfeile überspringen ja aber z. B. die 8 bzw. die 2, so dass
> ich nicht verstehe, was es mit den Pfeilen dort auf sich
> hat...
Wenn ich mich richtig erinnere, dann sind skip pointer ein allgemeineres Konzept als etwas das man nur zum Mergen braucht.
Die Idee ist folgende: du hast eine sortierte Menge (etwa von Zahlen) als Liste gespeichert. So eine Liste ist ja ziemlich optimal, wenn man einfach alle Elemente am Stueck abklappern moechte, wenn man schnell ewas ein- oder ausfuegen moechte. Aber um ein bestimmtes Element zu finden ist das alles andere als optimal.
Wenn man weiss, dass die Liste sortiert ist, kann man zumindest schonmal schneller aufhoeren nach einem bestimmten Element zu suchen, naemlich sobald man ein groesseres gefunden hat. Allerdings muss man immer noch alle davor abklappern.
Die Skip Pointer versuchen das jetzt zu verbessern, indem sie versuchen, die Idee von einem binaeren Baum (da geht Suchen ja ganz schnell) mit der einer Liste zu verbinden. Wenn man jetzt z.B. in der oberen Liste nach der 64 sucht, kann man von der 2 aus erstmal den Skip Pointer benutzen um zur 16 zu gelangen. Da 16 < 64 ist, nimmt man da wieder den Skip Pointer, um zur 128 zu gelangen. Nun ist 128 > 64, also ist man zu weit gegangen. Man springt also zurueck zur 16 (bzw. man hat sich die 16 einfach gemerkt) und geht von da aus in kleinen Schritten weiter, zuerst zur 32 (immer noch < 64), dann zur 64, und das ist dann ein Volltreffer. Insgesamt wurden hier also 5 Nodes abgeklappert. Wenn man einfach stumpf bei der 2 angefangen waere und jeweils immer einen Schritt nach Rechts gegangen waer, haette man 6 Nodes abklappern muessen.
Ok, bei diesem Beispiel ist der Unterschied (5 vs. 6) nicht so gross, aber wenn man jetzt mehr Skip Pointer benoetigt haette um erstmal grob das Ergebnis zu finden haette sich das schon wesentlich mehr gelohnt.
Man kann das uebrigens auch mehrmals machen, also nochmals eine Ebene hoeher Skip Pointer einfuehren, um noch groessere Schritte machen zu koennen. Wenn man das beliebig iteriert, erhaelt man im Endeffekt wieder einen $n$-aeren Baum (wenn man bei jeder Skip-Pointer-Ebene die Schrittweite mit $n$ multipliziert).
Ich hoffe das war jetzt verstaendlich genug :)
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:51 Sa 08.03.2008 | | Autor: | felixf |
Hallo Christiane
> Danke für deine Antwort. Verständlich war es, ja. Ich frage
> mich nur, wieso das denn in unserem Fall erwähnt wird.
Das frag ich mich auch... Fuer mich macht das beim Mergen zweier Listen ueberhaupt keinen Sinn. Wenn du's nochmal rausfinden solltest waer ich also auch dran interessiert *g*
> Wenn wir also die gemeinsamen Elemente von zwei Listen finden
> wollen, suchen wir dann jedes Element der einen Liste
> mithilfe der Skip-Pointer in der anderen Liste? Gibt's da
> keine bessere Möglichkeit?
Doch, das geht besser, also zumindest wenn beide Listen sortiert sind. Man geht im Prinzip genauso wie beim Mergen vor, nur dass man halt immer weiter springt bis man bei beiden Listen einen Pointer auf den gleichen Eintrag hat. Wenn man Skip Pointer zur Verfuegung hat, kann man die natuerlich auch nutzen um groessere Schritte zu machen, etwa wenn man die Listen $1, 2, 3, 4, 5$ und $5, 6, 7, 8, 9$ hat; dann macht man in der ersten erstmal einen grossen Schritt (sagen wir mal drei Elemente vorwaerts) und bemerkt dass der Eintrag da immer noch kleiner ist als der erste in der zweiten Liste.
LG Felix
|
|
|
|
