Re: minimum function?
Re: minimum function?
- Subject: Re: minimum function?
- From: has <email@hidden>
- Date: Wed, 6 Apr 2005 23:00:19 +0100
Martin Orpen wrote:
> > I shouldn't boast too much if I were you: your script uses a woefully
> > inefficient and wasteful algorithm that'd make even a junior-high CS student
> > cringe.
>
>Well, if I knew it was an exam piece I would have spent more than 3 minutes
>writing it. It wasn't posted for its efficiency or its good looks, it was
>posted because it was about twenty times faster than any of the scripts that
>were posted prior to it in that thread.
Hey, if you're going to get snooty at other folk, it's helps to know exactly what you're talking about yourself.:p Efficiency is generally the single biggest factor determining an algorithm's execution speed; e.g. an efficient algorithm written in a slow language will scale better than a less efficient algorithm written in a fast one.
A few simple speed tests comparing execution time over 10, 100 and 1000-item lists will show those previous min() examples are non-linear in performance - an immediate red flag that something very undesireable is going on in what should obviously be an O(n) algorithm. In this case it's a well-known issue: because AppleScript lists suck in their implementation, item lookups have only O(n) instead of O(1) efficiency. Thus the naive vanilla min() has O(n^2) efficiency (where n is number of items in list) when it should be O(n). The obvious solution is to apply the standard script object kludge to restore list lookups to O(1) efficiency, resulting in an O(n) vanilla min().
(Your Unix sort command has something like O(n log n) efficiency and in other respects is a weak alternative to a decent vanilla solution. And considering that even my old granny on her zimmer could beat that naive AS implementation, it's not really that much of an achievement.:p)
>I did try leaching a Python function later:
>
> do shell script "python -c 'y=min([" & x & "]); print y'"
>
>But that was slower than using sort (though faster than the previous
>scripts.
Pointless, since Python's min() function is no more efficient than the properly-optimised AS routine, plus you get an even bigger startup overhead as you're now starting a python interpreter process on top of a shell process. The 'do shell script' command is a very suboptimal solution for these sorts of problems.
As a rule: if you're dealing with medium-to-large or unknown-size lists in AppleScript, always use the script object kludge (it's not worth it for small lists though). The problem has been known for years and discussed regularly here and elsewhere, so you'd think folk'd just apply this rule automatically by now, but there you go. (Actually, you'd think Apple and/or third-parties would've had the sense to create libraries containing all these basic functions years ago and render 95% of these discussions completely moot, but that's another story...)
has
--
http://freespace.virgin.net/hamish.sanderson/
_______________________________________________
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