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 3 of 5 — ← Prev page 1 2 [3] 4 5  Next page →

#9623

Jan Burse schrieb:
> Interesting, cool! So its possible...

There should be a book titled THE
IMMUTABLES. I would carry it everywhere.

I have one problem with the usability
of Erics blog. He always writes:

Next time: ...

But I did not yet figure out where
I can press a next time link and
directly go to the next article.

Bye

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

#9624

Jan Burse schrieb:
> Jan Burse schrieb:
>> Interesting, cool! So its possible...
> Bye

Next requirement would be a fast iterator.

But he has:

         public IEnumerator<T> GetEnumerator()
         {
             foreach (T t in forwards) yield return t;
             foreach (T t in backwards.Reverse()) yield return t;
         }


The above doesn't looks so efficient with the reverse.

But I didn't mention this in my initial post...

Bye

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

#9639

Jan Burse writes:

> Jan Burse schrieb:
> > Interesting, cool! So its possible...
> 
> There should be a book titled THE
> IMMUTABLES. I would carry it everywhere.

There is a book titled PURELY FUNCTIONAL DATA
STRUCTURES by Chris Okasaki.

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

#9641

Jussi Piitulainen schrieb:
> There is a book titled PURELY FUNCTIONAL DATA
> STRUCTURES by Chris Okasaki.

Instead of buying the book, one might have a look
at his thesis. Found here:

http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf

I had a look yesterday. And had the feeling that some
parts are a little bit over the top for implementation
in Java, namely the lazy data structure stuff.

The lazy data structure stuff would need to
first figure out a way to easily and efficiently
implement this in Java, maybe for some special
cases only. Guess some closure would be needed.

But otherwise you find the double stack
queue again there.

Bye

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

#9648

On 11-11-06 05:22 AM, Jan Burse wrote:
> Jussi Piitulainen schrieb:
>> There is a book titled PURELY FUNCTIONAL DATA
>> STRUCTURES by Chris Okasaki.
> 
> Instead of buying the book, one might have a look
> at his thesis. Found here:
> 
> http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf
> 
> I had a look yesterday. And had the feeling that some
> parts are a little bit over the top for implementation
> in Java, namely the lazy data structure stuff.
> 
> The lazy data structure stuff would need to
> first figure out a way to easily and efficiently
> implement this in Java, maybe for some special
> cases only. Guess some closure would be needed.
> 
> But otherwise you find the double stack
> queue again there.
> 
> Bye

Okasaki is a great read (I have the hard copy myself), but his work on
functional data structures (either his online thesis or the book) is -
oddly enough - about data structures in *functional* languages. :-) It's
not necessary for getting the general concepts and implementing in an
imperative language like Java [1]. And in order to get the most out of
Okasaki's work one had best have a better than adequate grasp of
university-level CS-type math. If you can immediately understand him
(assuming you read the prior material) when he proclaims that:

"We have just shown that lazy evaluation is necessary to implement
amortized data structures purely functionally."

[Start of section 3.3.2 in online thesis; start of Section 6.2.2 in
book] then you're doing alright. :-)

Given your questions, might I suggest looking at
http://java.dzone.com/articles/fast-immutable-persistent? This guy is
working in Groovy. I won't vouch for the quality of his code but he
appears to be talking about exactly what interests you.

I expect that you have been looking at the Eric Lippert links that Peter
Duniho has pointed you at. These are useful articles.

AHS

1. Java is imperative OOP, Scala and F# can be functional OOP if you try
hard enough.
-- 
You should know the problem before you try to solve it.
Example: When my son was three he cried about a problem with his hand. I
kissed it several times and asked him about the problem. He peed on his
hand.
-- Radia Perlman, inventor of spanning tree protocol

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

#9649

Arved Sandstrom schrieb:
> "We have just shown that lazy evaluation is necessary to implement
> amortized data structures purely functionally."

I you strike out the phrase "purely functionally", then I
read it as "sufficient".

I can imagine that a little destructive mechanism under
the hood of a datastructure, does not need to violate it
beeing immutable. Here is an example, take the hashCode()
function java.lang.String. Usually the value is cached, so
code reads:

     if (hash==0) {
         /* compute the hash in h */
         hash = h;
     }
     return hash;

