Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.programmer > #9560 > unrolled thread

Immutable Datastructures with good Sharing

Back to article view | Back to comp.lang.java.programmer

Contents

  Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-05 04:03 +0100
    Re: Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-05 12:42 +0100
      Re: Immutable Datastructures with good Sharing markspace <-@.> - 2011-11-05 09:35 -0700
        Re: Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-05 19:33 +0100
          Re: Immutable Datastructures with good Sharing Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-11-05 14:42 -0400
            Re: Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-05 19:52 +0100
              Re: Immutable Datastructures with good Sharing Andreas Leitgeb <avl@gamma.logic.tuwien.ac.at> - 2011-11-05 19:32 +0000
              Re: Immutable Datastructures with good Sharing Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-11-05 15:31 -0400
                Re: Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-05 20:50 +0100
                  Re: Immutable Datastructures with good Sharing Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-11-05 16:26 -0400
                    Re: Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-05 21:35 +0100
                      Re: Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-05 21:38 +0100
                        Re: Immutable Datastructures with good Sharing Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-11-05 16:59 -0400
                          Re: Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-05 22:06 +0100
                      Re: Immutable Datastructures with good Sharing Arne Vajhøj <arne@vajhoej.dk> - 2011-11-05 16:41 -0400
                        Re: Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-05 21:42 +0100
                    Re: Immutable Datastructures with good Sharing Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-11-05 17:11 -0400
              Re: Immutable Datastructures with good Sharing Arne Vajhøj <arne@vajhoej.dk> - 2011-11-05 16:20 -0400
                Re: Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-05 21:33 +0100
                  Re: Immutable Datastructures with good Sharing Arne Vajhøj <arne@vajhoej.dk> - 2011-11-05 16:38 -0400
                    Re: Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-05 21:41 +0100
                      Re: Immutable Datastructures with good Sharing markspace <-@.> - 2011-11-05 17:20 -0700
                        Re: Immutable Datastructures with good Sharing Arved Sandstrom <asandstrom3minus1@eastlink.ca> - 2011-11-05 22:13 -0300
                          Re: Immutable Datastructures with good Sharing markspace <-@.> - 2011-11-05 20:05 -0700
                            Re: Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-06 10:27 +0100
                        Re: Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-06 10:14 +0100
      Re: Immutable Datastructures with good Sharing Lew <lewbloch@gmail.com> - 2011-11-05 10:06 -0700
        Re: Immutable Datastructures with good Sharing Peter Duniho <NpOeStPeAdM@NnOwSlPiAnMk.com> - 2011-11-05 10:55 -0700
          Re: Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-05 19:30 +0100
            Re: Immutable Datastructures with good Sharing Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-11-05 18:16 -0400
              Re: Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-05 23:20 +0100
              Re: Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-05 23:38 +0100
          Re: Immutable Datastructures with good Sharing Arved Sandstrom <asandstrom3minus1@eastlink.ca> - 2011-11-05 17:47 -0300
          Re: Immutable Datastructures with good Sharing Peter Duniho <NpOeStPeAdM@NnOwSlPiAnMk.com> - 2011-11-05 14:26 -0700
        Re: Immutable Datastructures with good Sharing Arne Vajhøj <arne@vajhoej.dk> - 2011-11-05 16:14 -0400
    Re: Immutable Datastructures with good Sharing Peter Duniho <NpOeStPeAdM@NnOwSlPiAnMk.com> - 2011-11-05 14:35 -0700
      Re: Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-05 22:42 +0100
        Re: Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-05 22:50 +0100
        Re: Immutable Datastructures with good Sharing Peter Duniho <NpOeStPeAdM@NnOwSlPiAnMk.com> - 2011-11-05 14:51 -0700
          Re: Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-05 22:58 +0100
            Re: Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-05 23:03 +0100
              Re: Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-05 23:07 +0100
              Re: Immutable Datastructures with good Sharing Jussi Piitulainen <jpiitula@ling.helsinki.fi> - 2011-11-06 09:44 +0200
                Re: Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-06 10:22 +0100
                  Re: Immutable Datastructures with good Sharing Arved Sandstrom <asandstrom3minus1@eastlink.ca> - 2011-11-06 09:05 -0400
                    Re: Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-06 14:16 +0100
                    Re: Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-06 14:22 +0100
                      Re: Immutable Datastructures with good Sharing Andreas Leitgeb <avl@gamma.logic.tuwien.ac.at> - 2011-11-06 14:30 +0000
                        Re: Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-06 16:02 +0100
                        Re: Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-06 16:08 +0100
                        Re: Immutable Datastructures with good Sharing Giovanni Azua <bravegag@hotmail.com> - 2011-11-06 16:18 +0100
                          Re: Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-06 16:54 +0100
                            Re: Immutable Datastructures with good Sharing Giovanni Azua <bravegag@hotmail.com> - 2011-11-06 17:31 +0100
                              Re: Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-06 22:33 +0100
                                Re: Immutable Datastructures with good Sharing Arne Vajhøj <arne@vajhoej.dk> - 2011-11-06 16:47 -0500
                          Re: Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-06 16:58 +0100
                            Re: Immutable Datastructures with good Sharing Tom Anderson <twic@urchin.earth.li> - 2011-11-07 01:01 +0000
                              Re: Immutable Datastructures with good Sharing Lew <lewbloch@gmail.com> - 2011-11-06 17:26 -0800
                                Re: Immutable Datastructures with good Sharing Tom Anderson <twic@urchin.earth.li> - 2011-11-07 23:45 +0000
                          Re: Immutable Datastructures with good Sharing Lew <lewbloch@gmail.com> - 2011-11-06 14:44 -0800
                            Re: Immutable Datastructures with good Sharing Arne Vajhøj <arne@vajhoej.dk> - 2011-11-06 17:51 -0500
                            Re: Immutable Datastructures with good Sharing Giovanni Azua <bravegag@hotmail.com> - 2011-11-07 01:28 +0100
                              Re: Immutable Datastructures with good Sharing Arne Vajhøj <arne@vajhoej.dk> - 2011-11-06 19:50 -0500
                                Re: Immutable Datastructures with good Sharing Giovanni Azua <bravegag@hotmail.com> - 2011-11-07 02:13 +0100
                                  Re: Immutable Datastructures with good Sharing Arne Vajhøj <arne@vajhoej.dk> - 2011-11-06 20:20 -0500
                              Re: Immutable Datastructures with good Sharing Lew <lewbloch@gmail.com> - 2011-11-06 17:29 -0800
                                Re: Immutable Datastructures with good Sharing Giovanni Azua <bravegag@hotmail.com> - 2011-11-07 11:22 +0100
                          Re: Immutable Datastructures with good Sharing Tom Anderson <twic@urchin.earth.li> - 2011-11-06 23:02 +0000
                            Re: Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-07 00:32 +0100
                              Re: Immutable Datastructures with good Sharing Giovanni Azua <bravegag@hotmail.com> - 2011-11-07 01:10 +0100
                                Re: Immutable Datastructures with good Sharing Andreas Leitgeb <avl@gamma.logic.tuwien.ac.at> - 2011-11-07 10:24 +0000
                                  Re: Immutable Datastructures with good Sharing Giovanni Azua <bravegag@hotmail.com> - 2011-11-07 11:52 +0100
                                    Re: Immutable Datastructures with good Sharing Andreas Leitgeb <avl@gamma.logic.tuwien.ac.at> - 2011-11-07 11:12 +0000
                                    Re: Immutable Datastructures with good Sharing Arne Vajhøj <arne@vajhoej.dk> - 2011-11-07 17:24 -0500
                            Re: Immutable Datastructures with good Sharing Giovanni Azua <bravegag@hotmail.com> - 2011-11-07 02:08 +0100
                              Re: Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-07 05:03 +0100
                                Re: Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-07 05:13 +0100
                              Re: Immutable Datastructures with good Sharing Tom Anderson <twic@urchin.earth.li> - 2011-11-07 23:38 +0000
                                Re: Immutable Datastructures with good Sharing Tom Anderson <twic@urchin.earth.li> - 2011-11-09 22:06 +0000
                                  Re: Immutable Datastructures with good Sharing Gene Wirchenko <genew@ocis.net> - 2011-11-09 18:02 -0800
    Re: Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-07 00:28 +0100
      Re: Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-07 00:39 +0100
        Re: Immutable Datastructures with good Sharing Arved Sandstrom <asandstrom3minus1@eastlink.ca> - 2011-11-06 20:57 -0400
          Re: Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-07 04:58 +0100
            Re: Immutable Datastructures with good Sharing Silvio Bierman <silvio@moc.com> - 2011-11-07 15:13 +0100
              Re: Immutable Datastructures with good Sharing Cthun <cthun_202@qmail.net.au> - 2011-11-07 12:54 -0500
                Re: Immutable Datastructures with good Sharing "B1ll Gat3s" <wm.g4t3s@m1cr0s0f7.c0m> - 2011-11-07 18:07 -0500
                  Re: Immutable Datastructures with good Sharing B1ll Gat3s <wm.g4t3s@m1cr0s0f7.c0m> - 2011-11-07 22:07 -0500
                    Re: Immutable Datastructures with good Sharing "B1ll Gat3s" <wm.g4t3s@m1cr0s0f7.c0m> - 2011-11-08 00:17 -0500
                      Re: Immutable Datastructures with good Sharing thoolen <th00len@th0lenbot.thorium> - 2011-11-08 16:03 -0500
                  Re: Immutable Datastructures with good Sharing Cthun <cthun_202@qmail.net.au> - 2011-11-08 15:49 -0500
                    Re: Immutable Datastructures with good Sharing "B1ll Gat3s" <wm.g4t3s@m1cr0s0f7.c0m> - 2011-11-08 18:01 -0500
                      Re: Immutable Datastructures with good Sharing thoolen <th00len@th0lenbot.thorium> - 2011-11-08 20:46 -0500
                        Re: Immutable Datastructures with good Sharing "Cthun" <cthun_202@qmail.net.au> - 2011-11-08 22:43 -0500
                          Re: Immutable Datastructures with good Sharing thoolen <th00len@th0lenbot.thorium> - 2011-11-09 08:28 -0500
                  Re: Immutable Datastructures with good Sharing thoolen <th00len@th0lenbot.thorium> - 2011-11-08 16:00 -0500
    Re: Immutable Datastructures with good Sharing Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2011-11-07 08:46 -0800

