Klassen Eine ArrayList<Long>, die sich automatisch sortiert

Hallo Forum,

ich benötige eine Liste mit long-Werten, welche sich bei jedweder Änderung der Liste automatisch selbst neu (von klein nach groß) sortiert. Beispiel: Ich füge per .add() irgendeinen neuen Wert hinzu, und die Klasse sortiert diesen automatisch ein, sprich: fügt ihn an der richtigen Position in der Liste ein.

Der letztendliche Sinn und Zweck der ganzen Übung ist, eine Möglichkeit zu haben, zu prüfen, ob ein Wert X in der Liste bereits enthalten ist oder nicht, und das geht bekanntlich am Schnellsten - und auf die Schnelligkeit kommt es im konkreten Anwendungsfall eben auch an - mit einer sortierten Liste.

Eine entsprechende Klasse, die so etwas kann, muss es doch in der Standard-Lib der JRE7 normalerweise vorgefertigt geben, oder?

Danke im Voraus für eure Anregungen!
 
Ja, die erste Antwort dort ist sehr aufschlussreich, danke für den Link!

java.util.TreeSet scheint für meine Zwecke perfekt geeignet zu sein, ist auch nicht synchronisiert.

Gruß
 
Der letztendliche Sinn und Zweck der ganzen Übung ist, eine Möglichkeit zu haben, zu prüfen, ob ein Wert X in der Liste bereits enthalten ist oder nicht, und das geht bekanntlich am Schnellsten - und auf die Schnelligkeit kommt es im konkreten Anwendungsfall eben auch an - mit einer sortierten Liste.
Am schnellsten wäre perfektes Hashing, da hier stets nur ein Zugriff notwendig wäre. Aber auch normales Hashing (in Java HashSet) ist in der Regel schneller als eine binäre Suche über eine sortierte Liste bzw. TreeSet.
 
Am schnellsten wäre perfektes Hashing, da hier stets nur ein Zugriff notwendig wäre. Aber auch normales Hashing (in Java HashSet) ist in der Regel schneller als eine binäre Suche über eine sortierte Liste bzw. TreeSet.
Ich hatte nun ein wenig Zeit darüber "weiterzubrüten", und leider scheint weder TreeSet noch HashSet für meinen Anwendungsfall geeignet zu sein. Es handelt sich zwar tatsächlich um long unique hashes, die gespeichert werden sollen, das Problem ist allerdings, dass keine der beiden Klassen einen Zugriff über Indizien bietet. Ich stoße damit wohl auf ein ähnliches Problem, wie der Fragesteller von dem von kneitzel verlinkten stackoverflow-Thread es wohl auch hatte...
 
Also, du brauchst eine Datenstruktur, die:
* Alle Elemente automatisch sortiert (was gegen vorhandene Listen spricht)
* Indexbasierten Zugriff erlaubt (was gegen Sets und Queues spricht)
* möglichst schnell prüfen kann, ob ein Element vorhanden ist?
 
Dann pack einfach beides in eine Klasse. Einfügen wäre dann z. B. in linearer Zeit, Abfrage in O(1) möglich.
 
Der letztendliche Sinn und Zweck der ganzen Übung ist, eine Möglichkeit zu haben, zu prüfen, ob ein Wert X in der Liste bereits enthalten ist oder nicht, und das geht bekanntlich am Schnellsten - und auf die Schnelligkeit kommt es im konkreten Anwendungsfall eben auch an - mit einer sortierten Liste.
dass keine der beiden Klassen einen Zugriff über Indizien bietet.
Ich verstehe nicht ganz, wozu noch ein Zugriff über Indizes notwendig ist. Du hast einen long Wert und prüfst, ob dieser bereits in einer Liste (Set?) vorhanden ist. Falls nein, füge ihn ein, falls ja, weißt du er ist da und kennst damit auch bereits den Wert, denn Schüssel und Wert sind ja identisch. Warum sollte man den noch extra auslesen wollen?
 
Ich werfe das mal in den Raum, nimm einfach so etwas:
Java:
import java.util.ArrayList;
import java.util.List;
import java.util.SortedSet;
import java.util.TreeSet;

