Erlang queue inconsistent behaviour

 

There are differences in internal representation of the queues depending on:

  • either it was created using queue:from_list() function
  • or using queue:new() function and them populating with elements.

    • Simple Code: 

    L = [1,2,3], 
Q = queue:from_list(L),  % convert it to Queue.
L2 = queue:to_list(Q),   % convert back to list.
QL2 = queue:from_list(L2), % And create queue representation
true =  Q =:= QL2.

    So far everything is OK,

  • Q looks like: {[3],[1,2]}
  • QL2 looks like {[3],[1,2]}

    • Now create queue by elements: 

    Q0 = queue:new(),
Q1 = queue:in(1,Q0),
Q2 = queue:in(2,Q1),
Q3 = queue:in(3,Q2),
Q =:= Q3.

    false

  • Q: {[3],[1,2]}
  • Q3: {[3,2],[1]}

    • Internal representation of Q and Q3 is different.

    if we do things like: 

    Q3x = queue:from_list(queue:to_list(Q3))

    We get the same representation: {[3],[1,2]}

    And now: 

    Q =:= Q3x.

    true as expected.

    This mean we can not compare 2 queues for equality just using code like: 

    Q == Q3.

    Is it a bug or a feature?

    The question is: if you out or out_r elements from both queues, do they give the same results? As the answer is yes, there is no inconsistent behavior.

    The internal representation is an "opaque" tuple which content depend on the history of the queue, how it was filled end emptied. This structure is there to optimized the operations with queue, and it is not reliable to write your code based on the actual representation since it is possible (even if not likely) that this representation change. One consequence is that yo cannot compare queues with pattern matching or ==, and there is no interface to do it, I guess that it is because this use case is rather seldom. If you really need it, I guess that the more efficient solution is to compare the the results of queue:to_list/1: queue:to_list(Q) == queue:to_list(Q3).

    According to algorithm complexity estimation technique called "Amortized analysis" some operations may "pay" for other operations. In this particular case with queue there is two lists representing queue: front list (which is used for constant add time) and rear list (which is used for constant access time). Elements from front list sometimes may migrate into rear list and it is up to implementation when it will happen.

    I found a paper "Amortized Analysis Explained by Rebecca Fiebrink Princeton University" very helpful in this subject. One of it's example is exactly your question.

    链接地址: http://www.djcxy.com/p/66294.html

    上一篇: 了解这个Erlang代码是什么？

    下一篇: Erlang队列行为不一致