[java] Collections, geheugenruimte

[Verwijderd]

Ik ben op zoek naar een overzicht van het gebruikte geheugen voor collections in Java.
De "big O" waarden bij verschillende operaties vind ik overal, maar het betreft steeds snelheid ipv ingenomen geheugenruimte.

In casu zoek ik naar een O(n) opslagstructuur.

Iemand een idee?

Veel dank.

[NetForce1]

En welk type structuur ben je dan naar op zoek? Als je een list wilt kun je denk ik het beste een LinkedList pakken, array-based structuren gebruiken nl nogal wat bufferruimte.

[Verwijderd]

Wel, het is een schoolopdracht, en de opgave is dat de geheugenruimte van die te ontwikkelen klassse O(n) moet zijn t.o.v. één van zijn instantiatie variabelen (een collectie dus), ik ben dus in eerste instantie niet op zoek naar de meest efficiente collectie, maar naar welke collectie(s) voldoen aan deze eis, daartussen kan ik dan nog kiezen op het gebied van efficientie.

[Creepy]

Eeeh, ok, het is voor een schoolopdracht en je wil ons dan alles voor je laten uitzoeken? Dus: wat heb je zelf al gevonden? Helemaal niks? Dat kan ik me niet voorstellen. Wat zei je docent?

[NetForce1]

Ik zou zeggen bekijk de documentatie van de verschillende Collection implementaties, en als je daar niet genoeg aan hebt kun je bijv. kijken hoe de add/put methode geimplementeerd is (source wordt meegeleverd met de Java SDK).

offtopic:
Hoe weet jij dat ts een vrouwelijke docent heeft?

[.oisyn]

Zijn er überhaupt collections (in de java framework bedoel ik dan, duh ) die niet O(n) zijn

[NetForce1]

ArrayList volgens mij, die maakt bij het toevoegen van items wel de array groter, maar bij het verwijderen van items wordt de array niet kleiner gemaakt.

[.oisyn]

Dat doet er niet toe . Hij schaalt lineair, dus hij is O(n).

[writser]

"In casu" groeit het geheugengebruik van praktisch alle collecties lineair met het aantal elementen (misschien speciale zoekstructuren daargelaten). Snap je uberhaupt wel wat O(n) geheugengebruik inhoudt?

[NetForce1]

Je hebt inderdaad gelijk volgens mij, intuitief voelt het alleen wat vreemd aan.

[Robtimus]

.oisyn schreef op maandag 31 maart 2008 @ 15:14:
Zijn er überhaupt collections (in de java framework bedoel ik dan, duh ) die niet O(n) zijn

HashSet en LinkedHashSet misschien? Die gebruiken hashing voor lookups etc, waardoor ze in theorie O(1) kan zijn. Afhankelijk van de hash codes van je objecten en het aantal buckets kan dit wat slechter worden.

[NetForce1]

IceManX schreef op maandag 31 maart 2008 @ 17:33:
[...]

HashSet en LinkedHashSet misschien? Die gebruiken hashing voor lookups etc, waardoor ze in theorie O(1) kan zijn. Afhankelijk van de hash codes van je objecten en het aantal buckets kan dit wat slechter worden.

Die snap ik niet helemaal, je moet toch nog steeds ergens in je collectie die objecten opslaan? Of je moet in een keer zoveel ruimte alloceren dat je nooit meer extra geheugen nodig hebt, maar dat lijkt me niet je bedoeling.

[Verwijderd]

writser schreef op maandag 31 maart 2008 @ 15:43:
"In casu" groeit het geheugengebruik van praktisch alle collecties lineair met het aantal elementen (misschien speciale zoekstructuren daargelaten). Snap je uberhaupt wel wat O(n) geheugengebruik inhoudt?

"Snap je uberhaupt wat het inhoudt" is nogal beledigend, waarom zou de aangroei lineair moeten zijn, het kan toch perfect dat je redundantie invoert om aan snelheid te winnen??
(en redundantie is in zeer veel gevallen niet linear!)

[ Voor 5% gewijzigd door Verwijderd op 31-03-2008 18:12 ]

[Verwijderd]

Creepy schreef op maandag 31 maart 2008 @ 14:56:
Eeeh, ok, het is voor een schoolopdracht en je wil ons dan alles voor je laten uitzoeken? Dus: wat heb je zelf al gevonden? Helemaal niks? Dat kan ik me niet voorstellen.

Alles?? Alleen 1 spec van een collectie, dit is een minimaal deel van een opdracht. Wat heb ik zelf al gedaan : De Java tutorials over collections uitgevlooid en een programma geschreven dat testen doet met collecties met 100,10 000, 1E6 leden, waaruit bij allen lineariteit blijkt wanneer ik de betreffende objecten vergelijk qua grootte. Het feit dat ik er daarom niet vanuit ga dat deze collecties ook een lineaire aangroei hebben in het geheugen is omdat mijn vergelijkings methode (het vergelijken van de grootte van de files wanneer ik de objecten persistent maak) misschien niet waterdicht is, mogelijk wordt er bij elke persistentie een omzetting gemaakt naar een lineaire structuur?

[Verwijderd]

.oisyn schreef op maandag 31 maart 2008 @ 15:14:
Zijn er überhaupt collections (in de java framework bedoel ik dan, duh ) die niet O(n) zijn

Ja, dat is inderdaad mede de vraag, een ontkennend antwoord zou me welkom zijn

[RobIII]

Zeg; als je iets wil toevoegen aan een topic, en je bent de laatste poster... gebruik dan de edit ( ) knop i.p.v. 3x je topic omhoog te schoppen wil je? Zie ook topickick binnen 24 uur

Verwijderd schreef op maandag 31 maart 2008 @ 18:10:
[...]
Wat heb ik zelf al gedaan : <snip>

Vermeld dat dan voortaan in je topicstart, dan hoeven we er niet naar te vragen. Zie ook onze Programming Beleid Quickstart

Verwijderd schreef op maandag 31 maart 2008 @ 18:10:
Het feit dat ik er daarom niet vanuit ga dat deze collecties ook een lineaire aangroei hebben in het geheugen is omdat mijn vergelijkings methode (het vergelijken van de grootte van de files wanneer ik de objecten persistent maak) misschien niet waterdicht is, mogelijk wordt er bij elke persistentie een omzetting gemaakt naar een lineaire structuur?

