[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
cell recycling; reference implementation; param ordering; fresh lists
I have altered the description of LIST-DELETE-NEIGHBOR-DUPS! and LIST-MERGE!
to include this text, which I think will clear up the cons-cell allocation
On the other hand, the procedures
make only a single, iterative, linear-time pass over their argument lists,
using SET-CDR!s to rearrange the cells of the lists into the final result
-- they work "in place." Hence, any cons cell appearing in the result must
have originally appeared in an input. The intent of this
iterative-algorithm commitment is to allow the programmer to be sure that
if, for example, LIST-MERGE! is asked to merge two ten-million-element
lists, the operation will complete without performing some extremely
(possibly twenty-million) deep recursion.
I have changed the SRFI accordingly. The new draft is at
and will propagate out to the standard url
in the hands of esteemed editor Solsona in the near future.
From: David Feuer <dfeuer@xxxxxxxxxxxxx>
I'm still wondering where the reference implementation is.
It is on my disk, not released. I need to clean up one of the routines before
I release it, and it's just not as important to me right now as the design
discussion, so that is what is getting my attention.
[On the subject of parameter order between the < arg & the data arg:]
Do you provide functions with the same _names_ as existing
implementations, or just the same interfaces?
Hmm, there is a small amount of clash, but less than I would have supposed.
Check the other-implementations summary. But even if the *names* don't clash,
the *convention* is completely inverted from current practice, which is asking
Let's hear from some other voices.
Another little thought: You could provide _both_, with the different
versions marked by asterisks or something. That could be a bit confusing
though, and even lead to a bit of bloat.
Ech. No, let's *settle* on a *standard* *convention*, and let implementations
deal with backwards compatibility for existing code if we depart from their
What I was thinking was that in functional-style code, if you sort an
array, and if the array was in fact already sorted, you get a little win
by using the old array rather than the new one (and letting the new one
get trashed almost immediately in the first generation) rather than having
2 identical arrays sitting around wasting memory, and missing the
opportunity for a first-generation collection. But I'm no expert at GC,
so this may not actually be significant. Of course you can always check
if the array is sorted first, but that would take more time.
We're trying too hard here, being too clever.
I was thinking of this in the "side-effecting world". I was guessing
(without any serious thought on the topic) that it could be faster (at
least on some implementations) to do a total-copy sort than a
copy-then-sort. Don't have a clue if this is really the case.
OK, here's the skinny. If you want to sort a list and guaranteed produce a
fresh copy, here is how I would choose an underlying algorithm:
- Best option, I think: Convert the list into a vector, sort that with an
in-place vector-sorting algorithm, then convert it back into a fresh
list. This wins for reasons of memory locality -- chasing pointers
through memory is slower than doing address arithmetic. The conversion
costs you linear time, so it doesn't affect your O(n lg n) run time, and
you need a linear amount of temp storage, but you're committed to
allocating a linear amount of memory, anyway. Need to be stable? OK,
allocate *two* vectors and use my opportunistic vector merge sort:
linear-time best case, O(n lg n) worst case, stable, good memory
locality, and you only changed the constant factor on your temp memory
requirements from a 1 to a 2.
- Don't want to use vectors / don't have vectors? You can roll a
version of my opportunistic destructive list merge sort algorithm
so that it copies the input list on the fly, as it goes, and then
uses destructive merge ops on the intermediate sorted lists. This
would give you linear-time best case, O(n lg n) worst case, stable,
and (here's the part you want) every cons cell allocated appears
in the result -- no "wasted" consing of temporary lists.
- Really want to be functional, no side effects? OK, use my opportunistic
list merge sort. As above, but no SET-CDR!s at all... hence you end
up allocating some intermediate lists that get thrown away.
Now, wanting to sort a list and produce a guaranteed fresh copy is probably
not the common case. You can do a fine job of this in three lines of code
using the tools provided by this lib, if you choose plans A or C above. I don't
think it is really probably worth tying up "API space" supporting it any more
OK, thank you for making me walk through that design analysis.
By the way, I keep referring to "my opportunistic merge-sort algorithm." Vas
ist das? It's an algorithm I invented about three years ago (which is what
led to the production of this SRFI). It is a surpisingly simple algorithm with
the properties I described above. It's been circulated privately, and I've
submitted a manuscript describing the algorithm with proofs establishing the
run-time bounds for publication, but it has not yet been published... so
that's why you have almost certainly not heard of it.
It is part of the reference implementation library, though.