[Delphi]Grote array of array of integer, out of memory

[Oscar Mopperkont]

Ik heb in Delphi de volgende array:

Delphi:

type
  CombinatieArray = Array of array of integer;

....

var
  CombinatieGegevens : CombinatieArray;

....

procedure TfrMain.btnStartClick(Sender: TObject);
var
 i : Integer;
begin
...
Setlength(CombinatieGegevens, StrToInt(edtAantalArtikelen.Text), StrToInt(edtAantalArtikelen.Text));

Hierbij is edtAantalArtikelen 11848. Het wordt dus een array die 11848 bij 11848 groot is.

Delphi gaat nu op zijn bek als ik de setlength doe. Ik heb de stacks al 10 maal zo groot gemaakt, maar dat helpt niet. Hoe kan ik toch ervoor zorgen dat ik zo'n array kan aanmaken?

In de Array hoeft niets veranderd te worden, het is alleen een "database" waar ik na hem 1 keer vol te stoppen, alles uitlees. De getallen die ik inlees zijn niet zo groot, maximaal iets van 10.000.

[Woy]

Als de waarde niet zo groot is dan zou je er ook over kunnen denken om geen int te gebruiken maar een kleiner type. Ik weet niet precies hoe het in Delphi zit want dat ken ik niet. Maar een int is volgens mij 32 bits. Je zou bijvoorbeeld een 16 bits type kunnen gebruiken. Deze kan van ~-32000 tot ~32000 dus je al je getallen passen erin. Je zou natuurlijk ook nog een unsigned datatype kunnen gebruiken. Je gebruikt dan ieder geval nog maar de helft van het geheugen als bij het gebruik van een 32 bits datatype

[whoami]

Of een integer nu groot is of klein, hij neemt evenveel ruimte in.
100 neemt niet meer ruimte in dan 1.

Waarom hou je al die gegevens in memory? Waarom maak je geen gebruik van een database?
Jij wil hier gewoon 535mb memory alloceren.

[Oscar Mopperkont]

whoami schreef op 14 augustus 2003 @ 10:09:
Of een integer nu groot is of klein, hij neemt evenveel ruimte in.
100 neemt niet meer ruimte in dan 1.

Waarom hou je al die gegevens in memory? Waarom maak je geen gebruik van een database?
Jij wil hier gewoon 535mb memory alloceren.

Omdat ik die gegevens supervaak nodig heb, en het belangrijk is dat de gegevens razendsnel beschikbaar zijn.

Maar hoe kom je bij die 535mb aan geheugen? En is het idd niet mogelijk om ervoor te zorgen dat ie minder geheugen reserveert?

Ik sprak net mijn afstudeerdocent hierover, en die had het over dat ik var moest gebruiken, dat ie dan al veel minder geheugen zou gebruiken. Maar ikw eet niet prceis wat ie bedoelde en hij zat in een vergadering. Weet iemand waar hij misschien op doelde?

[ Voor 19% gewijzigd door Oscar Mopperkont op 14-08-2003 10:15 ]

[whoami]

Oscar Mopperkont schreef op 14 augustus 2003 @ 10:13:
[...]

Maar hoe kom je bij die 535mb aan geheugen? En is het idd niet mogelijk om ervoor te zorgen dat ie minder geheugen reserveert?

Een array van 11848 bij 11848 om integers in op te slaan:
Je wilt dus 11848 * 11848 integers opslaan. Een integer heeft 4 bytes nodig =
11848 * 11848 * 4 = 561500416 bytes = 535 mb.

Ik sprak net mijn afstudeerdocent hierover, en die had het over dat ik var moest gebruiken, dat ie dan al veel minder geheugen zou gebruiken. Maar ikw eet niet prceis wat ie bedoelde en hij zat in een vergadering. Weet iemand waar hij misschien op doelde?

Ik denk dat hij bedoeld dat je die array niet op de stack maar op de heap moet opslaan.

[P_de_B]

Ik heb niet zoveel verstand van Delphi, maar even uit nieuwsgierigheid, zou een array van ints niet _altijd_ op de stack geplaatst worden?

[whoami]

P_de_B schreef op 14 augustus 2003 @ 10:29:
Ik heb niet zoveel verstand van Delphi, maar even uit nieuwsgierigheid, zou een array van ints niet _altijd_ op de stack geplaatst worden?

Als je nu een array maakt van pointers naar int's , dan wordt die toch op de heap gemaakt?

[Oscar Mopperkont]

Mijn programma accepteert het nu wel, nu ik er een Array of Array of SmallInt van gemaakt heb.

Alleen is het natuurlijk wel weer een beperking dat ik er nu nog maar getallen tot 32768 in kan zetten.