Page 1 of 5  [1] 2 3 4 5  Next page →

#9560 — Immutable Datastructures with good Sharing

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

[toc] | [next] | [standalone]

#9566

Stefan Ram schrieb:
>    However, in computer science, a stack is well known as a
>    specific mutable entity with specific performance
>    properties. So, an »immutable stack« should not be called
>    »stack«.

If you take the subdomain of functional programming
in computer science, the people there wouldn't
probably agree. A stack can be viewed as an abstract
datatype:

    push : Stack x Element -> Stack
    pop : Stack -> Stack x Element | Fault

By the above one would loose the possibility to directly
reference a stack by one process. And then see what
an another process is doing on it.

I am interested in functional programming like
implementations of a stack in Java. That show good
sharing. I know for example of the functional
Java project:

http://functionaljava.org/

I could eventually use something like HList from
there. But these classes are highly parameterized
and I don't know whether good Sharing was on their
primary focus.

The interesting case is the Queue.

Best Regards

[toc] | [prev] | [next] | [standalone]

#9577

On 11/5/2011 4:42 AM, Jan Burse wrote:

> I am interested in functional programming like
> implementations of a stack in Java. That show good
> sharing. I know for example of the functional
> Java project:
>
> http://functionaljava.org/


This may also be of interest to you:

