_ArrayCombinations Error Allocating Memory

[millisys]

Hi folks,

I am trying to create combinations from a TXT file that has 41 records. I am using a combination set size of 6, thus generating 4,496,388 possible combinations. I have 8GB of ram and am running Windows 7 with Service Pack 1. I am receiving the "Error Allocating Memory" dialog before the function completes. At the time of error allocating memory message, the memory used is 4.78GB.

Here is the code that I am using:

#include <file.au3>
Local $aArray = FileReadToArray("records.txt")
Local $aArrayCombo = _ArrayCombinations($aArray, 6, ";")

I have tried using WinXP, turning the Paging File on or off, yet the results are the same.

Does anyone know of a way to release the ram during the building of the combinations? Or some other solution? Thank you for your help.

[jchd]

What is the size of your records?

Said otherwise: do you realise that your answer will consist of an array containing 4,496,388 strings, each of size (6 times the average size of your records + 5 separators) times 2 (characters use 16-bits for AutoIt Unicode encoding) bytes?

Since you exceed memory limits by appending records this way, what you can do is build an array of indices 0..40, compute the combinations on indices and StringSplit each combination to obtain an array of line indices for that combination, which will allow you to do whatever you need to do with corresponding lines.

This way you only need something around 4496388 * (6 * 2 + 5 * 2) = 98920536 bytes, not including internal array structures.

Edited August 21, 2014 by jchd

[millisys]

Hi jchd,

Thank you for your reply. I considered this as well, but am not sure that splitting a combination would result in the same output. Do you have an example with a smaller sample as a working model? Thank you.

[jchd]

Why do you believe so?

Try this:

#include <Array.au3>

Local Const $iSetSize = 19      ; 41 in real runs (takes longer to compute!)
Local Const $iSubSetSize = 6

Local $aRecords[$iSetSize]      ; normally created by FileReadToArray($yourfile)
Local $aRecordIndices[$iSetSize]
For $i = 0 To $iSetSize - 1
    $aRecords[$i] = 'This is "record" number ' & $i + 1 & ', an example content which, as you can see, contains nothing but dummy prose.'
    $aRecordIndices[$i] = $i
Next

ConsoleWrite("Please wait until combination indices are computed... ")
Local $aCombinations = _ArrayCombinations($aRecordIndices, $iSubSetSize, ';')
ConsoleWrite(UBound($aCombinations) & " combinations computed." & @LF & @LF)

Local $n
Local $aIndicesInCombination
Local $limit = UBound($aCombinations) - 1       ; only used for randomizing samples
; show how to manage $aRecords thru indices in random combinations that got computed in $aCombinations
For $i = 1 To 3
    $n = Random(0, $limit, 1)
    ConsoleWrite(">>> Displaying combination number " & $n + 1 & @LF)
    $aIndicesInCombination = StringSplit($aCombinations[$n], ';')
    For $j = 1 To $iSubSetSize
        ConsoleWrite($aRecords[$aIndicesInCombination[$j]] & @LF)
    Next
    ConsoleWrite(@LF)
Next

; free this large array as soon as it is not needed any more
$aRecordIndices = 0

[millisys]

Hi jchd,

Thank you for your reply. Unfortunately I still receive the Error Allocating Memory message.

The records that I am using are quite long per line. For example, this is the first line of the records.txt file. I have attached the records.txt file as well:

#001(2.42) #002(0.96) #004(0.00) #007(-6.67) #015(-4.20) #005(2.37) #006(1.78) #003(0.72) #033(1.80) #028(5.98) #029(-1.50) #017(-10.20) #009(3.38) #013(0.70) #010(0.49) #032(12.75) #019(0.06) #008(-3.01) #011(-1.95) #023(0.75) #020(0.78) #012(3.06)

It seems like it would be ideal if the script could write the combinations to a TXT file as it develops the combinations rather than holding them in ram the whole time until completion. Any ideas? Thank you.