Hoe zet ik de array op de heap? Want ik ben ook nog maar een n00b op gebied van Delphi.

[ATS]

11848*11848*4 bytes=535.5 MB...
Wat al zou helpen, zoals al eerder gesuggereerd, is het gebruiken van een kleiner datatype. E.e.a. is natuurlijk afhankelijk van wat je precies wil opslaan in de array. Je zegt dat dat getallen zijn tot maximaal 10.000. Dat betekent dat je het getal in 14 bits kwijt kan. Je hebt dus voldoende aan een 16 bits integer, die uit mijn hoofd short int heet in Dephi. Dat scheelt al de helft van je geheugenverbruik. Als je nog zuiniger wil zijn, dan kan je nog 2 bits per datapunt besparen door 4 14-bits getallen te mappen op 7 bytes. Je kan dan waarden opslaan tot 2^14, wat volgens je beschrijving groot genoeg is. Je moet dan wel wat meer moeite doen om je gegevens te lezen en te schijven (een tweetal functies schrijven), maar het levert je wel weer een besparing op van 33 MB ten opzichte van het gebruik van 16 bits.

Je moet je echt afvragen of dit wel de beste optie is. Op een machine met minder dan zo'n 700 MB geheugen (gokje) gaat je systeem toch swappen, waardoor je veel van je snelheid weer kwijtraakt. Het gebruik van een var (=een type waar je elk type variabele in kan opslaan) is het ergste wat je kan doen. Dit kost nog VEEL MEER geheugen, omdat hij ook overhead heeft om op te slaan wat voor type er in de var zit. Verder kan je eens kijken waar precies die getallen uit bestaan. Zijn ze (snel) af te leiden? Heb je echt het hele spectrum nodig, of is het bijvoorbeeld 100, 200, 300, 400... 10000? Dan kan je namelijk nog veel meer besparen! Als je zoveel datapunten kwijt moet, dan helpt elke bit...

[Verwijderd]

Misschien dat de methode die je gebruikt niet de beste oplossing is voor het probleem wat je moet oplossen. Waarvoor dient deze reusachtige array ? Misschien kunnen we je betere oplossingen aanbiedingen voor het probleem opzich.

[Woy]

Oscar Mopperkont schreef op 14 August 2003 @ 10:31:
Mijn programma accepteert het nu wel, nu ik er een Array of Array of SmallInt van gemaakt heb.

Alleen is het natuurlijk wel weer een beperking dat ik er nu nog maar getallen tot 32768 in kan zetten.

Hoe zet ik de array op de heap? Want ik ben ook nog maar een n00b op gebied van Delphi.

Als dat een beperking is en je hebt bijvoorbeel geen negatieve getallen kan je ook zoals ik al eerder zij een unsigned type gebruiken dan kan je tot het dubbele gaan. Ik weet overigens niet of Delphi ook unsigned types kent maar daar valt natuurlijk altijd zelf iets voor te verzinnen.
Ik weet natuurlijk niet precies wat het doel van je programma is maar is er geen andere manier om deze gegevens in te lezen. Dus bijvoorbeeld per blok van 100 * 100 ( Of een andere grootte ). Of dit mogelijk is hangt natuurlijk helemaal af van wat je wilt bereiken.

[Oscar Mopperkont]

Met die smallint aanpassing werkt het dus wel, maar hij gaat idd swappen, omdat ik op deze pc maar 256mb geheugen heb
Belachelijkweinig natuurlijk, maarja het is er één op mijn werkplek dus ik kan er niks aan doen.

Wat wel weer zo is, is dat de array een hoop lege plekken heeft. Is daar niet nog iets mee te doen? Dat ie de array achteraf bestudeert op lege plekken ofzo, en die dan vrij maakt? Ik zeg maar wat, want dat zel wel niet kunnen.

Er zit overigens geen logica in de getallen. Ze zitten in een range van 1...7011

En ik heb er inmiddels overigens het type "word" vangemaakt, dat si een unsigned type dat van 0...65535 loopt, is voorlopig zat denk ik.

[ Voor 12% gewijzigd door Oscar Mopperkont op 14-08-2003 10:56 ]

[whoami]

Ik zou het toch maar in een DB opslaan.

Als je er berekeningen moet op uitvoeren, kan je de DB - server die berekeningen laten uitvoeren, en het resultaat dan teruggeven.
En een simpele select van de gegevens die je nodig hebt, kan ook wel best snel gaan hoor...

[ATS]

Hoe veel is veel als je het hebt over lege plekken? In % van het aantal datapunten? Als het er veel zijn, dan is er wel wat mee te doen denk ik. Ook als het dataseries zijn waarbij de getallen meestal weinig verschillen van het voorgaande getal, dan kan je efficiënter werken... Bovendien kan je toe met 13 bits! Scheelt weer een bitje...

