List of combinations

Got a LiveCode personal license? Are you a beginner, hobbyist or educator that's new to LiveCode? This forum is the place to go for help getting started. Welcome!

Moderators: FourthWorld, heatherlaine, Klaus, kevinmiller

MaxV
Posts: 1580
Joined: Tue May 28, 2013 2:20 pm
Contact:

Re: List of combinations

Post by MaxV » Fri Jan 27, 2017 2:19 pm

Hi,
probably I missed something, but...
how can I parrallel a repeat loop? I have computers from 4 to 8 CPUs, and I'd like to use them all to shorten the computation time.
Livecode Wiki: http://livecode.wikia.com
My blog: https://livecode-blogger.blogspot.com
To post code use this: http://tinyurl.com/ogp6d5w

[-hh]
VIP Livecode Opensource Backer
VIP Livecode Opensource Backer
Posts: 2262
Joined: Thu Feb 28, 2013 11:52 pm

Re: List of combinations

Post by [-hh] » Fri Jan 27, 2017 2:42 pm

You have now an inductive method with file i/o and also a direct recursive method.

You can also start the induction at higher n than 1 by computing combin(n,k) 'directly' with the recursive method for all k for that fixed n and then use the inductive method.

So you have only to manage the file I/O between your CPUs and prepare hundreds of TeraBytes of disk space.

That's like in real life: 60-70% is administration only and 30-40% do the job.
shiftLock happens

MaxV
Posts: 1580
Joined: Tue May 28, 2013 2:20 pm
Contact:

Re: List of combinations

Post by MaxV » Mon Jan 30, 2017 2:34 pm

[-hh] wrote:I was asked to script the "inductive law" for building lists of combinations.
So here it is.
...
Now have fun!
Well, I just understand your code, this is what it does, I suppose:
  1. buildcombiBib n create files to reduce calculations, it creates ALL Image combinations from k=1 to k=n
  2. inductiveCombi a looks for files created from buildcombiBib n to create the next file for combinations. It creates just the next combinations file.
Files are named like out(003of009).txt, that means Image.
So, it would speed up calculation only if I launch many times inductiveCombi n, but just if I already I know to have the previous files.
Is it right?
If so, it take more time than a normal nested repeat loops. If I have 8 CPU, I have 7 sleeping and just one working.

It would be better for any occasion that I could use:

Code: Select all

repeat..
  repeat..
    repeat...
     do this commands on the first CPU available
     ....
    end repeat
  end repeat 
end repeat
Livecode Wiki: http://livecode.wikia.com
My blog: https://livecode-blogger.blogspot.com
To post code use this: http://tinyurl.com/ogp6d5w

FourthWorld
VIP Livecode Opensource Backer
VIP Livecode Opensource Backer
Posts: 10052
Joined: Sat Apr 08, 2006 7:05 am
Contact:

Re: List of combinations

Post by FourthWorld » Mon Jan 30, 2017 3:56 pm

[-hh] wrote:@FourthWorld
FourthWorld wrote:Why have file I/O inside the loop?
When computing combin(n,k) for k=ceil(n/2) you are, roughly, doubling the size of combin(n-1,k) for k=ceil((n-1)/2).

combin(19,10) has size 2.3 Mbyte
combin(20,10) has size 4.7 MByte
combin(21,11) has size 10.0 MByte
combin(22,11) has size 20.1 MByte

Around (n=32,k=16) you will have crossed 1 GByte size for combin(n,k).
And combin(33,17) is built using combin(32,17) and combin(32,16) ...
And combin(42,21) alone may go close to the limit of your hardware resources (has 538257874440 lines of roughly length 100 each).

If you go high enough, this I/O must be even splitted into parts of files inside the repeat. And other 'compressed' methods of data storing (not decimal bytewise but bitwise) should come in.
Good point on file I/O, but it raises the question: how is this large output to be used? What is the goal of this exercise?
Richard Gaskin
LiveCode development, training, and consulting services: Fourth World Systems
LiveCode Group on Facebook
LiveCode Group on LinkedIn

[-hh]
VIP Livecode Opensource Backer
VIP Livecode Opensource Backer
Posts: 2262
Joined: Thu Feb 28, 2013 11:52 pm

Re: List of combinations

Post by [-hh] » Mon Jan 30, 2017 4:32 pm

@MaxV
inductivecombi n computes a full single step n->n+1:
It needs the files n over k for k=0,...,n as input and computes the files (n+1) over k for k=0,...,n+1.

The input files n over k for k=0,...,n can also be computed directly (using the recursive method).

So, for example
  • CPU 1 computes n over k for all k<=n and n up to 20 using inductivecombi.
  • CPU 2 starts with n=20 and computes first directly (using the recursive method)
    20 over k for k=0,..,20 and then, with inductivecombi, n over k for all k<=n and n from 21 up to 25.
  • CPU 3 starts with n=26 and computes first directly (using the recursive method)
    26 over k for k=0,..,26 and then, with inductivecombi, n over k for all k<=n and n from 27 up to 30.
  • ....
You have to find out the optimal "steps" for that.

Or use two CPUs for the direct computations when k is near n/2.

And you need at least one CPU for administrating the callbacks and the queuing of the jobs. And you have soon to split the files if you don't have TeraBytes of RAM.

@FourthWorld
FourthWorld wrote:Good point on file I/O, but it raises the question: how is this large output to be used? What is the goal of this exercise?
combin(42,21) alone has length (538257874440 lines of roughly length 60 each*) > 32 Terabytes ... It's a 'virtual' exercise only.

___________
length 100 was wrong, sorry.
shiftLock happens

Post Reply