[m-dev.] diff: better unsorted_aggregate/4

[Fergus Henderson]

Peter Schachte, you wrote:
> Since coding this, and in thinking about comments made on comp.lang.prolog
> by Karen Morrissey, it occurred to me there may be a better way to do this.
> In some cases, the aggregate itself will be very small, sometimes just an
> io__state, while the solutions themselves will be very large.  In such
> cases, it would be better never to copy parts of the solutions that aren't a
> part of the aggregation.
> 
> So here's a proposed algorithm:
> 
> 	1.  Call the generator closure, building a solution on the heap.
> 	2.  Swap (the runtime systems conception of) the heap and solutions
> 	    heap.
> 	3.  Call the collector closure, passing the "collection so far" and
> 	    the new solution, storing it as the new "collection so far."
> 	4.  Deep copy the "collection so far" to the solutions heap (which
> 	    is now thought of as the heap).  Since it was built on the
> 	    solutions heap, only the parts of the new solution which have
> 	    become part of the collection so far actually need to be copied.
> 	5.  Swap the heap and solutions heap back.
> 	6.  Force a failure, and return to 2 for each new success.
> 	7.  Return the collection so far as the aggregate.
> 
> The trouble with this is that (as I understand it) deep_copy needs to
> traverse the whole aggregate just to see that there isn't much it needs to
> copy.  So if the aggregate being built is large, the implementation you just
> checked in will be much better.

Right.  In particular, for unsorted_solutions/2, the implementation in my diff
is O(N), whereas your suggestion would be O(N^2).

> But if it's just an io__state, this proposal looks pretty good.

True.  On the other hand, I'm not willing to make solutions/2 O(N^N).

I suppose we could have two different versions of unsorted_aggregate/4,
one for each algorithm.  (Though I don't know what we'd call the two
different versions.)

-- 
Fergus Henderson <fjh at cs.mu.oz.au>   |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>   |  of excellence is a lethal habit"
PGP: finger fjh at 128.250.37.3         |     -- the last words of T. S. Garp.