set oder map?

hi

Welcher Container hat den schnelleren Zugriff mit find()
Ein Set oder eine Map?
Die Elemente sind structs, die ich per ID und einer Vergleichsfunktion vergleichen kann.

Danke im voraus

Maxi

imho haben beide O(n) = log n
von daher dürften beide gleich schnell sein.
Map verwendest du, wenn du einem Schlüssel einem Wert zuordnenn willst, ansonsten set, wenn du nur die Schlüssel speichern willst.

Danke

Ich brauch einfach schnelles find(), anhand der ID hab ich ja schon nen Schlüssel im struct.

struct Weapon
    {
        unsigned int id;
        unsigned short type;
        unsigned short level;
        unsigned short strength;
        unsigned short speed;
        unsigned short weight;
        unsigned short range;
        unsigned int price;
        std::string name;

        bool operator<( const Weapon& other )
        {
            return id < other.id;
        }
    };

std::set<Weapon> weapons;

find soll dann mit einer Referenz einer Weapon struct aus dem Container aufgerufen werden.

void fight( const Weapon& val )
{
    weapon = *(weapons.find( val ) );

Macht das so Sinn?
Gibts was effektiveres in dem Fall?

Fedaykin

am effektivsten kommst du wohl mit einer hash_map, ich weiß nicht ob map das gleiche ist, bei einer guten hash funktion hast du im Mittel O(1) zugriffszeit, sofern nicht zuviele schlüssel doppelt vergeben werden. (Im worst case aber O(n) *gg* aber das nur bei einer unglaublich miesen hashfunktion )

hustbaer

Suchzeit... set vs. map wird ziemlich gleich sein, hash_set vs. hash_map wird genauso ziemlich gleich sein.

Ob "hash oder nicht hash" hängt denke ich davon ab:

ob man die Einträge sortiert braucht (dann wohl eher set/map) und
ob es einen stört ggf. ein wenig Speicher zu verschwenden und
ob man einen schnell erzeugbaren, schnell vergleichbaren und gut verteilten Hashcode für die Elemente berechnen kann

In deinem Fall würde ich vermutlich ein hash_set nehmen, direkt mit "id" als Hashvalue -- es sei denn eben du musst nach ID sortiert auf die Elemente zugreifen.

Nein
Nein
Tja, wie mach ich das?

Also meine ID ist 4-stellig.
1. Ziffer: Art des Items (Waffe, Rüstung ...)
2. Ziffer: Variante (Schwert, Axt ... bzw. Helm, Brustpanzer ...)
3. Ziffer: Level ( 1, 2 ...)
4. Ziffer: noch unbenutzt

Dh. es ist relativ einfach von Ziffer zu Ziffer, wie in nem Baum runter zu gehen.

1---0---1---1  --> Schwert
 \   \--2---1  --> Langschwert
  \   \-3---1  --> Claymore
   -1---1---1  --> Axt
     \--2---1  --> Breitaxt
      \-3---1  --> Kriegeraxt

2---0---1---1  --> etc...
 \   \--2---1
  \   \-3---1
   -1---1---1
     \--2---1
      \-3---1

Kann man das als Hash verwenden?

hustbaer

Ich schätze das kann man als Hash verwenden, ja.

Ok, letzte dumme Frage (hoff ich:))
mit hash_set meinst du tr1::unordered_set? (im gcc 4.1.2 mit dabei)

Wenn ja, gibt es dazu Beispiele zur Verwendung?
Wenn nein, was meinst du dann?

hustbaer

Keine Ahnung wie TR1 das nennt, die ganzen Compiler die das als Extension anbieten nennen das hash_set. Zumindest die die ich kenne. Ich *schätze* mal stark dein unordered_set wird mein hash_set sein

Bei MSVC lebt das Teil in stdext::, bei GNU in __gnu_cxx::, bei der Dinkumware gleich in std::. Die SGI und STLport bieten die Klasse auch an, keine Ahnung wie dort der Namespace heisst.

Doku dazu findest du z.B. hier:
http://msdn2.microsoft.com/en-us/library/00htc7h2(VS.80).aspx
http://www.sgi.com/tech/stl/hash_set.html

Artchi

Im TR1 heißen die Hashcontainer std::tr1::unordered_*.

RHBaum

Aehm, warum heisst die hashmap hashmap?

Unter hash versteh ich ich: nen kleinerer wert (hash) der aus einer groesseren Datenstruktur generiert wird aber trotzdem zu einem hohen prozentsatz eindeutig fuer den grossen wert ist.

Damit machen hashmaps fuer mich nur bei groesseren Elementen Sinn ???

