Zobrazit příspěvky
Tato sekce Vám umožňuje zobrazit všechny příspěvky tohoto uživatele. Prosím uvědomte si, že můžete vidět příspěvky pouze z oblastí Vám přístupných.
Stale to neresi procesory kde je mul taktove "moc drahy".Násobení lze udělat jednoduše pomocí bitových posunů a sčítání, např. 131 * X je 128 * X + 2 * X + 1 * X. Tohle funguje jen pro unsigned aritmetiku, ale to nevadí, protože si můžeš vybrat, ze které strany budeš tu interpolaci dělat.
Ale tohle já přesně dělám.Cuckoo filtr je sofistikovanější, používá dvě různé hashovací funkce, takže každá položka se může vyskytovat na dvou různých pozicích, proto taky potřebuje dva lookupy. To umožňuje položky během kostrukce filtru (zřetězeně) přesouvat v případě kolize, takže se dá prakticky dosáhnout až 95% naplnění filtru. Opravdu jsou data relativně malá, tady je kalkulačka pro bloom filter, pro 5 milionů prvků ve filtru a pravděpodobnost 1% false positive je velikost dat 5.7 MB, což typicky vejde celé do L3 cache. Cuckoo filter je prostorově ještě úspornější, pro něj jsem ale online kalkulačku nenašel.
Vezmu kus čísla a zjistím, jestli pro něj je v tabulce nějaká hodnota, používám jeho fixní část jako index.
Pokud daný index není NULL, pak teprve začnu provádět porovnání.
To ano, ale pro každé to vstupní číslo (slovník si předpočítám) musíš spočítat hash, jestli penalizace při výpočtu hashe nebude horší než prostý formát.Záleží na tom, co je to za data. Pokud jsou čísla víceméně náhodná, tak hash počítat vůbec nemusíš, jako hash poslouží část toho 512-bitového čísla. Pokud data moc náhodná nejsou, dá se hash spočítat třeba jako XOR částí čísla, to je rychlá operace a pro účely filtrování je to dostatečné.
Ahoj, divoká myšlenka:Ano, takové algoritmy existují, jeden z nich se jmenuje Cuckoo filter
- čí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.
. Nemá cenu znovu vymýšlet kolo, lepší je použít ověřená řešení.
Asi mi nezůstane nic jiného, než pokusně zjistit, jaká je penalizace při zápisu mimo dostupnou stránku.Proč řešíš takové složitosti, jaký zápis, k čemu? Cuckoo filtr jsou dva lookupy, které můžeš prefetchovat, ale asi to ani nebude potřeba, protože celý filtr vejde do cache. Pokud máš náhodná data, tak to vyřeší 99+% případů. Nějaké UDP pakety a zbytečné zápisy jsou oproti tomu asi tak milionkrát pomalejší.
Stejně to nejspíš dopadne s tím odesíláním dat pryč, kolik takový UDP datagram sežere výkonu CPU netuším...
B-Tree vskutku není seznam, B-Tree je strom. Listy toho stromu jsou zaindexované hodnoty. Teprve od té hodnoty vede odkaz na seznam záznamů, kde se ta hodnota vyskytuje.
a jaký jazyk byste mu doporučili?Rust. Pro začátečníka je náročný na učení, ale to C++ taky. Výkon srovnatelný s C++. Spousta chyb, které se v C++ projeví až za běhu, odchytí Rust už při překladu.
-Wzero-as-null-pointer-constantKdyž dostane pointer a hodnotu, tak ti vynadá kompilátor.Nikoli.
Kdybyste si nalistoval diskusi asi tak pět stran zpět, psal jsem tam to samé :-) Teda až na to, že nesouhlasím, že pravidla jsou složitá – jsou naopak velmi jednoduchá, když se porovnávají primitivní typy, porovnávají se hodnoty (nic jiného porovnat nejde), když se porovnávají objektové typy, porovnávají se reference (protože objekt je pro Javu blackbox, neví nic o tom, jestli existuje něco jako hodnota toho objektu).Ne ty tady od začátku píšeš, jak je porovnání v Javě udělané skvěle, jednoduše, každý to hned pochopí a chyby se v tom nedělají. To je prostě demagogie, obhajuješ špatný design, pravděpodobně z neznalosti.
Root.cz (www.root.cz), informace nejen ze světa Linuxu. ISSN 1212-8309
Copyright © 1998 – 2023 Internet Info, s.r.o. Všechna práva vyhrazena. Powered by Linux.