Re: Re: Vector and Seq
2010-03-31 23:28:24 GMT
Daniel Sobral skrev 2010-03-31 23:59:You really need to read up on big O notation. log32(n) = log(n) / log(32), so O(log32(n)) = O(log(n) / log(32)) = O(log(n)).O(log32 n) is different than O(log n). You only ignore multiplicative
constant factors and constant factors. Perhaps you meant to say that
O(log 32 * n) == O(log n)?
Big O notation is a mathematical concept to describe for example running time and memory usage of algorithms when the number elements grows towards infinity. If you have a limited maximum number of elements it can only be used as a rough estimate to compare data structures and algorithms.As for O() notation being irrelevant for length limited data types,
given that all computers can only deal with limited size collections in
their memories, does that make O() notation irrelevant for in-memory
algorithms? That's non-sensical, and untrue anyway.
I'm not arguing that Vector is a useful and fast implementation, but if we agree that it's branching factor is at most 32, element access time is O(log n) not O(1) as the number of elements grows towards infinity. If you talk about a length limited implementation, the big O notation is not applicable.Right now, 2^30 elements on an in-memory collection of any kind is
downright impossible on 32 bits JVM, and very tough on current 64 bits
system. When the access time ratio between 100 and 2^30 elements is
about 1/2, it doesn't make any sense nit-picking the difference. The
slowest rate would have been good enough even for the smaller
collection, given the other nice properties of this collection, and it
is by this token that we can say it is O(1). If you want _the_ fastest
access speed possible, then just go with arrays.