Du verwendest einen veralteten Browser. Es ist möglich, dass diese oder andere Websites nicht korrekt angezeigt werden. Du solltest ein Upgrade durchführen oder ein alternativer Browser verwenden.
Hallo, ich brauche eine Datenstruktur wie SortedSet, nur dass ich ganz am Anfang beim Einfügen der Werte schon gleich weiß, wie viele es sein werden und sie bereits sortiert vorliegen habe. Könnte ich dem SortedSet das irgendwie sagen, so könnte man einiges an Zeit sparen. SortedSet müsste nämlich die neuen Werte nicht einsortieren sondern könnte mir einfach glauben und könnte gleich von Beginn die richtige Einteilung des Speicherplatzes organisieren. Sobald die Initialdaten jedoch drin sind, soll es sich ganz normal wie ein gewöhnliches SortedSet verhalten.
Soweit ich das weis, werden die Daten der Standard-SortedSets in Java eigentlich gar nicht in einer bestimmten bzw. sortierten Reihenfolge gespeichert. Einzelne Elemente erhalten lediglich Referenzen auf das vorhergehende bzw. das folgende Element. Beim Einfügen sowie beim Entfernen werden ausschliesslich die in Frage kommenden Referenzen neu gesetzt. Gibt wohl auch kaum was schnelleres. Wenn man also ein zuvor sortiertes Set einfügt, sollte das initiale Setzen dieser Referenzen kaum Zeit in Anspruch nehmen.
Soweit ich das weis, werden die Daten der Standard-SortedSets in Java eigentlich gar nicht in einer bestimmten bzw. sortierten Reihenfolge gespeichert.
Naja, sowohl SkipList, als auch Red-Black-Trees sind schon ziemlich ordentlich sortiert^^
@RungetSvohu:
1) Red-Black-Trees sind sowieso Bäume, und müssen mehr oder weniger aufwendig aus deiner sortierten Liste aufgebaut werden. Ganz ehrlich: mach dir keinen Kopf drum, pack alle elemente in so ein baum und fertig. Wenn's sich später als Flaschenhals rausstellen sollte, kannst du dir ja noch weitere Gedanken machen.
2) Die ConcurrentSkipListSet besitzt intern eine private methode namens buildFromSorted, dort wird dem anderen übergebenen SortedSet vertraut, und nicht neusortiert. Nur musst du den Konstruktor von ConcurrentSkipListSet irgendwie dazu überreden, deine sonstwie sortierte Liste als SortedSet anzuerkennen. Sowas in etwa:
Java:
import java.util.*;
import java.util.concurrent.*;
public class ListAsSortedSet {
public static <X> SortedSet<X> trustMeItsSorted(final List<X> list, final Comparator<X> comp){
return new SortedSet<X>(){
@Override public boolean add(X arg0) { throw new Error(); }
@Override public boolean addAll(Collection<? extends X> arg0) { throw new Error(); }
@Override public void clear() { throw new Error(); }
@Override public boolean contains(Object arg0) { throw new Error(); }
@Override public boolean containsAll(Collection<?> arg0) { throw new Error(); }
@Override public boolean isEmpty() { return list.isEmpty(); }
@Override public Iterator<X> iterator() { return list.iterator(); }
@Override public boolean remove(Object arg0) { throw new Error(); }
@Override public boolean removeAll(Collection<?> arg0) { throw new Error(); }
@Override public boolean retainAll(Collection<?> arg0) { throw new Error(); }
@Override public int size() { return list.size(); }
@Override public Object[] toArray() { throw new Error(); }
@Override public <T> T[] toArray(T[] arg0) { throw new Error(); }
@Override public Comparator<? super X> comparator() { return comp; }
@Override public X first() { throw new Error(); }
@Override public SortedSet<X> headSet(X arg0) { throw new Error(); }
@Override public X last() { throw new Error(); }
@Override public SortedSet<X> subSet(X arg0, X arg1) { throw new Error(); }
@Override public SortedSet<X> tailSet(X arg0) { throw new Error(); }
};
}
public static void main(String... _){
List<Integer> list = new LinkedList<Integer>();
list.add(1);
list.add(2);
list.add(45); // sorted, but not a SortedSet
Comparator<Integer> comp = new Comparator<Integer>(){
@Override
public int compare(Integer a, Integer b){
return a - b;
}
};
ConcurrentSkipListSet<Integer> skipList = new ConcurrentSkipListSet<Integer>(trustMeItsSorted(list, comp));
System.out.println(skipList);
}
}
Ich habe aber keine Ahnung, was da passiert, wenn du eine schlecht sortierte Liste als SortedSet tarnst und da durch schmuggelst: dann fliegt dir wahrscheinlich alles um die Ohren.
EDIT: hey, TreeMap hat auch eine spezielle optimierte buildFromSorted-Methode! Dann kannst du ja denselben Hack auch für TreeSet verwenden, musst aber evtl einige der "throw Error"-Stümmel noch sinnvoll ausfüllen, etwa tailSet und headSet... Gug genauer in dem Source code von TreeMap nach, was die buildFromSorted alles braucht (source code findest du im ordner mit deiner JDK-Installation, da ist so ein "src" archiv, dann zu java.util.TreeMap gehen und nach "buildFromSorted" suchen, da ist die mehtode selbst, sowie eine rekursive helfer-methode)
Hast meinen Beitrag wohl nicht zu Ende gelesen. Eine SkipList ist mir gerade nicht geläufig aber Red-Black-Trees, denke ich, schon. Gehören z.B. HashMap und TreeMap bzw. auch die gleichklingenden Sets nicht zu den letzteren und damit zur Gattung "doppelt verketteter Listen"? Elemente in solchen Listen sind recht selten bis gar nicht sortiert im Speicher abgelegt mit anderen Worten gespeichert. Wozu auch, die Reihenfolge wird ja durch die beschriebenen Referenzen (Red-Black, Previous-Next usw.) festgelegt. Wollte man die Elemente auch noch in der korrekten Reihenfolge im Speicher halten, könnte das mitunter doch sehr sehr Zeitaufwendig werden.
@Spacerat: Sicher, dass du verkettete Listen nicht mit binären Bäumen verwechselst? (Okay, man könnte natürlich verkettete Listen als unäre Bäume auffassen, aber das ist selten im Sinnes des Erfinders.)
Ein SortedSet ist eine Menge von Elementen, wobei eine Totalordnung (siehe Wikipedia) auf der Menge dieser Elemente existieren (und im Konstruktor einer implementierenden Klasse auch implizit oder explizit angegeben werden) muss. Alle Elemente in einem SortedSet liegen in diesem permanent sortiert (im Sinne der angegebenen Totalordnung) vor. Elemente sollten gleich laut equals() sein, wenn sie auch gleich im Sinne dieser Totalordnung sind. So kann auch relativ leicht bestimmt werden, ob ein bestimmtes Element in der Menge vorkommt, und ebenso kann auch leicht sichergestellt werden, dass niemals zwei gleiche (laut equals()) Elemente in einem SortedSet vorkommen. Die Reihenfolge der Elemente (in diesem Set) ist nicht frei wählbar, sondern wird durch die Totalordnung bestimmt.
Das sind wohl die wesentlichen Eckpunkte zu SortedSet, die so gar nicht auf List zutreffen. Wenn etwas nicht verstanden wurde: einfach nachfragen. ^^
@RungetSvohu: Sorry, ich habe den Thread mehr von unten nach oben als anders herum gelesen. ^^ 0x7F800000 hat wohl schon genau gesagt, was du machen musst.
(So, jetzt off topic. )
@Spacerat: Okay, ich glaube, jetzt verstehe ich, was du meinst. Ich nehme aber mal stark an, dass es dem TO gar nicht um die tatsächliche Anordnung im Arbeitsspeicher geht. Wie dem auch sei: Dank des GCs kann man in Java praktisch nie eine verlässliche Aussage darüber machen, "wo" im Arbeitsspeicher ein Objekt abgelegt ist. Unter den vielen verschiedenen Möglichkeiten, die so ein GC im Allgemeinen hat, kann man sich auch folgende bei JVMs vorstellen (einfach dargestellt, weiß gerade nicht mehr, wie man es nennt):
Ich (GC) will mal aufräumen. Dazu reserviere ich mir einen neuen Speicherbereich, der genauso groß ist wie der bisher benötigte Platz. Anschließend kopiere ich alle Objekte, von denen ich sehe, dass sie tatsächlich noch benötigt werden, in diesen neuen Speicherbereich (und aktualisiere die Referenzen). Wenn ich damit fertig bin, behaupte ich einfach, der alte Speicherbereich sei nun leer.
Durch das Umkopieren landen dann alle Objekte woanders im Arbeitsspeicher. Aber mal davon abgesehen: es gibt noch die Speicherverwaltung durch das Betriebssystem bzw. mehr oder weniger Hardware (Stichwort: protected mode). Insofern ist das mit dem "wo was im Arbeitsspeicher ist", gerade bei Java eine echt heikle Sache (und eben mehr oder weniger magic ).
HashMaps/-Sets haben wohl am wenigsten mit einer doppelt verketteten Liste zu tun: dort gibt es keinerlei Ordnung zwischen den elementen, die werden einfach anhand ihres hashcodes mehr oder weniger gleichverteilt auf die buckets verstreut, sonst nichts. Es gibt zwar auch eine LinkedHashSet, diese ist aber eine reine hybrid-struktur, das Verlinken ist nur für die "hübsche ausgabe in insertion-order" da, das hashen funzt auch ohne bestens. Genau dasselbe gilt für Bäume: die elemente hängen an einem Baum, und sind im normalfall nicht durch querkanten verbunden, das laufen zum nächsten Element kann im worst case O(log(n)) dauern. Man kann aber auch hier "verkettete Liste" in den Baum reinkleben, wenn das vor- und rückwärtsiterieren wichtig ist, das wäre aber wieder hybrid-struktur, für Red-Black-Baum an sich ist sowas nicht notwendig.
LinkedLists, SkipLists und LinkedQueues sehen schon eher aus, wie verkettete Listen.
Elemente in solchen Listen sind recht selten bis gar nicht sortiert im Speicher abgelegt mit anderen Worten gespeichert.
Naja, worüber kann man denn schon sagen, dass es "irgendwo im speicher liegt"? Alles wird einfach dorthin geschrieben, wo grad platz frei ist. Wahrscheinlich liegen Elemente von Arrays als ein zusammenhängender Block im Speicher (zumindest bei primitiven Datentypen). Alles andere ist irgendwo verstreut und nur über Referenzen erreichbar. Es ging hier die ganze Zeit nur um die Frage "wie schnell kann man die und die referenz auffinden?". Wie schnell das folgen entlang dieser referenz zum Objekt dauert, kannst du durch deine Datenstruktur nicht beeinflussen, das hängt von der Geschwindigkeit des RAMs ab.
Ja, das ist sehr wahrscheinlich. Bei Objekt-Arrays stehen dann wohl einfach die Referenzen direkt aufeinanderfolgend im Arbeitsspeicher. (Man müsste also eher von Referenz-Arrays sprechen.) Dies macht die Adressierung einzelner Elemente einfach:
Ist foo ein T-Array, dann liegt der Inhalt von foo[x] (x hier positive int-Zahl) genau bei (Position von foo[0]) + sizeof(T) * x. Vorsicht: Wenn T ein Referenztyp ("Objekttyp") ist, ist sizeof(T) gerade die Anzahl Bytes, die zum Speichern einer Referenz benötigt werden (und NICHT die Größe eines Objektes!). In Java werden nirgends Objekte direkt "am Ort" gespeichert oder übertragen. Stattdessen werden überall nur die Referenzen auf die jeweiligen Objekte gespeichert bzw. übertragen.
Wenn das mit der Adressierung nicht so wäre, wäre der Zugriff auf ein einzelnes Element auch nur umständlich zu realisieren: entweder über weitere Referenzen (sprich: verkettete Liste) oder doch wieder über den Abstand wie in einem Array. Man kommt also um eine Array-Implementierung à la malloc (zusammenhängender Speicher beliebiger Größe) nicht herum, wenn man halbwegs effizient sein können will.
Okay, hast unbestritten gewonnen... Wie und wo die JVM ihre Objekte ablegt, soll nicht Sache der Javaentwickler werden. Aber selbst die Objektreferenzen in den Arrays solcher Listen oder Sets müssen nicht mal sortiert sein und weil das so ist, weis ich nicht mal, wie man in Java eine solch vorsortierte Liste hinbekommt, ohne eine der hier vorgeschlagenen zu verwenden. Die einzelnen Elemente aus einer Solchen entnehmen und, um sie mit der Intention sie wiederum in einer derartigen einfügen zu wollen, in einer ArrayList auslagern? Warum sollte man so tun, wenn das TreeSet und die -Map zumindest ohnehin schon SortedSets bei seiner Instazierung als sortiert behandelt? Dort wird bei beiden Klassen die bereits von dir benannte "buildFromSorted()"-Methode aufgerufen. Das TreeSet verhält sich also bereits so, wie es vom TS gewünscht wird, solange er ein SortedSet übergibt.
Er hat aber kein SortedSet, sondern irgendeine ArrayList oder Array, die sonstwie sortiert wurde (mit irgendeinem quicksort oder mergesort oder sowas). Jetzt weis der Mensch zwar aufgrund irgendwelcher Überlegungen, dass die Liste sortiert sein muss, aber der Compiler weis es nicht, weil Compiler nur stur die Typen prüft, und keine mathematischen Beweise über den Zustand der Objekte erstellt. Und der Threadstarter will einfach wissen, wie man den Compiler dazu zwingt, eine solche sortierte Liste (die nicht von SortedSet erbt) effizient in ein SortedSet reinzuquetschen.
