A feladat:
Megyek végig egy integer listán. Ami megfelelő integer, azt berakom egy másik listába. Az eredeti lista sorrend nem változhat meg az eredmény listában.
Ha az integer már szerepel az eredmény listában, akkor nem adhatom hozzá (azaz nem lehetnek duplikáltak az eredményekben).
Max. olyan 400-500 ezer integer lehet az eredménylistában.
Az eredménylistának nem kell tartalmaznia mind a 400-500 ezer sort. Mivel lapozható, így csak az aktuális oldalszámnak megfelelően pl. 100 db-nak.
Jelenleg HashSet-el oldottam meg.
Viszont nem ártana a memóriára is figyelni. CPU-ra is figyelni kell, de arra most ideiglenesen jó a + HashSet töltése.
Tudom van a Bloom filter is, de az nem 100%-os. Viszont valami hasonló megoldást keresnék.
- 422 megtekintés
Hozzászólások
C-ben tudom, hogyan csinálnám. Gondolom, Java-ban is lehet úgy programozni, mintha C lenne. Mész végig az első listán, elemet vizsgálod megfelelőségre. Ha OK, elindulsz a második listán, ha megtalálod az elemet, nem csinálsz semmit, folytatod a keresést az első listán. Ha nincs a második listában, akkor realloc() egy jelenlegi második lista méret + sizeof(int) mérettel, majd beteszed az elemet a lista végére. Utána vissza az első listához, a következő elem megfelelőségét vizsgálod.
Biztos, hogy mindenhez már kész függvényeket kell használni?
tr '[:lower:]' '[:upper:]' <<<locsemege
LOCSEMEGE
- A hozzászóláshoz be kell jelentkezni
Köszönöm a válaszod, de mivel a CPU is számít, így ha mindig vizsgálom a 2. listát akkor egy 400-500 ezres eredménylistánál ez már jelentős erőforrás igényű. Egyébként hasonlóan volt eredetileg.
- A hozzászóláshoz be kell jelentkezni
Ha ekkora a listád, akkor az integered gondolom, hogy 32 vagy 64 bites. Ha nem nézed végig, mit tehetsz? Vagy van valamilyen plusz infó, ami statisztikában segít? Teszem azt, nem egyenletes a számok eloszlása?
tr '[:lower:]' '[:upper:]' <<<locsemege
LOCSEMEGE
- A hozzászóláshoz be kell jelentkezni
csinálnék egy második eredménylistát is, de rendezettet (STL:set),
a keresést ebben csinálnám, beszúrás mindkét listába
- A hozzászóláshoz be kell jelentkezni
A rendezett listában bináris keresés?
tr '[:lower:]' '[:upper:]' <<<locsemege
LOCSEMEGE
- A hozzászóláshoz be kell jelentkezni
Nekem nagyon fura az, hogy szamit az eredmenylistaban a sorrend, viszont megse lehetnek duplikalt adatok.
Tudnal tobbet irni a kontextusrol? Lehet hogy mar korabban masfele kellene vinni a problema megoldasat.
- A hozzászóláshoz be kell jelentkezni
- Kiveszel minden elemet az új listába ami jó. Utána rostálod elemként az újat, Hogy minden elembő csak 1 maradjon.
- Ha nem nagy az értékkészlet, lehet cserélni az "index" -érték párokat -> nem kell keseni.
- A hozzászóláshoz be kell jelentkezni
LinkedHashSet: nem enged duplikátumot, de megtartja a betett elemek sorrendjét.
- A hozzászóláshoz be kell jelentkezni
Köszönöm! Ez pontosan az ami megfelel a leírásnak.
De ilyenkor derül ki, hogy hibás a leírás. :)
Az eredménylistának nem kell tartalmaznia mind a 400-500 ezer sort. Mivel lapozható, így csak az aktuális oldalszámnak megfelelően pl. 100 db-nak.
Módosítottam a leírást is.
- A hozzászóláshoz be kell jelentkezni
Tedd el memóriába vagy diszkre, aztán lehet tömörítve/indexelve is tárolni. Az első N eredmény ismerete nélkül nem tudod, mi az N+1-edik. Esetleg hamarabb abbahagyod az iterációt, de azt nem úszod meg, hogy az elejétől végigmenj az adott oldalig, és a duplikátumok elkerülése miatt egyszerre meg is kell jegyezni mindet.
- A hozzászóláshoz be kell jelentkezni
Igen, most már valószínűsítem, hogy ez az egyetlen lehetőség. Memóriában tárolom el, de másodpercenként több száz kérés érkezik és a végrehajtandónak ez csak egy kis része.
Ami még fontos lehet: ~140 megáig terjed az integer értéktartománya. Kb. 50-100 közötti értékkihagyásokkal (ez tulajdonképpen egy fájl pointer).
Abban bíztam, hogy a Bloom filterhez hasonló megoldást találok, ami viszont 100%-os biztonságú és nem kell mind a 500 ezer integert eltárolnom kérésenként a legrosszabb esetben. Elég mondjuk néhány longot bizirgálni.
- A hozzászóláshoz be kell jelentkezni
Ha csak 140M a legnagyobb, az elfér int[]-ben is. Ha kicsik az ugrások, akkor tárolhatod úgy, hogy az oldal első eleme int a rendes értékkel, utána byte[] a deltákkal.
Amúgy a bitfield lehetne még jó megoldás de csak kisebb kihagyások esetén (vagy ha mindegyik szám utolsó néhány bitje fix). Pl. 140M-ig 100-as kihagyásokkal van 1.4M integered, ami trükközés nélkül tárolva 5.6M. Ugyanennyi szám bitfieldben 140M/8=17.5M. Ha mindegyik szám 4-el osztható akkor már nyertél.
- A hozzászóláshoz be kell jelentkezni
Köszönöm az ötleteket. Ezen az úton nyomulok tovább.
- A hozzászóláshoz be kell jelentkezni
Implementalj egy Map/List interface-t, ami virtualisan szamitja ki runtime, amit ki kell.
Kell bele 2 pointer:
- eredeti listabeli pozicio
- szurt listabeli pozicio
Ez alapjan barmikor tudod a kovetkezo/elozo 100 elemet eloallitani runtime, eltarolas nelkul. Tovabbi elonye, hogy lazy eval, szoval hacsak nem lapoz a user a lista vegere, sose toltesz CPU idot olyan szamolgatassal, ami sose lesz felhasznalva.
- A hozzászóláshoz be kell jelentkezni
Köszönöm. Most is hasonlóan működik. Csak át kell térnem majd ha lesz időm stream-re.
- A hozzászóláshoz be kell jelentkezni
Kicsit hasonlít a probléma a metszethez. Lásd programozási tételek metszet
- A hozzászóláshoz be kell jelentkezni
Java 8+ esetén használhatsz Stream-et ami ezeket mind tudja. Ha aggódsz a teljesítménye miatt akkor mérd ki, szinte biztos vagyok benne, hogy a lehető leghatékonyabb implementációval rendelkezik.
- A hozzászóláshoz be kell jelentkezni
A stream egyiranyu. Ha user visszafele lapoz, megszivtad.
- A hozzászóláshoz be kell jelentkezni
Én nem látom a nyitóban, hogy az eredeti lista bármikor módosulhat, ami alapján az eredmény listának is frissülnie kellene. Egy szerver-kliens felállásban ez teljesen jó, annyi hogy egy skip() is kellene a lapozhatósághoz, amit kifelejtettem.
- A hozzászóláshoz be kell jelentkezni
Köszönöm. A stream-os megoldásra ránézek majd, mert tisztább lehet a kód. Egyelőre jól működik a mostani megoldás is. A CPU idő elhanyagolható 10 ezer oldalnyi kiválasztásnál is. A memória sem vészes.
- A hozzászóláshoz be kell jelentkezni