Map mit festem/begrenztem Memory Pool

dooooomi

n'Abend zusammen,

Ich möchte gerne eine Map-Datenstruktur benutzen, bei der das Einfügen bzw. Löschen von Werten ohne die Allokation von Speicher auf dem Heap möglich ist (-> deterministische Laufzeit). Die maximale Anzahl von Elementen darf dabei allerdings von vornherein begrenzt sein.

Schön wäre es natürlich, wenn std::map ähnlich wie std::vector eine reserve() Funktion hätte, womit mein Problem auf wohl Anhieb gelöst wäre. Da dem aber leider nicht so ist, fallen mir jetzt 2 Alternativen ein:

1. Ich benutze std::map, und schreibe mir einen eigenen Allocator
2. Ich benutze std::tr1::unordered_map, wo man im Konstruktor eine Anzahl "Buckets" festlegen kann

Welche der beiden Varianten würdet ihr vorziehen, wenn das Ziel ist, mit möglichst wenig Aufwand und möglichst wenig Code eine möglichst effiziente Map zu bekommen? Oder gibt es noch eine bessere Lösung?
Die zu speichernden Daten werden eher klein sein, wahrscheinlich nur int -> int o.ä., und ich rechne nicht mit mehr als 100 Einträgen gleichzeitig in der Map. Nur schnell muß das ganze sein...

Danke schonmal für alle Tips...

hustbaer

Ich würde wahrscheinlich ziemlich viel rumprobieren und benchmarken.

pumuckl

kommt ganz drauf an welche Operationen du auf dem Ding ausfuehren moechtest. Eine Moeglichkeit waere z.B. einen std::vector<std::pair<key_type, value_type> > anzulegen und einmal entsprechend viel Speicher zu reserve()n. Das hat allerdings immernoch eine Speicherallokation, also koenntest du auch eine Klasse schreiben, die intern ein simples Array solcher pairs nutzt.

RHBaum

Nur schnell muß das ganze sein...

Das wuerd ich genauer praezisieren ....
Ne map iss ja schon aufs finden von eintraegen nach Key's optimiert.
Willst du das optimieren ?

Aber ne normale map hat meist nen ziemlich generischen algorythmuss dahinter.
Wenn du die daten genauer kennst kannst da mit nem anderen Algorythmis also ner anderen map, vielleicht ner hashmap etc. draufgehen.

Das wenn du hingegen das einfuegen optimieren willst ...
entweder map neuschreiben ^^

oder die stl maps verwenden eigene allokatoren, die man der map im template uebergibt. Diesen allokator kannst du ueberschreiben z.b. dahingehend, das der speicher aus nem statischen Array geholt wird, wo dein allocator der verwalter fuer ist.

Meist sind die allokatoren der stl schon optimiert, heisst die holen bei einer abfrage ned nur den speicher von einem element, sondern gleich bissi mehr, das beim naechsten aufruf nicht gleich wieder der globale Manager fuers new oder malloc bemueht werden muss.

Also richtig viel bei der optimierung wirst da ned rausholen ... aber kleinvieh macht unter umstaenden ja auch sehr viel mist ....

Ciao ...

dooooomi

RHBaum schrieb:

Nur schnell muß das ganze sein...

Das wuerd ich genauer praezisieren ....

Ok, ich versuch's...

Also, prinzipiell müssen alle Werte nach dem Einfügen in die Map nur ein einziges Mal gelesen werden, da sie dabei dann auch gleich wieder entfernt werden.
Die absolute Geschwindigkeit ist dabei eigentlich sogar zweitrangig. Aber der Code muß echtzeitfähig sein, d.h. malloc() und ähnliches ist Tabu. Denn was nützt es mir, wenn das Einfügen 1000 Mal blitzschnell geht, wenn dann beim 1001ten Mal der Pager angeschmissen wird, und erstmal ein paar andere Daten auf die Platte auslagern muß...?

pumuckl schrieb:

kommt ganz drauf an welche Operationen du auf dem Ding ausfuehren moechtest. Eine Moeglichkeit waere z.B. einen std::vector<std::pair<key_type, value_type> > anzulegen und einmal entsprechend viel Speicher zu reserve()n.

