Skip Listen

Diskutiere Skip Listen im Java Basics - Anfänger-Themen Bereich.
L

Louis12

Hallo,

Leider komme ich nicht weiter und kann mir garnicht vorstellen, wie ich vorzugehen habe oder was ich als erstes tuhen muss. Ich freue mich wirklich auf jede Antwort und vielen Dank im vorraus.

FRAGESTELLUNG

Implementieren Sie die SkipList-Datenstruktur für Integer-Daten. Die Indexliste soll hierbei ebenfalls eine fixe Größe von vier Feldern haben. Der in diesen Feldern gehaltene Index soll sich gleichmäßig über die Anzahl der Einträge in der Primärliste verteilen (d.h. Anzahl der nicht-indexierten Elemente in den durch die sekundäre Liste definierten Intervallen weicht nie um mehr als 1 ab; die Indexliste muss sich dynamisch anpassen). Weiter soll die Skiplist folgende Methoden anbieten: • add(value) – Fügt ein int in die Skiplist ein und updatet die Indexliste falls notwendig. Die Methode soll immer true zurückgeben, wenn das Einfügen erfolgreich war. • get(index) – Gibt den Wert an der durch index definierten Position zurück oder null, wenn index nicht vorhanden ist. • contains(value) – Gibt einen boolean-Wert zurück, welcher anzeigt ob das übergebene Element in der Primärliste enthalten ist. • size() – Gibt einen int-Wert zurück, welcher die Anzahl der Elemente in der Primärliste beschreibt. • clear() – Entfernt alle Einträge aus der Liste, so dass die Liste wie neu verwendet werden kann • toString() – Gibt eine Stringdarstellung der Listenelemente der Sekundär- und Primärliste zurück


konkrete Frage ; wie kann ich es implementieren das die Indexliste eine fixe Größe von vier Feldern hat.

was müsste ich im Code ergänzen damit so eine index Liste realisiert wird.

CODE




Code:
package main;

import java.util.Collection;
import java.util.Iterator;

public class SkipList implements Collection<Integer> {

    
    /**
     * Returns the value at the specified position
     *
     * @param index
     * @return
     */
    public Integer get(int index) {
        return null;
    }
    

    /**
     * Inserts a value into the SkipList.
     *
     * @param value
     * @return
     */
    @Override
    public boolean add(Integer e) {
        // TODO Auto-generated method stub
        return false;
    }
    
    /**
     * Checks, whether a number is contained in the list.
     * @param value
     * @return boolean value whether number is contained in list
     */
    public boolean contains(int value) {
        return false;
    }
    
    /**
     * removes all elements form the list
     */
    @Override
    public void clear() {
        // TODO Auto-generated method stub
        
    }
    
    /**
     * @return the size of the list
     */
    @Override
    public int size() {
        // TODO Auto-generated method stub
        return 0;
    }
    
    

    //#####################################
    //do not change the following methods!!
    //#####################################
    
    @Override
    public boolean isEmpty() {
        return size() <= 0;
    }
    
    @Override
    public boolean contains(Object o) {
        try {
            Integer casted = (Integer) o;
            return contains(casted) ;
        } catch (ClassCastException e) {
            return false;
        }
    }
    
    
    @Override
    @Deprecated
    public boolean remove(Object o) {
        return false;
    }

    @Override
    public boolean containsAll(Collection<?> c) {
        for(Object o : c) {
            if(!contains(o)) {
                return false;
            }
        }
        return true;
    }

    @Override
    public boolean addAll(Collection<? extends Integer> c) {
        for(Integer t:c) {
            add(t);
        }
        return true;
    }

    @Override
    @Deprecated
    public boolean removeAll(Collection<?> c) {
        return false;
    }

    @Override
    @Deprecated
    public boolean retainAll(Collection<?> c) {
        return false;
    }

    @Override
    public Iterator<Integer> iterator() {
        //really slow way to implement this but should be some what understandable
        return new Iterator<Integer>() {
            int index = 0;
            @Override
            public boolean hasNext() {
                // TODO Auto-generated method stub
                return index < size();
            }

            @Override
            public Integer next() {
                return get(index++);
            }
        };
    }

    @Override
    public Object[] toArray() {
        Object[] obj = new Object[size()];
        for (int i = 0; i < size(); i++) {
            obj[i] = get(i);
        }
        return obj;
    }

    @SuppressWarnings("unchecked")
    @Override
    public <X> X[] toArray(X[] a) {
        for (int i = 0; i < size(); i++) {
            a[i] = (X) get(i);
        }
        return a;
    }
}



package main;

import java.util.Arrays;
import java.util.List;

public class Main {
    
    public static void main(String[] args) {
        
        List<Integer> daten = Arrays.asList(1,3,6,7,12,14,21,34,36,37);
        
        SkipList list = new SkipList();
        
        list.addAll(daten);
        
        System.out.printf("test get(5) should be:14 is:%d\n",list.get(5));
        
        System.out.printf("test contains(7) should be:true is:%b\n",list.contains(7));
        System.out.printf("test contains(37) should be:true is:%b\n",list.contains(37));
        System.out.printf("test contains(-1) should be:false is:%b\n",list.contains(-1));
        
        System.out.printf("test toString() should be:\n"
                + "head -> 1 -> 7 -> 21 -> 36 -> null\r\n" +
                "head -> 1 -> 3 -> 6 -> 7 -> 12 -> 14 -> 21 -> 34 -> 36 -> 37 -> null\r\n" +
                "\nis:\n%s\n",list);
    }

    
}