Dat lijkt me niet waterdicht nee; als er al 'redundantie' in het geheugen zou zijn, waarom zou die dan bij het opslaan worden meegenomen Dat zou zonde zijn van de opslagruimte en bij het terug inladen is die 'redundantie' natuurlijk zo weer gemaakt in het geheugen. Let wel: als...

[ Voor 116% gewijzigd door RobIII op 31-03-2008 18:25 ]

[robbert]

IceManX schreef op maandag 31 maart 2008 @ 17:33:
[...]

HashSet en LinkedHashSet misschien? Die gebruiken hashing voor lookups etc, waardoor ze in theorie O(1) kan zijn. Afhankelijk van de hash codes van je objecten en het aantal buckets kan dit wat slechter worden.

Een hashset is in worst case lineair qua geheugenruimte, dit is het geval dat alle elementen dezelfde hash opleveren. In het geval van hashset van ruimte grote en een ideale hashfunctie is het inderdaad O(1).

[ Voor 11% gewijzigd door robbert op 31-03-2008 18:29 ]

[.oisyn]

IceManX schreef op maandag 31 maart 2008 @ 17:33:
[...]

HashSet en LinkedHashSet misschien? Die gebruiken hashing voor lookups etc, waardoor ze in theorie O(1) kan zijn. Afhankelijk van de hash codes van je objecten en het aantal buckets kan dit wat slechter worden.

Je wilt dus beweren dat het geheugengebruik constant is, onafhankelijk van hoeveel elementen je erin stopt? Doe mij ook zo'n container (tenzij je ook beweert dat die constante dan +∞ is )

robbert schreef op maandag 31 maart 2008 @ 18:26:
[...]

Een hashset is in worst case lineair qua geheugenruimte, dit is het geval dat alle elementen dezelfde hash opleveren. In het geval van hashset van ruimte grote en een ideale hashfunctie is het inderdaad O(1).

Zoals al impliciet blijkt uit mijn reactie op IceManX, een container kan nooit minder zijn O(n) geheugen gebruiken, aangezien je toch altijd minstens n items op moet slaan. Dat je bij een ideale hashfunctie maar 1 object per bucket opslaat doet er weinig toe - je hebt dan namelijk gewoon weer n buckets.

Ik heb het gevoel dat jullie beiden geheugencomplexiteit verwarren met tijdcomplexiteit.

[ Voor 4% gewijzigd door .oisyn op 31-03-2008 19:51 ]

[MSalters]

.oisyn schreef op maandag 31 maart 2008 @ 15:14:
Zijn er überhaupt collections (in de java framework bedoel ik dan, duh ) die niet O(n) zijn

TreeSet? Zou N log N kunnen zijn, dat hangt van de implementatie af.

[Janoz]

MSalters schreef op maandag 31 maart 2008 @ 20:13:
[...]

TreeSet? Zou N log N kunnen zijn, dat hangt van de implementatie af.

Dat is alleen wanneer de data enkel in de leafs opgeslagen wordt. De standaard implementatie van Tree in java slaat de data ook in de nodes op. Deze implementatie is dus ook nog steeds O(n).

[writser]

Verwijderd schreef op maandag 31 maart 2008 @ 18:06:
"Snap je uberhaupt wat het inhoudt" is nogal beledigend, waarom zou de aangroei lineair moeten zijn, het kan toch perfect dat je redundantie invoert om aan snelheid te winnen??

Maar dat gebeurt niet in een LinkedList, Vector, Hashmap, Queue, of weet ik veel. Anders was het per definitie geen LinkedList, Vector, Hashmap, Queue meer maar een andere datastructuur. Waarmee je dus al antwoord hebt op je initiele vraag.

(en redundantie is in zeer veel gevallen niet linear!)

Aha. Zou je ook een van deze "zeer veel gevallen" als voorbeeld kunnen geven?

[Robtimus]

.oisyn schreef op maandag 31 maart 2008 @ 19:39:
[...]

Je wilt dus beweren dat het geheugengebruik constant is, onafhankelijk van hoeveel elementen je erin stopt? Doe mij ook zo'n container (tenzij je ook beweert dat die constante dan +∞ is )

Never mind me, ik zat te denken aan snelheid...

[.oisyn]

writser schreef op maandag 31 maart 2008 @ 20:45:
Aha. Zou je ook een van deze "zeer veel gevallen" als voorbeeld kunnen geven?

Daarvan staat er al een in de topic, in de twee reacties boven je.

[ Voor 4% gewijzigd door .oisyn op 31-03-2008 20:54 ]

[Soultaker]

Beetje zinloze discussie i.m.o. Alle standaardcontainers gebruiken O(N) geheugen.

Janoz schreef op maandag 31 maart 2008 @ 20:16:
Dat is alleen wanneer de data enkel in de leafs opgeslagen wordt. De standaard implementatie van Tree in java slaat de data ook in de nodes op. Deze implementatie is dus ook nog steeds O(n).

Flauwekul, ook als je alleen in de leaf gegevens opslaat is het geheugengebruik O(N) (zolang het gemiddelde aantal kinderen per node maar groter dan 1 is).

[writser]

.oisyn schreef op maandag 31 maart 2008 @ 20:53:
Daarvan staat er al een in de topic, in de twee reacties boven je.

Ik lees hier dat die ook O(n) kan zijn. Maar ben geen expert op het gebied van TreeMaps . Punt is dat de topicstarter nu aankomt met aannames over niet-lineariteit en redundantie terwijl zijn vraag was:

In casu zoek ik naar een O(n) opslagstructuur.

Dan denk je 1) veel te moeilijk (want elke elementaire datastructuur verbruikt O(n) opslagruimte) of 2) snap je niet precies waar je het over hebt.

[ Voor 7% gewijzigd door writser op 31-03-2008 21:35 ]

[MrBucket]

.oisyn schreef op maandag 31 maart 2008 @ 19:39:
...een container kan nooit minder zijn O(n) geheugen gebruiken, aangezien je toch altijd minstens n items op moet slaan. Dat je bij een ideale hashfunctie maar 1 object per bucket opslaat doet er weinig toe - je hebt dan namelijk gewoon weer n buckets.