This does not destroy immutability of the String. So I
would be interested in Java solutions for the problem
at hand. And this solution could be inspired by solutions
coming from the purely functional world, but they don't
need to be based on purely functional programming.

The only requirement is "immutable" and "good sharing".

Bye

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

#9651

Arved Sandstrom schrieb:
> Given your questions, might I suggest looking at
> http://java.dzone.com/articles/fast-immutable-persistent? This guy is
> working in Groovy.

Thanks for the link, looks like he is implementing
the queue with two stacks, with the extra that
he has addFirst() and addLast(), besides only enQueue().

Bye

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

#9653

Jan Burse <janburse@fastmail.fm> wrote:
> Arved Sandstrom schrieb:
>> Given your questions, might I suggest looking at
>> http://java.dzone.com/articles/fast-immutable-persistent? This guy is
>> working in Groovy.
> Thanks for the link, looks like he is implementing
> the queue with two stacks, with the extra that
> he has addFirst() and addLast(), besides only enQueue().

But then again, the queue(s) before and after re-arranging the
stacks do not share much data...

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

#9655

Andreas Leitgeb schrieb:
> But then again, the queue(s) before and after re-arranging the
> stacks do not share much data...

Thats why I don't particularly like this solutions,
and hope that there will come up some other suggestions...

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

#9656

Andreas Leitgeb schrieb:
> But then again, the queue(s) before and after re-arranging the
> stacks do not share much data...

Thats why I don't particularly like this solutions,
and hope that there will come up some other suggestions...

There is only a sharing between subsequent enQueue(),
and also between subsequent deQueue(). But as soon as
a deQueue() its the empty stack the other stack is reversed.

Well that is not bad, but a little bit arbitrary. Maybe
there are datastructures where something happens based
on some bound, similarly like the elements allocated ahead
in an ArrayList. When you create an ArrayList it will have a
default allocation of 10 elements (implementation dependent)
for use, and it then grows by 150% (implementation dependent)
when additional elements are needed.

But an ArrayList is not immutable. You cannot keep a pointer
on it, it will get modified by subsequent operations...

Bye

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

#9658

Hello,

I haven't read/followed the whole OP Thread discussion but I thought it was
worth mentioning/recommending the Google "Guava Project":
http://code.google.com/p/guava-libraries/

I think they really "went to town" on that one. You have strongly typed
Immutable Collection definitions for all Java Collection types e.g.
ImmutableMap.Builder, ImmutableList.Builder. The design is awesome e.g. the
Builder pattern as prescribed in Effective Java (last edition) and the
performance gains are noticeable as well e.g. In a distributed system I have
been working on lately, switching the attribute instances of the DTO Beans
from ArrayList Java Collection to use instead the implementation from Guava
gave some noticeable 15-20% Serialization performance gain e.g. Test case
involving 1-Echo-Server and 1K-Clients.

I really enjoy the improvement in code readability as well, it suits the
appropriate template types e.g.

// from
List<RequestData> requests = new ArrayList<RequestData>();

// to
List<RequestData> requests = Lists.newArrayList();

Guava really rocks! Would this be the Java Collections design debt now
finally paid by Joshua Bloch?

HTH,
Best regards,
Giovanni
   

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

#9659

Giovanni Azua schrieb:
> Hello,
>
> I haven't read/followed the whole OP Thread discussion but I thought it was
> worth mentioning/recommending the Google "Guava Project":
> http://code.google.com/p/guava-libraries/
>
> I think they really "went to town" on that one. You have strongly typed
> Immutable Collection definitions for all Java Collection types e.g.
> ImmutableMap.Builder, ImmutableList.Builder. The design is awesome e.g. the
> Builder pattern as prescribed in Effective Java (last edition) and the
> performance gains are noticeable as well e.g. In a distributed system I have
> been working on lately, switching the attribute instances of the DTO Beans
> from ArrayList Java Collection to use instead the implementation from Guava
> gave some noticeable 15-20% Serialization performance gain e.g. Test case
> involving 1-Echo-Server and 1K-Clients.
>
> I really enjoy the improvement in code readability as well, it suits the
> appropriate template types e.g.
>
> // from
> List<RequestData>  requests = new ArrayList<RequestData>();
>
> // to
> List<RequestData>  requests = Lists.newArrayList();
>
> Guava really rocks! Would this be the Java Collections design debt now
> finally paid by Joshua Bloch?
>
> HTH,
> Best regards,
> Giovanni
>
>
>

