David Van Horn scripsit:
> As far as I know, there have never been time bounds placed on list-ref
> or vector-ref. So I don't understand the "it used to be true" comment.
Vectors are normally allocated contiguously in memory, whereas lists
are normally not (CDR-coding being an exception). On older hardware
where most people's intuitions about access time developed, contiguous
allocation meant O(1) access time, whereas lists had to be and still
are traversed in O(N) time.
However, so-called RAM is no longer random access in the sense of O(1)
access time; it is now O(N) (though with a much smaller constant than
is required for linked access) unless the vector is entirely within a
CPU cache.
> Moreover, I don't understand why vectors would "now" have O(N) access
> times (I assume you mean time and not space) based on what's in your
> Thing One document.
Nothing to do with Thing One.
--
Ambassador Trentino: I've said enough. I'm a man of few words.
Rufus T. Firefly: I'm a man of one word: scram!
--Duck Soup John Cowan <co...@ccil.org>
_______________________________________________
r6rs-discuss mailing list
r6rs-discuss@lists.r6rs.org
http://lists.r6rs.org/cgi-bin/mailman/listinfo/r6rs-discuss