liebe grüße
louis
 

Anhänge

J

JustNobody

Hast Du denn schon verstanden, wie die SkipList funktionieren soll?

Wie sah denn die einfache List aus? Was ist denn da gemacht worden?

Falls es Probleme beim Verständnis eine SkipList gibt hilft evtl https://www.geeksforgeeks.org/skip-list/
(Wobei es da auch andere Varianten gibt, in so einem Fall bräuchte man mehr Informationen zu dem, was euch diesbezüglich genau gesagt wurde.)

Evtl. auch interessant: Der Thread von jemandem, der die scheinbar gleiche Aufgabe bearbeitet: https://www.java-forum.org/thema/frage-zu-skiplist.186856/
 
L

Louis12

Hallo,

Vielen dank für den Link ich habe dank dem Link die Theorie verstanden.

wie sah denn die einfache List aus? Was ist denn da gemacht worden?
in einer einfachen Liste wird die ganze Liste durchsucht, wodurch es viel Zeit in Anspruch genommen wird.

In einer Skip List wird eine Index Liste bzw. mehrere express Lines parallel zu normalen Liste benutzt um bestimmte Zahlenbereiche zu überspringen, wie im Beispiel im geposteten Link erklärt.



(Wobei es da auch andere Varianten gibt, in so einem Fall bräuchte man mehr Informationen zu dem, was euch diesbezüglich genau gesagt wurde.)

uns wurde nicht viel über die Variante gesagt. ich werde aber die ganze Aufgabenstellung diesbezüglich anhängen, ich habe übrignes die weniger umfangreiche Aufgabe gewählt

FRAGEN:
Eine Basis Liste wurde quasi schon in der Main erstellt, muss ich eine extra Klasse für die Index Liste erstellen oder reicht schon die Klasse Skip List


Code:
 @Override
    public boolean add(Integer e) {
        // TODO Auto-generated method stub
        return false;
    }
In dieser Methode überprüfe ich erstmal ob eine zahl in der Liste existiert, wenn nein dann liefert es den Wert true zurück und ich kann in der Main methode List.add benutzen richtig ?

Wie kann ich in der Methode überprüfen ob in einer beliebigen Liste eine Zahl drin ist, denn ich kann ja nicht den Listenamen in der Main benutzen

Ich habe leider nicht verstanden, wie ich eine Indexliste implemtiere die eine fixe Größe von vier Feldern hat . Eine Liste kann doch beliebig viele Zahlen speichern.
 

Anhänge

J

JustNobody

Ok, bei der Aufgabe ist es aus meiner Sicht etwas anders aufgebaut.

Du hast neben der eigentlichen Liste einfach eine zweite Liste mit genau 4 Elementen. Das ist in den Abbildungen auch recht deutlich gezeigt. Da siehst Du dann, wie es mit einem Element und mit 4 Elementen in der Basisliste aussehen sollte.

Eine Liste mit 4 Elementen bekommst Du, in dem Du eine neue Liste erzeugst und dann 4 Elemente einfügst.

Bezüglich der add Methode: Die muss natürlich auch direkt das Element einfügen. Du hast ja eine SkipList und die inneren Listen (Index und Base List) sind nur innerhalb bekannt. Wenn auf der Skip List ein add aufgerufen wird, dann muss:
- wenn das Element bereits vorhanden ist, false zurück gegeben werden.
- das Element eingefügt werden in die Base List und die Index List ggf. angepasst werden.
 
L

Louis12

Danke für die Antwort

Eine Liste mit 4 Elementen bekommst Du, in dem Du eine neue Liste erzeugst und dann 4 Elemente einfügst.
jo danke das ergibt sinn



Bezüglich der add Methode: Die muss natürlich auch direkt das Element einfügen. Du hast ja eine SkipList und die inneren Listen (Index und Base List) sind nur innerhalb bekannt. Wenn auf der Skip List ein add aufgerufen wird, dann muss:
- wenn das Element bereits vorhanden ist, false zurück gegeben werden.
- das Element eingefügt werden in die Base List und die Index List ggf. angepasst werden.
ich verstehe leider nicht wie ich in der Methode die Base List kontrollieren kann also ob dieser Zahl vorhanden ist

und kann ich das mit instace of machen oder muss ich Comparable benutzen
 
J

JustNobody

ich verstehe leider nicht wie ich in der Methode die Base List kontrollieren kann also ob dieser Zahl vorhanden ist
Also ich würde innerhalb der Skip List keine andere List verwenden (als Klasse). Die Skip List implementiert alles, denn nach meinem Verständnis brauchst Du ja auch Zugriff auf die Nodes der Base List. Und das wäre ja sonst in der List Klasse gekapselt und Du hättest keinen Zugriff drauf.

Das ist also nur von der Beschreibung her halt eine Index List und eine Base List. Du verwendest vorhandenen Code aber nur in der Form, dass Du diesen sozusagen kopierst um ihn dann zu verwenden.
 
Thema: 

Skip Listen

Passende Stellenanzeigen aus deiner Region:
Anzeige

Neue Themen

Anzeige

Anzeige
Oben