Re: recursion depth
Re: recursion depth
- Subject: Re: recursion depth
- From: "Mark J. Reed" <email@hidden>
- Date: Sun, 9 Oct 2005 13:16:44 -0400
(On OS X 10.4. 2, AS 1.10. Hit send key too soon...)
On 10/9/05, Mark J. Reed <email@hidden> wrote:
> I get the same results as you. Works with max=504, fails with
> max=505, in Script Editor and osascript(1).
>
>
> On 10/9/05, Matt Neuburg <email@hidden> wrote:
> > Okay, let's all test the depth of recursion, please.
> >
> > on remvix(L, ix)
> > if L is {} then return {}
> > if ix is 1 then
> > return rest of L
> > else
> > return item 1 of L & remvix(rest of L, ix - 1)
> > end if
> > end remvix
> > set L to {}
> > set max to 504
> > repeat with x from 1 to max
> > set end of L to x
> > end repeat
> > remvix(L, max)
> >
> > OMM, that works, but if "max" is set to 505, we get a stack overflow.
> > However, other users report other numbers. So now I'd like to collect some
> > more data. Please report what your maximum "max" is (and anything else you
> > think might be affecting this - your ram size, for instance?).
> >
> > To make this easier, the following *might* be a correct testing algorithm,
> > though I'm not entirely certain:
> >
> > on remvix(L, ix)
> > if L is {} then return {}
> > if ix is 1 then
> > return rest of L
> > else
> > return item 1 of L & remvix(rest of L, ix - 1)
> > end if
> > end remvix
> > on test(max)
> > set L to {}
> > repeat with x from 1 to max
> > set end of L to x
> > end repeat
> > try
> > remvix(L, max)
> > return true
> > on error
> > return false
> > end try
> > end test
> > -- find an upper bound
> > set x to 2
> > repeat while test(x)
> > set x to x * 2
> > end repeat
> > -- do the search
> > on binarySearch(lt, rt)
> > local mid, ok1, ok2
> > repeat while (lt ¾ rt)
> > set mid to round (lt + rt) / 2 rounding down
> > set ok1 to test(mid)
> > if not ok1 then
> > set ok2 to false
> > else
> > set ok2 to test(mid + 1)
> > end if
> > if ok1 and not ok2 then return mid
> > if not ok1 then
> > set rt to mid - 1
> > else
> > set lt to mid + 1
> > end if
> > end repeat
> > end binarySearch
> > return binarySearch(2, x)
> >
> > On my machine, that yields 502, which makes sense because it's 504 minus the
> > two addition stack levels used by the nesting in the script. m.
> >
> > --
> > matt neuburg, phd = email@hidden, <http://www.tidbits.com/matt/>
> > A fool + a tool + an autorelease pool = cool!
> > AppleScript: the Definitive Guide
> > <http://www.amazon.com/exec/obidos/ASIN/0596005571/somethingsbymatt>
> >
> >
> >
> > _______________________________________________
> > Do not post admin requests to the list. They will be ignored.
> > Applescript-users mailing list (email@hidden)
> > Help/Unsubscribe/Update your Subscription:
> >
> > This email sent to email@hidden
> >
>
>
> --
> Mark J. Reed <email@hidden>
>
--
Mark J. Reed <email@hidden>
_______________________________________________
Do not post admin requests to the list. They will be ignored.
Applescript-users mailing list (email@hidden)
Help/Unsubscribe/Update your Subscription:
This email sent to email@hidden