Huge speedup for union WAS: Maxima/Ecl on 32-bit machine cannot evaluate "apply(union, listify({{..}}))"
Subject: Huge speedup for union WAS: Maxima/Ecl on 32-bit machine cannot evaluate "apply(union, listify({{..}}))"
From: Stavros Macrakis
Date: Thu, 4 Sep 2008 11:11:30 -0400
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