[Haskell-cafe] Re: best strategy for comparing comparisons
usenet at mkarcher.dialup.fu-berlin.de
Mon Aug 11 12:13:12 EDT 2008
Jason Dusek <jason.dusek at gmail.com> wrote:
[These are point 3 and 4]
> . Compare every Word32 with every other Word32 for equality,
> and see how long it takes.
> . Ditto with ByteStrings.
> The first two are easy and I'm done with them already. The
> latter two seem like they'll run afoul of laziness. I have two
> ideas about how to do them:
> . Do every comparison with a list comprehension, compressing
> the result as I go using `all`.
all is not a good idea: It stops as soon as it sees one false.
Better count the number of equals.
let count = length $ filter id [a==b,a <- bytestrings, b <- bytestrings]
> . Do every comparison in a recursive IO procedure.
Should work too. But you have to take care that implicit I/O thingies
don't spoil one version of your timing tests.
> Are there other ways? Will strictness annotations, for
> example, allow me to run comparisons on larger lists?
Strictness annotation might help, but I don't think they are the
correct tool to use here. The counting test I proposed above
should run in O(1) stack and heap, as well as O(n^2) time, which is
the best you can expect (of course, the list of bytestrings is O(n)
on the heap).
More information about the Haskell-Cafe