Érdekes halmaz/algoritmus kérdés
2011-04-21T18:23:57+02:00
2011-04-23T01:29:12+02:00
2022-07-24T16:16:24+02:00
  • A tartalmazás lekérdezés egy moduló művelet, ami egy mai procin hadd ne mondjam milyen gyors.


    A moduló-műveletek lassúak, hacsak nem kettőnek a maradékát képezed. Minden más esetben lassúak. (Más kérdés: Mit értesz lassú alatt.)

    Ez a prímes megoldás nekem nem tetszik. Akkor már inkább bittömb. Mindenesetre érdekes ötlet.
    Mutasd a teljes hozzászólást!
  • Írnék arról egy picit, hogy miért mondtam, hogy a like-nál nem lehet megúszni, hogy elmenként nagyjából 8-byte-ot (vagy amekkora az ojjektumid range) foglaljon.

    Jelöljük R-el a ranget: R féle elem lehet a halmazban
    Jelöljük S-el az elemszámot: S darab elem van benne a hlamazban.

    Intuitíve is lehet látni, hogy mind R és mind S növelése növeli a halmazreprezentációk méretét, akármilyen reprezentációt is válasszunk.

    De meg lehet nézni az információelméleti határokat matematikailag is, és lehet alsó határt mondani, hogy mennyi bit biztosan kell egy bizonyos (R,S) el jellemezhető halmaz tárolásához.

    Nézzük, hogy mi van a szélsőségeknél:
    R=négymilliárd
    S=1

    Ekkor nem nehéz belátni, hogy 32 bit alatt nem ússzuk meg. Ha létezik olyan eset, hogy S=1, és 32 bit kell, akkor elég hamar az lesz az intuíciónk, hogy kevés elemszámnál nagy range-nél kb. az S*log(R) lesz a minimális bitszám

    A másik szélsőség: R=négymilliárd, S= kétmilliárd.
    Ekkor látható, hogy elemenként kb. egy bit kell, vagyis a szükséges bitek száma kb. R.

    Ha valakiket a közbülső határok pontosan érdekelnek, akkor ezt kell tenni:

    (R,S) esetén meg kell nézni, hogy hányféleképpen tudunk kivlasztani R-ből S-et. Ez középiskolai kombinatorika: R alatt az S.
    Ennek kell a log2-jét venni, hogy ehhez minimum hány bit kell:

    log2(R alatt az S) bit alatt nem lehet megúszni a halmazreprezentációt.
    Mutasd a teljes hozzászólást!
  • Elsőkörben képzelj el egy olyan hashtáblát, amelyben egy vödörben csak egy bitet tárolunk. (Ez a k=1-es Bloom filter).

    Cucc bepakoláskor egyszerűen 1-re állítjuk a vödörben a bitet.

    Lekérdezéskor (contains()) megnézzük, hogy mi van a vödörben.

    Ha 0, akkor tutibiztos, hogy elemünk nincs a halmazban.

    Ha 1- akkor viszont lehet, hogy benne van, de az is lehet, hogy valamelyik másik elem állította be oda a bitet...

    A bloom filter tehát nem teljesen korrekt halmazreprezentáció.
    Mire jó a Bloom filter? Pl. bizonoys optimalizációknál jól jön, hogy bizonyos döntéseknél nagyongyorsan és kevés memóriával tudjuk kizárni az esetek nagy részét, és csak a kevés maradék esetben kell egy esetleges számolásintenzívebb branch-re ráugranunk.

    Vagy olyankor is jó, ha nem baj, ha nagyritkán téved a contains művelet. (Monte Carlo algoritmusoknál nem ritka ez sem.)

    Namost persze a tévedés valószínűségét némi memória árán tudjuk csökkenteni: elsőkörben minél nagyobb a hashtábla tömb, annál kisebb esélye lesz a tévedésnek.

    Második körben bevezettek a Bloom Filternek egy 'k' paraméterét:

    k darab hasfüggvénnyel dolgoznak. Elem betevésekor mind a k függvénnyel hashet és vödörindexet számolunk, és mind a k vödörbe egyet pakolunk. k=3-nál 3 vödröt állítunk 1-be.

    Lekérdezésnél akkor eleme valami a halmaznak, ha mind a k vödörben 1 van.

    Ha növeljük a k-t, akkor csökken a tévedés valószínűsége, de gyorsabban telítődik is a hashtábla: végülis a tévedés esélyének csökkentéséhez k-t és a hashtábla méretét párhuzamosan növelni kell.
    Mutasd a teljes hozzászólást!
  • Jó az intuíciód, jó irányból közelíted meg a dolgot (elsősorban az elemszám és a range határozza meg, hogy milyen a jó halmazreprezentáció), de a végkövetkeztetésed nem teljesen pontos.

    Ezt a reprezentációt mint érdekességet említettem meg, tényleg nagyon szűk alkalmazási területe van, ezért mondtam, hogy egzotikus.
    De mégis van egy nagyon szűk (range, elemszám) halmaz, amikor ez a cucc jobb mint bármi más.

    Mondjuk a ranged 1-200
    és mondjuk az elemszámod 0-3.
    Ekkor 32 bites aritmetikával használható a cucc ha jól számolom.
    Az első 200 prím letárolása nem tétel, ha halmazok millióit kell amúgy tárolnod.
    Még egy előnye van a bittömbhöz képest: ez multiset.

    De tényleg annyira szűken használható, hogy életemben egyszer használtam, ott is a multiset tuljadonságot is felhasználva: egy óriási mennyiségű előreleszámolt pókerleosztást használó leosztáselemzőben.

    Facebook likeolásnál nyilván szóba sem jöhet.

    U.i.: A multiset olyan adatstruktúra, ami olyan mint a set, csak a contains egy counter-t ad vissza, a put eggyel növeli a countert, a remove meg eggyel csökkenti a countert. Magyarul egy elem többször is eleme lehet a 'halmaznak'.
    Mutasd a teljes hozzászólást!
  • Elsőre ötletesnek tűnik, de ehhez még fel kell ébrednem
    Mutasd a teljes hozzászólást!
  • "Még egy nagyon érdekes nagyon gyors, kis memóriaigényű egzotikus halmazmegvalósítás"

    tényleg egzotikus, de szerintem ez az egyetlen, ami igaz rá egy sima bittömbbel összevetve. Ha letárolod az első n prímet, akkor rettenetes nagy a memóriaigénye, ha minden alkalommal kiszámolod, akkor meg nagyon lassú.
    Ráadásul nagy pontosságú aritmetika kell hozzá. Gondold meg, az első 32 prím szorzata biztosan nagyobb 2^32-nél (sőt, 2^64-nél is) azaz a processzor aritmetikája nem oldja meg helyből, miközben ugyanezt sima bitshift, or és and műveletekkel kb. 0 idő alatt lefut.
    Szóval olyan kis elemszámra és range-re, ahol ez a módszer esetleg működőképes, ott a sima bitset is az, csak kb. milliószor egyszerűbb és gyorsabb.
    Ha nagyobb a range, akkor meg egyszerűbb és gyorsabb magát a számot letárolni, mert n kisebb, mint az n. prím.
    Mutasd a teljes hozzászólást!
  • A fájlrendszer fedi le ezt a sémát. A saját adatok halmazai és részhalmazai a mappák és almappák a metszetek a megosztások
    Mutasd a teljes hozzászólást!
  • Szerintem sincs kezelhetetlen méretű halmaz userenként, de egy Facebook méretű cégnél a hely és processzoridő spórolás mindig jól jön: kevesebb szerver kell, kevesebb áramot kell fogyasztani. Természetesen egy memóriában lévő hashtábla performanciáját meg sem közelíti amit írtál, (meg nem is írtad le, hogy hogyan tartod karban a fileodat, és hogyan keresel benne.)
    Mutasd a teljes hozzászólást!
  • A Bloom Filterrel az a baj, hogy bizonyos eséllyel van false positive, vagyis valaki nem lájkolt valamit, de a bloom filter azt mondja, hogy igen. Ezért a Bloom filtert általában csak esetszűkítésre használják: A Bloom filter jól megszűri a lehetséges eseteket, de aztán amiket kiköp, azokat még valahogy máshogy egyesével megvizsgálják. Pl. asszem distributed joined queryknél használják helyspórolós volta miatt, hogy jó kevés adatot kelljen küldeni a node-ok között.
    Mutasd a teljes hozzászólást!
  • Akkor már inkább valami adatbázis. Az megoldja a fájlkezelést, indexelést is.
    Mutasd a teljes hozzászólást!
  • Mi van, ha nem egy dimenzióban gondolkozunk.
    Ha jól tudom valaki postol valamit fb-re és mások like-olják.
    Egy user sem fog milliós nagyságrendben postoni és likeolni, maradjunk max ezres, de inkább 100-as nagyságrendben.

    Egy post teljes azonosítója: user | postid
    Ezt megcímezni már egyszerűbb. Ha csak sima fájlokban van, akkor van egy közös regiszter, ami megmondja, hogy egy user postjainak azonosítói melyik fájlban vannak, azon belül meg 100-1000 nagyságrendű elem van, abban már könnyen lehet keresni.

    A like-ot is hasonlóan lehet tárolni, a like-olt cuccnál egy számláló, a like-oló user2-nél meg a bejegyzéshez hasonló user2 | (user|postid) kombó.

    Szerintem itt sehol nincs kezelhetetlen méretű halmaz.
    Mutasd a teljes hozzászólást!
  • Mutasd a teljes hozzászólást!
  • Én attól tenném függővé hogy mennyire sűrűk az adatok. Ha az adott range-en belül viszonylag kevés helyen van elem akkor talán valami b+fa és rendezett tömb kombinációt használnék (mondjuk az is kérdés hogy milyen gyakran változnak az adatok).
    Ha viszonylag sűrű a kitöltöttség akkor mindenképpen bittömb + címfüggvénnyel ellenőrzés. És ezt akár csinálhatod úgy is hogy egyetlen nagy példányod van az összes user adataival és webszolgáltatásokon keresztül kéred le az adatokat.

    Morzel
    Mutasd a teljes hozzászólást!
  • Én is csak annyit mondhatok, hogy hogyan csinálnám.

    A likeoldandó objektumokat valahogy nyilvántartanám, ennek a részleteitől el lehet tekinteni szvsz., annyi a lényeg, hogy 8 byteos id-je lenne az ojjektumoknak: a 8 byteos id tér soha nem fogy ki.

    Mondjuk egy user-facing szerveren 10000 user adatait tartanám nyilván.

    Minden userhez lenne egy halmaz: 8 byte-os ojjektumid - k halmaza.

    Az ojjektumid-k halmazánál lehet használni egy viszonylag helyspórolós hashtábla variánst: nyílt címzéses ütközésfeloldásos hash táblát.

    A hagyományos hashtábla a láncolásos ütközésfeloldásos hash tábla, amikor a vödrökben láncolt listákat tárolunk.

    A nyílt címzésnél egyszerűen csak ojjektumid-ket tárolunk a vödrökben. Ha betevésnél a vödör foglalt, akkor azt mondjuk elnézést, és 'iterálunk' a hashkódon egy iterálófüggvénnyel. Ha az így kapott vödör végre üres, akkor oda pakolunk, amúgy tovább iterálunk.
    A tartalmazás műveletnél pedig addig iterálunk megintcsak, amíg vagy meg nem találtuk a kérdéses elemet, vagy üres cellára nem iterálunk.

    A betevés és a tartalmazás művelet is természetesen így is O(1) idejű átlagban, de kicsit kevesebb memória kell. Ezt a 8 byte per ojjektumid-t viszont már nem nagyon lehet megúszni.

    U.i.: üres cellát úgy jelölhetünk, hogy a 0 érték van benne, és persze a 0 nem lenne valid ojjektumid.

    U.i. 2: Az egészet C-ben írnám meg.
    Mutasd a teljes hozzászólást!
  • Nem az a célom, hogy megtudjam, vajon a facebook mit használ, hanem hogy mi lehet a legoptimálisabb. .
    Nem valószínű, hogy olyan rendszert fogok írni az elkövetkezendő pár évben, aminél 10-20k konkurrens user lesz kluszterben - így nem ez a kérdés.
    Sokkal valószínűbb, hogy írok egy alkalmazást egy kkv-nak, aki egy kiszuperált P3/1GB RAM-os gépet nevez ki szervernek és azon kell megoldani hasonló feladatot - egy pár nagyságrenddel kevesebb felhasználóval, de szutyok vason kell csodát művelni. Ezért gondolkodtam el az ideális megoldáson és gondoltam vannak itt nálam okosabb tanultabb emberek is.
    Mutasd a teljes hozzászólást!
  • Szerintem lazán tárolják egy sima hashset-ben, hogy mit likeolt egy user. Ez nem sok háttértárat igényel: havonta pár tíz kilobytenyit ha összelikeol egy user, ez núdli.

    Ezeknél a cégeknél elosztott rendszerek vannak, egy egy szervergép mondjuk mittudomén csak 10000 userért felel. ott nyugodtan mehet a cucc cache-be is.

    (Ez szervergépenként a hasraütéses adataimmal számolva 100 Megabyte körüli likeolási adat havonta.)

    Én úgy tudom, hogy a Facebook jellegű cégeknél azok a lekérdezések macerásak inkább, amelyek nem csak egy userre jellemzőek: ekkor nem lehet elkerülni, hogy a query több gépet érintsen az elosztott rendszerben. (pl. két user közötti legrövidebb út keresése, és a userek más gépeken laknak)
    Mutasd a teljes hozzászólást!
  • A HashSet-en (és barátain) gondolkodtam, de iszonyat memóriazabáló, hisz minden elemhez többlet információt is tárol és nekem még az elemre magára sincs szükségem.

    A "bittömb" megoldás szintén eszembe jutott (a userId-kat "pagelni" 64-esével és így tárolni egy tömbben sok bigintet). Ezt tartom eddig a legoptimálisabbnak, és nem is túl bonyolult megoldani.
    Nagy userszámnál azonban ez is kezd halálos lenni (100k user az objektumonként egy ~1500 elemű tömb, nagyjából 12k memóriafoglalással). Facebook-on ez már rengeteg cache lehet, csak erre. Ráadásul mindig ennyi helyet foglal, függetlenül attól, hogy népszerű-e az adott dolog vagy sem.

    Az utolsó algoritmus nem rossz - de ekkora számoknál ez kivitelezhetetlen.
    Mutasd a teljes hozzászólást!
  • Sokféle halmazmegvalósítás létezik.

    Pl. a legimsertebbek:

    - Hash set (hash táblával) (nem sorted)

    - Tree set (valamilyen kiegyensúlyozott bináris fával) (sorted)

    - Skip list. (Ez egy nagyon szép, egyszerű elegáns cucc ahhoz képest, hogy annyit tud, mint a kiegyensúlyozott bináris fák, amelyek jóval bonyolultabbak. A Skip Listet nem annyira régen fedezték fel, talán csak 20 éve. A bináris fák jóval régebbiek, azért elterjedtebbek.) (sorted)

    Hogy melyik optimális, az függ a felhasználási statisztikáktól.

    Ha borzalmasan gyors contains() operáció kell, és a lehetséges értékek range-je nem túl nagy, akkor pl. szóbajön a bittömb is:

    az n-edik bit true akkor és csak akkor, ha n tagja a halmaznak. (a halmazműveletek ekkor bináris ÉS-ek és VAGY-ok, amik gyorsak mint a fene.)

    Még egy nagyon érdekes nagyon gyors, kis memóriaigényű egzotikus halmazmegvalósítás kis elemszámra és kis viszonylag kis alapelem range-re:

    A halmazt reprezentálja egy A szám.
    A kezdetben legyen 1.

    n-et úgy tesszük be a halmazba, hogy A-t megszorozzuk az n-edik prímszámmal!
    A tartalmazás lekérdezés egy moduló művelet, ami egy mai procin hadd ne mondjam milyen gyors.

    A facebookos like-on nem gondolkodtam mélyebben, de a FaceBook scale-jű cégek kőkeményen elosztott NoSQL adatbázisokkal dolgoznak, az biztos: ezek kőkorszaki API-val rendelkeznek egy SQL-es adatbázishoz képest, csak alap dolgokat tudnak (mint pl. key value párok tárolása), de azt brutális sebességgel tudják. (Jóval gyorsabban mint egy SQL-es adatbázis.)
    Mutasd a teljes hozzászólást!
  • Olyan algoritmust keresek, ami megmondja, hogy egy int tagja-e egy halmaznak vagy sem. Nem érdekel a halmaz többi eleme, soha nem akarom kiolvasni a halmaz elemeit, csak hozzá akarom adni a számot és utána valamikor ellenőrizni szeretném, hogy hozzáadtam-e már. Természetesen egy bármilyen halmazos, listás, stb megoldással jó, de keresem a legoptimálisabb (memória és processzor-igény tekintetében).

    Őszintén megmondom: semmiféle gyakorlati hasznát nem fogom ennek venni, csak azon gondolkodtam el, hogy vajon egy facebook méretű portál hogy csinálja a like-ot? Minden olyan userid-t, aki már lájkolta az adott oldalt/valamit cache-be tenni iszonyat pazarlás. E nélkül meg hogyan oldja meg, hogy like/unlike gombokat rak ki annak megfelelően, hogy az adott felhasználó lájkolt-e vagy sem?

    szerk:
    egy dolog eszembe jutott: nem cache-be menteni, hogy ki lájkolta az oldalt, hanem session-be, hogy az adott user mit lájkolt eddig. Az eredmény ugyan az, de talán kevesebb erőforrást igényel. Bár az algoritmus itt is játszhatna.

    Ennek ellenére érdekelne a fenti elméleti kérdésre van-e valakinek ötlete.
    Mutasd a teljes hozzászólást!
Tetszett amit olvastál? Szeretnél a jövőben is értesülni a hasonló érdekességekről?
abcd