On Sat, Dec 20, 2008 at 8:50 PM, Antony Blakey <[email protected]> wrote: > > On 21/12/2008, at 3:15 PM, Paul Davis wrote: > >> On Sat, Dec 20, 2008 at 11:32 PM, Antony Blakey <[email protected]> >> wrote: >>> >>> On 21/12/2008, at 2:54 PM, Paul Davis wrote: >>> >>>> View update times should be linear in terms of *new* records. >>> >>> Well, with a factor to deal with the reduction, which isn't O(n). >>> >> >> Kinda. I'm pretty sure they're still O(N), just not as pre calculated >> as one might expect. > > I would have thought + a tiny O(log M) where M is determined by the grouping > size of the partial reductions.
I think there's at least a linear cost associated with the number of groups in the final reduction. eg. a group=true result requires N as many as there are unique keys. If your range encompasses 5 groups, then you'd require 5 final reductions to be run. Requesting the same range with group=false, I'd expect a substantial speedup. If it's less than a linear relation to the number of groups, I'd be happy. -- Chris Anderson http://jchris.mfdz.com