Dat klopt, en ik kan het weten

Ik zit m'n hoofd te breken welke datastructuur niet lineair groeit ten opzichte van zijn aantal elementen. Ik bedoel, zelfs een gebalanceerde binaire boom of skiplist heeft max. 2n nodes.

Hmm... misschien een graaf, als je die opslaat als een matrix van afstanden tussen nodes? Deze groeit kwadratisch in verhouding tot zijn aantal nodes.

[writser]

MrBucket schreef op maandag 31 maart 2008 @ 21:34:
[...]

Dat klopt, en ik kan het weten

Ik zit m'n hoofd te breken welke datastructuur niet lineair groeit ten opzichte van zijn aantal elementen. Ik bedoel, zelfs een gebalanceerde binaire boom of skiplist heeft max. 2n nodes.

Hmm... misschien een graaf, als je die opslaat als een matrix van afstanden tussen nodes? Deze groeit kwadratisch in verhouding tot zijn aantal nodes.

Maar lineair in verhouding tot het aantal paden (niet noodzakelijk het aantal edges) en dat is wat je eigenlijk opslaat. Correct me if I am wrong ..

Je hebt wel gelijk: je vormt de graaf om er bijvoorbeeld makkelijker te rekenen, maar hij neemt zo wel meer ruimte in. off-topic: Google gebruikt ook zo'n soort matrix om de pagerank van een site te berekenen. Gelukkig is de grootte daarvan niet O(n^2). Dan zaten we vast aan Live Search ..

[ Voor 19% gewijzigd door writser op 31-03-2008 21:42 ]

[MrBucket]

writser schreef op maandag 31 maart 2008 @ 21:38:
[...]

Maar lineair in verhouding tot het aantal paden (niet noodzakelijk het aantal edges) en dat is wat je eigenlijk opslaat. Correct me if I am wrong ..

Nou, als je alle nodes met alle andere verbindt, en je staat toe dat elke node slechts 1 maal bezocht wordt, dan heb je al een factoriaal aantal paden. Klassiek Travelling Sales Person probleem

Je hebt wel gelijk: je vormt de graaf om er bijvoorbeeld makkelijker te rekenen, maar hij neemt zo wel meer ruimte in. off-topic: Google gebruikt ook zo'n soort matrix om de pagerank van een site te berekenen. Gelukkig is de grootte daarvan niet O(n^2). Dan zaten we vast aan Live Search ..

Google gebruikt Pigeon Ranking
_{Erg toepasselijk i.v.m. morgen...}

[Jeanpaul145]

NetForce1 schreef op maandag 31 maart 2008 @ 18:03:
[...]

Die snap ik niet helemaal, je moet toch nog steeds ergens in je collectie die objecten opslaan? Of je moet in een keer zoveel ruimte alloceren dat je nooit meer extra geheugen nodig hebt, maar dat lijkt me niet je bedoeling.

Wat hij zei slaat op een runtime asymptotic upper bound, niet op de upper bound van de opslag.

[writser]

Meestal wil je alleen de kleinste afstand tussen twee nodes opslaan lijkt me.

Die pigeon ranking had ik nog niet gezien, leuk . Vorig jaar o.i.d. had Google deze 1 april grap: http://www.google.com/tisp/ . Die was ook erg grappig.

[MrBucket]

writser schreef op maandag 31 maart 2008 @ 21:50:
Die pigeon ranking had ik nog niet gezien, leuk . Vorig jaar o.i.d. had Google deze 1 april grap: http://www.google.com/tisp/ . Die was ook erg grappig.

Of GMail Paper

Ben benieuwd wat ze dit jaar gaan doen, trouwens.

[Janoz]

Soultaker schreef op maandag 31 maart 2008 @ 21:11:
Flauwekul, ook als je alleen in de leaf gegevens opslaat is het geheugengebruik O(N) (zolang het gemiddelde aantal kinderen per node maar groter dan 1 is).

Je hebt inderdaad gelijk. Het was ietsje te kort door de bocht. Ik nam ff vlug aan dat de boom best kon groeien, maar deze is redelijk lineair afhankelijk van het aantal leaf nodes.

[Marcj]

Zonder compressie is het onmogelijk om objecten op te slaan in een collectie die een geheugengebruik heeft die kleiner is dan O(N), omdat je dat geheugen al kwijt bent aan de objecten zelf.

De enige manier om een grotere complexiteit te hebben is wanneer de extra data die voor de collectie nodig is groter is dan O(N). Dit kan ik me alleen voorstellen als je iets als indexering wilt toevoegen, en zelfs die zijn vaak makkelijk in O(N) te houden.

Maar met behulp van compressie (waarbij je dus de originele objecten gaat serializen en weggooit) kan je mogelijk wel lager komen in best of average case. Maar worst case zal altijd minimaal O(N) blijven (tenzij je aannames kan maken over het type object die je erin gaat stoppen).

Voorbeeldje: Minimized Automaton Representation kan heel efficient zijn

[ Voor 8% gewijzigd door Marcj op 31-03-2008 22:37 ]

[RobIII]

Marcj schreef op maandag 31 maart 2008 @ 22:34:
Maar met behulp van compressie (waarbij je dus de originele objecten gaat serializen en weggooit) kan je mogelijk wel lager komen in best of average case.

Is dat niet gewoon cheaten? Je hebt namelijk dan in principe de originele collectie niet meer.

[Marcj]

RobIII schreef op maandag 31 maart 2008 @ 22:37:
[...]

Is dat niet gewoon cheaten? Je hebt namelijk dan in principe de originele collectie niet meer.

Klopt Maar hij wou toch weten hoe je een collectie kan maken met een andere complexiteit?

[.oisyn]

Janoz schreef op maandag 31 maart 2008 @ 22:03:
[...]

Je hebt inderdaad gelijk. Het was ietsje te kort door de bocht. Ik nam ff vlug aan dat de boom best kon groeien, maar deze is redelijk lineair afhankelijk van het aantal leaf nodes.

