[Java] tabellen van onbekende grootte

[AquilaDus]

Hallo Mensen,

Ik ben een datastructuur aan het opbouwen van +/- 100 tabellen. Elk van deze tabellen is n bij n groot en elke cel verwijst naar een object. Op het moment dat ik deze tabellen ga vullen is deze n onbekend. Het enige wat ik kan is een schatting geven, maar ik kan niet garanderen dat de schatting altijd groter is dan n. Nu dacht ik: gebruik geneste HashMap's.

Zo gezegd, zo gedaan. Nu had ik een voorbeeld run waarbij deze n 500 was. Het resultaat was 700+ MB aan geheugengebruik. Dit leek mij een beetje veel.
Een HashMap met 500 items is vaak groter vanwege zijn marge (ik schat een factor 1.2). Daarom maakte ik het volgende rekensommetje met n = 600:

De HashMap in de 2e dimensie is: 600 * (4bytes (values) + 4bytes (keys)) = 4.9 KB

De HashMap in de 1e dimensie bevat 500 van deze 4.9KB hashtables (+ nog wat null pointers die ik even verwaarloos) = 2.4 MB

En ik heb 100 van deze tabellen: 100 * 2.4 MB = 240MB

Deze 240MB is een kleine factor 3 kleiner dan de 700+ MB die ik zag in de taskmanager. Nu kan ik me voorstellen dat ik wat overhead her en der ben vergeten, maar kan me niet voorstellen dat dit voor een factor 2 zorgt.
Nu vroeg ik me af, maar ik een rekenfout? Heeft bijvoorbeeld een HashMap meer ruimte nodig dan 4bytes voor elke key en 4bytes voor elke value?

De andere vraag die ik wilde stellen: Zijn er dat structuren die effectiever zijn qua geheugengebruik? Ik dacht zelf eerst aan de HashMap omdat ik niet weet hoeveel items ik moet opslaan bij het begin.

[Nick The Heazk]

Heb je vlak voor je het geheugengebruik meet steeds een garbage collection gedaan; dat scheelt namelijk nogal wat?

[AquilaDus]

Nick The Heazk schreef op vrijdag 02 februari 2007 @ 19:48:
Heb je vlak voor je het geheugengebruik meet steeds een garbage collection gedaan; dat scheelt namelijk nogal wat?

Ik had het getest als een los commandline programma, dus voor de rest was er geen significant geheugengebruik.

[Verwijderd]

Niet gehinderd door enige Java kennis, maar is een HashMap niet een soort van linked list? Zo ja, dan moet ieder item in die list ook weten wat z'n vorige en volgende sibling is. Da's 8 bytes extra per item (bij een 32 bits OS).

[AquilaDus]

Verwijderd schreef op zaterdag 03 februari 2007 @ 07:06:
Niet gehinderd door enige Java kennis, maar is een HashMap niet een soort van linked list? Zo ja, dan moet ieder item in die list ook weten wat z'n vorige en volgende sibling is. Da's 8 bytes extra per item (bij een 32 bits OS).

Nee, het is eigenlijk een hashtable. Dit staat er namelijk in de Java documentatie:

The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.

[joepP]

Een HashTable moet volgens mij weleens rehashen als ie te vol is. Dit betekent feitelijk dat de hele structuur opnieuw wordt opgebouwd in een ander stukje geheugen. Ik denk dat het "echte" geheugengebruik gewoon 240MB is, en de test nog opgeruimd moet worden door de garbagecollector.

Maar waarom werk je niet met dynamische arrays (Vector)? Dat lijkt me net zo snel, en daarmee verpruts je ook niet teveel geheugen. Zijn er trouwens veel cellen die dezelfde data bevatten (0?), of verwijzen ze echt allemaal naar iets anders? Zo ja, waar ben je dan eigenlijk precies mee bezig?

[AquilaDus]