<http://openjdk.java.net/projects/lambda/>

[toc] | [prev] | [next] | [standalone]

#9583

markspace schrieb:
> This may also be of interest to you:
>
> <http://openjdk.java.net/projects/lambda/>

Who knows, maybe this could give me a queue with
good sharing. Until now, no bell is ringing...

[toc] | [prev] | [next] | [standalone]

#9585

On 11/5/2011 2:33 PM, Jan Burse wrote:
> markspace schrieb:
>> This may also be of interest to you:
>>
>> <http://openjdk.java.net/projects/lambda/>
>
> Who knows, maybe this could give me a queue with
> good sharing. Until now, no bell is ringing...

     Out of curiosity, why do you want an immutable queue?  What
problem are you trying to solve?

-- 
Eric Sosman
esosman@ieee-dot-org.invalid

[toc] | [prev] | [next] | [standalone]

#9587

Eric Sosman schrieb:
>      Out of curiosity, why do you want an immutable queue?  What
> problem are you trying to solve?

Well it has to be seen in the context of garbage collection.
For example the immutable stack can have a good performance.
For push you just grab a new stack cell from the heap.

When you pop and you have no other pointers to the stack itself
anymore in the application, then cells become eligible to
garbage collection and will quickly reenter the heap and
thus again be available for the application.