wenn ich nach ner ID sortiere (32 bit integer) hab ich eh schon die groesse mit der der prozessor am schnellsten zurande kommt. du wuerdest sogar schneller fahren wenn du kleinere IDs auf 32 bit "aufbohrst" ...

ob man die Einträge sortiert braucht (dann wohl eher set/map)

wenn ich auf was schnell zugreifen will, brauch ich den Key (hash) soweiso in sortierter folge, anders gehts ned, also irgendwas wird jeder container mit O(n) = log n sortiert ablegen.

@Eldoran

wenn deine ID das ist was der Name vorgibt (eineindeutig fuer jedes element) und die ID wirklich dein suchkriterium sein sollt, brauchst du den ganzen hash geroedel sowieso nicht.

map oder set ist performance technisch ned ganz egal ...
beim set werden die structuren gegeneinander verglichen, mit ner operatorueberladung koenntest das ganz einfach auf die ID in der strukt mappen, so dass nur nach der id sortiert wird, aber, beim einfuegen wird das ganze set umsortiert, dabei werden elemente des sets ein oder mehrmals kopiert. bei Dir iss das immerhin eine komplexere struct.

bei der map wird hingegen nur der key sortiert und der value referenziert, also nur die IDs wuerden hin und her kopiert werden, waerend der value einmal in den allokator geschrieben wuerde und dann bis zum remove oder nen edit ned mehr angefasst ....

also besser :

typedef std::map<unsigned int, weapon> WeaponMapT; 

WeaponMapT mWeapons; 

// irgendwo nach ner waffe mit der id suchen, irgend ne methode an ner klasse

const WeaponMapT * getWeapon(unsigned int ID) const 
{
    WeaponMapT::const_iterator itfind = mWeapons.find(ID);
    return itfind != mWeapons.end() ? &(*itfind).second : NULL;
}
WeaponMapT * getWeapon(unsigned int ID)
{
    WeaponMapT::iterator itfind = mWeapons.find(ID);
    return itfind != mWeapons.end() ? &(*itfind).second : NULL;
}

Ciao ....

Konrad Rudolph

RHBaum schrieb:

Damit machen hashmaps fuer mich nur bei groesseren Elementen Sinn ???

wenn ich nach ner ID sortiere (32 bit integer) hab ich eh schon die groesse mit der der prozessor am schnellsten zurande kommt. du wuerdest sogar schneller fahren wenn du kleinere IDs auf 32 bit "aufbohrst" ...

Zumindest die letzte Aussage ist ganz schöner Quatsch. Denn das würde ja bedeuten, dass Du eine Hash-Tabelle von der Größe 32 Bit brauchst -- also mit 2^32 Feldern. Das ist nicht realistisch. Statttdessen werden generell nur die least significant bits verwendet, um aus einem Hashwert den Index für die Tabelle zu bilden. Daher ergibt es natürlich auch keinen Sinn, kleinere Werte auf 'int'-Größe aufzubohen. Und ich denke Du kannst davon ausgehen, dass die Hashfunktion von Ganzzahlwerten auch nichts weiter machen wird, außer eventuell die Verteilung zu verbessern (falls die Funktion annahmen über die Eingabeverteilung treffen kann, was ja bei Speicherbereichen z.B. durchaus der Fall sein könnte).

Langer Rede kurzer Sinn: Eine Hashtabelle ergibt auch für Ganzzahlwerte bzw. "kleine" Datenstrukturen Sinn.

RHBaum schrieb:

wenn ich auf was schnell zugreifen will, brauch ich den Key (hash) soweiso in sortierter folge, anders gehts ned, also irgendwas wird jeder container mit O(n) = log n sortiert ablegen.

Nach meinen verständnis ist das in einer hash map eben nicht so. klar im schlechtesten fall nicht, aber es wird ja nicht nach einen freien platz gesucht sondern dieser anhand der hashfunktion berechnet erst dann wird ggf gesucht, oder bei einer hashmap mit linked list hinten an die liste dran gehangen. Somit ist bei guter hash funktion die Zugriffszeit im mittel O(1) im normalfall muss er in der map nichts suchen sondern weiß genau. Der Schlüssel "1234" steht an stelle 1234 nur wenn er dort nicht ist wird dann nun gesucht. Also ist ein Hash map im grunde nicht geordnet sondern fest vorgelegt.

hustbaer

RHBaum, ein Hashtable hat die Keys NICHT sortiert.

http://en.wikipedia.org/wiki/Hash_table

Grundlegendste Grundlagen der Informatik. Datenstrukturen, Alter

Artchi

hustbaer schrieb:

RHBaum, ein Hashtable hat die Keys NICHT sortiert.

http://en.wikipedia.org/wiki/Hash_table

Grundlegendste Grundlagen der Informatik. Datenstrukturen, Alter

