Not specifically to any message in the subthread but...
When people are fretting over O(1) string ops I keep thinking,
by analogy at least, about "property lists" (associated with this
or that type of value and/or identifier). In some traditional lisps
it is O(N) to look up a property of an object with N properties.
In other traditional lisps it is O(log K) in the total number of
properties over all objects. Probably there are other cases as well.
And yet a lot of useful code can be written that is agnostic in
its detailed assumptions about the performance of looking up
object properties.
Why should core string-ops be different, at least until we have
enough meat in the standard for portable programs to reliably
dig down into the representations of things (if ever)?
-t
William D Clinger wrote:
I am posting this as an individual member of the Scheme
community. I am not speaking for the R6RS editors, and
this message should not be confused with the editors'
eventual formal response.
Shiro Kawai wrote:
Sorry for my ignorance, but is there an important algorithm
that requires string-set!, even if you have both (a) means
to construct strings sequentially, like string ports, and
(b) means to create a vector of characters then convert it
to a string efficiently, like vector->string?
Probably. I apologize for my ignorance also.
What I do know is that, if the vector operations are O(1),
then any O(f(N)) and Omega(N) time and space algorithm that
uses string-set! can be replaced by an O(f(N)) and Omega(N)
algorithm that doesn't use string-set!. You just convert
your string to a vector at the beginning of the algorithm
and convert back at the end.
If there are such algorithms, then again, which is important,
O(1) string-set! or O(1) substring (assuming that string
positions are given in a way to guarantee O(1) access),
under existence of preemptive threads?
Important to whom? That's why this stuff is so controversial:
We don't even have an objective objective function.
(It is highly likely that I don't have enough brain;
We share that problem.
can we have both?)
Silly answer: Yes, provided you're willing to abandon O(1)
string-ref.
Serious answer: I don't know. Probably not.
Will
_______________________________________________
r6rs-discuss mailing list
[email protected]
http://lists.r6rs.org/cgi-bin/mailman/listinfo/r6rs-discuss
_______________________________________________
r6rs-discuss mailing list
[email protected]
http://lists.r6rs.org/cgi-bin/mailman/listinfo/r6rs-discuss