Das würde sicherlich gehen, aber ein std::vector ist ja auch nur ein besseres Array, das einfach nicht für's häufige Einfügen/Entfernen von Werten gemacht ist. Oder meint ihr, daß bei so geringen Datenmengen wie in meinem Fall (wie gesagt, int -> int, und davon wahrscheinlich nie mehr als 100 gleichzeitig in der Map) eine so einfache Datenstruktur sogar von Vorteil wäre? Wie skalierbar das Ganze ist kann mir in diesem Fall eigentlich egal sein...

hustbaer

Bei 100 Elementen muss man sich wirklich schon die Frage stellen ob irgendwelche "schlauen" Dinge wie red-black-tree oder hash-map etwas bringen.

Für eine erste Abschätzung würde ich sowas in der Art verwenden:

#include <map>
#include <vector>
#include <iostream>
#include <windows.h>

struct with_vec
{
	typedef std::pair<int, int> my_pair;
	std::vector<my_pair> m_vec;

	void insert(int k, int v)
	{
		if (!m_vec.empty())
		{
			my_pair* b = &m_vec[0];
			my_pair* e = b + m_vec.size();

			for (; b != e; b++)
			{
				if (b->first == k)
				{
					b->second = v;
					return;
				}
			}
		}

		m_vec.push_back(my_pair(k, v));
	}

	size_t size() const
	{
		return m_vec.size();
	}

	int lookup(int k) const
	{
		if (!m_vec.empty())
		{
			my_pair const* b = &m_vec[0];
			my_pair const* e = b + m_vec.size();

			for (; b != e; b++)
			{
				if (b->first == k)
					return b->second;
			}
		}

		return 0;
	}
};

struct with_map
{
	std::map<int, int> m_map;

	void insert(int k, int v)
	{
		m_map[k] = v;
	}

	size_t size() const
	{
		return m_map.size();
	}

	int lookup(int k) const
	{
		std::map<int, int>::const_iterator it = m_map.find(k);
		if (it != m_map.end())
			return it->second;
		else
			return 0;
	}
};

template <class T> struct benchmark
{
	T m_coll;

	void go(int s1, int s2, size_t element_count)
	{
		// insert
		srand(s1);
		while (m_coll.size() < element_count)
			m_coll.insert(rand() % (element_count * 2), rand());

		srand(s2);

		LARGE_INTEGER frequency;
		LARGE_INTEGER t0;
		LARGE_INTEGER t1;

		::QueryPerformanceFrequency(&frequency);
		::QueryPerformanceCounter(&t0);

		// lookup
		int accu = 0;
		for (size_t i = 0; i < 100*1000; i++)
		{
			accu += m_coll.lookup(rand() % (element_count * 2));
		}

		::QueryPerformanceCounter(&t1);

		LONGLONG t = t1.QuadPart - t0.QuadPart;

		std::cout << "time: " << ((t * 1000 * 1000) / frequency.QuadPart) << " usec\n";
		std::cout << "result: " << accu << "\n";
	}
};

int main() 
{
	int s1 = GetTickCount();
	int s2 = s1 + 1000;

	for (size_t loops = 0; loops < 3; loops++)
	{
		std::cout << "---------------------------------------------\n";
		benchmark<with_vec> b_vec;
		benchmark<with_map> b_map;

		std::cout << "with vector:\n";
		b_vec.go(s1, s2, 100);

		std::cout << "with map:\n";
		b_map.go(s1, s2, 100);
	}
}

Gemessen wird nur Lookup, da das Einfügen ja bei der map new verwendet.

Bei mir ist die vector Variante bis ~25 Elemente schneller, danach die map Variante. Bei 100 Elementen braucht die vector Variante ca. 140% der Zeit wie die map Variante, sollte also vollkommen egal sein.

Bei 200 Elementen: ~200%
Bei 500 Elementen: ~360%
Bei 1000 Elementen: ~620%

etc.

Für den unsortierten vector spricht IMO dass es eine sehr einfache Lösung ist die sehr einfach richtig hinzubekommen ist, und sehr einfach so gemacht werden kann dass bis zu einer bestimmten Anzahl an Elementen kein Speicher dynamisch angefordert werden muss. Noch dazu braucht sie weniger Speicher, und weniger Code, was auch ein Vorteil sein kann.

p.S.: das rausnehmen der Elemente hab' ich nicht implementiert, sonst würde der Loop für die Benchmark sehr schnell die "map" leer machen. Ist beim Vector allerdings auch kein Problem, du tauscht einfach das zu entfernende Element mit dem letzten und entfernst dann das letzte. Billiger gehts nicht

