[Bc6,arrays] lange lijsten

[Verwijderd]

Ik heb voor mijn roosterprogramma lange lijsten nodig (300000 elementen maximaal). Ik gebruik nu een DynamicArray hiervoor en met kleine dingen gaat dat ook wel goed, maar als ik een paar honderd lessen heb geinitialiseerd, dan gaat hij plotseling veel(met veel bedoel ik ook VEEL) langzamer . Zelf denk ik dat dit komt doordat Windows ergens in het geheugen(op de plaats waar ik iets neer wil zetten) moet schuiven om die plek dus vrij te maken. Is er niet een manier zodat ik van te voren kan zeggen: Zeg Windhoos geef mij eens 200 MB geheugen achter elkaar of iets dergelijks (niet dat ik zoveel geheugen heb, maar dat doet er nu even niet toe ).

Als dit niet kan, dacht ik er aan om dan bijv. na elke 100 elementen een nieuwe Dynamicarray aan te maken en dan een soort boom te maken, maar dit kost weer tijd en dat heb ik dus liever niet.

Weet iemand wat ik hieraan kan doen?

[whoami]

Heb je al eens naar een TObjectList gekeken? Ik weet niet hoe die zich gedraagt bij zo'n hoeveelheid aan elementen.

Heb je die elementen trouwens wel allemaal nodig? Kan je je niet beperken tot het inlezen van enkel de op dat moment nodige elementen?

[nohtml]

Verwijderd schreef op 31 March 2003 @ 20:54:
Zelf denk ik dat dit komt doordat Windows ergens in het geheugen(op de plaats waar ik iets neer wil zetten) moet schuiven om die plek dus vrij te maken.

Windows moet helemaal niet schuiven met dat geheugen. Als een geheugenplek ingenomen is door iets anders, dan wordt er gewoon een andere geheugenplek genomen.
Wat er wel kan gebeuren is dat Windows gaat gaan 'pagen'.

Zeg Windhoos geef mij eens 200 MB geheugen achter elkaar of iets dergelijks (niet dat ik zoveel geheugen heb, maar dat doet er nu even niet toe ).

FYI, in Windows kan je tot 4 gigabyte aan geheugen alloceren.

[ Voor 59% gewijzigd door whoami op 31-03-2003 21:02 ]

[Verwijderd]

Het zit hem zoals je al vermoed in de geheugen allocatie, als je elke keer een paar bytes vraagt kost dit over het geheel genomen veel tijd. Je kunt beter in een keer een groot stuk aanvragen.

Het lijkt me in de geval het makkelijkst om in een keer de array me bijvoorbeeld 100 te verhogen. Als je nu gewoon met honderd groot begint en daarna na elke honderd de array de huidige lengte +100 maakt dan gaat het vast beter.

Je kunt de lengte toch gewoon op iedere waarde zetten met setlength(in delphi) of iets. Gewoon zelf een tellertje bijhouden en zo om de honderd verhogen.

[update]
Oh ja, wat voor een array is het eigenlijk, ik bedoel de inhoud. ALs het een string is zonder opgegeven lengte maar dat hij eigenlijk niet langer kan worden dan bijvoorbeeld 255 dan kun je eens proberen om de string als max 255 lang op te geven met string[255](in delphi weer)

[ Voor 21% gewijzigd door Verwijderd op 31-03-2003 21:20 ]

[Verwijderd]

Het is een lijst van ints. Dus ik zou eigenlijk iets moeten doen als lijst.Length=300000 en dan daarna pas als ik dus minder ruimte nodig heb het echte aantal elementen dat ik nodig heb moeten zetten als lengte.

Klopt het dus dat nadat de lengthproperty is gezet er ook echt zoveel vrij geheugen beschikbaar komt?

Dan nog een reactie: Ik zei dat ik minder dan 200 MB geheugen heb, daarmee bedoel ik intern geheugen en niet het geheugen dat in mijn swap zou kunnen staan.

[MSalters]

Je zou andere data structuren kunnen overwegen. std::vector heeft bijvoorbeeld een reserve, daar kun je gewoon opgeven hoeveel geheugen er gereserveerd moet worden (uitgedrukt in aantal objecten, niet bytes.) std::deque deelt onder water de array op in pagina's, en die hoeft dus niet alle 300000 elementen te kopieren als je int #300001 toevoegt.

[RickN]

Een bekende strategie bij een dynamisch array is om de lengte ervan te verdubbelen op het moment dat het array vol zit en de lengte te halveren op het moment dat ie voor minder dan een kwart vol zit.

Maar, zoals MSalters al zei, meestal zit er wel een geschikte datastructuur in de STL.

[ Voor 19% gewijzigd door RickN op 01-04-2003 10:07 ]

[Verwijderd]

Maar om mijn vraag te herhalen: Klopt het dus dat nadat de lengthproperty is gezet er ook echt zoveel vrij geheugen beschikbaar komt? Geheugen dat ik wel snel kan gebruiken?

[LordLarry]

Ja, dat maakt het ook meteen langzaam.

[Creepy]

Verwijderd schreef op 01 april 2003 @ 13:38:
Maar om mijn vraag te herhalen: Klopt het dus dat nadat de lengthproperty is gezet er ook echt zoveel vrij geheugen beschikbaar komt? Geheugen dat ik wel snel kan gebruiken?

Ligt eraan om hoeveel je vraagt. Als een programma aan het OS vraagt om bakken met geheugen gaat het meer zo van

"Ow.. dus jij wilt veel geheugen?? Sure.. Hier heb je genoeg.."
(stiekum krijg je veel minder, en gaat het OS zich pas zorgen maken als je het ook daadwerkelijk gaat gebruiken)