Integer keresése integerekben

Java

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.

  • 423 megtekintés

( locsemege v | 2022. 07. 15., p – 23:12 )

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

( Toth Lali | 2022. 07. 15., p – 23:20 )

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

( asm v | 2022. 07. 15., p – 23:24 )

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.

( fhuse | 2022. 07. 15., p – 23:29 )

  • 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.

( joco01 v | 2022. 07. 15., p – 23:32 )

LinkedHashSet: nem enged duplikátumot, de megtartja a betett elemek sorrendjét.

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.

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.

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.

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.

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.

( uid_17626 | 2022. 07. 16., szo – 07:57 )

Kicsit hasonlít a probléma a metszethez. Lásd programozási tételek metszet

( BaT | 2022. 07. 17., v – 15:09 )

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.