Thank you to the several people helped me with he development of my treeMapReduce
function. I have some preliminary tests of its performance as compared to normal foldLeft
. I’m adding all the fractions of the form 1/n
(excluding 1/0
) from -1/r
to 1/r
, with r
being in `List(10, 20, 50, 100, 200, 500, 1000, 2000, 5000).
The results are interesting. From somewhere between r=50
and r=100
, my implementation of treeMapReduce
behaves better, and apparently much better as the size increases. I don’t know yet whether it is polynomially better or exponentially better.
10 treeMapReduce: Elapsed time: 151011.685 u-seconds
10 fold: Elapsed time: 1285.852 u-seconds
20 treeMapReduce: Elapsed time: 883.631 u-seconds
20 fold: Elapsed time: 523.748 u-seconds
50 treeMapReduce: Elapsed time: 7806.193 u-seconds
50 fold: Elapsed time: 8578.5 u-seconds
100 treeMapReduce: Elapsed time: 3178.148 u-seconds
100 fold: Elapsed time: 12028.774 u-seconds
200 treeMapReduce: Elapsed time: 6827.183 useconds
200 fold: Elapsed time: 18540.335 useconds
500 treeMapReduce: Elapsed time: 12062.567 u-seconds
500 fold: Elapsed time: 70240.239 u-seconds
1000 treeMapReduce: Elapsed time: 16772.648 u-seconds
1000 fold: Elapsed time: 241687.172 u-seconds
2000 treeMapReduce: Elapsed time: 26706.833 u-seconds
2000 fold: Elapsed time: 1523622.028 u-seconds
5000 treeMapReduce: Elapsed time: 83140.555 u-seconds
5000 fold: Elapsed time: 2.0322914918E7 u-seconds
Here is the code I’m using to make the comparison.
def time[R](name: String, block: => R): R = {
val t0 = System.nanoTime()
val result = block // call-by-name
val t1 = System.nanoTime()
println(s"$name: Elapsed time: ${(t1 - t0) / 1000.0} =u-seconds") // time in micro seconds
result
}
locally{
import treereduce.TreeReducable._
import treereduce.TreeReduce._
import spire.algebra._
import spire.implicits._
import spire.math._
val zero = Rational(0,1)
for {r <- List(10, 20, 50, 100, 200, 500, 1000, 2000, 5000)} {
val piercedInterval = (-r to -1) ++ (1 to r)
time(s"$r treeMapReduce", {
val sum = piercedInterval.treeMapReduce(Rational(0, 1))(Rational(1, _), _ + _)
assert(sum === zero)
})
time(s"$r fold", {
val sum = piercedInterval.map {
Rational(1, _)
}.foldLeft(Rational(0, 1))(_ + _)
assert(sum === zero)
})
println()
}
}
Adding rational numbers is the type of folding which treeMapReduce
was designed for. The idea is that the more such rational numbers you try to add, the larger the denominators will become and the more difficult it is to find the least common denominator to add them. The more rationals you try to add, the more the calculation is dominated by this search for gcd. The goal of treeMapReduce
is to keep the gcds small as long as possible. It does this my making the heuristic assumption that the given numbers has small denominators as compared to the intermediate results.