On Sat, 10 Oct 2009, Eben King wrote:
> On Sat, 10 Oct 2009, ronan 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
>
>> You could try making a "function" inside your script, and having that
>> function call itself recursively. That way, you don't have the fork
>> overhead.
>
> Good idea. It appears, though, when a function (1) calls itself (2) in sh,
> sh replaces (1) with (2). That seems silly and I'm not sure it's happening
> but I can't see another bug. Should I try background + wait, or is there a
> cleaner/faster way?
&/wait made it work, but it's slower (24s, was ~18s for 12^3 balls/9 parts).
and the results come out in random order (to be expected with multiple code
paths), which is OK. Commenting out all the [ $debug = 1 ] lines didn't make
it faster.
Just thought, line 8 should be in "", but that causes no change so I guess
it wasn't necessary.
1 #! /bin/sh
2
3 debug=0 # debugging mode
4
5 divide () {
6 balls=$1
7 parts=$2
8 parts_so_far=$3
9 indent="$(echo "$parts_so_far" | sed 's/[^ ]//g')"
10 [ $debug -eq 1 ] && echo "$indent 1-start (balls=$balls parts=$parts size=$try_cubesize)"
11
12 if [ "z$parts_so_far" = z ] ; then # if parts_so_far is empty,
13 upper_bound=$balls # Way too big, but it'll do. It's guaranteed to be big enough.
14 else
15 upper_bound=${parts_so_far##*\ } # last number in the list
16 fi
17
18 try_cubesize=1 # If you want a minimum cube size, set it here.
19 while : ; do
20 [ $debug -eq 1 ] && echo "$indent 2-top of loop (balls=$balls parts=$parts size=$try_cubesize)"
21 balls_left=$((balls - try_cubesize * try_cubesize * try_cubesize))
22 [ $balls_left -lt 0 -o $try_cubesize -gt $upper_bound ] && break
23 [ $debug -eq 1 ] && echo "$indent 2.1-before if (balls=$balls parts=$parts size=$try_cubesize)"
24 if [ $parts -eq 1 ] ; then # parts=1
25 [ $debug -eq 1 ] && echo "$indent 2.1.1-before else (balls=$balls parts=$parts size=$try_cubesize)"
26 if [ $balls_left -eq 0 ] ; then # balls_left=0
27 echo "${parts_so_far#\ } $try_cubesize" # prints a "success"
28 break
29 fi
30 else # parts > 1, no idea what balls_left is
31 [ $debug -eq 1 ] && echo "$indent 2.1.2-after else (balls=$balls parts=$parts size=$try_cubesize)"
32 divide $balls_left $((parts - 1)) "$parts_so_far $try_cubesize" & # divide the rest
33 # This prevents the child's "parts" from being <=0 (and everything's a child) --
34 # its "parts" comes from $((parts-1)) and here parts>1.
35 fi
36 [ $debug -eq 1 ] && echo "$indent 2.2-after if (balls=$balls parts=$parts size=$try_cubesize)"
37 try_cubesize=$(( try_cubesize + 1 )) # increment test cube size;
38 [ $debug -eq 1 ] && echo "$indent 3-bottom of loop (balls=$balls parts=$parts size=$try_cubesize)"
39 done
40 [ $debug -eq 1 ] && echo "$indent 4-end (balls=$balls parts=$parts size=$try_cubesize)"
41 wait
42 }
43
44 #set -x
45 divide "$@"
46 #echo exiting "$@"
-- -eben QebWenE01R@vTerYizUonI.nOetP royalty.mine.nu:81 PISCES: Try to avoid any Virgos or Leos with the Ebola virus. You are the Lord of the Dance, no matter what those idiots at work say. -- Weird Al, _Your Horoscope for Today_ ----------------------------------------------------------------------- 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:00 EDT