[Israel.pm] Fwd: Re: Case Study: Splitting a Hash into Two

Shlomi Fish shlomif at iglu.org.il
Thu Jul 15 01:03:55 PDT 2004

Here's something that WLI wrote in response to what I said.


	Shlomi Fish

----------  Forwarded Message  ----------

Subject: Re: Case Study: Splitting a Hash into Two
Date: Thursday 15 July 2004 01:15
From: William Lee Irwin III <wli at holomorphy.com>
To: Shlomi Fish <shlomif at iglu.org.il>
Cc: Perl in Israel <perl at perl.org.il>

On Wed, Jul 14, 2004 at 09:48:30PM +0300, Shlomi Fish wrote:
> It took me some time to understand it. Note that this function uses a sort
> routine so it is O(N*log(N)) instead of O(N). WLI wrote some routines that
> are linear time, but they are longer and the code is somewhat uglier.
> That's it for today folks. Now go back to work.

I sent you a linear O(classes*N) time one. In your case, classes == 2.

fish = map snd
	. foldr (\(k, v) kvs -> maybe ((k, [v]):kvs)
				(\vs -> (k, v:vs) : filter ((/=k) . fst) kvs)
				(lookup k kvs)) []
	. map (\s -> ("_" `isPrefixOf` (fst s), s))



Shlomi Fish      shlomif at iglu.org.il
Homepage:        http://shlomif.il.eu.org/

Knuth is not God! It took him two days to build the Roman Empire.

More information about the Perl mailing list