This page is part of the web mail archives of SRFI 43 from before July 7th, 2015. The new archives for SRFI 43 contain all messages, not just those from before July 7th, 2015.
Michael Burschik wrote:
Correct me if I'm wrong, but R5RS does not provide resizable vectors, and functions generating vector element by element have no way of knowing the length of the resulting vector beforehand.
First, the SRFI process is about extending R5RS, so I don't see that as a restriction.
If you want to write portable code, this means you can either create n vectors of length 1 .. n and discard all but the last, or create a list and then convert it to a vector before returning it, which is, in fact, what the reference implementation does. Are you sure that the first alternative is more efficient?
You have to use some data structure or programming convention that stores the "active length" - i.e. Common Lisp's "fill pointer". If you're stuck with vanilla Scheme, then this would be a separate variable or a convention to use the the first variable of the vector. (The former is awkward and the latter is worse, whihc is why an extension is needed.) But assuming you have a separate fill pointer, then yes: It really is more efficient to allocate and re-allocate multiple vectors - as long as you each time double the allocated size. E.g. start with a small vector of say 8 slots, then when that gets full use one with 16 lots, then one with 32 slots etc. This uses less memory than cons cells (especially if you an object or malloc header), provides linear performance, and much better data locality. > Only if you know how large your data structures are going to be. If you
constantly have to resize your vectors, or create new vectors of an appropriate size, your performance might not be so stellar.
vectors are still faster in almost all applications - as long as you have a fill pointer.
But iterating over all elements of a sequence is an example of exploiting constant-time access to the elements of the sequence. Otherwise, one would recurse over the sequence.
I don' understand what you're saying here. Using recusion as the preferred mechanism to sequence through the elements of a sequence is I believe a mistake. Almost all programmers find it easier to work with iteration than with recursion, and with "sequence comprehensions" iteration can be just as functional and "clean" as recursion. There is a lot to be said for array languages, such as APL. I'm working on implementing XQuery, which is well worth taking a look at. (It's sequence model is different than vectors, since XQuery sequences don't nest directly, but they can be nested indirecty using "elements".) -- --Per Bothner per@xxxxxxxxxxx http://per.bothner.com/