Container gesucht: Indizierter Zugriff + Sortierung + Einfügen/Löschen

SeppJ

Hallo zusammen,

mal eine Frage an die Datenstrukturexperten: Ich benötige einen Container mit recht speziellen Anforderungen und die Standardbibliothek hilft mir nicht weiter. Daher die Frage, ob jemandem eine Datenstruktur einfällt, die folgendes bietet:
Wichtige Eigenschaften:
- Indizierter Zugriff in vertretbarer Zeit
- Sortiert^*
Sekundäre Eigenschaften:
- halbwegs vertretbares Löschen an jeder Stelle
- halbwegs vertretbares Einfügen an jeder Stelle
Ausdrücklich egal ist:
- Speicherverbrauch

^*Zur Sortierung: Sortierung soll von den Elementen abhängen. Dabei ist es ganz egal nach welchem Kriterium sortiert wird, Hauptsache es hängt deterministisch vom Wert der Elemente zusammen. Das heißt es kann eine Sortierung nach dem Wert der Elemente oder genausogut Sortierung nach einem Hashwert sein.

Die beste Antwort bis jetzt ist wohl std::set, das alles bietet außer Indexzugriff. Aber der Indexzugriff in O(N) wurmt mich schon, deshalb die Frage nach einer besseren Datenstruktur.

ipsec

Bei sowas denke ich immer zuerst an boost::multi_index_container .

knivil

std::map

http://www.c-plusplus.net/forum/143816

ipsec

knivil schrieb:

std::map

Du meinst sicher map<index, element> . Das ist dann aber nicht nach den Elementen sortiert.

volkard

SeppJ schrieb:

Die beste Antwort bis jetzt ist wohl std::set, das alles bietet außer Indexzugriff. Aber der Indexzugriff in O(N) wurmt mich schon, deshalb die Frage nach einer besseren Datenstruktur.

Aber Du willst ausdrücklich, daß der Kram sortiert ist.

Indizierter Zugriff? Kann alles heißen. Du willst also for(int i=0;i<c.size();++i) cout<<c[i]; zulassen? Also es soll so tun, als wäre es ein Array, das bei 0 anfängt?

ipsec

Auch interessant könnte boost::bimap<element, index> oder boost::bimap<index, element> sein, das basiert letztendlich auch auf boost::multi_index_container , bietet dir aber eventuell ein besseres Interface.

SeppJ

volkard schrieb:

SeppJ schrieb:

Die beste Antwort bis jetzt ist wohl std::set, das alles bietet außer Indexzugriff. Aber der Indexzugriff in O(N) wurmt mich schon, deshalb die Frage nach einer besseren Datenstruktur.

Aber Du willst ausdrücklich, daß der Kram sortiert ist.

Ja. Das Programm mus deterministisch sein, bezüglich des Inhalts des Containers und darf nicht von der Reihenfolge abhängen wie die Elemente eingefügt wurden. Wenn es da eine bessere Methode außer Sortierung gibt, bin ich dafür gerne offen.

Indizierter Zugriff? Kann alles heißen. Du willst also for(int i=0;i<c.size();++i) cout<<c[i]; zulassen?

Iteration ist nicht unbedingt nötig, aber ich möchte schnell und gezielt Elemente abhängig von einer Zahl anspringen können, siehe unten.

Also es soll so tun, als wäre es ein Array, das bei 0 anfängt?

An einigen Stellen möchte ich auf zufällig ausgewählte Elemente des Containers zugreifen. Die Idee dafür ist, dass ich eben einfach eine Zahl ziehe und als Index benutze. Auch hier bin ich offen für andere Möglichkeiten, ein zufälliges Element aus dem Container zu wählen.

SeppJ

@ipsec: Ja, die Vorschläge klingen schon einmal gut. Bin mal die Details durchlesen, was die genau machen.

volkard

SeppJ schrieb:

andere Möglichkeiten, ein zufälliges Element aus dem Container zu wählen.

So richtig gleichverteilt zufällig? Odert reicht es, wenn manche Elemente auch eine dreifache Ziehungschance haben.

SeppJ

volkard schrieb:

So richtig gleichverteilt zufällig? Odert reicht es, wenn manche Elemente auch eine dreifache Ziehungschance haben.

Gleichverteilt, möglichst exakt. Und der Zufall muss ein deterministischer Pseudozufall sein.

SeppJ

ipsec schrieb:

Bei sowas denke ich immer zuerst an boost::multi_index_container .

Passt leider nicht. Der zweite Index kann mir zwar helfen, ein weiteres Suchkriterium zu haben, aber ich kann damit kein Kriterium "das i'te Element des Containers' konstruieren.

knivil schrieb:

std::map

