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

• #3036 LordX veterán EQMontoya #3035

  Új Válasz 2015-12-09 22:02:19 #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