Date: Tue, 26 Jun 2001 00:55:51 -0600 (CST) From: Ryan Thompson <ryan@sasknow.com> To: Dag-Erling Smorgrav <des@ofug.org> Cc: Anton Berezin <tobez@tobez.org>, freebsd-chat@FreeBSD.ORG Subject: Re: most complex code in BSD? Message-ID: <Pine.BSF.4.21.0106260042370.82644-100000@ren.sasknow.com> In-Reply-To: <xzp1yobdfuf.fsf@flood.ping.uio.no>
next in thread | previous in thread | raw e-mail | index | archive | help
Dag-Erling Smorgrav wrote to Anton Berezin:
> Anton Berezin <tobez@tobez.org> writes:
> > perl -pe 's,.,,sg if $_{+lc}++' <in >out
> >
> > Like this, you mean? ;-)
>
> This is perfectly understandable. It copies its input less any
> duplicate lines (even if they don't immediately follow the first
> occurrence - uniq(1) can't do this).
>
> DES
Classic problem with this is, even if you can understand it (or at least
figure it out in less than a minute or so) who the hell could hazard a
guess at the efficiency of that "algorithm"? (Before going to the trouble
of testing it on a few million lines). I bet it isn't O(n) ;-)
Maybe you could guess, but you'd have to have a conventional algorithm in
head (or, one step further, in code), to recant the efficiency of a
well-written duplicate removal function. Then, you have to ask the
question... In terms of final algorithmic results, is 's,.,,sg if
$_{+lc}++' "well-written"? Or does it turn into some ghastly memory-greedy
exponential function?
<digression>
I suppose this is all irrelevant... Most competent Perl programmers
avoid things like this in reusable code, anything that requires any
amount of testing, and anything where efficiency might be a factor.
</digression>
Who can duplicate the dupe removal algorithm in Prolog? :-)
- Ryan <-- programs in Perl and admits it too
--
Ryan Thompson <ryan@sasknow.com>
To Unsubscribe: send mail to majordomo@FreeBSD.org
with "unsubscribe freebsd-chat" in the body of the message
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?Pine.BSF.4.21.0106260042370.82644-100000>