[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Too much of a good thing?




On Tuesday, April 15, 2003, at 01:35 AM, Sergei Egorov wrote:
I'd rather cut it to one third, but then Olin will come out of
his lair and add the rest and then some :)

Heheh.

The question is not whether LIST->VECTOR and VECTOR->LIST are
actually used in the implementation, but whether vector-specific algorithms you propose are better than just list operations followed by a conversion or the same operations on lists with no conversion at all. Did you turn any
SRFI-1 algorithms into something more effective (from linear- to
constant-time,
from quadratic to linear etc.)?

Oh, I see what you mean. (I missed the 'the performance is the same as' bit)

In that case, I'm not really sure...it's been a while since I wrote the
implementation, and my memory isn't that great.

For example, both vector search and list search are linear by number of
elements.
This means that there is no big insentive to use vectors if what you want is
linear search. On the other hand, you can sort vectors and use binary
search: this is where vectors are much more effective. Thus, I would
expect vector SRFI to include BINARY-SEARCH and SORT! operations
(real benefits), but can easily do without linear search (writing one more
DO loop is no big deal).

I deliberately avoided writing anything involving sorting vectors, since SRFI 32 will provide that. However, I may later include a VECTOR-BINARY-SEARCH -- it
merely didn't occur to me to do so previously.

Can you give me any pointers to drafts or notes on his project?

http://www.sgmiller.org/srfi-44.html

I'm in the process of writing the reference implementation.

Turns N-ary procedure into M-ary (M < K) by "fixing" or "binding"
values of some arguments.

Hmm.  Could you show me a definition of it, or an example of using it?

I wrote a draft myself long ago, but had no time to finish it. May be this
discussion will move it up on my priority list...

I'd love to see it.  Where can I find a copy?

I guess it is fine too.
By the way, you forgot to mention VECTOR-COPY!'s behavior in case of
intra-vector copy (target and vec are the same). Does it copy to the left,
to the right, or does it chose the "correct" direction automatically?

If they are the same in terms of EQ?, or EQUAL? ?  I assume the former.

True, but this somehow ligitimizes restrictive implementations.
I just consider them broken :)

Unfortunately, some of the major ones, like CHICKEN, have this sort of
restriction.  But if you insist upon having VECTOR-APPEND instead of
VECTOR-CONCATENATE[*] (please, someone: think up a better name than
VECTOR-CONCATENATE*), then I'll agree.

Which everybody can easily define by composition (especially when
given a suitable high-order primitive).

OK, then, show me your functional-ish SRFI thing!

 More, if you take this road,
nothing prevents you from making VECTOR-APPEND-REVERSE,
VECTOR-CONCATENATE-REVERSE,
VECTOR-REVERSE-CONCATENATE and dozens of others.

No, that's the C++ road, where you continue to add whatever you can possibly
think of, even if it could never be useful in any situation whatsoëver.

Of course, at first, I shamefully admit that this was the road taken, but I did
certainly intend to make great cuts to the thing.

Personally, I dislike REDUCEs because while giving you certain
performance benefits in some imaginary cases (the dreadful database
queries!),
they allow you to "cheat" (or make an honest mistake) by giving an
inconsistent
KONS/ RIDENTITY pair. Try to copy a list with REDUCE and you will
see that it's not only a performance hack - it is a *broken* performance
hack!

Very well -- no VECTOR-REDUCE[-RIGHT].

On the second thought, NO, unfolds are not very useful (no benefits
for vectors).

Indeed.

Just compositions with VECTOR-COPY...

OK.

Yes, with start and end; When there is only one vector argument,
they are easy to remember.

Good, good.

That's your only option if you don't want to reallocate the vector
for performance reasons, but can afford the loss of some "old"
elements. Some "history" stacks, circular buffers of fixed size etc.
work this way.

OK, I was just wondering if you had found them useful ever.

Start and End arguments are trouble... I'd prefer to have abstract
operations
that can work with "windows" over sequences as first-class objects.
I don't care much about operations taking any number of vectors, except
for the cases where people may expect them (MAP, FOR-EACH).

What about other cases like VECTOR-FOLD[-RIGHT], VECTOR=, et cetera?

(and that's another thing: should there be vector comparisons in this reduced SRFI? -- and, if so, I don't like the name VECTOR= -- I'd personally prefer VECTOR-EQUAL? or VECTOR=? or something. Has anyone else an opinion on this?)