p.p.S.: das Ergebnis spiegelt natürlich nicht das worst-case Szenario wider (was ja für realtime wichtig wäre). Das sollte sich aber sehr gut abschätzen lassen indem man die Laufzeit der vector Variante verdoppelt. Bei der map Variante sollte sich nix ändern. Bei 100 Elementen wären wir dann also bei 280% (vector relativ zu map). IMO immer noch nicht tragisch, aber das musst du wissen.

RHBaum

Also, prinzipiell müssen alle Werte nach dem Einfügen in die Map nur ein einziges Mal gelesen werden, da sie dabei dann auch gleich wieder entfernt werden.

d.h. Du willst daten nur kurz puffern und dabei sortieren ? Hast du die zeitpunkte des einfuegens und des abrufens in der Hand ?

Wie greifst du dann auf die daten zu, einmalig ? Ich denk du gehst einmal mit einem iterator drueber, dann wirfst sie weg ?
Dazu brauechtest du definitiv keine map !

Glaub es ist fast immer "effektiver" einmal ein array zu sortieren, als X mal beim einfuegen die lookups zu machen, fuer die richtige posi in der map.

Ciao ...

dooooomi

RHBaum schrieb:

Also, prinzipiell müssen alle Werte nach dem Einfügen in die Map nur ein einziges Mal gelesen werden, da sie dabei dann auch gleich wieder entfernt werden.

d.h. Du willst daten nur kurz puffern und dabei sortieren ? Hast du die zeitpunkte des einfuegens und des abrufens in der Hand ?

Wie greifst du dann auf die daten zu, einmalig ? Ich denk du gehst einmal mit einem iterator drueber, dann wirfst sie weg ?
Dazu brauechtest du definitiv keine map !

Glaub es ist fast immer "effektiver" einmal ein array zu sortieren, als X mal beim einfuegen die lookups zu machen, fuer die richtige posi in der map.

Ich glaube da hatte ich mich etwas unklar ausgedrückt. Sortiert werden muß gar nichts, die Reihenfolge der Werte in der Map spielt für mich keine Rolle. Von daher muß es ja auch keine std::map sein, sondern std::hash_map oder std::tr1::unordered_map würden's auch tun.

Abgerufen/entfernt werden die Werte immer einzeln. Sowohl das Einfügen als auch das Entfernen geschieht direkt als Reaktion auf Benutzereingaben. Wann das passiert, und wie lange ein einzelner Wert gespeichert bleiben muß, da habe ich keine Kontrolle drüber.

So, mal gucken was Hustbaers Code bei mir für Ergebnisse ausspuckt...

dooooomi

hustbaer schrieb:

Gemessen wird nur Lookup, da das Einfügen ja bei der map new verwendet.

Bei mir ist die vector Variante bis ~25 Elemente schneller, danach die map Variante. Bei 100 Elementen braucht die vector Variante ca. 140% der Zeit wie die map Variante, sollte also vollkommen egal sein.

Bei 200 Elementen: ~200%
Bei 500 Elementen: ~360%
Bei 1000 Elementen: ~620%

Jo, das entspricht auch ungefähr den Werten, die ich hier gemessen habe. Wobei sich die Map aber auch bei einer sehr geringen Anzahl von Elementen nicht vor dem Vector verstecken braucht. Viel tun die sich da nicht.

Ich habe dann auch einmal std::tr1::unordered_map mit in den Benchmark reingenommen. Das scheint noch die beste Alternative zum Vector zu sein, wenn es darum geht, Speicherallokationen zu vermeiden (da man ähnlich wie beim Vector Speicher vorreservieren kann).
Die unordered_map (die einen Hashtable verwendet) ist, egal mit wieviel Elementen, nochmal ein bißchen schneller als map. Interessant wird es vor allem dann, wenn ich den Benchmark so verändere, daß, wie in meinem Anwendungsfall, lookup() nur für tatsächlich vorhandene Schlüssel aufgerufen wird. Davon profitieren Vector und unordered_map recht deutlich, map hingegen nicht...

Lange Rede, kurzer Sinn, ich werde das Ganze jetzt erstmal mit der unordered_map implementieren, ich glaube viel kann ich damit nicht falsch machen