records.txt

[jchd]

I don't know what you've tried, but this works:

expandcollapse popup

#include <Array.au3>
#include <File.au3>
#include <WinApiEx.au3>

Local Const $iSubSetSize = 6

Local $aRecords
_FileReadToArray("records.txt", $aRecords, $FRTA_NOCOUNT + $FRTA_ENTIRESPLIT)
Local $iSetSize = UBound($aRecords)
Local $aRecordIndices[$iSetSize]
For $i = 0 To $iSetSize - 1
    $aRecordIndices[$i] = $i
Next

Local $iWSSbefore = _WinAPI_GetProcessMemoryInfo()[2]

ConsoleWrite("Please wait until combination indices are computed... ")
Local $aCombinations = _ArrayCombinations($aRecordIndices, $iSubSetSize, ';')
ConsoleWrite(UBound($aCombinations) & " combinations computed." & @LF & @LF)

Local $n
Local $aIndicesInCombination
Local $limit = UBound($aCombinations) - 1       ; only used for randomizing samples
; show how to manage $aRecords thru indices in random combinations that got computed in $aCombinations
For $i = 1 To 3
    $n = Random(0, $limit, 1)
    ConsoleWrite(">>> Displaying combination number " & $n + 1 & @LF)
    $aIndicesInCombination = StringSplit($aCombinations[$n], ';')
    For $j = 1 To $iSubSetSize
        ConsoleWrite($aRecords[$aIndicesInCombination[$j]] & @LF)
    Next
    ConsoleWrite(@LF)
Next

ConsoleWrite("Script is using " & _WinAPI_GetProcessMemoryInfo()[2] - $iWSSbefore & " bytes." & @LF)

; free this large array as soon as it is not needed any more
$aRecordIndices = 0

and produces that:

Please wait until combination indices are computed... 4496389 combinations computed.

>>> Displaying combination number 4172881
#007(-6.67) #018(0.81) #015(-4.20) #021(-7.61) #019(0.06) #011(-1.95) #014(-0.73)
#001(2.42) #002(0.96) #018(0.81) #016(2.32) #021(-7.61) #022(-3.08) #012(3.06)
#001(2.42) #004(0.00) #007(-6.67) #024(-3.33) #016(2.32) #003(0.72) #009(3.38) #030(-2.37) #010(0.49) #032(12.75) #031(-2.15) #011(-1.95) #023(0.75) #020(0.78)
#001(2.42) #002(0.96) #018(0.81) #003(0.72) #009(3.38) #013(0.70) #032(12.75) #019(0.06) #008(-3.01) #011(-1.95) #020(0.78) #012(3.06)
#019(0.06)
#001(2.42) #002(0.96) #004(0.00) #007(-6.67) #024(-3.33) #018(0.81) #015(-4.20) #005(2.37) #006(1.78) #016(2.32) #003(0.72) #017(-10.20) #021(-7.61) #009(3.38) #022(-3.08) #013(0.70) #010(0.49) #032(12.75) #019(0.06) #008(-3.01) #011(-1.95) #014(-0.73) #023(0.75) #020(0.78) #012(3.06)

>>> Displaying combination number 3233847
#003(0.72)
#001(2.42) #002(0.96) #004(0.00) #018(0.81) #003(0.72) #009(3.38) #032(12.75) #019(0.06) #008(-3.01) #011(-1.95) #020(0.78)
#001(2.42) #018(0.81) #015(-4.20) #019(0.06) #008(-3.01) #011(-1.95) #014(-0.73)
#008(-3.01) #023(0.75)
#002(0.96)
#001(2.42) #027(2.13) #026(2.89) #028(5.98) #029(-1.50) #022(-3.08) #030(-2.37) #034(-1.70) #023(0.75)