Hier gilt das gleiche.

ipsec schrieb:

Auch interessant könnte boost::bimap<element, index> oder boost::bimap<index, element> sein, das basiert letztendlich auch auf boost::multi_index_container , bietet dir aber eventuell ein besseres Interface.

Hier leider auch.

Ok, erst einmal wird das wohl ein std::set mit std::advance() zum Zugriff werden, damit ich erst einmal überhaupt etwas habe. Falls noch ein besserer Vorschlag auftaucht, sollte sich das leicht ersetzen lassen.

ipsec

Ein kleines Beispielprogramm:

#include <iostream>

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/random_access_index.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/identity.hpp>

using namespace boost;
using namespace boost::multi_index;

typedef multi_index_container<
	int,
	indexed_by<
		ordered_non_unique<identity<int>>,
		random_access<>
		>
	> container;

int main()
{
	container c;
	c.insert(5);
	c.insert(3);
	c.insert(8);

	c.get<1>().rearrange(c.begin());  // #1

	// Iterieren in sortierter Reihenfolge
	for(auto it = c.begin(); it != c.end(); ++it)
		std::cout << *it << " ";

	// erstes Element
	std::cout << c.get<1>()[0];
}

Die Zeile bei #1 ist nötig, wenn der Index der Elemente mit ihrer sortierten Position übereinstimmen muss. Ansonsten "merkt" sich der random_access<> -Index die Reihenfolge des Einfügens, das erste Element wäre dann also 5. Da du aber sowieso nur ein zufälliges haben möchtest, kann es dir ja egal sein, in welcher Reihenfolge der Random-Access-Index ist, so dass du das rearrange möglicherweise gar nicht brauchst.

volkard

advance(x) klingt nach Durchhangeln mit x Schritten.
rearrange() klingt gleich nach n Schritten, wenn's mal reicht.
rearrange() muß immer nach EInfügung oder Lsöchung aufgerufen werden, weil die nachvollziehbare Zufallsziehung nicht von der EInfüge-Reihenfolge abhängen darf.

volkard

Ein paar Anregungen, die sich ums Hashen drehen:

Eine Hashtable voller einfach verketter Listen. Fast wie auf Seite 184 von http://kurse.fh-regensburg.de/cato/module/Algorithmen/hashing_skript.pdf
Nur, daß unsere verketteten Listen innendrin aufsteigend sortiert sind. Durch die Sortierung der Einzellisten und dadurch, daß das selbe Element immer in die selbe Liste fallen wird, ist die Datenablage nicht mehr von Einfüge- und Löschreihenfolge abhängig. Die üblichen Betrachtungen führen dazu, daß man normalerweise nur keins, eine oder zwei Elemente in einer Liste hat, wenn die Hashtable mindestens 25% mehr Listen hat als insgesamt eingetragene Elemente. Außerdem speichern wir in z.B. einem vector<int>, wieviele Listen es von welcher Länge es gibt. Und wir führen eine Variable maxListLen, die angibt, wie lang die längste Liste ist.

Zufälliges gleichverteiltes Ziehen geht jetzt so:
:nochmal
Es wird eine zufällige Liste gezogen.
In dieser Liste wird rand()%maxListLen ein zufälliger Index gewählt.
Falls da kein Element ist, weil die Liste zu kurz ist, goto nochmal.

Keine Garantie, wenn wir echten Zufall unterstellen, aber ein Generator mit endlicher Periode und einigermaßen Gleichverteilung wird sicher mal die maximal lange Liste treffen und dann terminiert es ja schon. Denken wir uns einen bösen Fall mit einer Liste der Länge 7 und 999 Listen der Länge 1, um dann mehr als 50 Versuche zu brauchen, müßte man jedesmal eine Dumme Liste treffen 0.999^50 und jedesmal drin nicht das Element (6/7)^50, sind zusammen nur p=0.0004.

Denken wir uns eine brave Hashtable wieder mit ca 1000 Dingen, mit 80% Füllstand (also 1250 Listen) und sagen wir mal 250 Listen der Länge 2, 750 der Länge 1 und 250 der Länge 0, dann trifft ist die Abbruchwahtscheinlichkeit pro Zug 250/1250 + 750/1250/2 = 0.5, also um 30-mal vorbeizuwürfeln, sind wir schon bei 1:1Milliarde.

Problem:
Die Hashtable könnte zu leer sein, dann dauert es zu lange, eine Liste zu finden, die nicht leer ist. Das muß verhindert werden. Zum Beispiel, daß man erlaubt, daß die Hashtable schrumpft und wächst. Sagen wir, sie muß als Füllstand mindestens 40% haben, aber weniger als 80%. Sobald sie 80% erreicht, muß sie ihre Größe verdoppeln.

