Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.java.programmer > #9718
| From | Lew <lewbloch@gmail.com> |
|---|---|
| Newsgroups | comp.lang.java.programmer |
| Subject | Re: Immutable Datastructures with good Sharing |
| Date | 2011-11-06 17:26 -0800 |
| Organization | http://groups.google.com |
| Message-ID | <24833877.1073.1320629170928.JavaMail.geo-discussion-forums@prep8> (permalink) |
| References | (9 earlier) <j961n4$uts$1@news.albasani.net> <slrnjbd6fu.fvg.avl@gamma.logic.tuwien.ac.at> <CADC63E1.8F1D%bravegag@hotmail.com> <j96aql$n73$1@news.albasani.net> <alpine.DEB.2.00.1111070037450.4201@urchin.earth.li> |
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
Back to comp.lang.java.programmer | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
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