[edit] Nog een tip: maak gebruik van een accessfunctie (eventueel gedefinieerd als macro (kan dat in Delphi?)). Deze kan je gewoon een punt uit je array laten teruggeven/schrijven, maar op het moment dat besluit dat je toch wat efficiënters wil gaan gebruiken, dan hoef je alleen maar deze functies aan te passen in plaats van je hele programma...

[ Voor 35% gewijzigd door ATS op 14-08-2003 11:12 ]

[Oscar Mopperkont]

ATS schreef op 14 augustus 2003 @ 11:00:
Hoe veel is veel als je het hebt over lege plekken? In % van het aantal datapunten? Als het er veel zijn, dan is er wel wat mee te doen denk ik. Ook als het dataseries zijn waarbij de getallen meestal weinig verschillen van het voorgaande getal, dan kan je efficiënter werken... Bovendien kan je toe met 13 bits! Scheelt weer een bitje...

Ik haal de gegevens die ik in die array zet uit een notepad file die 45mb groot is. Daar staan dus lang niet 11848*11848 regels in. Zal zo ff laten tellen, mijn proggie is druk bezig met swappen....
Het zijn 1417465 regels., dus er wordt maar een lullige 1 % van die array gebruikt. Maar er zit geen logica achter welke 99% dan niet gebruikt wordt.


Maar hoe zou ik wat kunnen doen met die lege plekken? Kun je zeggen dat je voor die lege plekken nog maar 1 bitje toewijst ofzo? Dat is dus achteraf ff de array langsloopt en hem verkleint?

[ Voor 10% gewijzigd door Oscar Mopperkont op 14-08-2003 11:28 ]

[hammerhead]

Kun je dan niet beter gebruik van maken als iets van een HashMap (heet zo in Java, maar neem aan dat er ook wel zoiets voor Delphi is.) Wat je dan nog zou kunnen doen is het 2-D index (11848 x 11848) verhaal eerst nog even omzetten naar een 1-D index door middel van functie:
(a x b) => 11848 * a + b

Als je daar nu een hashSet voor gebruikt om het op te slaan dan is dat als het goed redelijk snel en je slaat niet meer op dan nodig is (dus allerlei 0-waarden)

[Woy]

Als je veel lege plekken in je array heb kan je beter gebruik maken van linked listen in een linked list. Op deze manier kan je ook een soort van 2 dimensionale array maken. Je hoeft hier dan echter de lege velden niet in op te slaan. De toegang van je getallen wordt dan wel iets langzamer maar dit zal niet opwegen tegen de tijd van het swappen naar hd denk ik. Je zult wel je linked listen zo moeten maken dat de index van de positie bij word gehouden.

[Woy]

hammerhead schreef op 14 augustus 2003 @ 11:24:
Kun je dan niet beter gebruik van maken als iets van een HashMap (heet zo in Java, maar neem aan dat er ook wel zoiets voor Delphi is.) Wat je dan nog zou kunnen doen is het 2-D index (11848 x 11848) verhaal eerst nog even omzetten naar een 1-D index door middel van functie:
(a x b) => 11848 * a + b

Als je daar nu een hashSet voor gebruikt om het op te slaan dan is dat als het goed redelijk snel en je slaat niet meer op dan nodig is (dus allerlei 0-waarden)

Dat is inderdaad ook een optie die een stuk sneller lijkt. Hoewel dit niet meteen je geheugen probleem meteen oplost aangezien er in een hasmap ook lege velden zitten. Je zult dan even moeten kijken bij welke van de 2 er meer lege plekken inzitten. Het voordeel van een Hashmap is wel weer dat het opzoeken weer sneller is als de linked list methode.

edit:

Aangezien je maar 1% van je velden vult is het zeker ook een goede oplossing. Je zult wel even moeten kijken wat de idiale size voor je hashmap is.

[ Voor 9% gewijzigd door Woy op 14-08-2003 11:31 ]

[whoami]

rwb schreef op 14 August 2003 @ 11:26:
Als je veel lege plekken in je array heb kan je beter gebruik maken van linked listen in een linked list. Op deze manier kan je ook een soort van 2 dimensionale array maken. Je hoeft hier dan echter de lege velden niet in op te slaan. De toegang van je getallen wordt dan wel iets langzamer maar dit zal niet opwegen tegen de tijd van het swappen naar hd denk ik. Je zult wel je linked listen zo moeten maken dat de index van de positie bij word gehouden.

Als je dan het 700ste element wilt benaderen, moet je dan wel de 699 elementen die ervoor zitten ook uitlezen.

In Delphi heb je ook een TObjectList. Misschien moet je daar ook eens naar kijken.

