Immutability in C# Part 10: A double-ended queue

re: Immutability in C# Part 10: A double-ended queue

Aaron G — Tue, 22 Jan 2008 20:20:05 GMT

It does leave a little to be desired. Now instead of an O(n²) algorithm, you have a recursive O(n²) algorithm, so we can hammer both the CPU and the stack with it. Nice. ;)

re: Immutability in C# Part 10: A double-ended queue

Olmo del Corral — Tue, 22 Jan 2008 20:22:28 GMT

The problem here is the recursive chain that is produced when you call EnqueueXXX and DequeXXX over a non trivial deque.

I'm working in a solution that has, for every generarl Deque, a cachedDequeLeft and cachedDequeRight, but I'm not sure if it´s going to work.

Cross your fingers :)

re: Immutability in C# Part 10: A double-ended queue

Eric Lippert — Tue, 22 Jan 2008 20:53:46 GMT

Aaron: Yep! It's truly awful. Each enqueue is O(n) in stack consumption, time and number of new nodes allocated, so enqueuing n items in a row is O(n²) in time.

Olmo: Sounds interesting!

Immutability in C#

Tue, 22 Jan 2008 21:31:01 GMT

For some reason, there's been a lot of buzz lately around immutability in C#. If you're interested in

re: Immutability in C# Part 10: A double-ended queue

Olmo del Corral — Tue, 22 Jan 2008 22:31:29 GMT

I've been working on it for a while and there is no end.

In my implementation Deque is FAST so eneque have to be defined in terms of Deque.

The end of the history is that, while you can reuse a lot of this trees (should we call them firs? hehe), for a deque with n elements you need about n^2 that represent every single instance of all the possible subintervals. So having a structure that needs so much memory is stupid. Also, inserting an element stills O(n)...

So a way to nowhere ... :S

re: Immutability in C# Part 10: A double-ended queue

Aaron G — Tue, 22 Jan 2008 22:59:19 GMT

I'm thinking that you could just throw together an immutable version of a doubly-linked list. You did say that the solution was tricky, and this one is downright banal, so it probably isn't what you're looking for, but it *would* work and give O(1) enqueue and dequeue performance.

All you'd need is an Element<T> with (read only) Left, Right and Value properties, and you could give the Deque<T> "beginning" and "end" fields of type Element<T>. Throw in a constructor that takes two Element<T> parameters and you've got yourself an immutable Deque.

I guess the problem is that it would have to allocate a new Deque<T> for each and every Dequeue operation. The memory performance isn't stellar. Then again, that's exactly what we did for the Queue<T>, so does it make a difference?

re: Immutability in C# Part 10: A double-ended queue

Aaron G — Tue, 22 Jan 2008 23:10:53 GMT

Actually... never mind, I can see now why that wouldn't work - the Element<T> would have to be mutable. The Deque could look immutable on the outside, but I imagine the point of this exercise is to build the whole thing using completely immutable data structures. So, scratch that, back to square one. :-)

re: Immutability in C# Part 10: A double-ended queue

Eric Lippert — Tue, 22 Jan 2008 23:39:21 GMT

Yep, you got it. Doubly-linked lists are always mutable.

re: Immutability in C# Part 10: A double-ended queue

Luke H — Tue, 22 Jan 2008 23:58:49 GMT

Going back to attempt #1, if when one stack is empty, you reverse and transfer just *half* the elements from the other stack, you get amortised O(1) performance, and you're done ;) This is mentioned in Chris Okasaki's book "Purely functional data structures" which describes a lot of interesting immutable data structures.

Looking forward to seeing your alternative as well!

re: Immutability in C# Part 10: A double-ended queue

Aaron G — Wed, 23 Jan 2008 01:17:56 GMT

I hope that the half-reverse idea isn't the solution; that was the first thing that popped into my head, but it's only reducing that worst-case O(n²) performance to O(n log n), and it also raises the performance cost of enqueuing everything from one end and dequeuing everything from the other end from O(n) to O(n log n). It's better than what we've got so far, but it ain't great.

You could get similar performance using an AVL or red-black tree as the internal data structure; the "beginning" is the outer-left leaf and the "end" is the outer-right. But it's still a high price to pay. Knowing Eric, I'm sure he's got some extremely clever and totally nonintuitive hack that gives O(1) performance almost all the time.

re: Immutability in C# Part 10: A double-ended queue

