Forum » Programiranje » [C] cache
[C] cache
misek ::
V eni svoji kodo bi potreboval cache za shranjevanje večje količine IPv4 naslovov in pripadajočega imena. Zadetke v cacheu bi iskal ali z IP naslovom ali z imenom. Cache mora biti čimbolj efektiven po možnosti brez dinamične alokacije pomnilnika (ali pa vsaj čim manj).
Ima kdo kakšen predlog, kako se naj tega lotim? Kakšni primeri kode morda?
Ima kdo kakšen predlog, kako se naj tega lotim? Kakšni primeri kode morda?
Brane2 ::
Jaz bi delal z dinamično alokacijo, vendar na večje število strani hkrati- recimo po 1024 strani = 4MB.
Poleg tega bi uporabil kako hash funkcijo z recimo 65536 bini ali kaj podobnega.
Poleg tega bi uporabil kako hash funkcijo z recimo 65536 bini ali kaj podobnega.
On the journey of life, I chose the psycho path.
BigWhale ::
Poglej ce lahko uporabis memcached.
Ce noces dinamicne alokacije pomnilnika in ce te skrbi memory management, potem je edini nacin, da to izvedes tako, da cim bolje ocenis koliko prostora bos utegnil potreboval, to pomnozis z 2, dodas se malo rezerve in si dober za nekaj casa. :)
IPje potem tako ali tako shranjujes kot 32 bitno stevilko, za imena tako kot je Brane predlagal izberi neko hash funkcijo. MD5 je verjetno ze overkill. Verjetno rabis samo kontrolo in te razprsenost hasha niti ne zanima, tako da je lahko ze kaka preprosta home-brew funkcija, ki je hitrejsa od MD5 ze povsem zadovoljiva.
Ce noces dinamicne alokacije pomnilnika in ce te skrbi memory management, potem je edini nacin, da to izvedes tako, da cim bolje ocenis koliko prostora bos utegnil potreboval, to pomnozis z 2, dodas se malo rezerve in si dober za nekaj casa. :)
IPje potem tako ali tako shranjujes kot 32 bitno stevilko, za imena tako kot je Brane predlagal izberi neko hash funkcijo. MD5 je verjetno ze overkill. Verjetno rabis samo kontrolo in te razprsenost hasha niti ne zanima, tako da je lahko ze kaka preprosta home-brew funkcija, ki je hitrejsa od MD5 ze povsem zadovoljiva.
fiction ::
Za shranjevanje IP-jev bi uporabil neke vrste patricia trie. V listu bi potem recimo hranil referenco na neko ime.
Za lookup v obratno smer bi potreboval razprseno tabelo, kjer bi bil kljuc ime. Odvisno od programskega jezika, ampak vcasih lahko vzames kar hash od stringa. Sicer bi izracunal hash kot XOR med posameznimi crkami (MOD velikost tabele). Velikost je ponavadi prastevilo. Kriptografska hash funckija je res overkill. Moras pa vedeti da v obeh primerih lahko pride do collisiona (torej da bos za dva razlicna stringa dobil isti hash in poskusal tisto stlaciti v isti element tabele). Najlazje to lahko resis tako, da je element tabele kar povezan seznam imen vseh imen z istim hashom in potem samo pogledas kateri element je res tisti pravi.
Za lookup v obratno smer bi potreboval razprseno tabelo, kjer bi bil kljuc ime. Odvisno od programskega jezika, ampak vcasih lahko vzames kar hash od stringa. Sicer bi izracunal hash kot XOR med posameznimi crkami (MOD velikost tabele). Velikost je ponavadi prastevilo. Kriptografska hash funckija je res overkill. Moras pa vedeti da v obeh primerih lahko pride do collisiona (torej da bos za dva razlicna stringa dobil isti hash in poskusal tisto stlaciti v isti element tabele). Najlazje to lahko resis tako, da je element tabele kar povezan seznam imen vseh imen z istim hashom in potem samo pogledas kateri element je res tisti pravi.
Vredno ogleda ...
| Tema | Ogledi | Zadnje sporočilo | |
|---|---|---|---|
| Tema | Ogledi | Zadnje sporočilo | |
| » | Ram kot shranjevalni prostorOddelek: Strojna oprema | 3944 (3344) | ABX |
| » | C# HashSet<T>, HashTable kako deluje iskanje v ozadju? a lahko faila?Oddelek: Programiranje | 1552 (1333) | detroit |
| » | Program v COddelek: Programiranje | 1940 (1779) | darkkk |
| » | int to string v c++Oddelek: Programiranje | 2341 (2069) | OwcA |
| » | Pointer-ji v C-juOddelek: Programiranje | 1785 (1483) | rokpok |