- From: Sandro Hawke <sandro@w3.org>
- Date: Tue, 05 May 2009 08:20:55 -0400
- To: Dave Reynolds <der@hplb.hpl.hp.com>
- cc: RIF <public-rif-wg@w3.org>
> Sandro Hawke wrote:
>
> > This functions-are-functions thing is worrying me, too. This means list
> > "union", "intersect", and "except" need to be defined with stable
> > ordering, I think, which I believe means they're stuck with n^2
> > algorithms.
>
> I don't think that follows. Take "intersect" for example. You can create
> a hashtable of one list then walk the other list emitting elements (in
> order) if they are also present in the hashtable. That's O(nlog(n)) (or
> O(n) if you think you have a good hash).
Yes, you're right, of course. Even union and distinct-values can do
this trick of building an indexed structure (hash table, b-tree,
whatever) to get better than n^2. Sorry for the mistake.
-- Sandro
Received on Tuesday, 5 May 2009 12:21:04 UTC