Het was helemaal niet te kort door de bocht, aangezien je in een generieke container niet kan wegkomen door de informatie alleen in de leafs op te slaan - je moet namelijk ook de data in de nodes opslaan om de compares mee te doen. Maar goed, als je dat al doet dan is de vraag waarom je het in hemelsnaam ook nog eens in de leaf nodes op zou slaan - het is minder efficient qua geheugen en je wint er niets mee qua tijdcomplexiteit . Als je een gescheiden key/value pair hebt dan zou het wel kunnen.

MrBucket schreef op maandag 31 maart 2008 @ 21:34:
Ik zit m'n hoofd te breken welke datastructuur niet lineair groeit ten opzichte van zijn aantal elementen. Ik bedoel, zelfs een gebalanceerde binaire boom of skiplist heeft max. 2n nodes.

Hmm... misschien een graaf, als je die opslaat als een matrix van afstanden tussen nodes? Deze groeit kwadratisch in verhouding tot zijn aantal nodes.

Zodra je gaat denken aan een meerdimensionale zoekstructuur zit je al gauw aan een geheugencomplexiteit minder efficient dan O(n). Een Range tree bijvoorbeeld, met complexiteit O(n log n)

[Robtimus]

Ik kan me trouwens wel een collectie voorstellen waarbij je minder dan N objecten hoeft op te slaan: de bag of multiset, maar ook die heeft een O(n) aan opslag.

[writser]

De andere kant op: Ik heb een collectie in gedachten die een enorme hoeveelheid nummers kan opslaan in een speciale datastructuur met O(1) geheugengebruik. Misschien maar eens patent op aanvragen.

Java:

class RoelPieper almostimplements Collection
  public void returnElementAt(int i) {
    return i;
  }
}

[ Voor 4% gewijzigd door writser op 01-04-2008 01:12 ]

[.oisyn]

Dat zei ik ook al in een ander... ehh.. topic

.oisyn schreef op maandag 31 maart 2008 @ 20:59:
Ik weet er wel een, een container waarin je N instanties van het volgende type op kunt slaan

C++:

enum MyEnum
{
    TheOnlyEnumValue
};

Ondersteunt worst-case O(1) inserts, deletes en lookups. Geheugengebruik is wederom worst-case O(1)

[Verwijderd]

writser schreef op maandag 31 maart 2008 @ 20:45:
Maar dat gebeurt niet in een LinkedList, Vector, Hashmap, Queue, of weet ik veel. Anders was het per definitie geen LinkedList, Vector, Hashmap, Queue meer maar een andere datastructuur. Waarmee je dus al antwoord hebt op je initiele vraag.

Ik heb inderdaad een antwoord op mijn initiele vraag : alle gangbare datastructuren in java blijken O(n).

writser schreef op maandag 31 maart 2008 @ 20:45:
Aha. Zou je ook een van deze "zeer veel gevallen" als voorbeeld kunnen geven?

Een voorbeeld blijkt dus Range tree (zie hoger).

Ik ben geen Java kenner, maar heb geen voorbeelden nodig om te weten dat het invoeren van redundantie niet lineair hoeft te zijn, zeker niet als het gaat om het winnen van snelheid, ik gaf die algemeen aan, niet perse betreffende java collections, omdat ik daar nu net niet veel van weet.

Maar het is niet moeilijk om structuren voor te stellen die geheugen-redundantie implementeren om snelheid te winnen, eg : een opslag van integers met een functie

code:

int[] getPrimes()

, waarbij voor snelheidswinst een array van priemgetallen wordt opgeslagen voor elke toegevoegde integer, dit ipv de tijdrovende adhoc berekening van priemgetallen.

Overigens ben ik blij deze vraag te hebben gesteld, los van het eigenlijke antwoord, want veel van de discussie die erop volgt, vind ik zeer interessant.

[Marcj]

Verwijderd schreef op dinsdag 01 april 2008 @ 12:16:
[...]
Maar het is niet moeilijk om structuren voor te stellen die geheugen-redundantie implementeren om snelheid te winnen, eg : een opslag van integers met een functie

code:

int[] getPrimes()

, waarbij voor snelheidswinst een array van priemgetallen wordt opgeslagen voor elke toegevoegde integer, dit ipv de tijdrovende adhoc berekening van priemgetallen.

Overigens ben ik blij deze vraag te hebben gesteld, los van het eigenlijke antwoord, want veel van de discussie die erop volgt, vind ik zeer interessant.

Dit voorbeeld is voor geheugen nog steeds ongeveer O(N) in geheugengebruik. Weliswaar wordt per item die wordt opgeslagen meer data toegevoegd, maar deze is nog steeds lineair met het aantal items die zijn toegevoegd. Onthou hierbij dat O(N + 10N) gelijk is aan O(N)

Ik kan me ook geen zinnige redundatie voorstellen die meer geheugen nodig is dan O(N). Misschien iets als de som van elke twee getallen uit die set, wat wel O(N^2) zou kosten. Maar dit is nu niet echt zinnig, wel?

[Verwijderd]

Marcj schreef op dinsdag 01 april 2008 @ 13:44:
[...]


Dit voorbeeld is voor geheugen nog steeds ongeveer O(N) in geheugengebruik. Weliswaar wordt per item die wordt opgeslagen meer data toegevoegd, maar deze is nog steeds lineair met het aantal items die zijn toegevoegd. Onthou hierbij dat O(N + 10N) gelijk is aan O(N)

Dit klopt mijn inziens niet : de lijsten zullen wel linear zijn, maar de sommatie (en dus het geheugengebruik) ervan niet. een voorbeeldje stel dat de lijst per toegevoegd item 1 langer wordt, dank is de som van alle lijsten gelijk aan (x² + x)/2 , dat is een kwadratische functie die toch leidt tot O(x²) en niet tot iets van de strekking van O(N + 10N) of vergis ik me?

Dit is maar 1 voorbeeld idd, vanaf er lijsten dienen opgeslagen te worden die per item (inderdaad lineair!) stijgen, zal denk ik de sommatie van deze lijsten kwadratisch stijgen.

[Marcj]

Verwijderd schreef op dinsdag 01 april 2008 @ 16:16:
[...]


Dit klopt mijn inziens niet : de lijsten zullen wel linear zijn, maar de sommatie (en dus het geheugengebruik) ervan niet. een voorbeeldje stel dat de lijst per toegevoegd item 1 langer wordt, dank is de som van alle lijsten gelijk aan (x² + x)/2 , dat is een kwadratische functie die toch leidt tot O(x²) en niet tot iets van de strekking van O(N + 10N) of vergis ik me?

