[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[OF miscellaneous] Hilbert curve: recursion faster than loop?
From: |
JuanPi |
Subject: |
[OF miscellaneous] Hilbert curve: recursion faster than loop? |
Date: |
Sun, 6 Aug 2017 03:26:11 +0200 |
Hi all,
I was trying to improve the function hilbert_curve.m in the
miscellaneous package[1], which is recursive.
I found a non-recursive algorithm by Jonas Lundgren using complex numbers.
My implementation is here[2].
However when I time these to functions I get
recursive (input arg = 2^9, i.e. 9 levels of recursion):
1.7e-3 +- 0.3e-3 s
nonrecursive (without pre-allocation, input args = 9, false): 0.6e-2 +- 0.1e-2 s
nonrecursive (with pre-allocation, input args = 9, true):
1.4e-2 +- 0.2e-2 s
These results go against rule-of-thumb: avoid recursion and pre-allocate.
Any ideas what's the source of the time cost in the non-recursive and
pre-allocated versions?
The octave profiler is not helping here, because it shows the time
spent on the operations (about 10% of self time), but not on slicing,
which I assume is the culprit here.
[1]:
https://sourceforge.net/p/octave/miscellaneous/ci/default/tree/inst/hilbert_curve.m
[2]: https://bitbucket.org/KaKiLa/mymfiles/src/tip/hilbert_curve_nr.m
--
JuanPi Carbajal
https://goo.gl/ayiJzi
Public GnuPG key: 9C5B72BF
-----
"Why is thought, being a secretion of the brain, more wonderful than
gravity, a property of matter?"
- C. Darwin
- [OF miscellaneous] Hilbert curve: recursion faster than loop?,
JuanPi <=
- Re: [OF miscellaneous] Hilbert curve: recursion faster than loop?, siko1056, 2017/08/06
- Re: [OF miscellaneous] Hilbert curve: recursion faster than loop?, Juan Pablo Carbajal, 2017/08/07
- Re: [OF miscellaneous] Hilbert curve: recursion faster than loop?, Juan Pablo Carbajal, 2017/08/07
- Re: [OF miscellaneous] Hilbert curve: recursion faster than loop?, siko1056, 2017/08/07
- Re: [OF miscellaneous] Hilbert curve: recursion faster than loop?, Juan Pablo Carbajal, 2017/08/07
- Re: [OF miscellaneous] Hilbert curve: recursion faster than loop?, Julien Bect, 2017/08/07
- Re: [OF miscellaneous] Hilbert curve: recursion faster than loop?, siko1056, 2017/08/07
- Re: [OF miscellaneous] Hilbert curve: recursion faster than loop?, Juan Pablo Carbajal, 2017/08/07
- Re: [OF miscellaneous] Hilbert curve: recursion faster than loop?, Juan Pablo Carbajal, 2017/08/07