Re: recursion depth
Re: recursion depth
- Subject: Re: recursion depth
- From: "Mark J. Reed" <email@hidden>
- Date: Sun, 9 Oct 2005 13:15:32 -0400
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>
_______________________________________________
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