This is basically a search problem. You can improve the speed dramatically
by discarding paths that will be fruitless (pruning). Basically the only
"optimization" you have is with your upper_bound logic which eliminates some
duplicate effort since you don't want to include every permutation of the
same answer (for an answer of 3-2-1... you wouldn't allow search for and
find 3-1-2/2-3-1/2-1-3/1-3-2/1-2-3). So you do that at least, but you can
prune much more.
I modified your script a bit. I don't do much in sh, so forgive the mess; I
tried to follow the same style/conventions in the example you pasted. I'm
sure this can be improved more, algorithmically too with some more basic
pruning in addition to more efficient ways to kick off the recursion faster
in sh and parallel processing etc, but even with just this the difference is
significant.
On my laptop, your sh script with args 1728 8:
real 0m35.864s
user 0m9.997s
sys 0m21.301s
On my laptop, my sh script with args 1728 8:
real 0m0.911s
user 0m0.272s
sys 0m0.484s
Based on the numbers you posted, it should faster still on your computer.
1 #! /bin/sh
2 balls=$1
3 parts=$2
4 parts_so_far=$3
5
6 if [ "z$parts_so_far" = z ] ; then # if parts_so_far is empty,
7 # approximate max cube root, first time only
8 try_cubesize=`echo
"tmp=e(1/3*l($balls+$parts));scale=0;tmp/=1;tmp;"|bc -l`
9 else
10 try_cubesize=${parts_so_far##*\ } # last number in the list
11 fi
12
13 while [ $try_cubesize -gt 0 ] ; do
14 cubed=$((try_cubesize * try_cubesize * try_cubesize))
15 if [ $balls -gt $(($cubed * $parts)) ]; then # won't find more, abort
16 exit
17 fi
18 balls_left=$((balls - cubed))
19 if [ $balls_left -eq 0 -a $parts -eq 1 ] ; then # balls=0 && parts=1
20 echo "${parts_so_far#\ } $try_cubesize"
21 exit
22 fi
23 if [ $balls_left -gt 0 -a $parts -gt 1 ]; then
24 "$0" $balls_left $((parts - 1)) "$parts_so_far $try_cubesize"
25 fi
26 try_cubesize=$(( try_cubesize - 1 ))
27 done
Rather than work with every cube from 1 thru the cube root of $balls, I
worked top down to reduce the search space more quickly. If I'm ever in a
position where there are more $balls remaining than $parts * upper_limit, I
abort the search of that branch.
Only problem when working top down is deciding where to start. Bottom up
it's easy: you started at 1 (the smallest cube) and tried every number until
you reached a number that works out to be at or past the cube root. Top
down I could start from $balls down to 1, but it would be better to start
with the largest reasonable cube root of $balls. I generate a start value
based on an approximation of the cube root (calculated with bc). You could
optimize further by having subsequent try_cubesize set to last number in the
$parts_so_far list or the approximate cube root, whichever is smaller. I
didn't test much how expensive that call to bc is, so you'd want to test
performance of that approach before possibly "over-optimizing" like that.
Good luck,
~ Daniel
On Fri, Oct 9, 2009 at 9:31 PM, Eben King <eben01@verizon.net> wrote:
> I wanted to figure out how to divide a large number of things (such as
> http://cgi.ebay.com/_W0QQitemZ170371530405 ) into several smaller groups
> that could each be formed into a cube, and I had the bright idea that this
> would be suited to a recursive program. So I whipped up this script. Its
> syntax is like so:
>
> /tmp/ball-recurse 1728 8
> # objects --^ ^-- parts
>
> and it finds the first hit (8 cubes of side 6) in about 3.5s and all 13
> possibilities in 17-18s. The results come out sorted and uniq-ed
> automatically. Let me know where I have some inefficiency, please. I'm
> eyeing that "if" structure on lines 18-23 suspiciously, but I don't
> immediately see a problem. Is there a way to invoke sh quicker?
>
> 1 #! /bin/sh
> 2 balls=$1
> 3 parts=$2
> 4 parts_so_far=$3
> 5
> 6 if [ "z$parts_so_far" = z ] ; then # if parts_so_far is empty,
> 7 upper_bound=$balls # Way too big, but it'll do.
> 8 else
> 9 upper_bound=${parts_so_far##*\ } # last number in the list
> 10 fi
> 11
> 12 try_cubesize=1
> 13 while : ; do
> 14 balls_left=$((balls - try_cubesize * try_cubesize * try_cubesize))
> 15 if [ $balls_left -lt 0 -o $parts -lt 1 -o $try_cubesize -gt
> $upper_bound ] ; then
> 16 exit
> 17 fi
> 18 if [ $balls_left -eq 0 -a $parts -eq 1 ] ; then # balls=0 && parts=1
> 19 echo "${parts_so_far#\ } $try_cubesize"
> 20 exit
> 21 else
> 22 "$0" $balls_left $((parts - 1)) "$parts_so_far $try_cubesize"
> 23 fi
> 24 try_cubesize=$(( try_cubesize + 1 ))
> 25 done
>
> --
> -eben QebWenE01R@vTerYizUonI.nOetP royalty.mine.nu:81
>
> He who will not reason is a bigot; he who cannot is a fool;
> and he who dares not is a slave. -Sir William Drummond
> -----------------------------------------------------------------------
> This list is provided as an unmoderated internet service by Networked
> Knowledge Systems (NKS). Views and opinions expressed in messages
> posted are those of the author and do not necessarily reflect the
> official policy or position of NKS or any of its employees.
>
-----------------------------------------------------------------------
This list is provided as an unmoderated internet service by Networked
Knowledge Systems (NKS). Views and opinions expressed in messages
posted are those of the author and do not necessarily reflect the
official policy or position of NKS or any of its employees.
This archive was generated by hypermail 2.1.3 : Fri Aug 01 2014 - 13:48:09 EDT