Set egy kicsit másképp?

Java

Ha jól gondolom, bár nem néztem, a java Set-jei letárolják a hash értéket, és az eredeti értéket is.
Szeretnék egy olyan Set-et, amiben nincsenek csak a hash értékek letárolva, így kevesebb memóriát foglalnának.

Tehát hozzáadom az értékeket egy fájlból, majd csak keresek benne, hogy létezik-e már ilyen elem. A keresés gyors legyen.

Tudtok valamit ajánlani? :-)

  • 1695 megtekintés

( drojid | 2009. 07. 07., k – 18:51 )

Persze. Első körben azt, hogy döntsd el, gyors legyen, vagy kevés memóriát használjon :-)
Mert hát a hash segítségével keres gyorsan...

Update: így a sokadik hozzászólás után most már látom, mennyire félreolvastam, bocs :-) :-(

( stoned | 2009. 07. 07., k – 11:31 )

Esetleg csak a hashCode-ot tárolod a Set-ben?

Egyébként az Object#hashCode() követelményei:
- Egy adott példány a teljes élettartama alatt ugyanazt a hashCode-ot adja vissza.
- Ha két példány az equals() metódus szerint egyenlő, a hashCode-juknak is egyenlőnek kell lennie.
- Ha két példány nem egyenlő az equals() szerint, a hashCode() értéke megegyezhet.

Ha a te hashCode implementációd nem garantáltan egyedi, akkor eleve nem jo a hashCode-ot használni.

( sibidiba | 2009. 07. 07., k – 11:44 )

A Set-ek nem kulcs-érték párokat tárolnak hanem csak szimpla értékeket. (Ami ezt csinálja, az a Map, pl. HashMap.)

Ha csak a hasheket szeretnéd bennük tárolni, akkor csak a hasheket add hozzá.

--
The Net is indeed vast and infinite...
http://gablog.eu

( persicsb | 2009. 07. 07., k – 12:52 )

A Set csak egy interface, aminek van par megvalositasa. Az, hogy melyik mit tarol le, implementaciofuggo.
http://java.sun.com/javase/6/docs/api/java/util/Set.html
Lasd: All Known Implementing Classes szekcio.
Alapvetoen a memoriafoglalas ilyen kontenerek eseteben nem nagy gond, hiszen csak objektumreferenciakat tarolnak le, nem az objektumok klonjait.

( yoursoft | 2009. 07. 07., k – 13:26 )

Köszönöm az eddigi hozzászólásokat.

Pontosítom a kérdést:
Egy HashSet szerű valamit keresek, amelyben csak a Hash értékek vannak letárolva.
Így megmarad a gyors keresés, de kevesebb memóriát foglalna.
Megnézem, sajnos a HashSet construktora már eleve így kezdődik:
public HashSet() {
map = new HashMap();
}
Valamint mivel ki lehet venni az eredeti értékeket belőle így biztos, hogy ezek is le vannak tárolva.

Tehát beolvasok egy String fájlt egy Set szerű valamibe.
Itt csak a Hash-ek kerülnek tárolásra.
Tehát ebből nekem nem kell, hogy kivegye az értéket, csak annyit mondjon meg, ha meghívom a "contains"-t, hogy a megadott String érték szerepelt-e az eredeti String halmazban.

1. Nem magát az objektumot tárolja, hanem csak egy hivatkozást rá.
2. A hash-ek között előfordulhat ütközés. Ilyen esetekben nem jó megoldás csak a hash-t tárolni. Ha garantáltan ütközésmentes lenne a hash függvényed akkor talán
3. Mit akarsz kezdeni egy táblázattal amiben hash értékek vannak?

Összefoglalva: nem világlik ki, hogy mit szeretnél elérni. Ha leírnád a teljes problémát biztos lenne aki tud jó ötlettel szolgálni.

1., 2. Igen, igazad van.
Látom, hogy a keresésénél itt is ellenőrzi az értéket. Nem csak a hash-t:
public V get(Object key) {
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
for (Entry e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
return null;
}

3.
Ez egy didyoumean funkció lenne. Itt előre legenerálom a beírt szó alapján a tévesztési lehetőségeket. Majd csak keresek egy szó-halmazban, hogy van-e ilyen. Ha van visszaadom, mint lehetséges elírást. Ez HashSet-el működik, de túl sok memóriát eszik.
Jelenleg egy Lucene alapú szóajánlóm van, de ez lassú és túl sok javaslatot tesz.
Pl.:
segéj
Lucene: segéd, segít, segge, segély, segédje (>200msec)
Új módszer: segéd, segély (~20-30msec)

Mivel hasonló szavakat keresel, nem értem mire mész a hash értékekkel. A hash index csak a pontosan azonos szavakat fogja megtalálni.

Ahhoz, hogy adatszerkezetet tudjunk javasolni ismerni kellene a teljes algoritmust.

Javában amúgy kb annyit kell tudni, hogy egy objektum az kb 12 bájt overhead, plusz a rajta lévő field-ek. A stringek immutable-k, azaz a substring új változatot hoz létre. A stringek betűi két bájton tárolódnak.

A HashMap tárolója egy array, aminek minden eleme egy reference, ami 4 bájt. Benne minden bejegyzéshez egy HahMap$Entry, ami a 12 bájt overhead plusz 4 4 bájtos mező, az összesen 30 bájt. Kb 1-es telítettségi tényezővel számolva tehát a hash index bejegyzésenként 34 bájt overhead-et jelent.

Ha például egy szöveg részeit akarod beindexelni (rész-egyezés kereshetővé tétele céljából), akkor érdemes lehet nem magát a sub-stringet tárolni, hanem az eredeti stringbe mutató pointerként értelmezett betűindexeket.

Ez egy szótár alkalmazás. Itt több szótár van. 2 irányba kell ajánlatokat tenni szótáranként.
A szótárban a kifejezéseket is szavakra bontottam. Ebből készítettem egy halmazt.
Tehát készítettem egy text fájlt:
a
az
azok
...

Bár a gyorsabb szókeresés érdekében a szótárakat memóriában tárolom. 1 szótár=2db utf8-as byte tömb.
Így lehet, hogy ezt is fel lehetne használni.

A lényegi kódrész így néz ki:
ArrayList javaslatok = javaslatok(word);
for (String s : javaslatok) {
if (szolista.contains(s)) {
results.add(s);
}
}

A kulcs hash-a önmagában nem elég a kereséshez..
.. ha megnézed a Hashtable forrását, a put()-nál láthatod, hogy
a "tömb" aktuális hossza alapján pozicionálja az adott elemet..
Ha egy új elemet adsz hozzá a put()-al akkor az egész table "újraszámolódik"..
ez is ott van feketén/fehéren a forrásban.

Továbbra sem értem mi a problémád a HashSettel. Csinálsz egy HashSet -t, amibe belepakolod a hash értékeket. Nem az elemeket, hanem .hashCode() -okat. Így nem tartalmazza az eredeti (String) elemeket (pontosabban a referenciáikat). Mivel a HashSet HashMap-el van implementálva, a contains() konstans időben fut le (feltéve, hogy a hash függvény megfelelően szór).

Áttekintés a Java collecionökről:
http://java.sun.com/docs/books/tutorial/collections/implementations/ind…

--
The Net is indeed vast and infinite...
http://gablog.eu

A hash értékek nem megbízhatóak, mint ahogy a HashSet kereső funkciója is használja:
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
Tehát a hash kódokra keres, de visszatérés előtt levizsgálja, hogy valóban arról az objektumról van-e szó.

Ha a haskódot rakom bele a HashSetbe, akkor is többszöröse történik a kívánt tárolásnak:
1. A hash kódok hash kódjai a kereséséhez.
2. A generált hash kódok.

Ha lenne egy megbízható, rövid hasht, vagy pl. integert generáló hash metódus, akkor elég lenne a hash kódokat letárolni és azokra keresni.
Bár a HashSet használatakor, ebben az esetben is generál még +hash-t.

Találtam egy btree megoldást, de ez meg lassú. :-(

sztem túlbonyolítod a problémát, ez nem cééé :) itt már kitalálták a frankót a nyelv fejlesztői.
"1 szótár=2db utf8-as byte tömb." utf8-as tömb?! miért nem String? ez nem C...
nem jó a HashSet?!
hashcode-al akarsz játszani? minek? a String tudja a saját hashcodeját, és kész...

Félreérted.
1. Az UTF8 nem a "didyoumean"-hoz használt. Ezt pont a memória miatt kellett meglépnem. Így ~150 megát eszik a memóriából, amúgy ~2 gigát evett.
2. A hashkód nem egyedi, mint fentebb kifejtettem. A HashSet 1 tábla 1 irányára evett kb. 25 megát. ~88-szor ennyit kellene kezelnem a mostani állapot szerint, de bővítenem is kellene.

Keresőfák O(log n) idő alatt fognak bármit is megtalálni, plusz a fát is fel kell építeni egyszer. A HashSet O(1).

Továbbra is HashSet oldja meg a problémádat. A hash eleve egy integer. Sőt, az Integer hash függvénye magát az Integert adja vissza int-ként. Hol ezzel a gond?

Az *tényleg* problémát jelent, hogy a *hash értékek* kétszer, azaz egyszer egy int, egyszer egy Integer formájában vannak tárolva? Az eredeti probléma az volt, hogy az elemeket, amikhez a hashek tartoznak, nem akarod végig memóriában tartani. És ha csak a hashCode-okat pakolod bele a Set-be, ez nem is gond.

Sajnos tényleg nincs Collection a primitiv típusok tárolására (ind stb.). Ha ennyire durva probléma, akkor nem túl nehéz átírni a HashMap implementációját, hogy int-ek legyenek a kulcsok de ne tároljanak értékeket, egyáltalán.

--
The Net is indeed vast and infinite...
http://gablog.eu

Igen, abban igazad van, hogy elég lenne ezeket tárolni.
Abban is, hogy jóval kisebb lenne a memória fogyasztás is.

A hash kódok továbbra is a hiba forrás, ugyanis eddigi ismereteim szerint nem garantált az egyedi generálás. Tehát lehet, hogy a 'hash' és a 'kód' szavak pl. ugyanazt a hasht adják.

Bár, ha tudsz egy viszonylag megbízható hash generálót azt szívesen veszem :-)
Ha esetleg van infód a String hash generálásának megbízhatóságáról az is érdekel. :-)