Dit is maar 1 voorbeeld idd, vanaf er lijsten dienen opgeslagen te worden die per item (inderdaad lineair!) stijgen, zal denk ik de sommatie van deze lijsten kwadratisch stijgen.

Het voorbeeld dat je geeft hangt af van de waarde x, niet van N. Je complexiteit wordt hier dat ongeveer O(N + ((x² + x) / 2)N), welke nog steeds lineair is.

[Verwijderd]

Ik ben nog niet mee : ik gebruikte hier x en N misschien wat verwarrend door elkaar, maar ik zie dat
f(n) = n²/2 + n/2 ten allen tijden kleiner is dan 2n² (gebruik makende van de feiten dat n <= n² en 1<=n voor alle n>=1), dus f(n)<=2n² en de grenswaarde is dus maximaal O(n²).

Dit wil niet zeggen dat de grenswaarden niet nog kleiner kunnen zijn, maar om jou stelling hard te maken moet je kunnen stellen dat n²/2 + n/2 ten allen tijden kleiner is dan een lineaire functie van n, en dat zou kunnen maar dat zie ik gewoon niet?

Er zou toch een assymptoot moeten bestaan voor deze functie wil je ze lineair begrenzen?

(Merk de '?' na de zinnen, ik ben immers geen wiskundige, en ik moet bekennen dat als ik me hier vergis ik er heel van wat zou opsteken, dus misschien is dat zo slecht nog niet )

[ Voor 0% gewijzigd door Verwijderd op 01-04-2008 18:39 . Reden: ergens de noemer vergeten ]

[Marcj]

Je moet met big-O notatie iets anders gaan denken. Laten we van de volgende set getallen uitgaan: {2, 3, 4, 5, 6}. Met jouw opslagmethode sla ik 12 nummer op, eens? Nu probeer ik twee keer zoveel nummers op te slaan:
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

Indien de opslagcomplexiteit maximaal O(N^2) zou zijn, dan zouden we 4x12 = 48 nummers verwachten op te slaan. Maar we hoeven slechts 26 op te slaan (tel maar na). Dit ligt veel dichter bij lineair.

Nog sterker voorbeeld, wat als ik nu {2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6} wil opslaan? 4x zoveel nummers opslaan kost slecht 4x zoveel opslagruimte.

Nu zeg ik natuurlijk wel dat dit bij benadering lineair is, omdat ik uitga dat ik willekeurige getallen opsla. Hierbij kunnen we van een constante overhead uitgaan.

Is dit zo een beetje duidelijk wat ik bedoel?

[Soultaker]

Wat zijn jullie nu precies aan het opslaan dan? Volgens mij bedoelt pedrib dat je per toegevoegd element een extra lijst van ongeveer dezelfde lengte als het aantal elementen in de collectie opslaat (dus bij N elementen, N lijsten van O(N) elementen elk!) en dan krijg je inderdaad O(N²).

Maar wederom: dat lijkt me niet zo'n zinnige constructie. Het is me dan ook niet echt duidelijk waar je heen wil met deze discussie. Ik denk dat een generieke collectie altijd O(N) geheugen gebruikt; pas als je specifieke indices gaat toevoegen (zoals bijvoorbeeld bij de range tree) zal dat anders worden.

[roy-t]

Verwijderd schreef op dinsdag 01 april 2008 @ 12:16:

Ik ben geen Java kenner, maar heb geen voorbeelden nodig om te weten dat het invoeren van redundantie niet lineair hoeft te zijn, zeker niet als het gaat om het winnen van snelheid, ik gaf die algemeen aan, niet perse betreffende java collections, omdat ik daar nu net niet veel van weet.

Maar het is niet moeilijk om structuren voor te stellen die geheugen-redundantie implementeren om snelheid te winnen, eg : een opslag van integers met een functie

code:

int[] getPrimes()

, waarbij voor snelheidswinst een array van priemgetallen wordt opgeslagen voor elke toegevoegde integer, dit ipv de tijdrovende adhoc berekening van priemgetallen.

Overigens ben ik blij deze vraag te hebben gesteld, los van het eigenlijke antwoord, want veel van de discussie die erop volgt, vind ik zeer interessant.

Ehm... een collectie is eigenlijk altijd een collectie van Objects (een enkele int array daar gelaten) als je dan wat invoegt in je lijst, collectie, whatever voeg je alleen de reference (pass by reference anyone?) toe aan de list. Omdat de reference in de list staat wordt het object niet gebarge collect. Als je nu nog een keer het zelfde object invoegt (zonder een nieuwe geheugen allocatie) voor je slechts nogmaals de dezelfde reference toe.
Deze reference is slechts enkele bytes groot en verwijst naar het eerste geheugenadres waar het object in voorkomt. Als het object meer geheugenadressen nodig heeft staat aan het einde van het geheugenadres welk volgend adres er nodig is.

Kortom als je 2maal het zelfde object voor redundantie in je collection wilt hebben dan heb je niet 2x SizeOf(objectX) in je collectie, maar 2x de reference naar objectX, en omdat objectX gereferenced staat in de collection dus eigenlijk het volgende geheugengebruik voor de collection omdat je natuurlijk de geheugenruimte van objectX bij het geheugengebruik van je collection telt

objectX, reftoX, reftoX


Dus in het ergste geval heb je een O(n+y*(verwaarloosbaar aantal aan reference bytes))
waarbij n de grote is van een instantie van ObjectX en y het aantal redundant references naar een objectX is per instantie van ObjectX. Dat is niet helemaal liniear maar wel zo sterk er tegen aan dat ik het niet anders zou durven noemen.

Dus zelfs bij redundandt Objects in collections is er geen O(!n) geheugenruimte

*Disclaimer dit geld natuurlijk steeds meer naar mate de grote van het Object in je collectie toe neemt*

*Btw: ik weet het niet 100% zeker maar dat aantal verwaarloosbare reference Bytes zou wel eens 4 Byte voor een 32bit en 8 byte voor een 64bit systeem kunnen zijn*