Problem:
Ein Einfüge-Lösch-Pendler könnte immer erzwingen, daß sie sich verdoppelt und halbiert. Das kann verhindert werden, indem bei Vergrößerung oder Verkleinerung die alte Table nicht gelöscht wird, sondern auch mitgeführt wird. Einfüge-Lösch-Pendeln würde nur zu schnellem Hastable-Wechsel führen. Es werden immer zwei Hashtables geführt werden. Echtes Wachsen erreicht man nur, wenn man tatsächlich die Datenmenge verdoppelt. Damit kommen wir amortiesiert wieder auf O(1).

Problem:
EINE der Listen könnte viel zu lang werden. Dann würde das Ziehen auch lange dauern. Angedachte Lösung: Langlisten führen auch zu Wachstum, und zwar mit nachvollziehbaren Regeln. Zum Beispiel einfach: Keine Liste darf mehr als 7 Elemente haben. Falls doch, wird auf die größere Hashtable geschaltet. Das habe ich noch nicht vollständig durchdacht.

Sackgasse:
Vielleicht einen kleinen Umbau machen: Wir wissen ja, wieviele Listen wie lang sind.
Sagen wir mal

Länge Anzahl (Produkt) (laufendeSummeDerProdukte)
0     50     0         0
1     150    150       150
2     40     80        230
3     10     30        260
4     0      0         260
5     0      0         260
6     2      12        272

Dann kann mit "Wo finde ich rand()%272" eine Listenlänge gewählt werden, und in der Listenlänge mit einem rand() die richtige Liste und dadrin mit einem rand() das Element. Die Ziehung würde sicher terminieren. Aber "in der Listenlänge mit einem rand() die richtige Liste" schaffe ich ja nicht, das ist nämlich das Ausgangsproblem.

Aber mein Gefühl sagt mir, daß Du O(log(n)) für einen Indexzugriff zahlen solltest.
Verabschieden wir uns mal von den Unwägbarkeiten oben und basteln einen höhenbalancierten deterministischen Baum. Falls das geht. Ach, ich werde müde. Der muß ja gar nicht deterministisch sein! Bauen wir einen schnellen höhenbalancierten Baum. Wir führen einfach in jedem Knoten mit, wieviele Blätter insgesamt unter ihm hängen. Das sind die von Dir erlaubten kleinen Zusatzkosten für Löschen und Einfügen, die Knoten bis zur Wurzel fangen einen zusätzlichen Schreibzugriff, es bleibt aber bei O(log(n)). Und mit den Zahlen kann man Indexzugriffe in O(log(n)) machen. Und mit den Zahlen kann man garantieren, daß der Baum balanciert bleibt.

ipsec

volkard schrieb:

advance(x) klingt nach Durchhangeln mit x Schritten.
rearrange() klingt gleich nach n Schritten, wenn's mal reicht.
rearrange() muß immer nach EInfügung oder Lsöchung aufgerufen werden, weil die nachvollziehbare Zufallsziehung nicht von der EInfüge-Reihenfolge abhängen darf.

Stimmt, rearrange ist für den Determinismus nötig. Aber advance braucht bei jeder Ziehung O(x) , wobei bei gleichverteilter Ziehung durchschnittlich x = n/2 , während rearrange einmalig nach jedem Einfügen oder Löschen O(n) braucht.
D.h. schon nach 2 Ziehungen ohne dazwischenliegendes Einfügen oder Löschen ist rearrange gleich schnell (wenn ganz grob betrachtet Elementkopierkosten = Iteratorinkrementkosten), bei vielen Ziehungen auf den gleichen Elementen sollte der Multi-Index-Container schneller sein, da der O(1) -Zugriff die einmaligen O(n) -Kosten ausgleicht. Nun weiß ich aber natürlich nicht, wie viele zufällige Elemente SeppJ braucht.

Deine Lösung mit den Hah-Listen klingt auch sehr interessant, allerdings könnte ich mir vorstellen, dass im Endeffekt der Verwaltungsoverhead zu groß wird. Schlussendlich wird man wohl nur messen können, was denn tatsächlich das schnellste ist.

SeppJ

Als Information: Der indizierte Zugriff, Löschen und Einfügen finden ungefähr im Verhältnis 1:1:1 statt. Die Gesamtzahl der Einträge liegt zwischen ein paar hundert bis hin zu einigen Zehntausend. Ist auf heutigen Rechnern natürlich Pfennigfuchserei, wegen eines 10000 advances eines Setiterators eine andere Datenstruktur zu suchen, aber ich mag's eben perfekt. Die Vorschläge finde ich gut, heute Nachmittag schaue ich mir das mal näher an, ob und wie sie genua helfen können.