Collections Wahl der richtigen Collection

[Gust]

Hallo zusammen,

ich bin auf der Suche nach einer Collection, die folgendes kann:
1. jedes Element darf nur einmal vorkommen
2. die Elemente sollen automatisch (und immer) sortiert sein
3. ich will wie bei einer List über den Index zugreifen können

Die naive Lösung wäre natürlich sowas hier:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;


public class SpecialList<T extends Comparable<T>> {

	private List<T> list = new ArrayList<T>();
	
	public void add (T element){
		if(!list.contains(element)){
			list.add(element);
			Collections.sort(list);
		}
	}
	
	//ein paar weitere delegations hier ...
}

.. was natürlich ziemlich "lame" ist.
Mir ist bewusst, dass es java.util.TreeSet gibt, was zumindest Anforderungen 1 und 2 erfüllt. Man kann aber nur über nen Iterator zugreifen. Ich könnte natürlich erben und die Methode get(int index) hinzufügen, aber das wäre ja genauso hässlich 🙁
Also habt ihr eine Idee, welche Collection dafür in Frage käme? Ich habe das java.util Package durchsucht, aber habe beim besten Willen nichts Passendes gefunden.

 

[Gast2]

1. jedes Element darf nur einmal vorkommen
2. die Elemente sollen automatisch (und immer) sortiert sein

TreeSet wie du selbst schon gesagt hast.

3. ich will wie bei einer List über den Index zugreifen können

Du kannst ne List erzeugen und die mit den Daten des Sets füttern. Dann hast du die Möglichkeit per index draufzuzugreifen.
Je nachdem wie oft du das brauchst ist die Lösung nicht so toll 😉

 

[Landei]

Das [c]add[/c] oben ist wirklich ziemlich lahm, aber man könnte es besser machen: Per binärer Suche den Einfügeindex finden, schauen, ob da schon das Element steht, das man einfügen will, und wenn nicht, dann einfügen.

 

[Gust]

Ok, die Lösung mit der binären Suche ist eine Idee. Aber ich komme mir immer doof vor, wenn ich Collections nachimplementieren muss. Ist meine Anforderung denn so ungewöhnlich, oder warum gibt es da nichts Passendes?

 

[Landei]

Sortierung und indizierter Zugriff sind nicht ohne weiteres unter einen Hut zu bringen. Bei den meisten Algorithmen ist klar, was benötigt wird, am häufigsten eben ein (eventuell sortierstes) Set, eine Liste, eine Map, eine (z.B. Priority-) Queue oder ein Stack. Auch bei Google Guava (früher u.a. "Google Collections") scheint es deine gewünschte Kombination nicht zu geben.

 

[Gregorrr]

Ok, die Lösung mit der binären Suche ist eine Idee. Aber ich komme mir immer doof vor, wenn ich Collections nachimplementieren muss. Ist meine Anforderung denn so ungewöhnlich, oder warum gibt es da nichts Passendes?

Was ist denn dein Problem mit EikeB Vorschlag?

Wie Landei komplett richtig sagt, beides sind orthogonale Konzepte, d.h. hier muss man einen Kompromiss schließen, was man lieber haben möchte.

Wobei ich mir Gedanken machen würde, wenn die TreeSet Implementierung wirkliche Performance-Probleme verursachen würde.

 

[Marco13]

Ungewöhnlich nicht, sowas braucht man schon ab und zu mal. Allerdings braucht man die spezifische Kombination relativ selten. Man könnte sagen, dass es eine handvoll Operationen gibt, die Collections können
add, remove, find (bzw. contains), get(int index)
und dazu orthogonale Eingeschaften wie "Jedes Element nur einmal drin", oder "Immer sortiert". Die Operationen sollten natürlich möglichst kleine Laufzeit haben, am besten alle O(1) oder schlimmstenfalls O(logn). Aber das kann man nicht alles auf einmal erreichen, und welche Implementierung die beste ist, hängt dann davon ab, welche Operationen besonders oft ausgeführt werden. Als Beispiel:
(ich sehe gerade, dass das bisherige auch schon andere geschrieben haben... hätte wohl erstmal "Reload" drücken sollen 😳 )
Oben wurde gesagt: Bei 'add' eine Binäre suche machen, und ggf. einfügen. Wenn der überwiegende Anteil der Aufrufe darin besteht, dass man 'add' mit einem Element aufruft, das schon enthalten ist, wäre die binäre Suche vielleicht weniger gut. Stattdessen wäre ein O(1)-Zugriff (wie bei einem HashSet) dort besser. Dann wird der indizierte Zugriff lahm, aber vielleicht braucht man den ja nur "ganz selten" (und an nicht-zeitritischen Stellen)?

Zusätzlich hat man oft den Tradeoff zwischen Speicherverbrauch und Zugriffszeit. Eine Triviallösung wäre natürlich, eine Wrapper-Klasse zu machen, die intern eine List und eine HashSet speichert, und z.B. bei 'add' sowas macht wie

void add(Object object)
{
    boolean added = set.add(object);
    if (added) binaryInsertInto(list, object);
]

"Mischformen" wie irgendwelche "lazy"-Strukturen wären auch denkbar:

Object get(int index)
{
    if (list==null)
    {
        list = new ArrayList<Object>(set);
    }
    return list.get(index);
}
void add(Object object)
{
    set.add(object);
    list = null;
}

Aber das hängt alles von den Zugriffsmustern ab.


[/code]

 

[Gust]

Dann ist mir alles klar. Vielen Dank für eure Hilfe 🙂

 

[Ark]

Aber das hängt alles von den Zugriffsmustern ab.

Genau das ist es, was ich hier nicht so ganz verstehe: In welchem Fall braucht man denn einen (echt) wahlfreien Zugriff per Index, aber gleichzeitig eine permanente Sortierung? Sobald ich ein Element einfüge, verschieben sich doch durch die Sortierung einige/alle Indices der bisher eingefügten Elemente, und damit bringen mir die Indices doch nichts mehr.

--> Ich wünsche mir gerade ein Beispiel, wo eine derartige Datenstruktur benötigt wird.

Ark

 

[Gelöschtes Mitglied 5909]

Was ist denn hiermit?

SetUniqueList (Commons Collections 3.2.1 API)

 

[maki]

Was ist denn hiermit?

SetUniqueList (Commons Collections 3.2.1 API)

Da fehlt die Sortierung 😉

 

[thinktank]

Genau das ist es, was ich hier nicht so ganz verstehe: In welchem Fall braucht man denn einen (echt) wahlfreien Zugriff per Index, aber gleichzeitig eine permanente Sortierung? Sobald ich ein Element einfüge, verschieben sich doch durch die Sortierung einige/alle Indices der bisher eingefügten Elemente, und damit bringen mir die Indices doch nichts mehr.

--> Ich wünsche mir gerade ein Beispiel, wo eine derartige Datenstruktur benötigt wird.

Ark

Nur der Vollständigkeit halber, weil ich gerade das gleiche "Problem" habe: Ein Beispiel ist ein zeitlich sortierter TreeSet aus OHLC Bars, von denen ich über die letzten 200 einen Durchschnitt bilden will. Dann will ich von (size - x) bis (size) loopen und irgendwas berechnen.