[ Voor 5% gewijzigd door roy-t op 01-04-2008 22:28 ]

[writser]

Dat is niet helemaal liniear maar wel zo sterk er tegen aan dat ik het niet anders zou durven noemen.

Het idee van ordes van grootte is niet dat je iets "bijna" lineair noemt. Dan is het niet lineair.

[roy-t]

writser schreef op woensdag 02 april 2008 @ 00:03:
[...]

Het idee van ordes van grootte is niet dat je iets "bijna" lineair noemt. Dan is het niet lineair.

Ok ok, als je kijkt naar het wiskundige begrip inderdaad, als je bekijkt naar praktijk, snelheid en werkelijke geheugen ruimte zit het natuurlijk net iets anders, ik heb dan ook aangegeven dat het precies O(n+nogiets) was. Maar daarna dat ik dit zelf meestal verwaarloosbaar vindt voor echte objecten. (Een byte array is natuurlijk een ander verhaal)

Weet iemand trouwens hoeveel geheugen zo'n pointer naar een geheugenlocatie kost? Lijkt me wel een handig feitje en ik denk dat ik met 8 byte toch vrij hoog zit.

[Marcj]

O(N + iets wat kleiner is dan N) = O(N)

Dus bijna lineair noemen we daarom meestal gewoon lineair

roy-t schreef op woensdag 02 april 2008 @ 00:13:
[...]
Weet iemand trouwens hoeveel geheugen zo'n pointer naar een geheugenlocatie kost? Lijkt me wel een handig feitje en ik denk dat ik met 8 byte toch vrij hoog zit.

Op een 32bits systeem normaal 4 bytes, op een 64bits systeem 8 bytes. Dat is helemaal niet hoog hoor.

Hou trouwens wel in de gaten dat Java vaak memory allocation doet per 8 bytes, dat houdt in dat een klein object vaak al snel groter is dan verwacht. Bijvoorbeeld:

Java:

public class A {
    private byte b;
}