joepP schreef op zaterdag 03 februari 2007 @ 18:27:
Een HashTable moet volgens mij weleens rehashen als ie te vol is. Dit betekent feitelijk dat de hele structuur opnieuw wordt opgebouwd in een ander stukje geheugen. Ik denk dat het "echte" geheugengebruik gewoon 240MB is, en de test nog opgeruimd moet worden door de garbagecollector.

Maar waarom werk je niet met dynamische arrays (Vector)? Dat lijkt me net zo snel, en daarmee verpruts je ook niet teveel geheugen. Zijn er trouwens veel cellen die dezelfde data bevatten (0?), of verwijzen ze echt allemaal naar iets anders? Zo ja, waar ben je dan eigenlijk precies mee bezig?

Ja, ik dacht zelf ook dat het iets met het rehashen te maken had. Maar die data kan dan worden opgeruimd door de garbage collector. Ik had ook al eens de hashtables geinitialiseerd met een capaciteit die ruim boven de verwachte waarde zit, maar dan groeit hij even hard (soms zelfs harder).

Dynamische arrays zijn niet echt handig voor mijn gebruik omdat ik met een key moet kunnen indexeren. Ik kan dan wel een omreken tabel bijhouden, maar dat wordt nog groter omdat het meer dan vijftig 2 dimensionale hashtables zijn.

Er zullen genoeg cellen zijn met dezelfde value, maar daarmee kan ik weinig doen ben ik bang. Ik zou dit apart kunnen administreren, maar dan is het moeilijk snel te achterhalen wat de waarde van een cel is, omdat je opslaat welke vectors bij welk cel resultaat horen. In een hashtable is het opvragen van die data O(1) per dimensie.

[joepP]

Ik snap je niet helemaal. In je openingspost heb je het over tabellen van n bij n. Als ik dat lees denk ik toch echt dat je een (1..n) x (1..n) domein wilt afbeelden op objecten. Maar nu heb je het ineens over een ander domein?

[AquilaDus]

joepP schreef op zondag 04 februari 2007 @ 10:42:
Ik snap je niet helemaal. In je openingspost heb je het over tabellen van n bij n. Als ik dat lees denk ik toch echt dat je een (1..n) x (1..n) domein wilt afbeelden op objecten. Maar nu heb je het ineens over een ander domein?

Nee, het klopt het gaat over tabellen van n bij n (waarbij ik wil indexer met objecten, en niet direct getallen). Ik vroeg me alleen af wat je dan wilde doen als cellen dezelfde inhoud hebben, want dit zal inderdaad wel heel vaak voorkomen.
Maar het probleem zit hem dus in het feit dat ik niet weet hoe groot n is als begin met het vullen van die tabellen en ik zou graag in een constante tijd de cel voor de indices willen achterhalen.

Als ik van arrays gebruik zou maken i.p.v. hashtables dan zou ik voor elke dimensie in een lookup tabel moeten gebruiken die de objecten afbeeldt op een integer.

[Jrz]

Ik zie niet waarom je met een arraylist lookups zou moeten doen.
Wat is nou je doel? Je bent behoorlijk vaag, en ja. referenties kosten geheugen. Een factor 2 is niet vreemd, als jij er vanuit gaat dat 1 entry 8 bytes kost. Je moet idd 2 refs bewaren, maar dat betekend dus 2*8 byte ")

[joepP]

Sorry, maar je uitleg is echt vager dan vaag.

Neem nou eens rustig een kwartiertje de tijd om duidelijk op te schrijven wat je uiteindelijke doel is. Je maakt nu een onbegrijpelijke mix van probleem, doelstelling en oplossing, en ik maak me sterk dat niemand begrijpt wat je bedoelt. Wat is nou je input, wat is het domein, wat is de output, etc.

[AquilaDus]

joepP schreef op zondag 04 februari 2007 @ 12:42:
Sorry, maar je uitleg is echt vager dan vaag.

Neem nou eens rustig een kwartiertje de tijd om duidelijk op te schrijven wat je uiteindelijke doel is. Je maakt nu een onbegrijpelijke mix van probleem, doelstelling en oplossing, en ik maak me sterk dat niemand begrijpt wat je bedoelt. Wat is nou je input, wat is het domein, wat is de output, etc.

