On Wed, 25 Feb 2009, Enrique Erne wrote:
... and i thought my list-drip-custom would win :( could somebody
explain how it exaclty works?
well, first, the right-inlet of [list] makes a copy of your list, so this
makes it take a lot more time when cutting lists into pieces.
second, the left-inlet of [list] also makes a copy of your list, so this
makes it take double the time that it just added, because [list] is a
[list append], and it's appending a bang to a list, and a bang is an
empty list, and it's not smart enough to skip the copy in that case.
this makes a regular list-drip make n*n atom copies, whereas when you cut
in chunks of 64, it makes n*n/64 atom copies, and then it makes
64*64*(n/64) = 64*n atom copies with the rest, almost.
this also means that your recursion and [until] run at the same speed
because they end up making the same copies, so you could achieve the same
results with two levels of [until].
you can achieve more speed by adding extra levels of [until] and tuning
the list chunk sizes for each level.
then also if you use a pair of [list split]s and a counter to iterate
through it, you have to use a [list] to hold it, and then it takes n*n
steps because it's an append, and if you try to use [textfile] or a
settable messagebox, it also copies because it's doing comma-expansion, so
it's no better (note that [textfile] is very much like an invisible
messagebox, there's no real parsing involved unless you load from a real
file)
so i figured out that I had to use [list split] with recursion without
[list], so that it doesn't copy the sublists. but then, attempting to do
it will output the elements in reverse order, so you have to use two [list
split]s, which only copies n atoms (the absolute minimum).
then, doing it with one or two [list split]s gets you a stack overflow
very soon, so by recursing over half-lists you can use up only
log(n)/log(2) levels of recursion. this only copies n atoms, so it's the
minimum possible.
when doing recursion, you have to be careful because pd's cold-inlets
interfere with normal use of recursion... so, for example, I had to
compute the half-list-size twice because I had two [list split]s.
there are several ways in which pd falls just short of allowing a simple
way. For example, just a simple [repeat] with a counter would be several
times less objects, cords and tricks, and can be somewhat speedier than
[list-drip-quick] because you can avoid a lot of the other things that
[list-drip-quick] has to do besides copying n atoms.
Actually, I just tried it with [repeat], and, the way I did it, it is
consistently 2.9 times faster than [list-drip-quick].
But from the moment that you get it down to n atom copies, the speed
differences don't tend to matter nearly as much, as the objects that
receive the dripping will have to process n messages, and that is often
taking more time than the splitting.
So, a pure C external version of [list-drip] may be still several times
faster than the [repeat] version, but only as long as you don't send its
output to any object at all! In real-life situations, the speed difference
is much thinner than the benchmarks, when the objects being benchmarks are
both quite fast.
Note that it's possible that adding to a messagebox cancels all speed
improvements. Its running-time is either n copies or n*n/2 copies, because
it's using a realloc, which may copy or not, depending on whether you're
lucky.
what license do you publish your code when you post code on the pd-list? same
as puredata?
yes, SIBSD license. well, it's on a case-by-case basis. there's no
automatic license for anything, but let's say that [list-drip-quick] is
SIBSD.
_ _ __ ___ _____ ________ _____________ _____________________ ...
| Mathieu Bouchard - tél:+1.514.383.3801, Montréal, Québec
_______________________________________________
Pd-list@iem.at mailing list
UNSUBSCRIBE and account-management ->
http://lists.puredata.info/listinfo/pd-list
