Hirdetés

  2. Fórumok
  3. Szoftverfejlesztés
  4. C++ programozás

Új hozzászólás Aktív témák

  • #3036 LordX veterán EQMontoya #3035
    Új Válasz #3036
    Új hozzászólás
    Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra
    Privát üzenet küldése

    LordX

    veterán

    válasz EQMontoya #3035 üzenetére

    Lehet jó falura, de ugyanannyit kell írni (na jó, a függvény/osztálynevek hosszabbak), ha rendesen használsz <random>-ot.

    Map: Nem értek egyet: mivel a map node-okban tárolja az adatot, amiben benne van a kulcs, az érték, és jellemzően 3 pointer (left, right, parent), ezért masszívan több memóriát foglal, mint a vector: Az összes általam ismert 64 bites implementációban 32 byte + sizeof(pair<K,V>) a node méret + allocation overhead. Win x64-en a sizeof 16 bye, tehát 40 byte a blokk, ahol az overhead átlagosan 56 byte (!!), azaz 96 byte. Per node. Ja, és a map-nek kell egy extra node (az end node). Szóval 10 elemhez kell 1056 byte heap memória map-el.

    Vector esetében ez N*sizeof(int) + overhead, ami most 10*4+56 = 96, összesen a 10 elemre. 100 elemre ez 9696 vs 449 byte.

    Szóval ha a cellák több, mint ~9%-át használod ki, akkor a vector nyer map ellen. És még nem is beszéltünk mennyire cache-friendly a vector, és mennyire cache-ellenséges a map; hogy a vektorban indexelsz, nem keresel.

    Azért ha tényleg el kell tárolnod a kulcsot, egy kategóriával szebben áll a map, de még mindig vesztésre áll, nem véletlen van a flat_map a boost-ban (ami gyakorlatilag egy map interfész vector felett).

Új hozzászólás Aktív témák