- From: Dave Reynolds <der@hplb.hpl.hp.com>
- Date: Tue, 05 May 2009 11:42:16 +0100
- 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 UTC