Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.java.programmer > #9622
| From | Jan Burse <janburse@fastmail.fm> |
|---|---|
| Newsgroups | comp.lang.java.programmer |
| Subject | Re: Immutable Datastructures with good Sharing |
| Date | 2011-11-05 22:58 +0100 |
| Organization | albasani.net |
| Message-ID | <j94bip$r6v$1@news.albasani.net> (permalink) |
| References | <j9292v$f69$1@news.albasani.net> <jamdnUwVbvmRMSjTnZ2dnUVZ_uKdnZ2d@posted.palinacquisition> <j94ajg$ost$1@news.albasani.net> <IuednQhC8Y-dLSjTnZ2dnUVZ_gmdnZ2d@posted.palinacquisition> |
But he has a second solution:
This looks as follows:
---- 1. stack --- | --- 2. stack (shown reverse) ---
^ pop here = dequeue enqueue = push here ^
Then he argues that we have in the average O(1), although
when 1. stack gets empty, 2. stack needs to be reverse.
Interesting, cool! So its possible...
Bye
Peter Duniho schrieb:
> On 11/5/11 2:42 PM, Jan Burse wrote:
>> Peter Duniho schrieb:
>>> Once you have seen those examples, hopefully that will help you see some
>>> of the basic techniques used that can lead you to implementations of
>>> other complex immutable data structures you might want.
>>>
>>> Pete
>>
>> It fullfils the requirement of immutable. But it has no sharing.
>>
>> public IQueue<T> Enqueue(T t) {
>> return new Queue<T>(backwards.Push(t)); }
>> public IQueue<T> Dequeue(T t) {
>> return new Queue<T>(backwards.Reverse().Pop().Reverse()); }
>>
>> Eric himself remarks when initially defining Reverse:
>>
>> This is an O(n) operation for a stack of size n.
>>
>> So I guess we did not yet find a solution.
>
> Yes, I agree…if you are looking for someone who has already done your
> work for you, then the link I offered doesn't specifically answer your
> question.
>
> But maybe you can learn something from it anyway. You may even find that
> it's not practical to expect an immutable queue to have "good sharing".
>
> Pete
Back to comp.lang.java.programmer | Previous | Next — Previous in thread | Next in thread | Find similar
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
csiph-web