>>> Displaying combination number 2346378
#002(0.96) #004(0.00) #005(2.37) #009(3.38) #010(0.49) #008(-3.01) #011(-1.95) #012(3.06)
#004(0.00) #005(2.37) #006(1.78) #003(0.72) #013(0.70) #008(-3.01)
#001(2.42) #004(0.00) #007(-6.67) #024(-3.33) #003(0.72) #009(3.38) #010(0.49) #032(12.75) #011(-1.95) #023(0.75) #020(0.78)
#001(2.42) #002(0.96) #018(0.81) #003(0.72) #009(3.38) #013(0.70) #032(12.75) #019(0.06) #008(-3.01) #011(-1.95) #020(0.78) #012(3.06)
#001(2.42) #022(-3.08) #023(0.75)
#001(2.42) #002(0.96) #024(-3.33) #018(0.81) #015(-4.20) #006(1.78) #016(2.32) #003(0.72) #021(-7.61) #009(3.38) #022(-3.08) #010(0.49) #008(-3.01) #011(-1.95) #014(-0.73) #020(0.78) #012(3.06)

Script is using 559702016 bytes.

roughly 533 Mb used.

[millisys]

Ok, I see. Very cool. You are using the _ArrayCombinations function to create an array of indicies which you reference later to build each individual combination.

 

I need to be able to create a TXT file of these combinations so I modified the ConsoleWrite to FileWrite the combinations to a TXT file but it takes several hours to write all of the combinations. Do you have a different method for writing the combinations to file that is faster? Thank you.

[jchd]

I left the processing to you, obviously, as I had no idea what you actually need to do with the text combinations.

About the processing time: let's see...

Your records.txt file is 4816 bytes. Every line will appear the same number of time in the combinations. So you're writing 4496388 * 4816 / 42 * 6 =  3093514944 bytes (3.01 Gb) to disk line by line. This is no surprise that outputing that guy is taking ages and I don't see a trick for cutting down write time significantly.

Then I wonder how you intend to further use such a huge flat text file in any efficient way. It would be much more appropriate to store both individual lines from records.txt and combination indices in two SQL tables and build text combination on the fly when they are needed. The standard SQLite UDF is a very good candidate for this task.

Anyway may I question the reason why you need all this? I don't see a practical use.

[BrewManNH]

Sounds like he's generating all possible combinations in a lottery or something similar.

[jchd]

Not so sure: positive and negative values, then those JSDA thingies...

[millisys]

Hi guys,

I had considered using SQLite but read that it was slower than using an array so I steered away from it. The goal is to optimize the arrangement/positioning of solar panels to maximize efficiency. Since we are dealing with thousands of panels, the combinations well exceed the 16 million limitation. We have tried using other data optimization software but it is too limited for our purposes. AutoIt allows us the flexibility that we seek and is more fun to work with.

My next question is how to exceed the 16 million max. Near as I can tell, we need around 96 million combinations. 

[jchd]

Fine but my main question remains: are you going to process/try/evaluate combinations one after the other? Then why store the combinations themselves? Storing the indices and the records is enough.

From this point of view you still should consider an SQLite DB. It can be loaded in memory (provided you only store combination of indices) and retrieve whatever combination number you want very fast. This way allows you to go well beyond the 2²⁴ cells limitation that our arrays have.

Also should some parameter of one or more solar panel change any day, changing the corresponding records (rows) will take millisecond but if all the raw input data is all bundled in text combinations (a poor choice for storing computational values BTW) changing one or more parameter(s) will take an engineer and significant work.

Last thought: wouldn't it be simpler to store actual panel characteristics and use some modeling software to perform optimization? Processing text isn't the premier choice in this context.

I'm willing to help/guide you as far as I can. But please don't tell me in few weeks that it's for a MMP game...

[millisys]

Hi jchd,

This might sound funny, but I don't even know what a MMP game is. I barely have any free time at all these days for anything resembling fun.

I am intrigued by the benefit of doing as you said and just storing the indices, and then processing the combinations one after the other.

