Klassen Eine ArrayList<Long>, die sich automatisch sortiert

inflamer

Bekanntes Mitglied
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!
 

inflamer

Bekanntes Mitglied
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ß
 

mihe7

Top Contributor
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.
 

inflamer

Bekanntes Mitglied
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...
 

mrBrown

Super-Moderator
Mitarbeiter
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?
 

mihe7

Top Contributor
Dann pack einfach beides in eine Klasse. Einfügen wäre dann z. B. in linearer Zeit, Abfrage in O(1) möglich.
 

temi

Top Contributor
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?
 
X

Xyz1

Gast
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());
  }
}
 

mrBrown

Super-Moderator
Mitarbeiter
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.
 

Neumi5694

Top Contributor
"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.
 
X

Xyz1

Gast
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.
 

temi

Top Contributor
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?
 

mrBrown

Super-Moderator
Mitarbeiter
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.
 
X

Xyz1

Gast
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.

Danke, aber etwas anderes behauptete ich auch nicht...

Gerne, aber ich frage mich im Moment, wie ich diese doch relativ einfache Frage hätte anders formulieren können, ohne deine Psyche dabei anzukratzen.

Ja schon gut... (psychologisch gesehen) ein übermäßiger "Ich-Bezug". :(
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
Kerstininer Vererbung Hilfe beim lernen von Objektorientierung für eine Klausur Java Basics - Anfänger-Themen 10
K Warum wird hier nur etwas in eine txt Datei geschrieben und nicht in alle drei (InputStream/OutputStream/Reader/Writer) Java Basics - Anfänger-Themen 1
I In unterschiedlichen Applikation Zugriff auf eine gemeinsame Anwendung? Java Basics - Anfänger-Themen 8
D 2 ArrayListen gleich sortieren bzw. eine Liste anhand einer anderen Sortieren Java Basics - Anfänger-Themen 6
T Ich brauche eine Schleife die eine beliebige Zahl so lange durch 10 teilt bis zur Null Java Basics - Anfänger-Themen 5
S Java: Wie sortiere ich eine ArrayList benutzerdefinierter Objekte nach einem bestimmten Attribut? Java Basics - Anfänger-Themen 2
J Eine konzeptionelle Frage zu OOP Java Basics - Anfänger-Themen 3
N Ich kriege ganze zeit die Fehlermeldung "Inhalt der Zwischenablage kann nicht in die ausgewählten Elemente eingefügt werden" hat jemand eine Lösung? Java Basics - Anfänger-Themen 6
M Vergleichen, ob eine Liste länger als andere ist Java Basics - Anfänger-Themen 6
T Methode soll etwas ausrechnen und zurückgeben (klappt nd) hat wer eine Idee? Java Basics - Anfänger-Themen 11
Shadowrunner Variablen Gibt es eine Möglichkeit die Ziffern/Stellen einer Zahl fest zu legen? Java Basics - Anfänger-Themen 3
Kingdako Wie löse ich eine Mathematische Formel mit Arrays und Schleifen? Java Basics - Anfänger-Themen 32
M Datentypen While-Schleife eine Java Methode erstellen Java Basics - Anfänger-Themen 3
G Wie wartet man bis ein URL eine Antwort zurückgibt? Java Basics - Anfänger-Themen 5
berserkerdq2 Intelij, wie kann ich einstellen, dass die aktuelle Klasse ausgeführt wird, wenn ich aufs Startsymbol drücke, gibts da eine Tastenkombination? Java Basics - Anfänger-Themen 11
S 2 Reihen ratio-btn, eine Reihe funktioniert andere nicht Java Basics - Anfänger-Themen 4
T Eingabe durch eine Zahl dividieren nachgucken? Java Basics - Anfänger-Themen 4
M mit Maven eine ausführbare Jar bauen Java Basics - Anfänger-Themen 7
P Java Selenium . Parameterized.Parameters erzeugt eine Fehlermeldung Java Basics - Anfänger-Themen 14
J Zugriff auf eine 2. Klasse die per UI-Designer erstellt wurde Java Basics - Anfänger-Themen 1
M Eine Funktion zuweisen Java Basics - Anfänger-Themen 3
J Eine theoretische Frage zur Praxis - JPanel oder Canvas Java Basics - Anfänger-Themen 5
A Methoden Guten Tag , ich wollte so machen dass wenn meine frog an eine fly/bee geht dann an meine Tafel geht der zahl +1 hoch. Java Basics - Anfänger-Themen 2
A Wie führe ich eine Batch-Datei von meiner Java-Anwendung aus? Java Basics - Anfänger-Themen 18
J Beim Start des Programms zB. eine Linie in JPanel ausgeben Java Basics - Anfänger-Themen 4
L Methoden Eine Methode um zu testen ob es ein Nachbar gibt Java Basics - Anfänger-Themen 10
S Eine Idee umsetzen ganz schnell!? Java Basics - Anfänger-Themen 68
I Grundsatzfrage: Belegt eine Referenz auf 'null' RAM, und wenn ja - wieviel ;-) ? Java Basics - Anfänger-Themen 5
jeff98 Wie kann man in Java eine Zeichenformation ausgeben? Java Basics - Anfänger-Themen 9
K loop pausieren für eine bestimmte Anzahl? Java Basics - Anfänger-Themen 1
_user_q Wie eine Methode/Funktion aus einer Klasse mit Constructor aufrufen? Java Basics - Anfänger-Themen 20
Thomas06 Wie kann man mithilfe von boolean herausfinden ob eine zahl durch 5 und 7 teilbart ist ? Java Basics - Anfänger-Themen 7
M Prüfen on eine Zahl im String enthalten ist Java Basics - Anfänger-Themen 3
U jUnit 5 Test für eine addMethode Java Basics - Anfänger-Themen 18
frager2345 Singleton-Muster Java ->Nur eine Instanz einer Klasse erzeugen können Java Basics - Anfänger-Themen 45
A Eclipse IDE - Wie bekomme ich eine ältere Version Java Basics - Anfänger-Themen 6
F Wie kann ich eine Funktion schreiben, die nur in bestimmten Fällen einen Wert zurückgibt? Java Basics - Anfänger-Themen 5
berserkerdq2 Warum muss man manchmal in der RUnmethode sleep in eine schleife tun? Java Basics - Anfänger-Themen 9
berserkerdq2 Findet eine parallele Verarbeitung in Java bei Threads erst statt, wenn man die Methoden auch synchronized? Und wie sieht bei Conditions aus? Java Basics - Anfänger-Themen 8
berserkerdq2 Wozu benötigt man den BiPredicate, kann ich nicht einfach eine normale Methode nutzen, statt BiPredicate? Java Basics - Anfänger-Themen 3
berserkerdq2 Habe eine Klasse, welche public ist, diese hat eine public Methode, die nicht static ist. Wenn ich nun versuche aufzurufen Probleme? Java Basics - Anfänger-Themen 8
berserkerdq2 Zwei Klassen Erben von der Klasse A, die eine Klasse kann ich an Methoden übergeben, die als Parameter A haben, die andere nicht? Java Basics - Anfänger-Themen 3
berserkerdq2 Sende eine Nachricht an den Client und leere den Ausgabestorm, was ist damit genau gemeint? Java Basics - Anfänger-Themen 3
S Eine Variable in einem Array speichern Java Basics - Anfänger-Themen 5
sserio Prüfen, ob eine Zahl eine periodische Zahl ist Java Basics - Anfänger-Themen 20
L Anpassung der Spaltenbreite auch auf eine zweite Tabelle anwenden Java Basics - Anfänger-Themen 8
NadimArazi Wie kann ich eine collision detection für die Paddles in meinem Pong Programm hinzufügen? Java Basics - Anfänger-Themen 4
JordenJost Java ist auch eine Insel für Anfänger Java Basics - Anfänger-Themen 2
berserkerdq2 Warum soll ich shuffle nutzen, um bei Rückgabewert Collection eine Liste zurückzugeben? Java Basics - Anfänger-Themen 3
berserkerdq2 Ich gebe eine ArrayList als List zurück per MEthode, wie kann ich nun aber die ArrayList speichern? Java Basics - Anfänger-Themen 46
berserkerdq2 Überprüfen ob eine Schreibberechtigung auf ein file exisitert bzw. ob man dieses file löschen kann, wie? Java Basics - Anfänger-Themen 9
sserio Java Fx, wie erstellt man einen EventHandler, der durch das Drücken eines Button Texte in eine Table view einfügt Java Basics - Anfänger-Themen 17
M Eine Methode die erkennt ob die ein gegebene zahl größer oder kleiner sein muss Java Basics - Anfänger-Themen 2
Avalon Warum funktioniert eine Bedingung und eine andere nicht? Java Basics - Anfänger-Themen 2
F Suche nach betreuender Person für eine Jahresarbeit der 12. Klasse. Java Basics - Anfänger-Themen 6
X Hilfe beim Übertragen in eine For-Schleife Java Basics - Anfänger-Themen 1
H Eine Methode über Actionlistener beenden Java Basics - Anfänger-Themen 8
A Wenn eine Zahl durch 7 teilbar ist, soll statt der Zahl ein ‘*‘ angezeigt werden. java? Java Basics - Anfänger-Themen 47
U Warum gibt das eine Nullpointerexception? (Switch) Java Basics - Anfänger-Themen 6
U Warum kriege ich hier eine nullpointer exception, sehe den Fehler nicht (swing) Java Basics - Anfänger-Themen 1
K Warum gibt mir z. B. 40^128 eine Zahl? Ich dachte mit xor kann man nur booleanwerte erhalten, also prüfen ob etwas whar oder falsch ist? Java Basics - Anfänger-Themen 1
M Wie lassen sich Objektkonstanten initialisieren, wenn sie eine Bedingung erreichen? Java Basics - Anfänger-Themen 6
K Präzedenregeln in Java sagen, dass +expr und -expr vor + von Addition und - von Addition stehen, warum wird dann z. B. a+b als eine Addition ausgeführ Java Basics - Anfänger-Themen 7
M Wie schreibe ich eine if-Verzweigung um, so dass ein Bedingungsoperator benutzt wird? Java Basics - Anfänger-Themen 9
M Wie kann eine Methode für ein vorhandenes "Array von char" einen Index-Wert zurückliefern? Java Basics - Anfänger-Themen 3
M Wie kann eine Methode (string) eine andere Methode (void) mit zufälligen int-Werten aufrufen? Java Basics - Anfänger-Themen 4
M Wie verknüpfe ich eine Bedingung mit einer Methode ohne if-Verzweigung & Bedingungsoperator? Java Basics - Anfänger-Themen 2
M Wie kann eine Methode eine andere Methode um Werte wie z.B. 1 erhöhen? Java Basics - Anfänger-Themen 6
B Methoden Rekursiv festellen, ob eine Zahl gerade-oft vorkommt oder nicht Java Basics - Anfänger-Themen 4
M Wie kann ich eine Methode aus einem Interface in eine Klasse implementieren, so dass sie ihre Funktion ausführt? Java Basics - Anfänger-Themen 7
Igig1 Welche Werte sind als default Werte in einem Array, der als Datentyp eine Klasse hat? Java Basics - Anfänger-Themen 1
Kiki01 Wie würde eine geeignete Schleife aussehen, die die relative Häufigkeit für jeden Charakter in einem Text bestimmt? Java Basics - Anfänger-Themen 3
M Wie richte ich eine Diagonale an Robotern in einer World ein? Java Basics - Anfänger-Themen 15
O Wie erstelle ich eine Instanz in einer Klasse für die ich die Instanz will? Java Basics - Anfänger-Themen 4
EchtKeineAhnungManchmal Hallo :) ich bekomme es nicht hin eine Fehlermeldung auszugeben über die GUI Java Basics - Anfänger-Themen 3
S Kann ich eine jar anschauen wie sie gecoded wurde? Java Basics - Anfänger-Themen 2
A Eine Textdatei auslesen Java Basics - Anfänger-Themen 16
A Objekte mit Parametern in eine Liste packen Java Basics - Anfänger-Themen 19
Poppigescorn scan.nextInt() wiederholen bis eine Zahl eingeben wird Java Basics - Anfänger-Themen 7
D Welche GUI Library für eine Client Server Chat App Java Basics - Anfänger-Themen 14
B Programm, dass alle 3 Tage eine Webseite öffnet? Java Basics - Anfänger-Themen 20
N Variabel in eine class mit "extends JLabel" übertragen Java Basics - Anfänger-Themen 2
C Programm das feststellen kann, ob eine eingegebene Zahl einem Schaltjahr entspricht, richtig geschrieben? Java Basics - Anfänger-Themen 11
Vivien Auf eine Variable von einer anderen Klasse aus zugreifen Java Basics - Anfänger-Themen 3
B eine methode erstellen Java Basics - Anfänger-Themen 7
F Wann ist es eine Instanz und wann nicht? Java Basics - Anfänger-Themen 1
E Warum lässt sich eine Klasse nicht starten, wenn eine andere Klasse in dem Modul fehlerhaft ist? Java Basics - Anfänger-Themen 1
J Alle .java Dateien von einem Verzeichnis in eine Zip speichern Java Basics - Anfänger-Themen 2
H Kann eine while-Schleife ein Programm blockieren? Java Basics - Anfänger-Themen 8
P eine kleine Aufgabe mit Audio Java Basics - Anfänger-Themen 1
O zweidimensionales array in eine csv-Datei Java Basics - Anfänger-Themen 1
P Wie rufe ich Methoden mit einer Referenz auf eine Klasse||Objekt auf Java Basics - Anfänger-Themen 4
Bademeister007 Hallo Leute ich hab eine Frage zur ArrayList Java Basics - Anfänger-Themen 8
M Nach einer erstmaligen Eingabe, eine zweite Eingabe nur noch gegen bestätigung möglich Java Basics - Anfänger-Themen 2
TimoN11 Java - Eine oder mehrere Eingaben möglich machen Java Basics - Anfänger-Themen 6
A Wie schaffe ich das eine while Schleife addiert danach subtrahirt? Java Basics - Anfänger-Themen 1
Y Einfügen in eine doppelt verkettete Liste Java Basics - Anfänger-Themen 8
T Ich habe eine Variabel die nicht Methoden übergreifend ist. Kann mir jemand Helfen :) Java Basics - Anfänger-Themen 5
H Daten aus einer Datei in eine Liste speichern Java Basics - Anfänger-Themen 23
Tino1993 for-Schleife, die eine vorgegebene Anzahl von Zeichen ausgibt Java Basics - Anfänger-Themen 3

Ähnliche Java Themen

Neue Themen


Oben