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
> r6rs-discuss_at_lists.r6rs.org
> http://lists.r6rs.org/cgi-bin/mailman/listinfo/r6rs-discuss
>
>
Received on Tue Mar 20 2007 - 18:03:33 UTC