schnellster zugriff in map



  • hallo,
    ich habe einen suchbaum, in dem auf jeden knoten
    ca 5000-20000 knoten kommen, wenn ich nun
    den baum durchsuche, muss ich ja jedesmal eine kante
    aussuchen, bisher habe ich das über

    std::map<schluessel,kind_knoten>
    

    wobei schluessel ein size_t ist

    gelöst, gibts da irgendwas schnelleres?

    1. ich werde mal die unordered_map probieren.

    2. der Suchbaum ist eigentlich statisch, bringt es da was
    mit gperf anzufangen, denn wenn der baum steht, kann ich ja
    eine perfekte hash-funktion berechnen lassen und dann benutzen

    ich wäre froh wenn mir jemand hinweise geben könnte, wie man
    das ganze "verschnellern" könnte,
    am besten mit erfahrungen

    der Suchbaum hat nun ca 12.000.000 Knoten und ist die absolute bremse
    in meinem Programm ...

    aber ich will nicht 2 wochen alles durchprobieren, bis mir die beste
    lösung in die hände fällt



  • Ne Hashmap wäre auf jedenfall schneller bei sovielen einträgen. Was ist das für ein Programm, dass du soviel suchen musst?



  • Hi,

    bei dermaßen vielen Elementen bringt glaube ich auch ein perfekter Hash nicht mehr viel. Eventuell lohnt es sich hier aber, ein normales Array zu verwenden, wenn die Schlüssel bei Dir eh numerisch sind. Klar, 2^96 Einträge kannst Du nicht reservieren, aber vielleicht kannst Du ja den Wertebereich entsprechend einschränken? Keine Ahnung. Bei diesen Größenordnungen muss man sich eh schon überlegen, wie man das sinnvoll adressiert. Vielleicht doch häppchenweise aus einer Datei?

    (Ich stehe gerade vor einem ähnlichen Problem und versuche es erst mal mit einer Skipliste, welche in dem von mir verwendeten Framework bereits verfügbar ist.)

    /EDIT: Der erste Satz ist Schrott. Ein perfekter Hash wäre natürlich ideal. Muss man halt erst mal konstruieren; da habe ich keine Erfahrung in diesen Größenordnungen (per Hand, wie Knuth das vorschlägt, geht es jedenfalls nicht mehr ;-)).



  • ich habe viele sequence ereignissen
    x1,x2,x3,x4,x5 ...

    und suche den wert für eine bestimme sequence

    die erste stufe ist noch vollbesetzt, (in dem fall die x1) und
    die habe ich auch als std::vector implementiert,
    dort finde ich also alles noch in O(1)

    für (fast) jedes x1 gäbe es dann eigentlich wieder so einen
    vector für die ereignisse (x1,x2)

    der baum ist aber in der tiefe immer spärlicher besetzt, deshalb kann ich
    den vector ansatz nicht bis in die tiefe durchziehen
    (auch würde das ganze vollbesetzt garnicht mehr in den speicher passen 😮 )

    ich habe mich nun mal in minimale perfekte hash funktionen eingelesen,
    und werde mal versuche etwas in der art zu implementieren

    aber alle papers die ich gefunden habe, sind eher darauf ausgerichtet
    eine hash-funktion für eine sehr grosse schlüsselmenge zu generieren,
    wobei es bei mir ja eher auf schnelle zugriffe ankommt
    ( schnelle evaluierung der funktion)

    ich werde mal berichten, was dabei rausgekommen ist



  • hola treb

    kannst du mal genauere angaben zu deinen daten machen ?

    wie ist so eine sequenz aufgebaut ? also ist das ein int oder so ?
    wie spaerlich wird es in der tiefe ? und wie tief wird es ?
    musst du auch ueberpruefen ob du eine bespimmte sequenz hast oder gibt es nur bestimmte sequenzen die du da dann auf dein ergebnis abfragen musst ?

    die erste stufe ist noch vollbesetzt, (in dem fall die x1) und
    die habe ich auch als std::vector implementiert,
    dort finde ich also alles noch in O(1)

    für (fast) jedes x1 gäbe es dann eigentlich wieder so einen
    vector für die ereignisse (x1,x2)

    wie jetzt ? voll besetzt oder doch nur fast ?

    Meep Meep


Log in to reply