Re: Immutable Datastructures with good Sharing
On 11/4/11 8:03 PM, Jan Burse wrote:
Dear All,
Value objects are some well known immutable
datastructures, when an operation is applied,
typically simply a new object is created. So
for example doing:
3 = 1 + 2
With java.lang.Integer objects would involve
creating a new Integer with value left.intValue()
+ right.intValue().
But instead of call the constructor, one can also call
Integer.valueOf(), and there you have some sharing.
Namely the class Integer caches the value objects for
small values (at least the last time I looked into
the Oracle source, it was there...).
More elaborate sharing is seen in the String class
by the substring() operation. This operation does
reuse the original character array and only encapsulates
the offset and the length in a new object. I wouldnt
recomende that to get one character from a 1 MB
long string, since it will prevent the original
character array from GC. But in some situation this
is quite handy.
I am now looking for immutable datastructures with
a similar sharing. In the String class example, the
operation was substring() that produced a new immutable
object. I am looking for:
Some stack class, where: (Easy)
pop() creates a new immutable stack
push() creates a new immutable stack
With good sharing.
Some queue class, where: (Hard?)
enqueue() creates a new immutable queue
dequeue() creates a new immutable queue
With good sharing.
What is your favorite datastructure?
Bye
Linked list will definitely work well as a "shared" stack object,
because the "tail" of any given stack doesn't change with the operations.
As far as the queue goes, you run the risk of packratting if you share
the underlying data structure. AFAIK, there are three common ways to
implement a straight (as opposed to priority) queue.
1. Linked lists with a head and tail reference
2. Array list with a tail reference, and dequeue shifts all data.
3. Array list with a head and tail reference. Known as a ring deque.
With the array approaches, you need to clear release the head reference
on dequeue to avoid packratting. This happens automatically with the
linked list. This means they can't be "immutable" as dequeue must be
mutative.
For the linked list approach, enqueue is the problematic operation. A
new tail must be appended and the old tail pointer made to point to it.
That operation changes the "next" value in the old tail.
So, you can decide "share on enqueue, copy on dequeue" or "copy on
enqueue, share on dequeue". Based on requirements of your use-case, you
can choose the appropriate alternative. You can't have both, but if you
can get halfway there.