Thank you very much for the hint. Just googled the google
code library for "Immutable". Found another project as well:

http://code.google.com/p/pcollections/

And one based on Scala:

http://code.google.com/p/scala-deque/

And some not projects which do not yet show some download.

Bye

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

#9661

Hi Jan,

On 11/6/11 4:54 PM, in article 4EB6ADAD.8040001@fastmail.fm, "Jan Burse"
<janburse@fastmail.fm> wrote:
> Thank you very much for the hint. Just googled the google
> code library for "Immutable". Found another project as well:
> 
> http://code.google.com/p/pcollections/
> 
> And one based on Scala:
> 
> http://code.google.com/p/scala-deque/
> 
> And some not projects which do not yet show some download.
> 
> Bye
>
Be careful with what you re-use. What I recommended is __Google's core
libraries__ "The Guava project contains several of Google's core libraries
that we rely on in our Java-based projects: collections, caching, primitives
support, concurrency libraries, common annotations, string processing, I/O,
and so forth."

What you found are OS projects from independent non-Google developers that
are just _hosted_ in Google code. I haven't used those and can't recommend
them. The difference might be somewhat similar to watching Hollywood movies
vs. Alternative "artsy" low cost movies :) so to speak.

HTH,
Best regards,
Giovanni

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

#9682

Giovanni Azua schrieb:
> Be careful with what you re-use. What I recommended is __Google's core
> libraries__ "The Guava project contains several of Google's core libraries
> that we rely on in our Java-based projects: collections, caching, primitives
> support, concurrency libraries, common annotations, string processing, I/O,
> and so forth."

I don't need all this, I only need
some collection.

> What you found are OS projects from independent non-Google developers that
> are just _hosted_ in Google code. I haven't used those and can't recommend
> them. The difference might be somewhat similar to watching Hollywood movies
> vs. Alternative "artsy" low cost movies  so to speak.

Well being a Googler might imply profes-
sionality. But being a non-Googler then
does not necessarily imply non-profes-
sionality.

This is the fallacy of:

If

    A -> B

Then

    ~A -> ~B

You can easily verify this conclusion
to be false by a truth table.

Bye

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

#9683

On 11/6/2011 4:33 PM, Jan Burse wrote:
> Giovanni Azua schrieb:
>> Be careful with what you re-use. What I recommended is __Google's core
>> libraries__ "The Guava project contains several of Google's core
>> libraries
>> that we rely on in our Java-based projects: collections, caching,
>> primitives
>> support, concurrency libraries, common annotations, string processing,
>> I/O,
>> and so forth."
>
> I don't need all this, I only need
> some collection.
>
>> What you found are OS projects from independent non-Google developers
>> that
>> are just _hosted_ in Google code. I haven't used those and can't
>> recommend
>> them. The difference might be somewhat similar to watching Hollywood
>> movies
>> vs. Alternative "artsy" low cost movies so to speak.
>
> Well being a Googler might imply profes-
> sionality. But being a non-Googler then
> does not necessarily imply non-profes-
> sionality.
>
> This is the fallacy of:
>
> If
>
> A -> B
>
> Then
>
> ~A -> ~B
>
> You can easily verify this conclusion
> to be false by a truth table.

I think that was exactly what Giovanni said.

Arne

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

#9660

Giovanni Azua schrieb:
> I think they really "went to town" on that one. You have strongly typed
> Immutable Collection definitions for all Java Collection types e.g.
> ImmutableMap.Builder, ImmutableList.Builder.

Somebody here, who could throw a spot light on how they do a Queue?

Bye

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

#9713

On Sun, 6 Nov 2011, Jan Burse wrote:

> Somebody here, who could throw a spot light on how they do a Queue?

I can tell you how i do an O(1), well-sharing queue:

public final class ImmutableQueue<E> {

 	private static class Link<E> {

 		public final E element;
 		public final Link<E> next;

 		public Link(E element, Link<E> next) {
 			this.element = element;
 			this.next = next;
 		}

 	}