[Oscar Mopperkont]

Ik zal ook eens naar TObjectList kijken. Maar stel nu dat ik 512mb erbij weet te regelen? Dan is dat toch eigenlijk de makkelijkste en snelste oplossing? Want dan staat het helemaal in het geheugen (mag ik toch hopen), en dan werkt zo'n array of array het snelst neem ik aan.

[hammerhead]

Het is misschien wel de makkelijkste en snelste oplossing. Totdat morgen ineens blijkt dat er 2xzoveel rijen en kolommen moeten komen met ongeveer hetzelfde vulpercentage. Dan is het toch echt veel makkelijker als je toch iets meer hebt nagedacht over geheugengebruik....

Ik vermoed namelijk dat een hashset in delphi ook wel ergens zal bestaan of dat er genoeg voorbeelden van in delphi zijn. Zeker met dit soort lage vulpercentages is dat waarschijnlijk toch een van de snelste en minst geheugendure opties, er vanuit gaande dat je de hash paramters een beetje goed kiest.

[Woy]

whoami schreef op 14 August 2003 @ 11:31:
[...]


Als je dan het 700ste element wilt benaderen, moet je dan wel de 699 elementen die ervoor zitten ook uitlezen.

In Delphi heb je ook een TObjectList. Misschien moet je daar ook eens naar kijken.

Ja inderdaad dit is een van de nadelen van deze aanpak. Dit natuurlijk alleen als alle object gevuld zijn. Je gaat natuurlijk geen lege elementen in je list zetten. Als er zo weinig elementen in zitten zul je relatief weinig stappen moeten maken voordat je bij het juiste object bent. Als het vaak voor komt dat in alle ( of bijna alle ) kollomen wel een element zit kan je natuurlijk ook een Array van LinkedLists nemen. Dan is de toegangs tijd voor de juiste LinkedList weer lager. Het ligt natuurlijk maar net aan wat het probleem precies is of deze oplossing bruikbaar en sneller of efficienter is.

[ATS]

Met een simpele array kan je van die lege plekken geen gebruik maken, maar wel als je een andere datastructuur kiest. Deze kan je dan alsnog via de gesuggereerde accessfuntie benaderen, dus dat hoeft geen bezwaar op te leveren. Als je 99% lege plekken hebt, dan kan het uit om eens goed na te denken over een handige structuur. Enkele opties:

1) Lookup table
Map je 11848*11848 op een 32 bits getal, en maak een datatype (longword, word). Sla je 'coordinaat' op in het longword (32 bits getal toch?) en je datapunt in het word (16 bits getal). Maak nu een array van dit datatype, met net zoveel entries als je nodig hebt. Nu kan je de lijst aflopen om het punt te vinden wat je nodig hebt. Dat is minder inefficieënt als het lijkt, zolang de lijst gesorteerd is op je key, in dit geval het longword. Je kan een punt vinden in O(log(n)/log(2)), wat voor jouw dataset op maximaal 20 stappen is (1,4 miljoen datapunten). Voor deze datastructuur heb je ongeveer 1,4M punten * 6 bytes = 8MB nodig. Dat is te overzien...

2) een andere mogelijkheid is het opzetten van een 2d datastructuur (past mooi in je datamodel). Is nog wat ingewikkelder, maar is wel nog wat sneller. Een mogelijkheid is bijvoorbeeld een quadtree. Dit werkt alsvolgt: je deelt je gebied op in vier gebieden: NW, NE, SW en SE. In elk van de vier vakjes kan je óf een datapunt opslaan, of opnieuw een indeling in vier delen. Hier kan je heel efficiënt in zoeken, zeker als de verdeling over je gebied niet gelijkmatig is (bijvoorbeeld: je hebt relatief veel punten met hoge coordinaten). Een variant is het introduceren van 'buckets': elke quadrant bevat een bucket, waar je een x-aantal datapunten in kan opslaan (16 bijvoorbeeld). Moeten er meer in, dan verdeel je het quadrant eerst weer in 4 quadranten, met in elk quadrant weer een bucket of een nieuwe onderverdeling in quadranten. Zo kan je tot een uitermate efficiënte structuur komen.

[edit]: zoals iemand hierboven al zei: voor dit soort grote structuren kan het écht uit om even goed na te denken over een efficiënte manier van opslaan en benaderen. Gewoon maar geheugen bijkopen is niet schaalbaar, een efficiënte datastructuur wel... In de vergelijking tussen de lookup-table hierboven en jouw array bij een verdubbeling van de arraygrootte (dus 23696*23696) heeft de simpele array 1071 MB nodig, en de lookup table 32 MB.

[ Voor 12% gewijzigd door ATS op 14-08-2003 11:51 ]