In the current situation at hand, you can imagine that
some pointers to the datastructure will nevertheless
still remain, so that I can kind of have a historical
view of what happened with the stack.

This historical view is easiest implemented by an immutable
data structure, but its performance hinges on the fact how
good the sharing works. Same holds for the queue. If a push()
were to copy the full stack I would get a lame application.

Bye

[toc] | [prev] | [next] | [standalone]

#9590

Jan Burse <janburse@fastmail.fm> wrote:
> In the current situation at hand, you can imagine that
> some pointers to the datastructure will nevertheless
> still remain, so that I can kind of have a historical
> view of what happened with the stack.

An immutable stack is quite simple to roll one's own: just a
single-linked list.
An immutable queue is not all that trivial, wrt being able to
add further elements.

Most likely the actually precious and memory-consuming parts of
any stack or queue is the actual payload: the elements, and Java
helps you very well, anyway, to keep those shared.

[toc] | [prev] | [next] | [standalone]

#9591

On 11/5/2011 2:52 PM, Jan Burse wrote:
> Eric Sosman schrieb:
>> Out of curiosity, why do you want an immutable queue? What
>> problem are you trying to solve?
>
> Well it has to be seen in the context of garbage collection.
> For example the immutable stack can have a good performance.
> For push you just grab a new stack cell from the heap.

     First, "stack" and "queue" are not usually thought of as
synonyms.  Second, I don't see what immutability has to do with
the queue's or stack's internal memory management -- especially
if the claimed performance benefits are only seen when mutations
occur!  Third, have you looked at LinkedList?

> In the current situation at hand, you can imagine that
> some pointers to the datastructure will nevertheless
> still remain, so that I can kind of have a historical
> view of what happened with the stack.

     The obvious way to represent the history of a stack is to
build a tree.  For queues (which is what you asked about), the
situation is less obvious -- One can, of course, implement a
queue as a pair of stacks and keep histories of the stacks, but
it's not clear that such a history would be useful.

> This historical view is easiest implemented by an immutable
> data structure,[...]

     Why?  How is this superior to a tree?  What advantage does
immutability grant?  And what happened to queues?

-- 
Eric Sosman
esosman@ieee-dot-org.invalid

[toc] | [prev] | [next] | [standalone]

#9594

Eric Sosman schrieb:
> Why?  How is this superior to a tree?

I don't know what you mean by tree. Via the immutable stack
also a tree arises. Known as spaghetti stack:

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

Lets write [a,b,c] for new Stack("a",new Stack("b",new Stack("c",null))).

     x = [a,b,c];
     y = x.pop();
     z = y.push(d);

Gives you the following tree, I have indicated the variable
pointers by a colon (:):

      x : a   z : d
           \ /
        y : b
            |
            c

 > What advantage does immutability grant?

Immutability grants that the tree does not change, but only
grow. And only the variable pointers might change. And via
GC the tree might also shrink in memory.

 > And what happened to queues?

Just the other operations. Instead of the operations push/pop,
we have the operations enqueue/dequeue. I don't know whether
historical data picture has a special name. My picture so far
is the same as in a supermarket:

      people queing, imagine a supermarket filmed and then
      run 8x times faster or some such.

But no graph theoretic name for it... Sniff.

Bye

[toc] | [prev] | [next] | [standalone]

#9600

On 11/5/2011 3:50 PM, Jan Burse wrote:
> Eric Sosman schrieb:
>> Why? How is this superior to a tree?
>
> I don't know what you mean by tree.

     Wikipedia defines it as "a widely-used data structure that