 	private final Link<E> head;
 	private final Link<E> tail;
 	private final Link<Link<E>> tuft;

 	private ImmutableQueue(Link<E> head, Link<E> tail, Link<Link<E>> tuft) {
 		assert (tuft == null) || (tuft.element.next == tail);
 		this.head = head;
 		this.tail = tail;
 		this.tuft = tuft;
 	}

 	private ImmutableQueue(Link<E> element) {
 		this(element, element, null);
 	}

 	public ImmutableQueue() {
 		this(null);
 	}

 	public boolean isEmpty() {
 		return head == null;
 	}

 	public int size() {
 		if (isEmpty()) return 0;
 		int size = 1;
 		Link<E> link = head;
 		while (link != tail) {
 			++size;
 			link = link.next;
 		}
 		return size;
 	}

 	public ImmutableQueue<E> enqueue(E element) {
 		Link<E> enqueued = new Link<E>(element, head);
 		if (isEmpty()) return new ImmutableQueue<E>(enqueued);
 		else return new ImmutableQueue<E>(enqueued, tail, null);
 	}

 	public ImmutableQueue<E> dequeue(E[] holder) {
 		ImmutableQueue<E> queue;

 		if (head == null) {
 			throw new NoSuchElementException();
 		}
 		else if (head == tail) {
 			queue = new ImmutableQueue<E>();
 		}
 		else {
 			Link<Link<E>> tuft = this.tuft;
 			if (tuft == null) {
 				tuft = backcomb();
 				assert tuft.element.next == tail;
 			}
 			queue = new ImmutableQueue<E>(head, tuft.element, tuft.next);
 		}

 		holder[0] = tail.element;
 		return queue;
 	}

 	private Link<Link<E>> backcomb() {
 		Link<Link<E>> tuft = null;
 		Link<E> link = head;
 		while (link != tail) {
 			tuft = new Link<Link<E>>(link, tuft);
 			link = link.next;
 		}
 		return tuft;
 	}

}

I'm sure it's obvious what's going on here.

But if not: the core of it is a normal immutable linked list, growing at 
the enqueue end. Dequeue is handled by tracking a tail pointer, and 
pretending that links past the tail don't exist (rather than treating a 
null next pointer as defining the end as usual). There is then an 
antiparallel linked list (rooted in 'tuft' - extending the 'tail' metaphor 
a bit), starting just before the tail and running back to the head; this 
list essentially turns the list into a doubly-linked list, and so allows 
efficient dequeues.

Keeping that list accurate at all times would be expensive, so instead, it 
is constructed when needed, ie when we need to dequeue and we don't have 
it. Note that when it is constructed, it reaches all the way back to the 
head, but as more elements are enqueued, the head moves away from its 
tail, leaving it only partially covering the queue. That's fine: we only 
use it to find the link before the tail, so we don't need it to go far. 
When we've dequeued enough elements to have worn it down completely, we 
rebuild it.

Enqueueing is obviously O(1). Dequeueing is O(1) if you don't need to 
rebuild the backwards list. If you do need to rebuild the backwards list, 
it's O(n); you will then not need to rebuild for another n dequeues, which 
makes it amortatively O(1).

In terms of sharing, all the forward links are shared. Backwards links 
will be shared too, but if two separate lineages of queues both have to 
rebuild the backwards list, the links will not be shared, even though 
they are identical. Consider:

ImmutableQueue noah; // has one backward link remaining
ImmutableQueue shem = noah.dequeue(holder);
ImmutableQueue ham = noah.dequeue(holder);
// shem and ham are identical
ImmutableQueue elam = shem.dequeue(holder);
ImmutableQueue cush = ham.dequeue(holder);
// elam and cush are identical, but have separate backward lists

In terms of packratting, backwards lists become garbage, but the links in 
forward lists never do. You could always walk from any head right back yea 
even unto the first tail. I think that's hard to avoid in an immutable 
structure.

Also, i think i've just grokked what that C# dude's half-backwards list is 
all about. It's like this, but throwing away the forwards list when you 
make the backwards list, which saves memory and lets forward list links 
become garbage. Clever stuff.

tom

-- 
FRUIT FUCKER has joined the party!

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

#9718