[LordLarry]

Oscar Mopperkont schreef op 14 August 2003 @ 10:13:
Ik sprak net mijn afstudeerdocent hierover, en die had het over dat ik var moest gebruiken, dat ie dan al veel minder geheugen zou gebruiken. Maar ikw eet niet prceis wat ie bedoelde en hij zat in een vergadering. Weet iemand waar hij misschien op doelde?

'var' of 'const' is alleen van invloed bij parameters waarbij je je array doorgeeft naar een andere functie en zorgt er voor dat er geen copy gemaakt wordt van je array, maar gewoon de pointer wordt doorgegeven. Dit hele verhaal gaat niet op bij dynamische array's zoals jij ze gebruikt. Die worden altijd als pointer doorgegeven. Zie ook [rml][ Delphi] Hoe wordt parameter aan procedure doorgegeven?[/rml].

Globale variabelen komen op de heap en lokale op de stack, maar dynamisch gereserveerd geheugen zoals objecten en dynamische array's komen zoiezo op de heap. Heeft dus niet veel met dit verhaal te doen.

Gewoon niet alles in het geheugen houden door het weg te schrijven naar bijvoorbeeld een database. Die zijn daarvoor geoptimaliseerd dus kunnen dat best goed aan. Anders idd je structuur zo klein als mogelijk houden. Of nog mooier, zoals ATS voorstelt.

[ Voor 5% gewijzigd door LordLarry op 14-08-2003 11:44 ]

[Oscar Mopperkont]

FF wat verduidelijken, mijn afstudeerdocent bedoelde met zijn var opmerking het volgende:

wat betreft die "var" opmerking, bedoelde ik niet (zoals iemand opmerkte) dat je de array als array of variant moet definieren. Variant is immers het "zwaarste" type. Ik bedoele dat wanneer je de array meegeeft aan een procedure of functie meegeeft, je er "var" voor zet, dus:

procedure dus(VAR x: array of....)

in plaats van

procedure dus(x: array of....)

Verder stelde hij het volgende voor:

Mocht je het daarmee nog niet redden dan moet je proberen een sparse-array type te definieren. Dit is een type dat geen lege ruimtes heeft, zoals in jouw vierkante array. Hier zijn hele libraries voor geschreven in pascal/delphi. Zoek maar eens in google naar "sparse arrays delphi" of "sparse arrays pascal".

ik ben momenteel weer even met wat anders bezig. Maar misschien is het voor sommigen een interessante tip.

[LordLarry]

Oscar Mopperkont schreef op 14 augustus 2003 @ 13:29:
Wat betreft die "var" opmerking, bedoelde ik niet (zoals iemand opmerkte) dat je de array als array of variant moet definieren. Variant is immers het "zwaarste" type. Ik bedoele dat wanneer je de array meegeeft aan een procedure of functie meegeeft, je er "var" voor zet, dus:

procedure dus(VAR x: array of....)

in plaats van

procedure dus(x: array of....)

Had ik het goed geraden. Maar zoals ik al uitlegde heeft dat geen invloed op Dynamische array's.

[ Voor 53% gewijzigd door LordLarry op 14-08-2003 13:35 . Reden: quote in quote ]

[farlane]

De oplossing die voor jou het beste is, is sterk afhankelijk van wat je met die gegevens moet gaan doen.

Dus, wat moet je ermee doen ?

[Oscar Mopperkont]

Het gaat om het verdelen van artikelen over verschillende zones in een magazijn.

Wat je wilt is dat artikelen die vaak bij elkaar in een order zitten, dat die bij elkaar in dezelfde zone liggen.

Nu haal ik uit een database het aantal keren dat artikelen met elkaar in een order voorkomen. Elke combinatie van artikelen kan in principe voorkomen, maar het hoeft niet.
Om deze gegevens op te slaan in het geheugen heb ik die array. Het aantal artikelen is 11848, de array moet dus 11848*11848 zijn.

Er zijn echter ongelofelijk veel combinaties die nooit bij elkaar voorkomen, vandaar dat ik maar in 1% van die array wat hoef neer te zetten.

Is het een beetje duidelijk zo? Of is het te veel TBK-taal?

[Verwijderd]

Kan je dan niet beter het volgende doen:\

code:

loop alle orders af:
    loop alle artikelen in een order af op artikelnr:
         plak de artikelnrs achterelkaar (als string -> strArtikelen).
   einde artikelen van order.
  
   zoek strArtikelen in lijst.
  
   als gevonden 
       verhoog aantal met 1
  anders
       voeg strArtikelen toe aan lijst 
       zet aantal op 1.
  einde als gevonden.

einde orders.

Dan heb je als resultaat een lijst met alle mogelijke artikelcombinatie's in een order, die je kan sorteren op aantal etc.

