[Haskell-cafe] Space Efficiency When Sorting a List of Many Lists
daniel.is.fischer at web.de
Thu Dec 31 06:07:58 EST 2009
Am Donnerstag 31 Dezember 2009 11:38:51 schrieb Luke Palmer:
> This cartesian product varies in its tail faster than its head, so
> every head gets its own unique tail. If you reverse the order of the
> bindings so that it varies in its head faster, then tails are shared.
> If my quick and dirty reasoning is correct, it improves the space
> usage by a factor of the number of sublists.
That reasoning is supported by
However, that concerns only the generation of the lists to be sorted, as far as I can see
(that will be faster and use less memory).
The main problem here is the space usage of the sorting, I think. For that, probably an
external sort is the best solution.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Haskell-Cafe