Tom Anderson wrote:
> Jan Burse wrote:
>> Somebody here, who could throw a spot light on how they do a Queue?
> 
> I can tell you how i do an O(1), well-sharing queue:
> 
> public final class ImmutableQueue<E> {
> 
>  	private static class Link<E> {

Side note:  One might observe that this 'E' does not correspond to the 'E' of the outer class's generic parameter.  One might also observe that this does no harm whatsoever.

Side note 2:  TABs?  Really?

>  		public final E element;
>  		public final Link<E> next;
> 
>  		public Link(E element, Link<E> next) {
>  			this.element = element;
>  			this.next = next;
>  		}
> 
>  	}
> 
>  	private final Link<E> head;
>  	private final Link<E> tail;
>  	private final Link<Link<E>> tuft;
> 
>  	private ImmutableQueue(Link<E> head, Link<E> tail, Link<Link<E>> tuft) {
>  		assert (tuft == null) || (tuft.element.next == tail);
>  		this.head = head;
>  		this.tail = tail;
>  		this.tuft = tuft;
>  	}
> 
>  	private ImmutableQueue(Link<E> element) {
>  		this(element, element, null);
>  	}
> 
>  	public ImmutableQueue() {
>  		this(null);
>  	}
> 
>  	public boolean isEmpty() {
>  		return head == null;
>  	}
> 
>  	public int size() {
>  		if (isEmpty()) return 0;
>  		int size = 1;
>  		Link<E> link = head;
>  		while (link != tail) {
>  			++size;
>  			link = link.next;
>  		}

Alternative form if you like for loops:

                for (Link<E> link = head; link != tail; link = link.next) {
                        ++size;
                }

>  		return size;
>  	}
> 
>  	public ImmutableQueue<E> enqueue(E element) {
>  		Link<E> enqueued = new Link<E>(element, head);
>  		if (isEmpty()) return new ImmutableQueue<E>(enqueued);
>  		else return new ImmutableQueue<E>(enqueued, tail, null);
>  	}
> 
>  	public ImmutableQueue<E> dequeue(E[] holder) {
>  		ImmutableQueue<E> queue;
> 
>  		if (head == null) {
>  			throw new NoSuchElementException();
>  		}
>  		else if (head == tail) {
>  			queue = new ImmutableQueue<E>();
>  		}
>  		else {
>  			Link<Link<E>> tuft = this.tuft;
>  			if (tuft == null) {
>  				tuft = backcomb();
>  				assert tuft.element.next == tail;
>  			}
>  			queue = new ImmutableQueue<E>(head, tuft.element, tuft.next);
>  		}
> 
>  		holder[0] = tail.element;
>  		return queue;
>  	}
> 
>  	private Link<Link<E>> backcomb() {
>  		Link<Link<E>> tuft = null;
>  		Link<E> link = head;
>  		while (link != tail) {
>  			tuft = new Link<Link<E>>(link, tuft);
>  			link = link.next;
>  		}
>  		return tuft;
>  	}
> 
> }
> 
> I'm sure it's obvious what's going on here.
> 
> But if not: the core of it is a normal immutable linked list, growing at 
> the enqueue end. Dequeue is handled by tracking a tail pointer, and 
> pretending that links past the tail don't exist (rather than treating a 
> null next pointer as defining the end as usual). There is then an 
> antiparallel linked list (rooted in 'tuft' - extending the 'tail' metaphor 
> a bit), starting just before the tail and running back to the head; this 
> list essentially turns the list into a doubly-linked list, and so allows 
> efficient dequeues.
> 
> Keeping that list accurate at all times would be expensive, so instead, it 
> is constructed when needed, ie when we need to dequeue and we don't have 
> it. Note that when it is constructed, it reaches all the way back to the 
> head, but as more elements are enqueued, the head moves away from its 
> tail, leaving it only partially covering the queue. That's fine: we only 
> use it to find the link before the tail, so we don't need it to go far. 
> When we've dequeued enough elements to have worn it down completely, we 
> rebuild it.
> 
> Enqueueing is obviously O(1). Dequeueing is O(1) if you don't need to 
> rebuild the backwards list. If you do need to rebuild the backwards list, 
> it's O(n); you will then not need to rebuild for another n dequeues, which 
> makes it amortatively O(1).
> 
> In terms of sharing, all the forward links are shared. Backwards links 
> will be shared too, but if two separate lineages of queues both have to 
> rebuild the backwards list, the links will not be shared, even though 
> they are identical. Consider:
> 
> ImmutableQueue noah; // has one backward link remaining
> ImmutableQueue shem = noah.dequeue(holder);
> ImmutableQueue ham = noah.dequeue(holder);
> // shem and ham are identical
> ImmutableQueue elam = shem.dequeue(holder);
> ImmutableQueue cush = ham.dequeue(holder);
> // elam and cush are identical, but have separate backward lists
> 
> In terms of packratting, backwards lists become garbage, but the links in 
> forward lists never do. You could always walk from any head right back yea 
> even unto the first tail. I think that's hard to avoid in an immutable 
> structure.
> 
> Also, i think i've just grokked what that C# dude's half-backwards list is 
> all about. It's like this, but throwing away the forwards list when you 
> make the backwards list, which saves memory and lets forward list links 
> become garbage. Clever stuff.

