10.4 Skiplist

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

10.4 Skiplist
Hi,

ich steh grad irgendwie auf dem schlauch.

ich komme gerade bei der methode containsAll(Collection<?> c)
nicht weiter.
Wie komme ich denn an die einzelnen Elemente der Collection ran.
Bei addAll habe ich es geschafft aber hier nicht.


Google (Java Collection Traversing) => https://docs.oracle.com/javase/tutorial/collections/interfaces/collection.html

Auf der Seite findest du drei Möglichkeiten über alle Elemente einer Collection zu traversieren. Beachte aber, dass bei AuD JDK 8 nicht zugelassen ist!


Darf ich Fragen wie man auf die einzelnen Elemente der Collection oder der Set ran kommt? Ich check das irgendwie nicht und ich will das nur verstehen um ein Element in der size zu benutzen.


Wie du anhand der Java-Api zur Collection feststellen kannst, gibt es eine Methode toArray. Diese gibt ein Array vom Typ Objekt zurück, welches alle Elemente deiner Collection enthält. Wie du mit einem Array arbeiten kannst, weißt du hoffentlicht.

Beispiel:

Collection eineCollection = new ArrayList();
Object[] einArray = eineCollection.toArray();

Ich steh irgendwie auch grade auf dem Schlauch. Um den Aufwand von add auf O(log(n)) schrumpfen lassen zu lassen, brauche ich ja binäre Suche und dazu wieder die Größe der Menge. Wie soll ich aber size in O(1) machen ohne eine vorher im Konstruktor deklarierte Größe size, die ich in add jeweils um 1 hochgehen lasse? >_> Danke im Voraus!


Du machst dir einfach eine private Hilfsvariable size und zaehlst damit deine Groesse mit.


Also darf ich diesmal irgendwo am Anfang einfach private int size = 0; reinhauen? Normalerweise soll man ja bei der Vorlage nix hinzufügen oder ändern, deswegen war ich irritiert.


Genau, da darf man eine Hilfsvariable anlegen. Sonst wäre O(1) ja auch nicht möglich.


Binäre Suche auf einer Liste ist nämlich nur O(log(n)), wenn du wahlfreien Zugriff auf dieser Liste hast. Da die Verknüpfung der einzelnen Elemente durch eine einfach verkettete Liste gegeben ist, hilft dir eine traditionelle binäre Suche wenig. Du erhälst den Aufwand O(log(n)) dadurch, dass du dir zu Nutze machst, dass sich auf Ebene 0 im Schnitt 100% der Elemente befinden, auf Ebene 1 im Schnitt 50%, auf Ebene 2 25% usw. Wenn du die Suche nach der Einfügeposition auf der obersten Ebene startest und korrekt nach unten absteigst und an den entsprechenden Stellen deine Elemente einfügst, verringert sich dein Aufwand ebenfalls auf O(log(n)).

Auf den Übungsfolien wir der Einfügeprozess ebenfalls erklärt (ab Folie 59): https://www2.cs.fau.de/teaching/WS2015/AuD/uebungen/secure/uebung10_handout.pdf


Gut, deswegen geht das mit binärer Suche nicht, wie ich mir das vorstelle :smiley:

Wahrscheinlich wieder eine doofe Frage bzgl der size. Wenn ich ganz am Anfang ohne einen Konstuktor

private int size = 0;

angebe, zeigt er mir, wenn ich später an size rumdoktore an “Muss noch initalisiert werden”. Bei der Resizingaufgabe ging das aber, da hatte ich eben noch einen Konstruktur. Soll man denn auch noch einbauen?


Rumdoktor’n musst du eigentlich nicht. Wenn du das an der richtigen Stelle platzierst kommt diese Meldung nicht :wink:


Was meinst Du mit „ganz am Anfang“? Wenn Du bei der Deklaration (der Instanzvariablen) gleich den Wert mit angibst, dann sollte das ohne Probleme funktionieren. Dann kannst Du Dir auch den Konstruktor schenken.