Daniel Sobral skrev 2010-03-31 23:59:

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)?

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)).

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.

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.

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.

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.

/Jesper Nordenberg

Daniel Sobral skrev 2010-03-31 23:59:

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)?

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)).

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.

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.

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.

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.

/Jesper Nordenberg

I can't understand what you mean by "persistent", "not persistent", "half persistent" here. Who defines these terms and where?

I'm aware of these terms: http://en.wikipedia.org/wiki/Persistent_data_structure

(Partially/fully/confluently persistent, as defined by Robert Tarjan and others).

2010/4/1 James Iry <jamesiry <at> gmail.com>

Probably not all that useful. Take List for example.

List is persistent for tail and :: (prepend)

List is not persistent for init and :+(append)

List is half persistent for ++ (concatenate)

Other structures will make different tradeoffs.  It's really a slight misnomer to say a structure is persistent - we can only say it is or isn't persistent under a particular operation.

On Wed, Mar 31, 2010 at 7:15 PM, Blair Zajac <blair <at> orcaware.com> wrote:

Please excuse any misused terms here and even suggesting this change before 2.8 is released :), but here goes:

After reading this thread today on Google Guava:

http://groups.google.com/group/guava-discuss/msg/94af57687167c443

and after writing an (unreleased) wrapper to some of the Google Collections/Guava classes it appears that it could be useful to distinguish between immutable and persistent data structures:

http://en.wikipedia.org/wiki/Persistent_data_structure

The immutable Google Collection/Guava classes are not persistent so when I wrapped them I overrode the + and - operators to throw a UnsupportedOperationException because they would be very inefficient to build an entire new collection to add or subtract a single item and I wanted to ensure people wouldn't use such an inefficient operation.

For my server based code there are many places where I build an immutable data structure and don't care about the previous versions of it that were built to generate the final version and plus with the Google collections there is no synchronization at all so I don't need to pay for that either.

So it seems like further separating the Scala Collections from mutable and immutable into immutable, persistent and mutable may be useful.  The persistent traits would extend the immutable traits and would supply the relatively efficient + and - operators.

Blair

I think it depends on whether you require that persistence cost less than copying everything to really count.

In that context, James' comments make sense:

val a = Nil
val b = 1 :: a
val c = 2 :: b
c.tail == b  // Of course they're the same
c.tail eq b  // Returns true => persistent, we didn't copy everything

val a = Nil
val b = 1 :: a
val c = b :+ 2
c.init eq b  // Of course they're the same
c.init eq b  // Returns false; we actually copied everything twice here :(
// This isn't what I'd call persistent, at least not if I'm distinguishing it from immutable!

val a = Nil
val b = 1 :: a
val c = 2 :: a
val d = b ++ c
d.drop(1) == c  // True, of course
d.drop(1) eq c  // True, c wasn't copied, yay!
d.take(1) == b  // True, of course
d.take(1) eq b  // False, we actually copied twice :(
// This is parsimonious in c but not have in b => "half-persistent"

Whether we call the failures "not persistent" or "persistent but maximally inefficient", the point is that saying that a _persistent_ data structure is usefully distinct from an _immutable_ data structure relies upon deeper knowledge of which operations you're going to support.  You can't really map "performs better but is safe" onto "persistent", but the former is what library users are more likely to care about.

  --Rex

On Thu, Apr 1, 2010 at 10:46 AM, Dimitris Andreou <jim.andreou <at> gmail.com> wrote:

I can't understand what you mean by "persistent", "not persistent", "half persistent" here. Who defines these terms and where?

I'm aware of these terms: http://en.wikipedia.org/wiki/Persistent_data_structure

(Partially/fully/confluently persistent, as defined by Robert Tarjan and others).

2010/4/1 James Iry <jamesiry <at> gmail.com>

Probably not all that useful. Take List for example.

List is persistent for tail and :: (prepend)

List is not persistent for init and :+(append)

List is half persistent for ++ (concatenate)

Other structures will make different tradeoffs.  It's really a slight misnomer to say a structure is persistent - we can only say it is or isn't persistent under a particular operation.

On Wed, Mar 31, 2010 at 7:15 PM, Blair Zajac <blair <at> orcaware.com> wrote:

Please excuse any misused terms here and even suggesting this change before 2.8 is released :), but here goes:

After reading this thread today on Google Guava:

http://groups.google.com/group/guava-discuss/msg/94af57687167c443

and after writing an (unreleased) wrapper to some of the Google Collections/Guava classes it appears that it could be useful to distinguish between immutable and persistent data structures:

http://en.wikipedia.org/wiki/Persistent_data_structure

The immutable Google Collection/Guava classes are not persistent so when I wrapped them I overrode the + and - operators to throw a UnsupportedOperationException because they would be very inefficient to build an entire new collection to add or subtract a single item and I wanted to ensure people wouldn't use such an inefficient operation.

For my server based code there are many places where I build an immutable data structure and don't care about the previous versions of it that were built to generate the final version and plus with the Google collections there is no synchronization at all so I don't need to pay for that either.

So it seems like further separating the Scala Collections from mutable and immutable into immutable, persistent and mutable may be useful.  The persistent traits would extend the immutable traits and would supply the relatively efficient + and - operators.

Blair