Do you think that by using indices rather than creating one big array of combinations, that the 16 million combination limitation could be exceeded? Can SQLite help in this regard?

[jchd]

You can build Terabyte databases yet get very decent query times.

Selecting the right design for a DB implies some in-depth thinking about the best representation for data and making explicit relationships between entities. Also the type of queries envisionned impact the design as well. A well suited schema (DB design) is mandatory for satisfactory results over the long-term.

May I ask what the records mean (#015(-4.20) #035(5.58) JSDA(-3.77)) and how combining them works toward a meaningful result? PM if you don't want to make details public.

[millisys]

Hi jchd,

I will definitely look into SQLite. I have enjoyed the few times I have worked SQL and am interested in increasing my knowledge.

As an explanation as to what we are trying to do: It's a theory at this point, be we are noticing in individual instances that in addition to the evaluating the efficiency of possible arrangements of solar panels within a group, if we evaluate the possible arrangements of the groups within the whole field, the efficiency appears to improves even further. This is why the combinations include so many numbers and also why the numbers repeat themselves sometimes. We figure we should turn the problem over to computers to confirm or deny our theory.

 

We have over 1000 groups, so a small combination set size of just 3 puts the number of combinations over the 16M limit. Is there a way to break it into smaller groups of 100 x 3 and still create the same combinations that would have been created if the 16M limit didn't exist?

 

Thank you for your help

Edited August 28, 2014 by millisys

[jchd]

Some remarks:

1/ in the #001(2.42) format I assume that it refers to the "panel" or more generally "device" 001. I interpret the float value in parenthesis as a measure (maybe efficiency or something else) of said device. I also notice that every occurence of a given device carries the same measure.

I also would assume that the order of devices in a given record is meaningless.

This can be simplified for compact storage.

2/ you have duplicate records in your input. Again if I understand your context, you try to group various "records" by, say, combinations of 6 records.

Some combinations of records give the same combination of devices, so that helps cutting down the number of combinations to evaluate.

Once again, a more compact storage convention can be used.

Am I any close to a correct understanding?

If so, which computation would you perform on a given combination of devices?

[millisys]

You are correct, once measured the value stays the same - perhaps a variable could be used to represent that device. You are also correct that the order is irrelevant. Since there is a duplication of the combinations, I was using _ArrayUnique to remove those to decrease the array size. The values are negative and positive gain. For the computation, we are trying to find the combinations that result in the devices functioning as closely as possible to zero.

[jchd]

Fine!

Some more questions:

1/ are "records" the only possible arrangements for grouping devices or are we free to combine devices (not records) freely? Anyway, either by grouping panels freely or only predefined groups of panels, then the problem boils down to a knapsack problem for which we have known algorithms (01KP).

2/ how do you compute the gain of a given combination of devices? Is it just by summing up individual gain of each device in an attempt to get near zero?

3/ I guess that solutions of interest group the maximum number of devices. E.g. solution with only device #004(0.00) isn't very attractive. BTW, device #004 can be added to any solution as it is neutral.

4/ Is device JSDA different from the other?

Edited August 29, 2014 by jchd

[millisys]

Hi jchd,

Some answer to your quesions:

1] I would say yes, they are best regarded as records that are not free to combine

2] We calculate the weighted average to account for outliers

3] yes

4] JSDA is a manufacturer's name. I don't know why that one uses the MFR name instead of Device ID. Other people also use this data some maybe it means something to someone else. 

Thank you

[jchd]

Thanks for precisions, but I still need more.

How exactly do you "calculate the weighted average to account for outliers"?

Are the weights associated with individual devices or with groups (records) or some other cryptic way?

If the weights are associated with records, then how does that work when combining records which share common devices?

In all cases, this key information is missing from the posted data. Can you post it?

I've setup a database to model your problem but I'm stuck there to go further.

Edited September 3, 2014 by jchd