Hehe, das sollte einem spätestens klar werden, wenn man den Begriff unordered_map liest.

RHBaum

RHBaum, ein Hashtable hat die Keys NICHT sortiert.

aber dafuer der hash, der ja quasi die sortierung ist. Ich meint nur ohne ne sortierung geht gar nix ....

Also in der praxis hab ichs noch nie gebraucht, nen normaler baum war immer schnell genug, bei 32bit IDs.
Ob die Hashmap wirklich performanter waer haengt ja dann auch stark von der verteilung und der Menge der ID's ab ...

wie gesagt in meinem Buch ueber Algos steht das Hashes sich erst bei groesseren Structuren lohnen ... bei kleineren waeren Tree's meist effizenter.

Denn das würde ja bedeuten, dass Du eine Hash-Tabelle von der Größe 32 Bit brauchst -- also mit 2^32 Feldern.

So meint ich das ned ... Ich meint er hat eh ne 32bit als ID, da sollten die lookups im Baum effizient genug sein.
Ich kenn hashes nur aus der DB Welt, und da entschiedet die art des hashes, wie das zeugs arrangiert wird. Das kann nen fest positioniertes array sein, aber auch nen Baum, der auf den hashwert matcht. Wusst ned das bei ner hashmap bei datenstrukturen immer das positionierte array gemeint ist ...

Ciao ...

finix

RHBaum schrieb:

RHBaum, ein Hashtable hat die Keys NICHT sortiert.

aber dafuer der hash, der ja quasi die sortierung ist. Ich meint nur ohne ne sortierung geht gar nix ....

Vielleicht solltest du dir das Kapitel Hashtabelle noch einmal genauer anschauen. :p
Das einzige was "sortiert" ist, ist der Index.

Fedaykin

also was ich wann verwende ist halt sache,

map, etc die man in O(log n) durchsucht wenn es mehr darauf ankommt elemente geordnet zu halten, und es viele elemente werden könnten hash map wenn ich wirklich sehr schnellen zugriff brauche aber die anzahl moderat genug das sich der mehraufwand an speicher auch lohnt den man verbraucht.

hustbaer

RHBaum, der Hash ist nicht sortiert, der "ist" einfach. Weiters wird er (meist per Modulodivision) auf [0-N) runtergebrochen (wobei N die Grösse des Tables ist), wodurch die Ordnung des Hash (die ja schonmal nix mit der Ordnung der Keys zu tun hat) erst zerstört wird. Allgemein kann man sagen dass die Einträge (bzw. Zeiger auf die Einträge) in keiner verwendbaren Ordnung im Hashtable liegen -- nur die Position eines einzelnen Eintrages eignet sich zum schnellen Auffinden.

Weiters muss im Idealfall (und auch im Normalfall, wenn man es richtig implementiert) nicht ein Baum mit 3, 4, 5... Ebenen durchwandert werden, sondern der erste bzw. spätestens zweite Table-Lookup ist meist ein Treffer.

Ob bzw. um wieviel ein Hashtable schneller ist als z.B. ein RB-Tree hängt dann auch noch stark davon ab wie teuer der Vergleich 2er Keys ist. Hat man z.B. Strings als Keys (wo vielleicht vorne noch ein Namespace-Teil dranhängt, so dass viele Strings sich erst weit hinten unterscheiden) dann ist ein Hashtable auch bei ganz wenigen Elementen schon oft deutlich schneller.

Fedaykin

hustbaer schrieb:

Ob bzw. um wieviel ein Hashtable schneller ist als z.B. ein RB-Tree hängt dann auch noch stark davon ab wie teuer der Vergleich 2er Keys ist. Hat man z.B. Strings als Keys (wo vielleicht vorne noch ein Namespace-Teil dranhängt, so dass viele Strings sich erst weit hinten unterscheiden) dann ist ein Hashtable auch bei ganz wenigen Elementen schon oft deutlich schneller.

Das versteh ich nicht, in beiden fällen muss ich vergleichen. Und auch das gleiche. Wo soll man nun bei den vergleichen unterschiede machen? Solange ich schlüssel nicht nur aufgrund ihrer Struktur vergleiche dauert es gleich lang.

Es bleibt halt nur noch das problem, wende ich divide and conquer an, so das ein O(log n) zugriff habe. Oder halt so ein zugriffsverfahren wie bei der hashmap wo ich im grunde direkt in eine zelle greife in der ich vermute das dort das element steht. Aber ich muss im endeffekt immer die beiden schlussel vergleichen.

Aber nochmal zum eigentlichen problem zurück. Bei der sturktur die gespeichert werden soll eignet sich auch ein trie hervorragend. http://en.wikipedia.org/wiki/Trie