(ff snel verzonnen, zitten nog wat haken en ogen aan)

[ Voor 17% gewijzigd door Verwijderd op 14-08-2003 14:33 ]

[Verwijderd]

Oscar Mopperkont schreef op 14 August 2003 @ 14:11:
Het gaat om het verdelen van artikelen over verschillende zones in een magazijn.

Wat je wilt is dat artikelen die vaak bij elkaar in een order zitten, dat die bij elkaar in dezelfde zone liggen.

Nu haal ik uit een database het aantal keren dat artikelen met elkaar in een order voorkomen. Elke combinatie van artikelen kan in principe voorkomen, maar het hoeft niet.
Om deze gegevens op te slaan in het geheugen heb ik die array. Het aantal artikelen is 11848, de array moet dus 11848*11848 zijn.

Er zijn echter ongelofelijk veel combinaties die nooit bij elkaar voorkomen, vandaar dat ik maar in 1% van die array wat hoef neer te zetten.

Is het een beetje duidelijk zo? Of is het te veel TBK-taal?

Het zijn dus artikelen. Je weet dus niet of het er volgend jaar 100000 of nog meer zijn. Qua geheugen ga je dus waarschijnlijk de mist in.

Ik zie niet in waarom je dit in het geheugen wilt. Waarom wil je dit zo supersnel hebben? Wil je realtime je complete magazijn aanpassen
Als je het in een database zet kun je elke selectie maken die je wilt (ga er trouwens maar van uit dat dat zeker zo snel werkt als dat je het zelf in het geheugen gaat schrijven). Bovendien moet jij bij iedere start van het programma opnieuw alles in het geheugen gaan zetten. In de database blijft het gewoon staan.

[Oscar Mopperkont]

Verwijderd schreef op 14 augustus 2003 @ 14:49:
[...]


Het zijn dus artikelen. Je weet dus niet of het er volgend jaar 100000 of nog meer zijn. Qua geheugen ga je dus waarschijnlijk de mist in.

Ik zie niet in waarom je dit in het geheugen wilt. Waarom wil je dit zo supersnel hebben? Wil je realtime je complete magazijn aanpassen
Als je het in een database zet kun je elke selectie maken die je wilt (ga er trouwens maar van uit dat dat zeker zo snel werkt als dat je het zelf in het geheugen gaat schrijven). Bovendien moet jij bij iedere start van het programma opnieuw alles in het geheugen gaan zetten. In de database blijft het gewoon staan.

Ik wil het supersnel hebben, omdat ik een indeling maak. Vervolgens ga ik ongelofelijk veel alternatieve indelingen genereren, en daarvan moet ik weten hoeveel "combinaties" er liggen in een zone. Vandaar.

[Verwijderd]

Oscar Mopperkont schreef op 14 augustus 2003 @ 14:54:
[...]


Ik wil het supersnel hebben, omdat ik een indeling maak. Vervolgens ga ik ongelofelijk veel alternatieve indelingen genereren, en daarvan moet ik weten hoeveel "combinaties" er liggen in een zone. Vandaar.

En als je nu eens alle combinaties eenmalig uitrekent en opslaat in de database?
Dan kun je ze daarna gebruiken naar hartelust.

Nog beter is natuurlijk om een algoritme te maken wat de perfecte indeling voor je genereerd. Dus niet alle mogelijke indelingen genereren en dan kijken welke het beste is, maar gewoon de beste genereren.
Misschien wat ingewikkeld, maar het kan wel denk ik.

Mocht je dit niet doen, zou je wel kunnen overwegen om een simpele vorm van het algoritme te gebruiken, om de meest slechte er meteen uit te filteren, zodat je die er niet zelf hoeft uit te halen.

[ATS]

In één keer naar 100.000 artikelen groeien zal wel meevallen, maar het is wel handig om rekening te houden met meer artikelen dan 11.848. 16 bits zou aardig zijn (65535, als je 0 niet gebruikt).
Een optimalisatie die je in ieder geval kan doen is dat je maar de helft van je array nodig hebt. Immers: als in een bestelling artikel a en artikel b samen voorkomen, dan moeten punt (a,b) en (b,a) hetzelfde zijn. Die moet je dus niet dubbel in je dataset hebben. Je krijgt dus een driehoekige dataset. Dat scheelt je weer de helft van je geheugengebruik als je daar rekening mee houdt...
Wel moet je er rekening mee houden dat je getallen groter gaan worden dan je eerder genoemde 7800... Dat betekent dat je minstens 16 bits, maar liever nog meer wil kunnen verwerken. Doe je dat in een eenvoudige array dan krijg je dus je geheugenprobleem weer keihard terug. Toch tijd voor een betere structuur... De door mij eerder voorgestelde quadtree valt daarbij natuurlijk af, omdat je coordinaten niet rechthoekig zijn. De lookup-table werkt wel. Eventueel kan je die nog wel wat verder tweaken als dat nodig is... Hij is bovendien veel eenvoudiger te programmeren dan de quadtree

