On Wed, Nov 19, 2014 at 01:53:02PM -0500, David Feuer wrote:
> I meant O(m log (mn)) = O(m (log m + log n)), because there are m appends,
> building up from O(n) to O(mn), but it really doesn't matter because we can
> easily do better.
Indeed it's moot, but appending a tree of size n to one of size mn
costs O(log n).
On Nov 19, 2014 7:38 PM, "Ross Paterson" <R.Pat...@city.ac.uk> wrote:
>
> On Wed, Nov 19, 2014 at 02:58:46PM -0500, David Feuer wrote:
> > I got to looking at <*> just now, and it suggests the
> > following question: is there a particularly efficient way to build a Seq when
> > its ultimate size is known in advance, avoiding the usual incremental
> > rebuilding?
>
> The following avoids the rebuilding, but I haven't tweaked or timed it:
I don't know how well this will work for fromList, but it looks like it will almost certainly be good for <*> and *>. I'll try it out.
On Thu, Nov 20, 2014 at 12:37:49AM +0000, Ross Paterson wrote:
> On Wed, Nov 19, 2014 at 02:58:46PM -0500, David Feuer wrote:
> > I got to looking at <*> just now, and it suggests the
> > following question: is there a particularly efficient way to build a Seq when
> > its ultimate size is known in advance, avoiding the usual incremental
> > rebuilding?
>
> The following avoids the rebuilding, but I haven't tweaked or timed it:
>
> [...]
Actually this is pretty much what the existing fromList2 does.
The ideal goal, which has taken me forever to identify and which may well be unattainable, is to get O(log(min{i,mn-i})) access to each element of the result, while maintaining O(mn) time to force it entirely. Each of these is possible separately, of course. To get them both, if it's possible, we need to give up on the list-like approach and start splitting Seqs instead of lists. As we descend, we want to pass a single thunk to each element of each Digit to give it just enough to do its thing. Representing the splits efficiently and/or memoizing them could be a bit of a challenge.