Dit object zou 16 bytes kosten (8 bytes header en 4 bytes! voor de byte, maar dan afgerond naar boven.

Zie ook: JavaSpecialists 29

Daar laat hij bijvoorbeeld zien dat het volgende object zelfs 264 bytes kost:

Java:

public class SixtyFourBooleanFactory implements ObjectFactory {
  private static class SixtyFourBooleans {
    boolean a0, a1, a2, a3, a4, a5, a6, a7;
    boolean b0, b1, b2, b3, b4, b5, b6, b7;
    boolean c0, c1, c2, c3, c4, c5, c6, c7;
    boolean d0, d1, d2, d3, d4, d5, d6, d7;
    boolean e0, e1, e2, e3, e4, e5, e6, e7;
    boolean f0, f1, f2, f3, f4, f5, f6, f7;
    boolean g0, g1, g2, g3, g4, g5, g6, g7;
    boolean h0, h1, h2, h3, h4, h5, h6, h7;
  }
  public Object makeObject() {
    return new SixtyFourBooleans();
  }
}

Maar ik dwaal af ...

[ Voor 109% gewijzigd door Marcj op 02-04-2008 00:24 ]

[.oisyn]

roy-t schreef op dinsdag 01 april 2008 @ 22:25:
[...]


Ehm... een collectie is eigenlijk altijd een collectie van Objects (een enkele int array daar gelaten) als je dan wat invoegt in je lijst, collectie, whatever voeg je alleen de reference (pass by reference anyone?) toe aan de list. Omdat de reference in de list staat wordt het object niet gebarge collect. Als je nu nog een keer het zelfde object invoegt (zonder een nieuwe geheugen allocatie) voor je slechts nogmaals de dezelfde reference toe.

Dat doet er niet toe bij de grote-O notatie. Het gaat om schaalbaarheid, niet om hoeveel bytes je geheugen inneemt. Als een collectie O(n) geheugencomplexiteit heeft, dan betekent het dat het ruwweg 2x zoveel geheugen inneemt bij een 2x zo grote n, als n heel groot wordt. Als een collectie O(n²) geheugencomplexiteit heeft, dan neemt het geheugen ruwweg kwadratisch toe met het aantal elementen dat je erin stopt.

Daarom is O(2n) ook niet anders dan O(n) - bij een verdubbeling van n verdubbel je nog steeds het geheugengebruik.

Ten tweede snap ik de relevantie van jouw reactie niet tov de reactie van pedrib die jij quote. Hij heeft het toch helemaal niet over absoluut geheugengebruik?

Deze reference is slechts enkele bytes groot en verwijst naar het eerste geheugenadres waar het object in voorkomt. Als het object meer geheugenadressen nodig heeft staat aan het einde van het geheugenadres welk volgend adres er nodig is.

Kortom als je 2maal het zelfde object voor redundantie in je collection wilt hebben dan heb je niet 2x SizeOf(objectX) in je collectie, maar 2x de reference naar objectX, en omdat objectX gereferenced staat in de collection dus eigenlijk het volgende geheugengebruik voor de collection omdat je natuurlijk de geheugenruimte van objectX bij het geheugengebruik van je collection telt

objectX, reftoX, reftoX

Onzin natuurlijk . Als je stelt dat Java met references werkt, dan hoort dat object ook niet in je collectie, en kun je enkel references opslaan in de collectie (wat ook het geval is). De O(n) slaat op de collectie zelf, niet wat je daarbuiten nog nodig hebt om je references betekenis te geven.

Marcj schreef op woensdag 02 april 2008 @ 00:15:
Daar laat hij bijvoorbeeld zien dat het volgende object zelfs 264 bytes kost

Hmm, beetje lame, een boolean past prima in een byte (of in een enkele bit, maar dan krijg je weer problemen met atomische operaties). Ik kan geen reden bedenken om daar dwords van te maken. Overigens lijkt het me ook nogal platform/VM specifiek
.edit: ik lees nu dat dat voor alle primitives geldt, dus ook byte, char en short.

[ Voor 9% gewijzigd door .oisyn op 02-04-2008 00:39 ]

[Marcj]

.oisyn schreef op woensdag 02 april 2008 @ 00:33:
[...]

Dat doet er niet toe bij de grote-O notatie. Het gaat om schaalbaarheid, niet om hoeveel bytes je geheugen inneemt. Als een collectie O(n) geheugencomplexiteit heeft, dan betekent het dat het ruwweg 2x zoveel geheugen inneemt bij een 2x zo grote n, als n heel groot wordt. Als een collectie O(n²) geheugencomplexiteit heeft, dan neemt het geheugen ruwweg kwadratisch toe met het aantal elementen dat je erin stopt.

Daarom is O(2n) ook niet anders dan O(n) - bij een verdubbeling van n verdubbel je nog steeds het geheugengebruik.
[...]

Eindelijk iemand die het even duidelijk uitlegd. Ik probeerde dit zel een aantal posts terug al duidelijk te maken, maar blijkbaar nog niet duidelijk genoeg.

Hmm, beetje lame, een boolean past prima in een byte (of in een enkele bit, maar dan krijg je weer problemen met atomische operaties). Ik kan geen reden bedenken om daar dwords van te maken. Overigens lijkt het me ook nogal platform/VM specifiek
.edit: ik lees nu dat dat voor alle primitives geldt, dus ook byte, char en short.

Ik weet het. Dit is natuurlijk wel getest op een Windows NT platform. Is er iemand die zin heeft om die tests uit te voeren op een linux bak?

[Verwijderd]

Ondertussen (ik leer bij) kan ik me bij Java dit soort Collections ook niet direct meer een echt nuttige toepassing bedenken, maar het principe, redundantie, zelfs kwadratische, om snelheidswinst te boeken op zich komt toch vaak voor? Kijk maar naar datawarehousing , waar geprecalculeerde (aggregaats) waarden worden bijgehouden waarbij elke bijkomende waarde zorgt voor een exponentiele stijging van het gebruikte opslag-geheugen?

[roy-t]

.oisyn schreef op woensdag 02 april 2008 @ 00:33:
[...]


Ten tweede snap ik de relevantie van jouw reactie niet tov de reactie van pedrib die jij quote. Hij heeft het toch helemaal niet over absoluut geheugengebruik?


[...]

Het ging om dit stukje:

Ik ben geen Java kenner, maar heb geen voorbeelden nodig om te weten dat het invoeren van redundantie niet lineair hoeft te zijn, zeker niet als het gaat om het winnen van snelheid, ik gaf die algemeen aan, niet perse betreffende java collections, omdat ik daar nu net niet veel van weet.

En ik wilde aangeven dat het wel degelijk liniair is ook als je een object vaker laat voorkomen in je collection. Miesschien dat ik me een beetje te veel uitwijdde

Bedankt trouwens jij en MarcJ om even helderder te maken wat O(n) is en me daarmee ongeveer gelijk te geven.

Onzin natuurlijk . Als je stelt dat Java met references werkt, dan hoort dat object ook niet in je collectie, en kun je enkel references opslaan in de collectie (wat ook het geval is). De O(n) slaat op de collectie zelf, niet wat je daarbuiten nog nodig hebt om je references betekenis te geven.

Ok daar heb je wel een punt, maar als de reference in de collection naar het object niet was geweest was het object verdwenen (Garbage collection). Als je een gereferenced object in een collection niet bij een collection rekent dan is elke collectie in java slechts n*8bytes groot en tsja dan is het moeilijk om te gaan na denken over de grote van je collectie.

Ik zie het zelf meer als dat de Collection de 'owner' is van het object door hem te referencen, en andere objecten komen meestal pas bij het object door via de collection te gaan. Maar ok ok, dit is natuurlijk een discutabel puntje.

[Marcj]

Verwijderd schreef op woensdag 02 april 2008 @ 09:58:
Ondertussen (ik leer bij) kan ik me bij Java dit soort Collections ook niet direct meer een echt nuttige toepassing bedenken, maar het principe, redundantie, zelfs kwadratische, om snelheidswinst te boeken op zich komt toch vaak voor? Kijk maar naar datawarehousing , waar geprecalculeerde (aggregaats) waarden worden bijgehouden waarbij elke bijkomende waarde zorgt voor een exponentiele stijging van het gebruikte opslag-geheugen?

Ik mag niet hopen dat datawarehousing kwadratische opslag gebruikt. Dat houdt namelijk in dat voor elke verdubbeling van de hoeveelheid data, 4x zoveel opslagruimte nodig is.

Voor zover ik weet zijn ook alle indexeringsmethoden etc. gewoon lineair.

En bij gecombineerde waarden is het vaak efficienter om deze live te berekenen dan om ze op te slaan. Stel je voor dat ik twee tabellen heb met ieder 100.000 rijen (is nog niet eens zo gek veel). Nu wil ik een functie aanroepen die een deel nodig is van die twee tabellen in een kruisproduct. Als ik deze zou opslaan ben ik 10.000.000.000 rijen nodig. Maar aangezien je meestal niet al deze 10^10 rijen allemaal nodig bent, kun je deze waarschijnlijk sneller berekenen dan ze in die enorme lijst te moeten opzoeken. Daarnaast ben je in plaats van enkele megabytes voor de twee originele tabellen, vele 10-tallen gigabytes nodig om het te kunnen opslaan

[Verwijderd]

Volgens mij is er geen zinnig woord over te zeggen. Als het niet in de standaard is opgenomen lijkt het me vrij aan de JVM om het te implementeren op welke manier ze het willen. Je kan natuurlijk aannemen dat een JVM-bouwer het zo efficiënt mogelijk wil oplossen, maar dat hoeft natuurlijk niet.

Je zal dus een JVM van een specifieke bouwer moeten pakken (e.g. SUN, IBM, etc.) en dan daar proberen te achterhalen voor welke strategie ze hebben gekozen.

Overigens zegt de standaard wel iets over de initiele grootte van lege collecties. Zie de betreffende collecties in de java.util-package in de API van de SE-envirement.

[writser]

Marcj schreef op woensdag 02 april 2008 @ 00:15:
O(N + iets wat kleiner is dan N) = O(N)
Dus bijna lineair noemen we daarom meestal gewoon lineair

Dat is niet wat Roy bedoelde.Als iets "net niet lineair is dan is het bijv. O(n wortel n). En dat scheelt al een factor 1000 bij een miljoen elementen. Tuurlijk, O(10 * n + 100000) is gewoon lineair. Het punt is dat je dat onderscheidt heel precies houdt, juist omdat het bij grote datasets een enorm verschil gaat uitmaken of iets "net niet lineair" is of "precies lineair".

[Janoz]

@writser: Er is een verschil tussen eneTerm + andereTerm en eneTerm x andereTerm.

[Marcj]

writser schreef op woensdag 02 april 2008 @ 11:35:
[...]


Dat is niet wat Roy bedoelde.Als iets "net niet lineair is dan is het bijv. O(n wortel n). En dat scheelt al een factor 1000 bij een miljoen elementen. Tuurlijk, O(10 * n + 100000) is gewoon lineair. Het punt is dat je dat onderscheidt heel precies houdt, juist omdat het bij grote datasets een enorm verschil gaat uitmaken of iets "net niet lineair" is of "precies lineair".

Maar hier staat toch echt wat anders:

roy-t schreef op dinsdag 01 april 2008 @ 22:25:
[...]
Dus in het ergste geval heb je een O(n+y*(verwaarloosbaar aantal aan reference bytes))
[...]

Dit is toch echt een lineaire functie...

offtopic:
@Writser: Heb je vroeger op het esdal gezeten?

[ Voor 4% gewijzigd door Marcj op 02-04-2008 11:51 ]

[roy-t]

Ik zal nog even een voorbeeldje geven van wat ik bedoel

Stel: ObjectX is 100KB (stukje tekst ofzo) en die heb je hangen in 5 eind leafs van je tree
en een Reference naar de memory locatie van objectX is 8Bytes

code:

                             root
   /               /          |              \            \
refToX1   refToX1   refToX1   refToX1   refToX1   
   \             \            |              /             /
                           ObjectX

Dan heb je in je collectie 5*8bytes = 40Byte + 100KB = 100,40KB

Stel nu heb je slechts 1x ObjectX via een reference in je tree hangen

Dan heb je 1*8bytes + 100KB = 100,08KB

Dus per toevoegen van 1 referentie naar ObjectX voeg je 8 bytes toe
En per toevoegen van een nieuw Object voeg je 100,08KB toe

Eigenlijk is je collectie nu het slechtstse geval (*alleen nieuwe objecten*) O(n) waar n is 100KB + 8 bytes per object

in het beste geval is je collectie nog steeds O(n) maar nu is n eenmalig 100,08KB en wordt bij elke toename van n de collectie 8byte groter

Dit is dus nogsteeds linieair alleen weergeven in een grafiek een lijn met een veel zwakkere positieve hoek tov de X as

code:

Situatie 1:
|         *
|    *
|*________


Situatie 2:

|               *
|  *      
|_________

However wat wel interessant is is een tussengeval waarbij zowel nieuwe als duplicaten worden toegevoegd, hierbij krijg je een soort schuin trappetje met toenames van soms 8Byte en soms 100,08KB dat is dus niet liniear vrees ik, maar als je dit zou normalizeren wel *het is absoluut niet kwadratich, facultatief of iets anders eng snel groeiends* maarja of er een naam voor is?

*yay ascii aart faillure!*

[ Voor 12% gewijzigd door roy-t op 02-04-2008 12:33 ]

[Marcj]

Ik snap het nut hiervan niet Waarom wil je graag 5 referenties naar hetzelfde object toevoegen? Het gaat hier toch voornamelijk om collecties waar je verschillende objecten aan toe wilt voegen?

[roy-t]

Marcj schreef op woensdag 02 april 2008 @ 12:35:
Ik snap het nut hiervan niet Waarom wil je graag 5 referenties naar hetzelfde object toevoegen? Het gaat hier toch voornamelijk om collecties waar je verschillende objecten aan toe wilt voegen?

Nouja ik raak eigenlijk een beetje carried away door de TS voorbeeld van zelfde object in een collectie.

Maar het zou bijvoorbeeld nut kunnen hebben in een HashMap waar meerdere keys naar het zelfde object kunnen verwijzen, of in een graaf, tree of trie waarin meerdere paden een zelfde uitkomst object zouden kunnen hebben hebben maar op een ander sink / leaf

Maar ik geef toe dat het nut meestal vrij beperkt is :-)

