3 ms·
So this is only tangentially related, but it's all bloody neat, so I'm going to mention it anyway. First, keeping a length of a list, as part of the library im
by lostcolony 12y ago
So this is only tangentially related, but it's all bloody neat, so I'm going to mention it anyway.
First, keeping a length of a list, as part of the library implementation, is a bad idea, because due to how immutability works, you'd need to keep a length from -every item in a linked list-. That is, rather than
[4, 3, 2, 1]
you would need to have
[{4, 4}, {3, 3}, {2, 2}, {1, 1}]
Why? Because adding a new element to the head of a list needs to be O(1), -and- maintain the existing list. That is, if I have
List1 = [4, 3, 2, 1].
I need to be able to do
List2 = [5 | List1]
That is, List2 is now
[5, 4, 3, 2, 1]
and List1 remains unaffected. So both List1 and List2 would need to still know their lengths, as would any other variables with heads further down in the list.
So we have ~doubled the memory usage of a list, in that we need both a pointer (to the contents), and an integer, for each cell of the list. We can't simply store a 'total' value for a list (well, we could, and then every time we perform -any- operation on a list, that generates a new list(s) we re-calculate the length for it/them. Which would be a pain to code, results in a lot of extra garbage (since the intermediate values of the counter are thrown away, again, immutable), is unnecessary...and is actually impossible in lazy languages like Haskell that allow infinite lists. Quite frankly, in functional languages you don't need the length enough to go through such hassles, and when you do, yeah, it's easy enough to write it for your one use case).
And that said, we don't need any of that noise for implementing an efficient queue. An immutable queue in Erlang is implemented via Okasaki's queue implementation (though with a recognizable API by default; Okasaki's API is still there). This is actually a really cool data structure, and has parallels to the interview question "how would you implement a (double ended) queue using two stacks".
In short, it looks like this -
{[], []}.
Where you have a tuple of two elements; two lists (and an immutable list works identically to a stack; operations upon the head of it work in O(1) time)
Enqueue 1 at the front ->
{[1], []}
Enqueue 2 at the front; note that this is actually stacking the 2 in front of the 1 ->
{[2,1], []}
Dequeue examines the second list, sees it's empty, reverses the first list, puts it in for the second (and an empty list in the first), and pops off the top of it, a la ->
{[2,1], []} -> {[1, 2], []} -> {[], [1, 2]} -> {1, {[], [2]}}
Where 1 is your return value, and {[], [2]} is the new queue.
Further enqueues keep going onto that first list, dequeues come off the second, until it's empty, whereupon the first list is reversed again and placed in for the second. Etc.
This has an amortized constant time enqueue and dequeue, despite being immutable, and a constant time 'is_empty' check, where you just check each list to see if it's empty or not (easily doable by checking to see if it pattern matches [] or [_ | _].
Pushing onto the start of the second list, and pulling off the first, allows you to work on the other end of the queue.
So all your usual operations for a double ended queue work in the same big-O time as for the mutable implementation, but you maintain immutability.
The problem here is that the implementation relied on an O(n) behavior, when all it needed was an O(1) one.
While the article states "The problem is not with erlang:length() being slow. It’s about being unpredictably slow.", I would counter that asking for length when you just want to see if it's empty or not is INDEED the problem. Length explicitly tells you it will traverse the list, and yes, it makes no guarantees about where the elements of the list are in memory. Same as in every other language. Because contiguous pointers in memory are called "an array of pointers" not a "list of pointers".
Note, too, that this article is from 2010. I'm guessing that basic.get has since been rewritten to not use an O(n) implementation when an obvious O(1) implementation exists.
- steventhedev 12y agoNope. I'm barely literate in Erlang, but it looks like they haven't fixed it, unless they've wrapped the backing queue somewhere: https://github.com/rabbitmq/rabbitmq-server/blob/master/src/rabbit_amqqueue_process.erl#L997 https://github.com/rabbitmq/rabbitmq-server/blob/master/src/...
- lostcolony 12y agoHeh, as I just replied to the comment you made elsewhere - "Yeah, RabbitMQ opted for the 2nd because of that. BQ in that case is whatever queue implementation was selected; if you look at both the lqueue.erl and priority_queue.erl, you see that they implemented len() by pulling apart a tuple and taking a value verbatim; no further operations. As such, I'd assume every queue type they support has its own internal wrappers to maintain a length." EDIT: Just to explain the Erlang a bit, what is happening is the #q record that is being pattern matched on in the function you mention has a background_queue field. This field is an atom, corresponding to the module the queue implementation lives in. So 'lqueue' or 'priority_queue', or whatever else fits the interface (behavior in Erlang terms). So it actually ends up calling lqueue:len(BQS) or priority_queue:len(BQS), or similar. If you look at the implementations of those, you'll see they've wrapped up the actual queue into a tuple, bundling along a length, such that they can simply return the length, rather than recalculate it every time. So it looks like in the intervening 4-5 years, they -have- fixed it.
- jbapple 12y agoI think the queue of Okasaki's that you mention is only amortized constant-time in a persistent setting if certain laziness is carefully enforced. I don't know if Erlang's queues do this, but I do know that implementations of Hinze and Paterson's finger trees, which rely on a similar laziness for their amortization argument, are often implemented without the laziness. It wouldn't surprise me if this were common in translations of purely functional data structures.
- lostcolony 12y agoWe're moving into an area whose terminology I'm not as familiar with as the underlying concepts, but what I recall, yes, the actual big-o of a -single- operation, if this is implemented strictly and used as a single ended queue, has a worst case bound of O(n), and a best case bound of O(1), and an average case of O(1), and would be described in big-O terms as "amortized O(1), worst case of O(n)"; much like an arraylist (where the general case for adding at the end is O(1), but when it's full, is actually O(n) as we create a new array and copy elements over, but we describe it as having an amortized cost of O(1)). Or put another way, for n enqueues, rather than thinking of each enqueue taking one operation, think of it taking two, one now, one deferred, for a still constant enqueue time. On a dequeue where the right side is empty, you have n deferred operations 'stored up', that you then use to reverse the list, and then you use one operation to take the head. So while that -particular- operation actually uses up n+1 operations, the amortized time across the entire sequence of operations so far is constant. And so while you may not have real time dequeue performance of a single operation if implemented strictly (that is, in the worst case, where the right list is empty), the act of enqueueing n things, and dequeueing n things, leads to a total time proportional to n, leading to an averaged constant time per operation. Now, that said, if you treat it as a double ended queue, there is a worst case in the strict implementation that runs in O(n) per operation; that's by inserting onto one end, then alternately pulling off one end, then the other (so that for every dequeue, we have to reverse the remaining list again). But that's extremely degenerate, and is more egregious than describing quicksort as O(n^2) due to its degenerate case of an already sorted list (since that's far more common a use case than inserting always on one end, and perfectly alternating your dequeues).