Omzetten integer identificatiemiddelen pointers

stemmen
1

Ik heb ID waarden van het type unsigned int. Ik moet een ID Kaart met een pointer in constante tijd .


Key Distribution:

ID is een waarde in het traject van 0 tot uint_max hebben. De meeste van de sleutels zullen worden geclusterd in één groep, maar er zullen uitschieters.


Implementatie:

  • Ik dacht na over het gebruik van de C ++ ext hash_map dingen, maar ik heb gehoord dat hun prestaties niet te groot is wanneer toetsen hebben een enorm potentieel bereik.

  • Ik heb ook gedacht aan het gebruik van een of andere vorm van geketend lookup (gelijk aan recursief onderverdelen van het bereik in C chucks). Als er geen sleutels in een bereik valt, wordt dat bereik wijzen op NULL.

    N = Key Range

    0 (verdeeld in C = 16, dus 16 stuks) = [0, N / 16) [N / 16, 2 * (N / 16)), ...

    1 (verdeeld in C = 16, dus 16 * 16 stuks) = ...


Heeft iemand anders ideeën over hoe dit in kaart brengen efficiënter kunnen worden geïmplementeerd?

Bijwerken:

Door constante, ik bedoelde alleen elke toets lookup wordt niet significant beïnvloed door de # van de waarden in het item. Ik wilde niet dat het moest een enkele op te zijn.

De vraag is gesteld op 27/08/2009 om 06:11
bron van user
In andere talen...                            


7 antwoorden

stemmen
11

Gebruik een hash kaart ( unordered_map). Dit geeft ~ O (1) look-up tijden. You "gehoord" Het was slecht, maar heb je proberen, testen en te bepalen dat het een probleem? Zo niet, gebruik een hash kaart.

Nadat uw code zo goed als voltooid, profiel is en bepalen of de look-up tijden zijn de belangrijkste oorzaak van de traagheid in uw programma. De kans is groot, zal het niet zijn.

antwoordde op 27/08/2009 om 06:14
bron van user

stemmen
3

Als je een boom gebaseerde oplossing willen en uw ids zijn in het bereik {0..n-1} dan kunt u een zeer koele datastructuur genaamd gebruik van Emde Boas boom . Hiermee worden alle handelingen op in O (log log n) en gebruik O (n) space.

antwoordde op 27/08/2009 om 06:35
bron van user

stemmen
1

Hoeveel items zijn om in zo'n een kaart en hoe vaak is het veranderd?

Als alle waarden passen in de cache van de processor, dan is een std::vector<std::pair<unsigned int,T*>>met voorgesorteerd waarden en binary search snelste zou zijn, ondanks de toegang dat O (N).

antwoordde op 27/08/2009 om 10:40
bron van user

stemmen
1

Als GMan suggereert een unordered_map is waarschijnlijk een goede oplossing. Als u zich zorgen over een groot aantal botsingen in deze hash kaart zijn, gebruik dan een hash-functie die het clusteren van uw gegevens zal verwijderen. Bijvoorbeeld, kon u de bytes te wisselen rond.

Een goed punt om op te merken is dat je waarschijnlijk meer tijd debugging zal besteden en blijkt een aangepaste datastructuur dan één die al een goede stamboom heeft.

antwoordde op 27/08/2009 om 06:55
bron van user

stemmen
1

Reserve 4 GB RAM-geheugen voor deze, en gewoon cast uw uint om de aanwijzer. Dat is zeker constante tijd.

antwoordde op 27/08/2009 om 06:20
bron van user

stemmen
1

Als gehele waarden zijn 32 bits breed, dan kan een 64-bits platform hebben, de 32 gigabyte geheugen (8 bytes per 4000000000 pointers), en met een platte array. Dat zal zo dicht als je gaat constant lookup tijd te krijgen.

antwoordde op 27/08/2009 om 06:17
bron van user

stemmen
1

Je gaat niet om een ​​constante tijd te krijgen.

Ik zou waarschijnlijk gebruik maken van een B + Tree

antwoordde op 27/08/2009 om 06:15
bron van user

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more