emulates a hierarchical tree structure with a set of linked nodes."
That's not a very good definition, since trees need not have links,
but it's close enough for jazz.

> Via the immutable stack
> also a tree arises.

     If you don't know what I mean by tree, I don't know what you
mean by tree, either.

> Known as spaghetti stack:
>
> http://en.wikipedia.org/wiki/Spaghetti_stack

     Never heard the term before.  It looks like a tree to me, of
the kind that arises when processing equivalence relations, for example.

> Lets write [a,b,c] for new Stack("a",new Stack("b",new Stack("c",null))).

     Sorry; you've lost me again.  You're clearly not talking about
java.util.Stack (because it has no such constructor), so you must
mean some other kind of Stack -- but you haven't explained what this
Stack is like, so the meaning of your example remains private to you.

>  > What advantage does immutability grant?
>
> Immutability grants that the tree does not change, but only
> grow. And only the variable pointers might change. And via
> GC the tree might also shrink in memory.

     I seem to be having trouble with reading comprehension today.
First, in what sense can the tree grow without changing?  Second,
what can be garbage-collected from a tree that only grows and
never shrinks?

-- 
Eric Sosman
esosman@ieee-dot-org.invalid

[toc] | [prev] | [next] | [standalone]

#9603

Eric Sosman schrieb:
> Stack is like, so the meaning of your example remains private to you.

Fast forward in this thread, and you find the source of
the class Stack. Or you might lookup up a more extended
version here:

http://blogs.msdn.com/b/ericlippert/archive/2007/12/04/immutability-in-c-part-two-a-simple-immutable-stack.aspx

[toc] | [prev] | [next] | [standalone]

#9604

Jan Burse schrieb:
> Eric Sosman schrieb:
>> Stack is like, so the meaning of your example remains private to you.
>
> Fast forward in this thread, and you find the source of
> the class Stack. Or you might lookup up a more extended
> version here:
>
> http://blogs.msdn.com/b/ericlippert/archive/2007/12/04/immutability-in-c-part-two-a-simple-immutable-stack.aspx
>
>

Ok, I make it easy for you:

Jan Burse was writing (19:30):
>      public class Stack {
>           final Object element;
>           final Stack next;
>
>           Stack(e, n) {
>              element = e;
>              next = n;
>           }
>
>           public Stack push(Object e) {
>              return new Stack(e,this);
>           }
>
>           public Object top() {
>              return element;
>           }
>
>           public Stack pop() {
>              return next;
>           }
>       }

[toc] | [prev] | [next] | [standalone]

#9613