Eric Lippert — Wed, 23 Jan 2008 01:41:06 GMT

Aaron: no, Luke is right. If you are clever about when you rebalance the deque, you can get amortized O(1) performance. You end up having to keep around extra information about how big each queue is, but that's not hard.

However, that is in fact not the solution I had in mind. Rather than fixing Attempt #1, I'm going to fix Attempt #2 by being more clever about what exactly goes in the left, middle and right sections.

re: Immutability in C# Part 10: A double-ended queue

Chris M — Wed, 23 Jan 2008 11:06:48 GMT

I don't think that's exactly what you meant, and I'm sure I'm missing something, but would

return new Deque<T>(left, middle.DequeueRight(), middle.PeekRight());

even work as planned? Wouldn't we end up with the wrong right element after we do this? Did I just say 'wrong right element'? How is it you manage to do this to me almost every time?

re: Immutability in C# Part 10: A double-ended queue

DRBlaise — Wed, 23 Jan 2008 20:32:17 GMT

I was able to make an efficient Deque using 2 "Trimmable Stacks" and keeping Deque Count information, but I am not sure about approach #2. I am thinking it might be possible by making left and right into Stacks and keeping middle a Deque. EnqueueLeft would be:

return new Deque<T>(left.Push(value), this, right);

I am just not sure if this works for all other operations.

Great series by the way. Keep it going!

re: Immutability in C# Part 10: A double-ended queue

Eric Lippert — Wed, 23 Jan 2008 20:52:47 GMT

Chris: Why would we end up with the wrong right element?

Remember, middle is IMMUTABLE. Dequeuing it does not change the value of middle, it returns a different deque. We can dequeue that thing all we want and its rightmost element is the same as it ever was.

Dr. Blaise: Your intuition is good. I'm going to stick with something-on-the-left, something-in-the-middle and something-on-the-right, and those somethings will be more complex than Attempt #2. It's not going to be exactly as you've sketched out though.

re: Immutability in C# Part 10: A double-ended queue

Aaron G — Thu, 24 Jan 2008 00:13:23 GMT

I'm not sure if I'm on the right track, but the thing I'm noticing is that since a deque implicitly has 3 pieces, it's easier to deal with 2 elements at a time than it is to deal with just 1. What if you made the left and right sides a kind of "buffer" (stacks with a count, I guess), and did the recursive enqueuing only when you had 2 elements to move?

For example... if you're enqueuing from the left, and the left buffer has one or two elements, just tack it on. If it has three, then pop all 3 elements, enqueue the last two onto the inner deque, and put the 1st back on the stack, then enqueue the new element normally. There is some recursion, but 50% of the time the depth is zero, 25% of the time it's one level deep, 12.5% of the time it only goes two levels, etc. Once you hit the end, which would be a SingleDeque, then enqueuing two elements at a time is trivial; just move the left to the right, the first element into a new SingleDeque in the middle, and the last element onto the right.

I think this is also "amortized" O(1) performance, right? To dequeue off of either side you just reverse this process, same performance. It can end up being lopsided, but I don't think it matters; if you run out of elements on the "requested" side, just start taking them off the other side - since you've got a maximum of 3 elements to pop at any level before you find the "tail", it's still pretty fast.

Is this making any sense or have I officially gone off the deep end?

re: Immutability in C# Part 10: A double-ended queue

Eric Lippert — Thu, 24 Jan 2008 02:01:26 GMT

Give that man a cigar!

The part of the trick that you've not explicitly stated is that the inner deque is a deque of _stacks of elements_, not of _elements_.

I'll be presenting an implementation of this technique in the next few days.

re: Immutability in C# Part 10: A double-ended queue

DRBlaise — Thu, 24 Jan 2008 21:29:47 GMT

WOW! Truly mind blowing stuff.

Am I wrong or will the final version be:

IDeque<T> left;

IDeque<IDeque<T>> middle;

IDeque<T> right;

re: Immutability in C# Part 10: A double-ended queue

Eric Lippert — Thu, 24 Jan 2008 22:01:32 GMT

Very close. We're actually going to make a "lite" deque that can store between one and four elements, and then we'll have

Dequelette<T> left

IDeque<Dequelette<T>> middle

Dequelette<T> right

