W3C home > Mailing lists > Public > public-rif-wg@w3.org > May 2009

Re: [DTB] issues with numeric casting/built-in functions

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>
Message-ID: <3308.1241526055@ubehebe>
> 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 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Tuesday, 2 June 2009 18:34:08 GMT