octave-maintainers
[Top][All Lists]
Advanced

[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



reply via email to

[Prev in Thread] Current Thread [Next in Thread]