final ImmutableSet.Builder<A> builder = ImmutableSet.builder()
builder.addAll(set0);
builder.add(new A());
final Set<A> set1 = builder.build();
Hi,starting to dig into guava I wonder what the general contract is to add an element to an already existing immutable collection.Of course that addition would not modify the existing object.final Set<A> set0 = ImmutableSet.of();final Set<A> set1 = set0.add2(new A());//does not modify set0, returns a new set1 which is a superset to set0System.out.println(set0.size()) //0System.out.println(set1.size()) //1I am quite sure that you have thought about the use case of an immutable collection that one might want to build dynamically for instance. For that particular case I think that the builder is used(?).List<A> buildList(final int n, final ImmutableList.Builder<A> builder) {if(n == 0) { return builder.build(); }else { return buildList(n - 1, builder.add(new A()); }}But should I also use the builder if I already have an immutable list and want to add only a single element to it? E.g.final ImmutableSet.Builder<A> builder = ImmutableSet.builder()builder.addAll(set0);builder.add(new A());final Set<A> set1 = builder.build();I am just asking because it would add unnecessary boilerplate to the code and if that is the proposed way to handle this.I would expect a helper method like set1 = Sets.add(set0, value). But again that is why I am asking. I probably missed something in the docs.Best,Joa Ebert--
guava-...@googlegroups.com.
http://groups.google.com/group/guava-discuss?hl=en
unsubscribe: guava-discus...@googlegroups.com
This list is for discussion; for help, post to Stack Overflow instead:
http://stackoverflow.com/questions/ask
Use the tag "guava".
Okay, I will quickly explain why I would like to use an immutable list.I have a class Signal with observers attached. Signal can dispatch a message to all its observers. Anyone can add or remove observers to the signal, or clear the list of observers.During the dispatch phase, the state of the observer list does not change and is only taken into account in the next phase.In pseudo code:o1.exec = signal.remove(o2)o2.exec = signal.add(o3);signal.add(o1);signal.add(o2);signal.dispatch(); //o2 is executed, o3 is not executedsignal.dispatch(); //o2 has been removed, o3 is executed because it has been added in the previous dispatch phase.Here is pseudo code for an implementation that uses immutable lists:Signal<A> {List<Observer<A>> list = Niladd(Observer<A> observer) { list = list.add(observer) }remove(Observer<A> observer) { list = list.remove(observer) }clear() { list = Nil }dispatch(A value) {List<Observer<A>> listSnapshot = listfor(Observer<A> o : listSnapshot) { o.exec(value) }}}How would this work with a mutable list? Well obviously one can clone the list in the beginning of dispatch to make sure you are working with a snapshot of the state. But then I would ask: why are you not using an immutable list in the first place? The memory footprint would be much better. Of course then you could say: Use a boolean to capture when you are in the dispatch phase, and clone the list only as needed. That is correct but would make the code larger and unnecessarily complex.Best,Joa
--
guava-...@googlegroups.com.
http://groups.google.com/group/guava-discuss?hl=en
unsubscribe: guava-discus...@googlegroups.com
This list is for discussion; for help, post to Stack Overflow instead:
http://stackoverflow.com/questions/ask
Use the tag "guava".
I strongly recommend that you get a copy of Java Concurency in Practice -- and then _read it_. :) It exactly covers this. Seriously, it's exactly what it's for. The only reason you might not want it is because the number of mutations to the list is so frequent that COWAL is no longer efficient. Keep in mind that with your solution as-is, you aren't guaranteed thread safety, and could lose mutation operations. Or are you not interested in thread safety?
On Wed, Dec 29, 2010 at 3:09 AM, Joa Ebert <joae...@googlemail.com> wrote:Thank you Robert, it is definitely an option.Is there any particular reason you voted against more powerful immutable collections (add, remove, filter, ...)?
--
guava-...@googlegroups.com.
http://groups.google.com/group/guava-discuss?hl=en
unsubscribe: guava-discus...@googlegroups.com
This list is for discussion; for help, post to Stack Overflow instead:
http://stackoverflow.com/questions/ask
Use the tag "guava".
Just for the record, there's some good research on purely function
data structures. The Okasaki paper (and book with same name) is a
great starter:
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.62.505
Best regards,
Daniel Yokomizo.
Immutable collections in general make concurrency easy. Persistent
collections have pretty good performance characteristics -- often good
enough to suit needs. Graph and search algorithms become easier to
implement, especially when you want them to be concurrent. You might
win some by implementing specialized structures, but often it won't be
much and chances are it's just not worth it.
--
Johan Van den Neste
I'd say they typically perform much better than that. At least the
implementations used in Clojure and Scala 2.8 do.
log32(n) vs log2(n)
--
Johan Van den Neste
> On Thu, Dec 30, 2010 at 6:39 AM, Dimitris Andreou <jim.a...@gmail.com>
> wrote:
>>
>>
>> On Thu, Dec 30, 2010 at 2:47 AM, Torbjorn
>> Gannholm <to...@google.com> wrote:
>>>
>>>
>>> On Thu, Dec 30, 2010 at 11:28 AM, Dimitris
>>> Andreou <jim.a...@gmail.com> wrote:
>>>>
>>>> On Thu, Dec 30, 2010 at 2:10 AM, Torbjorn
>>>> Gannholm <to...@google.com> wrote:
>>>>>
>>>>>
>>>>> On Thu, Dec 30, 2010 at 11:00 AM, Dimitris
>>>>> Andreou <jim.a...@gmail.com> wrote:
>>>>>>
>>>>>> I'd love to see good persistent collections, at the quality level of
>>>>>> guava, but probably guava would not be the proper place for this. With
>>>>>> guava's popularity, putting these there would just encourage overusing them
>>>>>> - and from my scala experience I learned that many people would love to
>>>>>> start choosing suboptimal structures just for the sake of "purity".
>>>>>> Persistent structures border (and not coincide, since classic work on
>>>>>> persistent structures actually depends on mutations) with functional
>>>>>> programming, which can trigger that effect.
>>>>>> There are various graph algorithms though that cannot be implemented
>>>>>> efficiently without persistent collections. A good example is finding k
>>>>>> shortest paths, instead of just one (so to have some alternatives) - this
>>>>>> needs persistent heaps. Another example is simply depth-first traversals,
>>>>>> where persistent stacks can offer richer semantics: instead of just visiting
>>>>>> nodes, client code can safely be visiting the whole paths from the root,
>>>>>> basically for free.
>>>>>
>>>>> Do you have some pointers for this?
>>>>> /tobe
>>>>>
>>>>
>>>> I'll assume that you refer to the shortest paths: this is what I had in
>>>> mind: Finding the k Shortest Paths (pdf), specifically section 2.
>>>
>>> Thanks.
>>>
>>> I'm still having a problem seeing that persistent collections could be
>>> useful (and used for the right reasons) in a larger context. I assume that
>>> when writing an optimal algorithm one would tend to write a specialized data
>>> structure anyway.
>>
>> I agree with the scope, these are just needed for a small minority
>> compared to java/guava collections. That said, it's still a pity, in the
>> java community that is in the millions, to be working on a problem, then
>> realizing that a persistent structure is needed, then be sidetracked for a
>> couple of weeks producing a so-and-so implementation.
>>
>>>
>>> A persistent stack seems to give a large savings, but I'm not sure I see
>>> it being very useful
>>
>> I don't know. I only found it useful in graph algorithms, for
>> representing/combining paths (persistent stack is not too useful for
>> combining paths either, since it can only append a single element, but this
>> can be easily generalized to a rope-like structure with O(1)
>> appending/prepending of other ropes; only the shape of the implicit tree
>> would change, consecutive versions of ropes wouldn't have to form a
>> right-leaning tree, as consecutive versions of a stack would). By the way,
>> scala guys use it passionately as a replacement for java.util.ArrayList, but
>> this just wastes memory.
>>
>>>
>>> Is there any particular structure that you see as both giving a
>>> significant savings and a high utility (i.e. all other existing
>>> implementations would be a significantly worse choice)?
>>
>> I won't suggest a specific structure, but I've ran many times into the
>> need of creating a new set that is basically some existing one, with some
>> additions and/or removals, but without being able to destroy the original
>> set. I typically end up copying HashSets, which is painfully inefficient
>> when the changes are small. But: (1) I don't know if this is a common
>> problem for other people too, and (2) one could try to simulate some of the
>> benefits of a persistent structure by using the union/difference/etc views
>> in Sets, but such an approach has tricky performance implications
>> (especially so if views are recursively built/pile up).
>> Other than that, I can't think of anything important right now, if this
>> carries enough importance at all.
>> Dimitris
>>>
>>> /tobe
>>>
>>>>
>>>>
>>>>>>
>>>>>> On Thu, Dec 30, 2010 at 1:35 AM, Johan Van den
>>>>>> Neste <jvdn...@gmail.com> wrote:
>>>>>>>
>>>>>>> Related, I would love to see persistent collections added to guava.
>>>>>>>
>>>>>>> Such as http://code.google.com/p/pcollections/
>>>>>>>
>>>>>>>
>>>>>>> --
>>>>>>> Johan Van den Neste
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> On Wed, Dec 29, 2010 at 6:39 PM, Louis Wasserman
>>>>>>> <wasserm...@gmail.com> wrote:
> As a programmer with a purely functional background, I should mention thatI'd say they typically perform much better than that. At least the
> the asymptotics and performance of well-designed persistent map
> implementations are essentially the same as those of TreeMap.
implementations used in Clojure and Scala 2.8 do.
log32(n) vs log2(n)
I'd love to see good persistent collections, at the quality level of guava, but probably guava would not be the proper place for this. With guava's popularity, putting these there would just encourage overusing them - and from my scala experience I learned that many people would love to start choosing suboptimal structures just for the sake of "purity". Persistent structures border (and not coincide, since classic work on persistent structures actually depends on mutations) with functional programming, which can trigger that effect.
--
guava-...@googlegroups.com.
http://groups.google.com/group/guava-discuss?hl=en
unsubscribe: guava-discus...@googlegroups.com
This list is for discussion; for help, post to Stack Overflow instead:
http://stackoverflow.com/questions/ask
Use the tag "guava".
Thank you Robert, it is definitely an option.Is there any particular reason you voted against more powerful immutable collections (add, remove, filter, ...)?
--
Thank you Robert, it is definitely an option.Is there any particular reason you voted against more powerful immutable collections (add, remove, filter, ...)?
--
guava-...@googlegroups.com.
http://groups.google.com/group/guava-discuss?hl=en
unsubscribe: guava-discus...@googlegroups.com
This list is for discussion; for help, post to Stack Overflow instead:
http://stackoverflow.com/questions/ask
Use the tag "guava".
Such as http://code.google.com/p/pcollections/
--
Johan Van den Neste
On Wed, Dec 29, 2010 at 6:39 PM, Louis Wasserman
<wasserm...@gmail.com> wrote:
I'd love to see good persistent collections, at the quality level of guava, but probably guava would not be the proper place for this. With guava's popularity, putting these there would just encourage overusing them - and from my scala experience I learned that many people would love to start choosing suboptimal structures just for the sake of "purity". Persistent structures border (and not coincide, since classic work on persistent structures actually depends on mutations) with functional programming, which can trigger that effect.There are various graph algorithms though that cannot be implemented efficiently without persistent collections. A good example is finding k shortest paths, instead of just one (so to have some alternatives) - this needs persistent heaps. Another example is simply depth-first traversals, where persistent stacks can offer richer semantics: instead of just visiting nodes, client code can safely be visiting the whole paths from the root, basically for free.
On Thu, Dec 30, 2010 at 11:00 AM, Dimitris Andreou <jim.a...@gmail.com> wrote:
I'd love to see good persistent collections, at the quality level of guava, but probably guava would not be the proper place for this. With guava's popularity, putting these there would just encourage overusing them - and from my scala experience I learned that many people would love to start choosing suboptimal structures just for the sake of "purity". Persistent structures border (and not coincide, since classic work on persistent structures actually depends on mutations) with functional programming, which can trigger that effect.There are various graph algorithms though that cannot be implemented efficiently without persistent collections. A good example is finding k shortest paths, instead of just one (so to have some alternatives) - this needs persistent heaps. Another example is simply depth-first traversals, where persistent stacks can offer richer semantics: instead of just visiting nodes, client code can safely be visiting the whole paths from the root, basically for free.
Do you have some pointers for this?
/tobe
On Thu, Dec 30, 2010 at 2:10 AM, Torbjorn Gannholm <to...@google.com> wrote:On Thu, Dec 30, 2010 at 11:00 AM, Dimitris Andreou <jim.a...@gmail.com> wrote:
I'd love to see good persistent collections, at the quality level of guava, but probably guava would not be the proper place for this. With guava's popularity, putting these there would just encourage overusing them - and from my scala experience I learned that many people would love to start choosing suboptimal structures just for the sake of "purity". Persistent structures border (and not coincide, since classic work on persistent structures actually depends on mutations) with functional programming, which can trigger that effect.There are various graph algorithms though that cannot be implemented efficiently without persistent collections. A good example is finding k shortest paths, instead of just one (so to have some alternatives) - this needs persistent heaps. Another example is simply depth-first traversals, where persistent stacks can offer richer semantics: instead of just visiting nodes, client code can safely be visiting the whole paths from the root, basically for free.
Do you have some pointers for this?
/tobe
I'll assume that you refer to the shortest paths: this is what I had in mind: Finding the k Shortest Paths (pdf), specifically section 2.
On Thu, Dec 30, 2010 at 11:28 AM, Dimitris Andreou <jim.a...@gmail.com> wrote:
On Thu, Dec 30, 2010 at 2:10 AM, Torbjorn Gannholm <to...@google.com> wrote:On Thu, Dec 30, 2010 at 11:00 AM, Dimitris Andreou <jim.a...@gmail.com> wrote:I'd love to see good persistent collections, at the quality level of guava, but probably guava would not be the proper place for this. With guava's popularity, putting these there would just encourage overusing them - and from my scala experience I learned that many people would love to start choosing suboptimal structures just for the sake of "purity". Persistent structures border (and not coincide, since classic work on persistent structures actually depends on mutations) with functional programming, which can trigger that effect.There are various graph algorithms though that cannot be implemented efficiently without persistent collections. A good example is finding k shortest paths, instead of just one (so to have some alternatives) - this needs persistent heaps. Another example is simply depth-first traversals, where persistent stacks can offer richer semantics: instead of just visiting nodes, client code can safely be visiting the whole paths from the root, basically for free.
Do you have some pointers for this?
/tobe
I'll assume that you refer to the shortest paths: this is what I had in mind: Finding the k Shortest Paths (pdf), specifically section 2.
Thanks.
I'm still having a problem seeing that persistent collections could be useful (and used for the right reasons) in a larger context. I assume that when writing an optimal algorithm one would tend to write a specialized data structure anyway.
A persistent stack seems to give a large savings, but I'm not sure I see it being very useful
Is there any particular structure that you see as both giving a significant savings and a high utility (i.e. all other existing implementations would be a significantly worse choice)?
/tobe
>>>>>>> >>> unsubscribe: guava-discuss+unsub...@googlegroups.com
>>>>>>> >>>
>>>>>>> >>> This list is for discussion; for help, post to Stack Overflow
>>>>>>> >>> instead:
>>>>>>> >>> http://stackoverflow.com/questions/ask
>>>>>>> >>> Use the tag "guava".
>>>>>>> >>
>>>>>>> >>
>>>>>>> >>
>>>>>>> >> --
>>>>>>> >> Robert Konigsberg
>>>>>>> >> konig...@gmail.com
>>>>>>> >>
>>>>>>> >> --
>>>>>>> >> guava-...@googlegroups.com.
>>>>>>> >> http://groups.google.com/group/guava-discuss?hl=en
>>>>>>> >> unsubscribe: guava-discuss+unsub...@googlegroups.com
>>>>>>> >>
>>>>>>> >> This list is for discussion; for help, post to Stack Overflow
>>>>>>> >> instead:
>>>>>>> >> http://stackoverflow.com/questions/ask
>>>>>>> >> Use the tag "guava".
>>>>>>> >
>>>>>>> > --
>>>>>>> > guava-...@googlegroups.com.
>>>>>>> > http://groups.google.com/group/guava-discuss?hl=en
>>>>>>> > unsubscribe: guava-discuss+unsub...@googlegroups.com
>>>>>>> >
>>>>>>> > This list is for discussion; for help, post to Stack Overflow
>>>>>>> > instead:
>>>>>>> > http://stackoverflow.com/questions/ask
>>>>>>> > Use the tag "guava".
>>>>>>> >
>>>>>>>
>>>>>>> --
>>>>>>> guava-...@googlegroups.com.
>>>>>>> http://groups.google.com/group/guava-discuss?hl=en
>>>>>>> unsubscribe: guava-discuss+unsub...@googlegroups.com
>>>>>>>
>>>>>>> This list is for discussion; for help, post to Stack Overflow
>>>>>>> instead:
>>>>>>> http://stackoverflow.com/questions/ask
>>>>>>> Use the tag "guava".
>>>>>>
>>>>>> --
>>>>>> guava-...@googlegroups.com.
>>>>>> http://groups.google.com/group/guava-discuss?hl=en
>>>>>> unsubscribe: guava-discuss+unsub...@googlegroups.com
>>>>>>
>>>>>> This list is for discussion; for help, post to Stack Overflow instead:
>>>>>> http://stackoverflow.com/questions/ask
>>>>>> Use the tag "guava".
>>>>>
>>>>
>>>> --
>>>> guava-...@googlegroups.com.
>>>> http://groups.google.com/group/guava-discuss?hl=en
>>>> unsubscribe: guava-discuss+unsub...@googlegroups.com