Overigens vraag ik me af of je niet beter een statistisch pakket kan gebruiken voor je analyse. SPSS ofzo... Die kan je zo vertellen hoe sterk te correlaties tussen de diverse artikelen zijn voor zover ik weet.

[Verwijderd]

ATS schreef op 14 August 2003 @ 15:24:
In één keer naar 100.000 artikelen groeien zal wel meevallen, maar het is wel handig om rekening te houden met meer artikelen dan 11.848. 16 bits zou aardig zijn (65535, als je 0 niet gebruikt).

idd, maar 't was maar 'ns voorbeeldje om aan te geven dat je meteen je grenzen hard neerzet. Maar 16 bits is genoeg, zoals hierboven ook al geadviseerd was.

Een optimalisatie die je in ieder geval kan doen is dat je maar de helft van je array nodig hebt. Immers: als in een bestelling artikel a en artikel b samen voorkomen, dan moeten punt (a,b) en (b,a) hetzelfde zijn. Die moet je dus niet dubbel in je dataset hebben. Je krijgt dus een driehoekige dataset. Dat scheelt je weer de helft van je geheugengebruik als je daar rekening mee houdt...

Dat is een goed idee idd.
Het is zelfs nog minder dan de helft. a=b hoef je natuurlijk ook niet op te slaan. Dan hadden ze wel gewoon 2a of 2b besteld

[alienfruit]

Waarom kijk niet naar een CDS, lijkt me wel handig voor dit. Heb je ook niet een hele zware database nodig

[Oscar Mopperkont]

ATS schreef op 14 August 2003 @ 15:24:
Overigens vraag ik me af of je niet beter een statistisch pakket kan gebruiken voor je analyse. SPSS ofzo... Die kan je zo vertellen hoe sterk te correlaties tussen de diverse artikelen zijn voor zover ik weet.

Er is geen sprake van een analyse. Het is een optimaliseringsprobleem. Er zijn zo ongeveer oneindig veel mogelijkheden om artikelen te verdelen over een magazijn. Ik gebruik een zoekalgoritme om tot een goede oplossing te komen.

Daarvoor heb ik een oplossing, daarvan bereken ik (oa) hoeveel combinaties er voorkomen in een toewijzing. Ik heb bijvoorbeeld een "zone" waarin artikel a,b en c liggen. Dan zoek ik op hoe vaak artikel a en b, a en c, en b en c bij elkaar voorkomen en tel dat op.
Vervolgens pas ik de oplossing iets aan door artikelen te verwisselen van zone, en dan kijk hoeveel combinaties er dan liggen (bereken ik incrementeel, dus alleen de verandering). Dit doe ik echt super vaak miljoenen keren, dus daarom moet de tabel met combinaties snel toegankelijk zijn.

Ik hoop dat het nog een beetje te volgen is, want het is lastig te volgen als je een buitenstaander bent. (en ik ben ook niet echt een kampioen uitleggen )

[Verwijderd]

Kijk eens naar rekenprogramma's zoals MATLAB, die hebben gewoon functies om met sparse-array's om te gaan.
Beetje onzinnig om het wiel weer opnieuw uit te vinden door het in Delphi te gaan programmeren.

[ATS]

Het lijkt me toch handig om niet in het wilde weg te gaan zoeken naar oplossingen, maar wél je dataset te analyseren. Zo kan je in ieder geval je zoekruimte beperken. Je kan bijvorobeeld oplossingen waarbij de producten een hoge correlatie hebben prefereren boven die waar die correlatie minder sterk is.
SPSS kan overigens zelfs zelf clusteren...

[Oscar Mopperkont]

Verwijderd schreef op 14 augustus 2003 @ 15:48:
Kijk eens naar rekenprogramma's zoals MATLAB, die hebben gewoon functies om met sparse-array's om te gaan.
Beetje onzinnig om het wiel weer opnieuw uit te vinden door het in Delphi te gaan programmeren.

Geloof me, ik vind het wiel niet opnieuw uit.

[Janoz]

Toch zou ik aanraden om of over te stappen op matlab (achtig iets) of gebruik te maken van een datastructuur die iets zuiniger met geheugen omgaat.

De eerste optie ga ik je niet opdringen aangezien je al duidelijk voor een eigen implementatie in delphi hebt gekozen dus richt ik me even op de tweede.

