[email protected]
[Top] [All Lists]

Re: [Haskell-cafe] Space Efficiency When Sorting a List of Many Lists

Subject: Re: [Haskell-cafe] Space Efficiency When Sorting a List of Many Lists
From: Daniel Fischer
Date: Thu, 31 Dec 2009 12:07:58 +0100

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

http://www.haskell.org/pipermail/haskell-cafe/2009-December/070184.html

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.

_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
<Prev in Thread] Current Thread [Next in Thread>