It's a sweet piece of work.  Thanks for sharing it.

-- 
Lew

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

#9757

On Sun, 6 Nov 2011, Lew wrote:

> Tom Anderson wrote:
>> Jan Burse wrote:
>>> Somebody here, who could throw a spot light on how they do a Queue?
>>
>> I can tell you how i do an O(1), well-sharing queue:
>>
>> public final class ImmutableQueue<E> {
>>
>>  	private static class Link<E> {
>
> Side note:  One might observe that this 'E' does not correspond to the 
> 'E' of the outer class's generic parameter.  One might also observe that 
> this does no harm whatsoever.

Yes, certainly worth noting, though. I did have this being a non-static 
inner class at some point; i think that works, but given that instances of 
it are shared between many different instances of the outer class, it 
seems wrong.

> Side note 2:  TABs?  Really?

I wrote it in Eclipse, which i have set up to use tabs, and 
copy-and-pasted it. The tabs stayed tabs. I could have reformatted it with 
spaces, but i just wanted to post it and get to bed.

Actually, i did it just to annoy you.

>>  	public int size() {
>>  		if (isEmpty()) return 0;
>>  		int size = 1;
>>  		Link<E> link = head;
>>  		while (link != tail) {
>>  			++size;
>>  			link = link.next;
>>  		}
>
> Alternative form if you like for loops:
>
>                for (Link<E> link = head; link != tail; link = link.next) {
>                        ++size;
>                }
>
>>  		return size;
>>  	}

Yes, that's nice.

A serious implementation of this would probably just track the size in a 
variable, rather than counting the links each time.

tom

-- 
There is no violence or enmity in the LEGO universe until you, the
builder, decide what to build with the pieces. -- Pyrogenic

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

#9690

Giovanni Azua wrote:
> I haven't read/followed the whole OP Thread discussion but I thought it was
> worth mentioning/recommending the Google "Guava Project":
> http://code.google.com/p/guava-libraries/
> 
> I think they really "went to town" on that one. You have strongly typed
> Immutable Collection definitions for all Java Collection types e.g.
> ImmutableMap.Builder, ImmutableList.Builder. The design is awesome e.g. the
> Builder pattern as prescribed in Effective Java (last edition) and the
> performance gains are noticeable as well e.g. In a distributed system I have
> been working on lately, switching the attribute instances of the DTO Beans
> from ArrayList Java Collection to use instead the implementation from Guava
> gave some noticeable 15-20% Serialization performance gain e.g. Test case
> involving 1-Echo-Server and 1K-Clients.
> 
> I really enjoy the improvement in code readability as well, it suits the
> appropriate template types e.g.
> 
> // from
> List<RequestData> requests = new ArrayList<RequestData>();
> 
> // to
> List<RequestData> requests = Lists.newArrayList();
> 
> Guava really rocks! Would this be the Java Collections design debt now
> finally paid by Joshua Bloch?

I'm not saying anything against Guava, but I fail to see the advantage of that particular idiom.  'Lists.newArrayList' vs. 'new ArrayList<>' - eh, mezza mezz'.

Whatever floats your boat.


-- 
Lew

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

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

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

csiph-web