Je geeft duidelijk aan dat snelheid je beperkende factor is. Een datastructuur die de ruimte efficient benut hoeft helemaal niet langzamer te zijn. Deze kan zelfs een stuk sneller zijn (door bv cache trashing). Zoals eerder aangegeven zijn er een heleboel intressante datastructuren te bedenken zonder nutteloos geheugen te bezetten en waarbij een logaritmische zoektijd mogenlijk is.

Man, als je een binaire zoekboom maakt met een 32bit sleutel waarin je in de 16 lsb's de X-waarde en in de 16 msb's de Y-waarde opslaat. en vervolgens een functie die met een gegeven x en y waarde de boom doorzoekt (in logaritmische tijd) en de waarde van de node of, bij niet gevonden, 0 teruggeeft en ten slote ook een invoeg methode schrijft die bij gegeven x en y op de juiste positie een nieuwe node aanmaakt,/ bestaande vervangt hoef je aan de rest van je programma helemaal niks te veranderen!

Het enige waar je nog rekening mee moet houden is dat je de boel gebalanceerd houdt. Waarschijnlijk zit zo'n structuur wel standaard in Delphi, en als die er niet is zijn er op internet vast wel 1000 + 1 implementaties te vinden.

[freddifish]

hier heeft iemand het werk voor een simpele sparse array al voor je gedaan...
http://www.peter3.com/Freestuff/Sparse.zip
Hij gebruikt een Tstringlist met daaraan gekoppeld objecten, in mijn ervaring is de stringlist een van de snelste delphi native componenents

Description:
A very simple sparse array.
How it works:
A pseudo 2D array is maintained as a sparse array by converting Col / Row
info to a string representation and adding these along with a TObject reference
to a sorted TStringlist. Retrieving and adding objects is done after checking
the Array with the IndexOf function of the Tstringlist.
If CheckBounds is true, an Exception is raised if the index for Row or Col
are less than 0 or more than Row and Col defined in the constructor.

[farlane]

Is het dan niet handiger om een soort multiset te gebruiken ?

Dwz, een verzameling obecten die gesorteerd worden op basis van een criterium ( het aantal keren dat ze voorkomen ).

Het object zou dan zelf bijhouden welke combinatie van producten het bevat, en hoevaak het voorkomt. ( Zeg maar een struct met een fixed size array voor de productnummers, en een count veld. Ik zeg fixed size, want volgens mij hoef je niet te zoeken op combinaties van 1000 producten, afhankelijk van het aantal zones en het aantal producten in een zone )

Je zou dan de verzameling kunnen beperken tot de bovenste X combinaties, afhankelijk tot waar het nog interessant is om moeite en tijd te steken in het bij elkaar houden van de producten.

[Varienaja]

Volgens mij he.. als je 11.000 artikelen hebt, en je gaat maar een beetje schuiven met die dingen zodat je de 'beste' indeling vind ben je helemaal verkeerd bezig.

Het aantal mogelijke indelingen gaat ieder voorstellingsvermogen te boven, en een pc kan dit ook niet uitrekenen. Maakt niet uit hoe efficient (snel, groot) je geheugen is.

Voor dit soort optimalisatieproblemen gebruikt met heuristieken; oplossings-algoritmen die niet botweg alle mogelijkheden uitproberen, maar algoritmen die wat slimmer proberen zo dicht mogelijk bij het doel te komen.

Had je daar al over nagedacht?

[Macros]

Gebruik gewoon standaard Spare Matrix libraries. Deze zijn er voor elke taal.
Waarom zou je het wiel opnieuw uitvinden?

[Oscar Mopperkont]

Varienaja schreef op 14 August 2003 @ 22:04:
Volgens mij he.. als je 11.000 artikelen hebt, en je gaat maar een beetje schuiven met die dingen zodat je de 'beste' indeling vind ben je helemaal verkeerd bezig.

Het aantal mogelijke indelingen gaat ieder voorstellingsvermogen te boven, en een pc kan dit ook niet uitrekenen. Maakt niet uit hoe efficient (snel, groot) je geheugen is.

Voor dit soort optimalisatieproblemen gebruikt met heuristieken; oplossings-algoritmen die niet botweg alle mogelijkheden uitproberen, maar algoritmen die wat slimmer proberen zo dicht mogelijk bij het doel te komen.

Had je daar al over nagedacht?

Alle mogelijkheden enumereren is idd onmogelijk daar heb je ongeveer oneindige tijd voor nodig.

Dus ik gebruik simulated annealing, een lokaal zoekalgoritme dat in staat is om uit lokale minima te ontsnappen. het begint als local search, en de kans dat een verslechtering geaccepteerd word wordt steeds kleiner. Op het einde worden alleen nog verbeteringen geaccepteerd en is het dus een local search.