On Fri, Oct 09, 2009 at 09:31:20PM -0400, Eben King 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
Code it in C. That's the fastest way to do it. But I suspect if you
could do that, you already would have. Alternatively, it seems like you
could code this as a script for bc (the calculator program). The man
page for bc makes it sound like this kind of thing is normal for that
program. It would have to be faster than bash.
Paul
-- Paul M. Foster ----------------------------------------------------------------------- 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:47:15 EDT