headers
Stavros Macrakis | 4 Sep 17:08
Favicon

Huge speedup for union WAS: Maxima/Ecl on 32-bit machine cannot evaluate "apply(union, listify({{..}}))"

Here's a fix users can apply immediately to a running Maxima.

:lisp (defun require-set (x context-string)  (cond (($setp x) (cdr x))(t  (merror "Function ~:M expects a set, instead found ~:M" context-string x))))

The results are dramatic:

Test: XXreduce('union,create_list({random(100000)},i,1,1000))$

        lreduce rreduce tree_reduce
Before   1.44    1.38    0.08
After    0.30    0.20         0.05

With the old code, doing this for 10000 took a rather long time.  With the new code:

        lreduce rreduce tree_reduce
        21.19   17.67    0.35

And with {i}, we see the expected result that lreduce is the worst case and rreduce is fast.

        lreduce rreduce tree_reduce
        27.28    4.17    0.36

With some additional optimization in the core merge function (reducing list copies) for this (important) special case, rreduce would become even faster than tree_reduce.

One note: the new version of require-set will break set operations when simp:false.  But that is true for large parts of Maxima: turning simp off is a very dangerous thing.

             -s

_______________________________________________
Maxima mailing list
Maxima <at> math.utexas.edu
http://www.math.utexas.edu/mailman/listinfo/maxima
Permalink | Reply |
headers
Barton Willis | 4 Sep 18:00
Favicon

Re: Huge speedup for union WAS: Maxima/Ecl on 32-bit machine cannot evaluate "apply(union, listify({{..}}))"

It was my bug that converted the nice core nset algorithms from O(n)
to O(n log(n)). My apologies to Stavros and rest of the Maxima
community.

We need users to test nset (and all of Maxima) with big problems.

Barton
Permalink | Reply |
headers
Judy Toth | 8 Sep 06:42
Favicon

Re: Huge speedup for union WAS: Maxima/Ecl on 32-bit machine cannot evaluate "apply(union, listify({{..}}))"

How big?  What I am working on lately is very large lists, about 30000-50000 elements each one a sublist of 5 elements.

Rich

 ------------Original Message------------
From: Barton Willis <willisb <at> unk.edu>
To: "Stavros Macrakis" <macrakis <at> alum.mit.edu>
Cc: "Robert Dodier" <robert.dodier <at> gmail.com>, maxima <at> math.utexas.edu, maxima-bounces <at> math.utexas.edu
Date: Thu, Sep-4-2008 12:00 PM
Subject: Re: [Maxima] Huge speedup for union WAS: Maxima/Ecl on 32-bit machine cannot evaluate
"apply(union, listify({{..}}))"

It was my bug that converted the nice core nset algorithms from O(n)
to O(n log(n)). My apologies to Stavros and rest of the Maxima
community.

We need users to test nset (and all of Maxima) with big problems.

Barton
_______________________________________________
Maxima mailing list
Maxima <at> math.utexas.edu
http://www.math.utexas.edu/mailman/listinfo/maxima
Permalink | Reply |
headers
Richard Hennessy | 8 Sep 06:57
Favicon

Re: Huge speedup for union WAS: Maxima/Ecl on 32-bit machine cannot evaluate "apply(union, listify({{..}}))"

I noticed some bugs that I have not been reporting.  One was if the list is too large like around 1,000,000 you
lose the connection to Maxima when creating it.  The same thing happens with large strings and stringout.  

Rich

 ------------Original Message------------
From: "Judy Toth"<judyt2009 <at> comcast.net>
To: "Barton Willis" <willisb <at> unk.edu>, "Stavros Macrakis" <macrakis <at> alum.mit.edu>
Cc: maxima <at> math.utexas.edu, "Robert Dodier" <robert.dodier <at> gmail.com>, maxima-bounces <at> math.utexas.edu
Date: Mon, Sep-8-2008 0:42 AM
Subject: Re: [Maxima] Huge speedup for union WAS: Maxima/Ecl on 32-bit machine cannot evaluate
"apply(union, listify({{..}}))"

How big?  What I am working on lately is very large lists, about 30000-50000 elements each one a sublist of 5 elements.

Rich

 ------------Original Message------------
From: Barton Willis <willisb <at> unk.edu>
To: "Stavros Macrakis" <macrakis <at> alum.mit.edu>
Cc: "Robert Dodier" <robert.dodier <at> gmail.com>, maxima <at> math.utexas.edu, maxima-bounces <at> math.utexas.edu
Date: Thu, Sep-4-2008 12:00 PM
Subject: Re: [Maxima] Huge speedup for union WAS: Maxima/Ecl on 32-bit machine cannot evaluate
"apply(union, listify({{..}}))"

It was my bug that converted the nice core nset algorithms from O(n)
to O(n log(n)). My apologies to Stavros and rest of the Maxima
community.

We need users to test nset (and all of Maxima) with big problems.

Barton
_______________________________________________
Maxima mailing list
Maxima <at> math.utexas.edu
http://www.math.utexas.edu/mailman/listinfo/maxima

_______________________________________________
Maxima mailing list
Maxima <at> math.utexas.edu
http://www.math.utexas.edu/mailman/listinfo/maxima
Permalink | Reply |
headers
Stavros Macrakis | 5 Sep 01:28
Favicon

Re: Huge speedup for union WAS: Maxima/Ecl on 32-bit machine cannot evaluate "apply(union, listify({{..}}))"

Using this patch (which Barton has now checked in):

:lisp (defun require-set (x context-string)  (cond (($setp x) (cdr x))(t  (merror "Function ~:M expects a set, instead found ~:M" context-string x))))

I retested Barton's test case qq: makelist({i},i,1,10000); XXreduce('union,qq)$; recall that xreduce/apply doesn't work on GCL.

        lreduce rreduce tree_reduce
Before  176.40  155.40    0.25
After    25.81    3.89    0.03

Given the continued speed advantage of tree_reduce in many cases (though I've only tested on GCL), I wonder if we should a) define xreduce as assuming that the operation is associative, thus allowing it to use any grouping it prefers; b) use tree_reduce by default when apply is not available.

By the way, there seems to be some problem with l/rreduce for long lists on GCL -- I will write up a bug report.

               -s

_______________________________________________
Maxima mailing list
Maxima <at> math.utexas.edu
http://www.math.utexas.edu/mailman/listinfo/maxima
Permalink | Reply |

Gmane