A Hash per definition mindig fog adni ütközéseket. Vagy a Stringeket hasonlítod össze, és akkor biztos az eredmény, de cserébe a teljes Stringet a memóriában kell tárolnod. Vagy a hasheket hasonlítod össze, ami egy kis integer, de előfordulnak kulcsütközések. Mivel a String tetszőleges hosszú, egy hash pedig véges, nem lehetséges kulcsütközés nélküli (injektív) relációt találni.

String.hashCode(): 


Returns a hash code for this string. The hash code for a String object is computed as

     s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

A kérdés az, hogy az egyébként ritka kulcsütközések okoznak-e neked bármilyen problémát? Ha igen, akkor találat esetén tudod-e ezt külön ellenőrizni, akárcsak a HashMap.contains() teszi?
Hashmapek etalon tárolók, lépten-nyomon használják őket, és megbízhatóak. Csak mindig tudni kell, hogy *lehetséges* a kulcsütközés. (Ez nem azt jelenti, hogy mert kicsi a valószínűsége, úgysem fog bekövetkezni! Hanem kell írni akár igen költséges, erőforrásigényes kezelést rá, ami csak kicsi valószínűséggel, így ritkán fog lefutni.)

--
The Net is indeed vast and infinite...
http://gablog.eu

Jónak tűnik ez a bloom filter.
Az eredményeket, ha ellenőrzöm még egy kereséssel a szótárban, akkor nem lehet gond.
Bár, mégsem. Lehet olyan amikor pl. egy mondatnak a szavát találja csak meg, ilyenkor lassabb a keresés.

No, erre még alszunk egyet :-)