[Haskell-cafe] what is the fastest way to extract variables from a proposition?

Cetin Sert cetin.sert at gmail.com
Thu Feb 21 00:13:57 EST 2008


> I would expect my (well, I didn't invent it) to work better on something
that didn't have this unique structure, such as:
> test 0 = Var 0
> test n | even n    = Or  (Var n) (test (n-1))
>       | otherwise = And (test (n-1)) (Var n)

for some reason this still does not perform as well as it should o__O
I think function composition might somehow be the bottleneck behind this.

--with
plong 0 = Var 0
plong n | even n    = Or  (Var n) (plong (n-1))
        | otherwise = And (plong (n-1)) (Var n)

--and n = 1000000

sert at elite:~/workspace/Haskell-1/bin$ time ./theResult sert
1000001

real    0m0.692s
user    0m0.624s
sys     0m0.040s

sert at elite:~/workspace/Haskell-1/bin$ time ./theResult sert
1000001

real    0m0.696s
user    0m0.644s
sys     0m0.036s

sert at elite:~/workspace/Haskell-1/bin$ time ./theResult sert
1000001

real    0m0.840s
user    0m0.744s
sys     0m0.052s

sert at elite:~/workspace/Haskell-1/bin$ time ./theResult bromage
1000001

real    0m1.561s
user    0m1.360s
sys     0m0.100s

sert at elite:~/workspace/Haskell-1/bin$ time ./theResult bromage
1000001

real    0m1.692s
user    0m1.392s
sys     0m0.136s

sert at elite:~/workspace/Haskell-1/bin$ time ./theResult bromage
1000001

real    0m1.959s
user    0m1.580s
sys     0m0.116s

Best Regards,
Cetin Sert

On 21/02/2008, ajb at spamcop.net <ajb at spamcop.net> wrote:
>
> G'day all.
>
> Quoting Cetin Sert <cetin.sert at gmail.com>:
>
>
> > It is astonishing to see that your version actually performs the worst
> (at
> > least on my machine).
>
>
> On your example, I'm not surprised:
>
>
> > plong 0 = Var 0
> > plong n | even n    = Or  (Var n) (plong (n-1))
> >         | otherwise = And (Var n) (plong (n-1))
>
>
> This is effectively a singly linked list.  I would expect my (well, I
> didn't invent it) to work better on something that didn't have this
> unique structure, such as:
>
> test 0 = Var 0
> test n | even n    = Or  (Var n) (test (n-1))
>         | otherwise = And (test (n-1)) (Var n)
>
>
> Cheers,
> Andrew Bromage
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20080221/b57397b5/attachment.htm


More information about the Haskell-Cafe mailing list