Oke, misschien ben ik wat vaag. Ik zal probleem duidelijk proberen te omschrijven.

Input:
Met een programma genereer ik tuples bestaande uit een vector (x, y) en een waarde z: {(x, y), z}. Hierbij zijn x, y en z objecten van hetzelfde type. Het domein van x, y en z is nog niet bekend op het moment dat de eerste tuples worden gegenereerd (de onbekende n waar ik het steeds over had is de grootte van dit domein).

Doel:
Ik wil deze tuples zo opslaan dat ik voor elke willekeurige vector (x, y) kan bepalen wat de bijbehorende waarde z is. Ik zou het liefst willen dat dit opvragen O(1) is. Verder wil ik de benodigde geheugenruimte zoveel mogelijk beperken.

Huidige oplossing:
Een geneste hashtable. Als het tuple {(x, y), z} moet worden opgeslagen, dan wordt voor key x in de hoofd hashtable een nieuwe hashtable opgeslagen als value. In deze nieuwe hashtable wordt dan voor key y value z opgeslagen.
Het opvragen van data uit deze datastructuur is dan eenvoudig, maar zoals ik omschreef in mijn eerste post is het geheugen gebruik veel groter dan ik dacht. Er is namelijk 7MB nodig voor zo'n geneste hashtables waarbij x, y en z uit een domein komen wat 500 items bevat.

[joepP]

Nou snap ik het, en ik heb ook een methode bedacht om het allemaal wat efficienter in te richten.

Allereerst zal ik alle waarden van x en y afbeelden op het domein van positieve gehele getallen. Hiervoor kan je inderdaad het beste een hashtable gebruiken. Het geheugengebruik hiervan is lineair in de grootte van je domein, en is dus te verwaarlozen. Voor de rest van het verhaaltje neem ik aan dat je domein 1...n is, voor zowel x als y.

Na deze stap kan je je data als een n bij n matrix representeren, met als elementen de waarden van z. Als dit lukt is je geheugengebruik dus 4 * n^2, wat bij n = 500 neerkomt op ongeveer 1MB. Het probleem dat je hierbij moet oplossen is dat je domein groeit, en je geen geheugen wil verprutsen. Dit gaan we doen door de matrix met behulp van schillen te representeren. De eerste schil bestaat uit het element (0,0), de tweede schil uit de elementen (0,1),(1,1),(1,0), etcetera. Een afbeeldinkje voor de duidelijkheid:

12345
22345
33345
44445
55555

Dit kan je eenvoudig representeren met fixed length arrays van lengte 1,3,5,7,etc die je in een dynamische array hangt. Als je een lookup wilt doen moet je eerst controleren in welke schil je moet zijn, en dan in welk element van de schil. Dit is triviaal in O(1) te doen. Toevoegingen zijn ook O(1) als ze binnen het domein vallen. Een domeinuitbreiding is uiteraard duurder, maar geamortizeerd kost dit natuurlijk ook maar O(1) per toevoeging.

Veel efficienter dan dit zal niet lukken zonder aannames over de verdeling van z over de (x,y) paren te doen. Je kan eventueel nog alle z waarden ook hashen, en dan proberen het minimaal aantal bits voor een representatie te gebruiken. Bij n = 500 heb je maar 9 bits nodig ipv 32, dat kan nog aardig schelen. Ik denk alleen niet dat het loont om zo ver te gaan met je optimalisaties, maar dat kan je zelf beter beoordelen.

[AquilaDus]

joepP schreef op zondag 04 februari 2007 @ 16:11:
...

Hartelijk dank voor de tip. Ik heb het eens geimplementeerd en het geheugengebruik is eeen factor 6 kleiner dat bij de geneste hashtables.

[joepP]

Uitstekend! Mooi dat er iets gedaan wordt met mijn geraaskal, leuk om te horen.