On 11/5/2011 4:38 PM, Jan Burse wrote:
> Jan Burse schrieb:
>
> Ok, I make it easy for you:
>
> Jan Burse was writing (19:30):
>> public class Stack {
>> [...]

Stack.java:6: <identifier> expected
     Stack(e, n) {
            ^
Stack.java:6: <identifier> expected
     Stack(e, n) {
               ^
2 errors

-- 
Eric Sosman
esosman@ieee-dot-org.invalid

[toc] | [prev] | [next] | [standalone]

#9614

Eric Sosman schrieb:
> On 11/5/2011 4:38 PM, Jan Burse wrote:
>> Jan Burse schrieb:
>>
>> Ok, I make it easy for you:
>>
>> Jan Burse was writing (19:30):
>>> public class Stack {
>>> [...]
>
> Stack.java:6: <identifier> expected
> Stack(e, n) {
> ^
> Stack.java:6: <identifier> expected
> Stack(e, n) {
> ^
> 2 errors
>

Ok, here comes the revision:

      public class Stack {
           final Object element;
           final Stack next;

           Stack(Object e, Stack n) {
              element = e;
              next = n;
           }

           public Stack push(Object e) {
              return new Stack(e,this);
           }

           public Object top() {
              return element;
           }

           public Stack pop() {
              return next;
           }
       }

     // No license attached

[toc] | [prev] | [next] | [standalone]

#9606

On 11/5/2011 4:35 PM, Jan Burse wrote:
> Eric Sosman schrieb:
>> Stack is like, so the meaning of your example remains private to you.
>
> Fast forward in this thread, and you find the source of
> the class Stack. Or you might lookup up a more extended
> version here:
>
> http://blogs.msdn.com/b/ericlippert/archive/2007/12/04/immutability-in-c-part-two-a-simple-immutable-stack.aspx

That is C# not Java.

The same technique may be possible in Java, but it is not Java.

Arne

[toc] | [prev] | [next] | [standalone]

#9608

Arne Vajhøj schrieb:
> That is C# not Java.

Yes, you are right.

[toc] | [prev] | [next] | [standalone]

#9615

On 11/5/2011 4:48 PM, Stefan Ram wrote:
> Eric Sosman<esosman@ieee-dot-org.invalid>  writes:
>>      Wikipedia defines it as "a widely-used data structure that
>> emulates a hierarchical tree structure with a set of linked nodes."
>> That's not a very good definition, since trees need not have links,
>[...]
>    Without links, how does one represent the absence of a
>    subtree?

     Ever studied Heapsort, or a heap-based priority queue?  There's
clearly a tree involved, but where are the links?  In a heap of N
elements, element [N-1] has two empty subtrees; how is their absence
denoted?

     Or consider the tree (A (B (C D) E (F (G H) I)) () J): Where are
the links?  See the empty subtree?

     See also Knuth "The Art of Computer Programming, Volume I:
Fundamental Algorithms."  The title of section 2.3.3 is "Other
Representations of Trees" ...

-- 
Eric Sosman
esosman@ieee-dot-org.invalid

[toc] | [prev] | [next] | [standalone]

#9598

On 11/5/2011 2:52 PM, Jan Burse wrote:
> Eric Sosman schrieb:
>> Out of curiosity, why do you want an immutable queue? What
>> problem are you trying to solve?
>
> Well it has to be seen in the context of garbage collection.
> For example the immutable stack can have a good performance.
 > For push you just grab a new stack cell from the heap.
 >
 > When you pop and you have no other pointers to the stack itself
 > anymore in the application, then cells become eligible to
 > garbage collection and will quickly reenter the heap and
 > thus again be available for the application.

I would expect worse performance with typical stack operations.

> In the current situation at hand, you can imagine that
> some pointers to the datastructure will nevertheless
> still remain, so that I can kind of have a historical
> view of what happened with the stack.
>
> This historical view is easiest implemented by an immutable
> data structure, but its performance hinges on the fact how
> good the sharing works. Same holds for the queue. If a push()
> were to copy the full stack I would get a lame application.

Yes.

But will the time you spend investigating this really cost less
than what it cost to buy 4 GB more RAM and just clone the objects
you want to store as history.

Arne

[toc] | [prev] | [next] | [standalone]

#9602

Arne Vajhøj schrieb:
> But will the time you spend investigating this really cost less
> than what it cost to buy 4 GB more RAM and just clone the objects
> you want to store as history.

I do this already. But I have an application case where the
cloning not only incures more memory use but also more runtime.
When you clone you need to go through the whole array and copy
each element, this takes time. When you share, you don't need
to spend this time.

Currently the runtime is too high. So if you show me a shop
where I can buy CPU time as I can buy RAM, then this could be a 
solution. But les assume that the CPU time is bounded, so that
we have a real problem case here.

Bye

[toc] | [prev] | [next] | [standalone]

#9605

On 11/5/2011 4:33 PM, Jan Burse wrote:
> Arne Vajhøj schrieb:
>> But will the time you spend investigating this really cost less
>> than what it cost to buy 4 GB more RAM and just clone the objects
>> you want to store as history.
>
> I do this already. But I have an application case where the
> cloning not only incures more memory use but also more runtime.

How do you know that the clone solution use more CPU than
the solution you are looking for now??

> When you clone you need to go through the whole array and copy
> each element, this takes time. When you share, you don't need
> to spend this time.

But you will need to do other things instead.

> Currently the runtime is too high. So if you show me a shop
> where I can buy CPU time as I can buy RAM, then this could be a
> solution.

I believe there are many shops that will sell you
faster CPU's for the existing computers or
more CPU's for other computers.

Arne

[toc] | [prev] | [next] | [standalone]

Page 1 of 5  [1] 2 3 4 5  Next page →

Back to top | Article view | comp.lang.java.programmer

csiph-web