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

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

From: Dave Reynolds <der@hplb.hpl.hp.com>
Date: Tue, 05 May 2009 11:42:16 +0100
Message-ID: <4A001808.7060508@hplb.hpl.hp.com>
To: Sandro Hawke <sandro@w3.org>
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).

Dave
Received on Tuesday, 5 May 2009 10:43:04 GMT

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