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

[Tyson Richard DOWD]

Fergus Henderson wrote:
> 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.)

Well, you could do a runtime type check to see which version to call.
If type of aggregate is a builtin type then use Peter's algorithm.
Solutions has a list as it's aggregate type, so it would still use
Fergus's.
This might be the default, but the user can choose between the two if
it's not satisfactory (that is, if they know better).

-- 
       Tyson Dowd           #          Another great idea from the 
                            #            people who brought you
      trd at .cs.mu.oz.au      #               Beer Milkshakes!
http://www.cs.mu.oz.au/~trd #	         Confidence --- Red Dwarf