[ Voor 4% gewijzigd door roy-t op 02-04-2008 12:43 ]

[Marcj]

Maar zelfs wanneer je meerdere keys is een HashMap naar hetzelfde object laat wijzen, zitten er nog steeds niet meer objecten in, wanneer je er vanaf de buitenkant naar kijkt

Maar we dwalen hierbij wel erg af... waar het om gaat dat in het algemeen te zeggen is dat Collecties een opslagcomlexiteit hebben van O(n). Veel interresantere discussie is natuurlijk complexiteit van de snelheid van verschillende operaties in verschillende

writser schreef op woensdag 02 april 2008 @ 13:15:
[...]

offtopic:
Ja. Bij jou in de klas toevallig?

offtopic:
Ja Zet je Direct Messages eens aan

[ Voor 19% gewijzigd door Marcj op 02-04-2008 13:31 ]

[writser]

Marcj schreef op woensdag 02 april 2008 @ 11:49:
[...]


Maar hier staat toch echt wat anders:

[...]

Dit is toch echt een lineaire functie...

offtopic:
@Writser: Heb je vroeger op het esdal gezeten?

offtopic:
Ja. Bij jou in de klas toevallig?

[MSalters]

Verwijderd schreef op woensdag 02 april 2008 @ 09:58:
Ondertussen (ik leer bij) kan ik me bij Java dit soort Collections ook niet direct meer een echt nuttige toepassing bedenken, maar het principe, redundantie, zelfs kwadratische, om snelheidswinst te boeken op zich komt toch vaak voor? Kijk maar naar datawarehousing , waar geprecalculeerde (aggregaats) waarden worden bijgehouden waarbij elke bijkomende waarde zorgt voor een exponentiele stijging van het gebruikte opslag-geheugen?

Workaround voor harddisks. Heel simpel gezegd zou je de read latency kunnen halveren door twee schijven precies 180 graden uit fase te laten draaien. RAM werkt niet zo. Sterker nog, bij SDRAM is het verstandiger om geen kopie te hebben, en voor je CPU caches helpen kopieen ook niet.