Funktion zum indexieren von 32Bit Werten

BerndD

Hallo,

Ich benötige eine Funktion die sich sicher leicht durch einen STL-Container oder ähnliches implementieren lässt. Leider bin ich aber in C++ nicht so fit, das ich ohne weiteres selbst drauf komme:

Die Klasse erhält einen 32 Wert (z.B. einen Zeiger) und liefert dafür eine fortlaufende Nummer (den Index von 1 aufwärts). Wenn ein Wert erneut übergeben wird, muss der selbe Indexwert wie beim vorhergehenden Aufruf zurückgeliefert werden. Ist es ein neuer Wert wird die nächst freie Nummer zurückgegeben. Das ganze soll möglichst schnell für mindestens 10000 Werten funktionieren. Für die Optimierung hilfreich ist, dass keine "Löschen"-Operation nötig ist. Also einfach nur eine "Einfügen"-Operation die den Index liefert.

Wie würdet ihr das implementieren? Sicher nicht "from scratch" - oder?

Hallo,

meinst Du sowas? Geht sicher auch noch eleganter.

int getIndex(int value)
{
 static index=0;
 static std::map<int,int> indexTable;
 std::map<int,int>::iterator i=indexTable.find(value);
 if (i!=indexTable.end()) return (*i);
 index++;
 indexTable[value]=index;
 return index;
}

Ist aber ungetestet.

DJohn

Ne Hashmap anstatt der map ist noch schneller

BerndD

Danke DJohn! Gleich eine fertige Funktion geliefert zu bekommen ist super nett von dir. Habe ein kleines Testprogramm daraus gemacht. Vielleicht hilft es ja noch jemanden. Für 1Mio. Aufrufe (+ Werte erzeugen) braucht mein AMD3800-PC 5,3 Sekunden. Denke das ist schon ganz schön hastig.

walöm Tipp hashmap konnte ich nicht finden. Scheint nicht zur STL zu gehören.

#include "stdafx.h"
#include <time.h> // für Zeitmessung
#include <map>
#include <iostream>
using namespace std;

int getIndex(int value)
{
 static int index=0;
 static std::map<int,int> indexTable;
 std::map<int,int>::iterator i=indexTable.find(value);
 if (i!=indexTable.end()) return (i->second);
 index++;
 indexTable[value]=index;
 return index;
}

int _tmain(int argc, _TCHAR* argv[])
{
    int RANGE_MIN = 0;
    int RANGE_MAX = 1000;
	double t0, t1;
	srand(42);
	t0 = clock();
	for (int i=0; i<1000000; i++) {
      int value = (((double) rand() / (double) RAND_MAX) * RANGE_MAX + RANGE_MIN);
      getIndex(value);
	}	  
    t1 = (clock()-t0) / CLOCKS_PER_SEC;
    cout << "  time = " << t1 << " sec." << endl;

	return 0;
}

eigentlich brauchst du nur ein Array und ne Hashfunktion die deinen Großen Wert auf was kleineres bringt. Der kleinere Wert ist dann der Arrayindex. Im Array speicherst du dann jeweils eine map oder list mit allen Werten die diesen Hashwert (Arrayindex) haben.

BerndD

Wenn ich das selber machen würde, würde ich ganz auf höher integrierte Bestandteile verzichten. Aber durch DJohn@work wurde meine Vermutung bestätigt, dass es mit den richtigen STL-Container schon sehr gut geht. Ich habe bei der Suche nach dem von dir vorgeschlagenen hashmap ein interessanten Link gefunden: http://code.google.com/p/google-sparsehash/

Bei Hash-Algorithmen ist ja das Problem, das man ein guten Kompromiss für die Hash-Größe finden muss. Wählt man ihn zu groß, wird viel Speicher verschwendet. Wählt man ihn zu klein kommt es zu oft zu Kollisionen, was viel Rechenzeit verbraucht.

Selbst wenn ich in obigen Programm den Zufallszahlenbereich auf 1 Mio. setze, bleibt die Ausführungszeit unter 8 Sekunden. Der Map-Container skaliert also ganz gut. Solange alles im Speicher gehalten werden kann, ist die binäre Suche sowieso in der Geschwindigkeit nicht zu toppen (maximal 20 Vergleiche bei 1.Mio Einträge). Der eigentliche Zeitverbrauch liegt offensichtlich nicht bei der Suche, sondern beim Einfügen, also der Speicherverwaltung.

Hätte richtig Lust auf eine kleine Wette, das es nicht möglich ist bei vergleichbaren Speicherverbrauch die obige Ausführungsgeschwindigkeit zu halbieren ;).