Klassen Eine ArrayList<Long>, die sich automatisch sortiert

Diskutiere Eine ArrayList<Long>, die sich automatisch sortiert im Java Basics - Anfänger-Themen Bereich.
I

inflamer

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!
 
I

inflamer

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

mihe7

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

inflamer

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

mrBrown

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?
 
I

inflamer

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?
Exakt das, also eine Art eierlegende Wollmilchsau. ;)
 
mihe7

mihe7

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

inflamer

Dann pack einfach beides in eine Klasse. Einfügen wäre dann z. B. in linearer Zeit, Abfrage in O(1) möglich.
Darauf wird's wohl hinauslaufen. Eine HashMap-Instanz nur für die .contains()-Abfrage.

An dieser Stelle meinen aufrichtigen Dank an alle, die geantwortet haben!
 
Zuletzt bearbeitet:
T

temi

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

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

mrBrown

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

Xyz1

Ich habe noch remove Methoden usw. vergessen... Ich weiß nicht, ob das verlangt ist...
 
N

Neumi5694

"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

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

temi

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

Xyz1

Na ja, ich hatte den Vorschlag in den Raum gestellt... Nicht so bissig bitte.
 
mrBrown

mrBrown

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.
 
Thema: 

Eine ArrayList<Long>, die sich automatisch sortiert

Passende Stellenanzeigen aus deiner Region:
Anzeige

Neue Themen

Anzeige

Anzeige
Oben