import com.google.common.collect.Iterables;

public class SS {
  private SortedSet<Integer> ss = new TreeSet<Integer>();

  public boolean hinzufügen(int e) {
    if (ss.contains(e))
      return false;
    ss.add(e);
    return true;
  }

  public boolean vorhanden(int e) {
    return ss.contains(e);
  }

  public int gib(int pos) {
    return Iterables.get(ss, pos);
  }

  public List<Integer> toList() {
    return new ArrayList<Integer>(ss);
  }

  public static void main(String[] args) {
    SS ss = new SS();
    ss.hinzufügen(1);
    System.out.println(ss.vorhanden(0));
    System.out.println(ss.vorhanden(1));
    System.out.println(ss.vorhanden(2));
    System.out.println(ss.gib(0));
    System.out.println(ss.toList());
  }
}
 
Ich verstehe nicht ganz, wozu noch ein Zugriff über Indizes notwendig ist. Du hast einen long Wert und prüfst, ob dieser bereits in einer Liste (Set?) vorhanden ist. Falls nein, füge ihn ein, falls ja, weißt du er ist da und kennst damit auch bereits den Wert, denn Schüssel und Wert sind ja identisch. Warum sollte man den noch extra auslesen wollen?
Würde mich auch interessieren, wofür @inflamer den Index-basierten Zugriff braucht, der ist ja "zufällig" und einen Grund für die Anforderung, das 6367-größte Element abzufragen, kann zumindest ich mir grad noch nicht vorstellen.
 
"Der letztendliche Sinn und Zweck der ganzen Übung ist, eine Möglichkeit zu haben, zu prüfen, ob ein Wert X in der Liste bereits enthalten ist oder nicht, und das geht bekanntlich am Schnellsten " Die Zeit, die du beim Durchsuchen einer sortierten Liste gewinnst, verlierst du beim ständigen Neusortieren mehrfach.

WANN brauchst du für dein Programm effektiv die sortierte Liste und den Zugriff per Index? Wenn sich die Liste ständig neu sortiert, ändern sich auch ständig die Indizes. Insofern kann ich mir kaum vorstellen, dass du schon während des Einfügevorgangs damit arbeiten willst.
Falls Indizes erst zum Schluss ein Thema sind, kannst du
a) mit dem TreeSet arbeiten und am Ende mit new ArrayList<>(treeSetVariable) eine sortiere Liste kriegen (mit Index-Zugriff).
b) mit HashSet (ohne ständiges Neusortieren) arbeiten und am Ende mit new ArrayList<>(hashSetVariable) eine unsortierte Liste kriegen, die du dann sortieren lässt.
 
Ich habe nicht geschrieben dass es Sinn machen würde, eine stets sortierte Liste zu haben.... Wie bereits völlig richtig erwähnt... summieren sich dann konstante/logarithmische Zeiten auf... und das wäre dann eben (etwas) langsamer, als einmal alles zu sammeln und dann zu sortieren.
 
Ich habe nicht geschrieben dass es Sinn machen würde, eine stets sortierte Liste zu haben.... Wie bereits völlig richtig erwähnt... summieren sich dann konstante/logarithmische Zeiten auf... und das wäre dann eben (etwas) langsamer, als einmal alles zu sammeln und dann zu sortieren.
Kann es sein, dass du gar nicht gemeint warst?
 
Die Zeit, die du beim Durchsuchen einer sortierten Liste gewinnst, verlierst du beim ständigen Neusortieren mehrfach.
Wobei man ja gar nicht ständig neu sortieren muss, sondern nur an der passenden Stelle einfügen.
Dürfte in Big O (wenn man das einfügen an beliebiger Stelle mit O(1) annimmt) genauso wie das einmalige Sortieren bei O(N * log N) landen (N mal einfügen, Punkt zum einfügen suchen ist jeweils log N).

Ist halt durch konstante Faktoren langsamer, aber immer noch in der gleichen Größenordnung.
 
Passende Stellenanzeigen aus deiner Region:

Neue Themen

Oben