Zobrazit příspěvky
1
Vývoj / Re:C, zápis do pole čísel a zápis mimo cache L1/L2
« kdy: 12. 01. 2020, 22:08:24 »
Ahoj, divoká myšlenka:
- čísla jsou 512-bitová => obor hodnot je obrovský
- slovník má kolem 400 MB, tedy v něm je asi 400/8 = 50M položek
50M je proti 2^512 tak nevýznamné číslo, že určitě půjde obrovské množství dat vytřídit pomocí předpočítaných patternů.
Kdybych to zjednodušil na bajty (8-bitová čísla), a měl slovník pro jednoduchost třeba { 0,1,128 }, tak si můžu pomocí testu (x & 0b01111110) == 0 eliminovat většinu vstupních možností a teprve pro zbytek udělám vyhledání.
Nevím jestli na předpočítání těch optimalizačních testů z obsahu slovníku existují slušné algoritmy, ale vzhledem tomu že (velikost slovníku << počet možných čísel), mohla by taková optimalizace výrazně pomoct.
- čísla jsou 512-bitová => obor hodnot je obrovský
- slovník má kolem 400 MB, tedy v něm je asi 400/8 = 50M položek
50M je proti 2^512 tak nevýznamné číslo, že určitě půjde obrovské množství dat vytřídit pomocí předpočítaných patternů.
Kdybych to zjednodušil na bajty (8-bitová čísla), a měl slovník pro jednoduchost třeba { 0,1,128 }, tak si můžu pomocí testu (x & 0b01111110) == 0 eliminovat většinu vstupních možností a teprve pro zbytek udělám vyhledání.
Nevím jestli na předpočítání těch optimalizačních testů z obsahu slovníku existují slušné algoritmy, ale vzhledem tomu že (velikost slovníku << počet možných čísel), mohla by taková optimalizace výrazně pomoct.
