Skip site navigation (1)Skip section navigation (2)
Date:      Wed, 27 Jun 2001 14:06:57 -0500
From:      Mike Meyer <mwm@mired.org>
To:        Anton Berezin <tobez@tobez.org>
Cc:        Dag-Erling Smorgrav <des@ofug.org>, Ryan Thompson <ryan@sasknow.com>, freebsd-chat@FreeBSD.ORG
Subject:   Re: most complex code in BSD?
Message-ID:  <15162.11985.348196.939734@guru.mired.org>
In-Reply-To: <20010627205835.A72506@heechee.tobez.org>
References:  <Pine.BSF.4.21.0106260042370.82644-100000@ren.sasknow.com> <xzpzoavadi6.fsf@flood.ping.uio.no> <20010627205835.A72506@heechee.tobez.org>

next in thread | previous in thread | raw e-mail | index | archive | help
Anton Berezin <tobez@tobez.org> types:
> On Tue, Jun 26, 2001 at 09:47:45AM +0200, Dag-Erling Smorgrav wrote:
> > Ryan Thompson <ryan@sasknow.com> writes:
> > > 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) ;-)
> > I strongly suspect it's O(n*log(k)), where k is the number of distinct
> > lines in the input.  In most cases k will probably be a significant
> > fraction of n, so call it O(n*log(n)).
> 
> I do think that in fact it is closer to O(n), if one replaces s,.,,sg
> with $_="", which is the obvious optimization, and which you already
> mentioned.  The hash accesses are essentially O(1) for random enough
> keys and in case there are enough buckets - and there is always enough
> buckets in Perl since it rebalances its hashes when necessary.  So it
> should be close to O(n).

If I understand the problem correctly, the deviation from O(n) will be
the cost of rebalancing the hashes. Unless that's O(n) or less, Ryan's
correct.

	<mike
--
Mike Meyer <mwm@mired.org>			http://www.mired.org/home/mwm/
Independent WWW/Perforce/FreeBSD/Unix consultant, email for more information.

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?15162.11985.348196.939734>