Ich würde dringend empfehlen (auch weil ich es so gemacht hätte), wenn du den Code hast (am besten natürlich davor), das ganze einfach mal auf Papier sich aufzuzeichnen was passiert bei dem vorliegendem Code und vergleichen ob es zu dem passt, was man erwarten würde.
Persönlich bin ich kein Freund von solchen Aufgaben, klar ich sehe ihren Nutzen (einigermaßen) aber bin dann doch eher pragmatiker und sehe an der Liste nicht unbedingt den Vorteil und nutze eher fertige Dinge als sowas selber zu basteln (trotz schlimmen Not Invented Here Syndroms)
Das sollte jetzt „richtiger“ sein, aber ich weiß noch nicht, was height bedeutet:
import java.util.LinkedList;
import java.util.Random;
public class SkipList {
public final static int MAX_HEIGHT = 32;
private class SkiplistNode {
public int value;
public SkiplistNode[] next;
public SkiplistNode(int value, SkiplistNode[] next) {
this.value = value;
this.next = next;
}
}
private final Random random = new Random(0);
private final double p;
@SuppressWarnings("unused")
private int height = 0; // ?
private final SkiplistNode head = new SkiplistNode(0, new SkiplistNode[MAX_HEIGHT]);
public SkipList(double p) {
this.p = p;
}
public void add(int value) {
if (value < 0)
/*
* I restricted the list to hold only values greater than or equal to 0
*/
throw new IllegalArgumentException();
/*
* Calculate the skip list node insertion path
*/
SkiplistNode[] path = new SkiplistNode[MAX_HEIGHT];
SkiplistNode sn = head;
for (int level = MAX_HEIGHT - 1; level >= 0; level--) {
while (sn.next[level] != null && value > sn.next[level].value) {
sn = sn.next[level];
}
path[level] = sn;
}
sn = sn.next[0];
if (sn != null && value == sn.value) {
/*
* value is already in the list
*/
System.out.println(value + " is already in the list.");
return;
} else {
/*
* Calculate the maximum level
*/
int i = 0;
for (; i < MAX_HEIGHT && p < random.nextDouble(); i++)
;
int max_level = i;
/*
* Insert and restructure the list
*/
sn = new SkiplistNode(value, new SkiplistNode[MAX_HEIGHT]);
for (int level = 0; level <= max_level; level++) {
sn.next[level] = path[level].next[level];
path[level].next[level] = sn;
}
}
}
@Override
public String toString() {
StringBuilder b = new StringBuilder();
for (int i = MAX_HEIGHT - 1; i >= 0; i--) {
LinkedList<Integer> ll = new LinkedList<>();
SkiplistNode sn = head;
while (sn != null) {
ll.add(sn.value);
sn = sn.next[i];
}
b.append(String.format("Ebene%02d %s%n", i, ll));
}
return b.toString();
}
public static void main(String[] args) {
SkipList list = new SkipList(0.5);
System.out.println(list);
list.add(5);
System.out.println(list);
list.add(6);
System.out.println(list);
list.add(4);
System.out.println(list);
list.add(7);
System.out.println(list);
list.add(3);
System.out.println(list);
list.add(8);
System.out.println(list);
list.add(2);
System.out.println(list);
list.add(9);
System.out.println(list);
list.add(1);
System.out.println(list);
list.add(10);
System.out.println(list);
list.add(10);
System.out.println(list);
}
}
Die aktuelle Höhe oder aktuelle maximale Höhe? Das ist ja ein Unterschied…
Edit: Und die Liste basiert ja auf dem Zufall und einer zufälligen Gleichverteilung… Deswegen ist O(log n) auch nur ein theoretischer Wert. Und das soll bedeuten: Wenn man Pech hat, muss für jedes Element die gesamte Liste durchsucht werden…
Solche, nicht alternativlosen DS mit zufälligem Aufwand sind natürlich nur ungerne gesehen, d. h. aus nachvollziehbaren Gründen nicht in Java implementiert, imho. Oder?
Hier ist noch ein Benchmark, und das schockiert mich wirklich:
import java.util.LinkedList;
import java.util.Random;
import java.util.SortedSet;
import java.util.TreeSet;
public class SkipList {
public final static int MAX_HEIGHT = 32;
private class SkiplistNode {
public int value;
public SkiplistNode[] next;
public SkiplistNode(int value, SkiplistNode[] next) {
this.value = value;
this.next = next;
}
}
private final Random random = new Random(0);
private final double p;
@SuppressWarnings("unused")
private int height = 0; // ?
private final SkiplistNode head = new SkiplistNode(0, new SkiplistNode[MAX_HEIGHT]);
public SkipList(double p) {
this.p = p;
}
/**
* Assume, this costs O(log n).
*
* @param value
*/
public void add(int value) {
if (value < 0)
/*
* I restricted the list to hold only values greater than or equal to 0
*/
throw new IllegalArgumentException();
/*
* Calculate the skip list node insertion path
*/
SkiplistNode[] path = new SkiplistNode[MAX_HEIGHT];
SkiplistNode sn = head;
for (int level = MAX_HEIGHT - 1; level >= 0; level--) {
while (sn.next[level] != null && value > sn.next[level].value) {
sn = sn.next[level];
}
path[level] = sn;
}
sn = sn.next[0];
if (sn != null && value == sn.value) {
/*
* value is already in the list
*/
// System.out.println(value + " is already in the list.");
// return;
} else {
/*
* Calculate the maximum level
*/
int i = 0;
for (; i < MAX_HEIGHT && p < random.nextDouble(); i++)
;
int max_level = i;
/*
* Insert and restructure the list
*/
sn = new SkiplistNode(value, new SkiplistNode[MAX_HEIGHT]);
for (int level = 0; level <= max_level; level++) {
sn.next[level] = path[level].next[level];
path[level].next[level] = sn;
}
}
}
/**
* Assume, this costs O(log n).
*
* @param value
* @return
*/
boolean contains(int value) {
SkiplistNode sn = head;
for (int level = MAX_HEIGHT - 1; level >= 0; level--) {
while (sn.next[level] != null && value > sn.next[level].value) {
sn = sn.next[level];
}
}
sn = sn.next[0];
if (sn != null && value == sn.value) {
return true;
}
return false;
}
@Override
public String toString() {
StringBuilder b = new StringBuilder();
for (int i = MAX_HEIGHT - 1; i >= 0; i--) {
LinkedList<Integer> ll = new LinkedList<>();
SkiplistNode sn = head;
while (sn != null) {
ll.add(sn.value);
sn = sn.next[i];
}
b.append(String.format("Ebene%02d %s%n", i, ll));
}
return b.toString();
}
public static void main(String[] args) {
int n = 1_000_000;
Random r = new Random(0);
SkipList list = new SkipList(0.5);
SortedSet<Integer> set = new TreeSet<>();
long t0 = System.currentTimeMillis();
int sum = 0;
for (int i = 0; i < n; i++) {
list.add(r.nextInt(Integer.MAX_VALUE));
}
for (int i = 0; i < n; i++) {
sum += list.contains(r.nextInt(Integer.MAX_VALUE)) ? 1 : 0;
}
long t1 = System.currentTimeMillis();
System.out.println(sum);
long t2 = System.currentTimeMillis();
int sum2 = 0;
for (int i = 0; i < n; i++) {
set.add(r.nextInt(Integer.MAX_VALUE));
}
for (int i = 0; i < n; i++) {
sum2 += set.contains(r.nextInt(Integer.MAX_VALUE)) ? 1 : 0;
}
long t3 = System.currentTimeMillis();
System.out.println(sum2);
System.out.println(t1 - t0);
System.out.println(t3 - t2);
}
}
477
488
4289
2070
Die new TreeSet<>(); ist ca. doppelt so schnell wie die SkipList… Mit dem Zufall ist halt nicht zu spaßen. Gut, aber ich habe height noch nicht mit einbezogen.
n*log_2(n) ist also ca. 1.5 Sekunden oder 1500ms. Wie kann ich jetzt n berechnen, also wie komme ich auf die 910 Sekunden?
Wolfram|Alpha:
a) https://www.wolframalpha.com/input/?i=x*log_2%28x%29%3D1500 => 197
b) https://www.wolframalpha.com/input/?i=x*log_2%28x%29%3D1.5 => 1.79
?
Ein kurzer Einschub, auch wenn er nicht als konstruktiv angesehen werden wird:
Davon, hier die Aufgabenstellung zu posten mit „Wie macht man das?“ halte ich nicht viel
Viele Antworten sind einfach nur hingedengelter Code - zuerst ohne Bezug zur (bis dahin unbekannten) Aufgabenstellung, und wenn der Bezug hergestellt wurde, dann immernoch schlechter Code
Dass die Kommunikation nur über Code stattfindet (d.h. ein Codeblock ohne einen Hauch einer Beschreibung, was der Code macht, und dann ein „Danke, voll toll!“ als Reaktion darauf) finde ich höchst verstörend (allerdings nicht überraschend)
Spätestens, wenn hier irgendwelche „Benchmarks“ gezeigt werden, die auf keiner Ebene der Analyse irgendeinen Sinn ergeben, muss ich aber einschreiten, und das erwähnen: Das ergibt keinen Sinn.
Dass ein Informatikstudium heutzutage nichts mehr damit zu tun hat, dass man sich die Kompetenz aneignet, solche Probleme angemessen zu lösen, weiß ich schon. Aber das ganze hier finde ich im Moment einfach nur total schräg
@Marco13 : Ich habe doch die add-Methode dokumentiert. Sind dir die Kommentare nicht ausführlich genug? Ich habe fast jede Zeile/jeden Block kommentiert.
schlechter Code
Das müsstest du bitte etwas genauer darlegen, sonst ist es einfach nur ein subjektives Empfinden.
Dass die Kommunikation nur über Code stattfindet
Das ist wirklich etwas traurig, schien mir aber hier angemessen zu sein, aus unterschiedlichen Gründen.
Spätestens, wenn hier irgendwelche „Benchmarks“ gezeigt werden, die auf keiner Ebene der Analyse irgendeinen Sinn ergeben
Auch dabei würde mich bitte eine Begründung interessieren, warum man zwei O(log n)-Datenstrukturen und eine O(n)-Datenstruktur nicht miteinander sinnvoll vergleichen kann.
Dass ein Informatikstudium heutzutage nichts mehr damit zu tun hat, dass man sich die Kompetenz aneignet,
Schade, dass du das so siehst!
PS: Oder war ich mit den von dir aufgezählten Punkten gar nicht gemeint?
Vieles ist NICHT subjektiv, und ich (und andere) haben dir schon dutzende oder hunderte Male den Quälkot zerpflückt, den du hier immer postest. Ich könnte das jetzt auch hier wieder tun, und wieder alles aufzählen, was daran schlecht und falsch ist, und du würdest beim einen oder anderen Punkt wieder sagen „Ähnaja, da vielleicht, das auch, das eher nicht, vielleicht, ähm, ein bißchen“, dann den gleichen Code mit halbherzigen „fixes“ posten und fragen „Ist das jetzt besser?“, und bei der nächsten „Kann mal jemand kurz meine Hausaufgaben machen?“-Frage, die hier gepostet wird, würdest du wieder irgendwas schauderhaftes hindengeln. Been there. Done that.
Aber diesmal ist der Sachverhalt doch anders gelagert… a) Ein Teil der Implementierung war vorgegeben, b) den anderen Teil der Implementierung hab ich aus einer SO-Antwort abgeleitet! Also so schlecht kann das alles doch nicht sein…
Aber nur interessehalber: Wie hättest du hier richtigerweise agiert, also wie hättest du auf die Frage des TEs geantwortet?
Nun, an sich ist da nicht sooo viel „Vorwurf“ drin. Man hätte weniger Code posten und mehr Eigeninitiative erwarten können, andererseits war der Threadersteller aber „zufrieden“ mit den Antworten. Das Dilemma, das darin besteht, dass ich von so einem Forenthread einen anderen Verlauf und andere Inhalte erwarten würde, ich selbst aber nicht die Zeit aufwenden … kann (oder will? hmmm…) … die dafür notwendig wäre, kann ich auch nicht auflösen. Normalerweise umgehe ich die Frage, indem ich dann nichts schreibe, solange alle anderen Diskussionspartner „zufrieden“ sind. Aber den obigen Einschub hielt ich dann doch für angemessen.