(Since the Dequelette does not meet the IDeque contract, I don't want to say that it does.)

That gives us fast access to the stuff at the end points, and logarithmic access to the stuff in the middle -- unlike, say, a binary tree, which gives us fast access to the stuff "in the local middle" and logarithmic access to the stuff at the end points. It's like pulling a binary tree inside out, a bit.

But patience! We'll get to it next week.

Community Convergence XL

Charlie Calvert's Community Blog — Wed, 30 Jan 2008 02:15:14 GMT

Welcome to the fortieth issue of Community Convergence. This week we have two new releases of note: We

re: Immutability in C# Part 10: A double-ended queue

Weeble — Wed, 30 Jan 2008 16:38:25 GMT

I've convinced myself that this works in C#, but I'm curious as to how the compiler remains happy and sane. The number of concrete types involved seems to be O(log N) in the number of elements, which, while very slow-growing, does not have an upper bound. Are the concrete types really only created as needed at run-time? Would you be unable to implement this same structure using C++ templates? Or have I fundamentally misunderstood something?

I'm eager to see the next installment!

re: Immutability in C# Part 10: A double-ended queue

Joren Vermijs — Wed, 06 Feb 2008 02:04:26 GMT

Doesn't the compiler simply use the same implementation for Foo<T> as it does for Foo<Foo<T>>, if T is a reference type? After all, there is no need for the _implementation_ to be strongly typed if only typesafe usage of it is allowed to compile.

re: Immutability in C# Part 10: A double-ended queue

Sebastien Lorion — Sat, 09 Feb 2008 16:12:12 GMT

Shouldn't the interface be:

public interface IDeque<T>

{

T PeekLeft();

T PeekRight();

IDeque<T> EnqueueLeft(T value);

IDeque<T> EnqueueRight(T value);

IDeque<T> DequeueLeft(out T value);

IDeque<T> DequeueRight(out T value);

bool IsEmpty { get; }

}

ie, add argument "out T value" to Dequeue operations. Same goes for previously posted data structures ...

re: Immutability in C# Part 10: A double-ended queue

Eric Lippert — Sat, 09 Feb 2008 18:06:49 GMT

No. That would be conflating two logically separate operations into one method. One method should do one thing, and do it well. Examining the data structure and producing a new data structure are two entirely different operations, so they should be represented by two methods.

re: Immutability in C# Part 10: A double-ended queue

Sebastien Lorion — Mon, 11 Feb 2008 03:08:07 GMT

I understand your point, thought it seems to conflict with current .NET mutable collections API (not saying one is wrong vs others, just different way of seeing things I guess).

re: Immutability in C# Part 10: A double-ended queue

Eric Lippert — Mon, 11 Feb 2008 20:34:12 GMT

Mutable collections must conflate unrelated operations because mutable collections are impossible to reason about.

Suppose for example you want to pop a stack AND know what value you popped. In an immutable stack you can ask "are you empty?" and then peek and then pop. In a mutable stack asking "are you empty?" tells you nothing about whether peeking is safe. Someone could have popped everything off the stack on a different thread.

In a mutable stack, if you peek and then pop you have absolutely no idea if the value you peeked is the value that was just popped off. Someone might have done a push after your peek.

Mutable structures are "threadsafe" only insofar as they guarantee to behave as though their operations are atomic, not that combinations of those operations are atomic. Therefore, any operations which must be logically atomic in a mutable structure must be conflated together. That's why mutable collections have methods that do everything all at once, rather than cleanly separating different operations into different methods.

Immutable structures give you a much stronger thread safety -- they give you the ability to reason logically from past calls to future calls. In an immutable stack, the value you peek is always the value you pop.

re: Immutability in C# Part 10: A double-ended queue

snprbob86 — Wed, 13 Feb 2008 00:37:06 GMT

I've been loving this immutability series! Any hope for a System.Collections.Immutable someday? :-)

re: Immutability in C# Part 10: A double-ended queue

Sebastien Lorion — Fri, 15 Feb 2008 21:11:26 GMT

Thanks for your thoughtful answer. Following on what you say, then there is no advantage of putting 2 logical operations in one method in a mutable stack who is not threadsafe. A thread could push a value before Pop() get a chance to peek. In that case, an external lock is necessary and then, why not have 2 methods to make this requirement explicit ? Am I right in thinking that way ?

re: Immutability in C# Part 10: A double-ended queue

Eric Lippert — Fri, 15 Feb 2008 21:31:43 GMT

That is a reasonable way of thinking about it, yes.