3 ms·
oh, I suspect they do. Which is why the manual page for erlang:queue talks about the topic in detail and explains the rationale, gives a workaround, and links
by felixgallo 12y ago
oh, I suspect they do. Which is why the manual page for erlang:queue talks about the topic in detail and explains the rationale, gives a workaround, and links to the literature.
http://erlang.org/doc/man/queue.html http://erlang.org/doc/man/queue.html
- rtpg 12y agoThis talks about the O(n)-ness of length, but I don't see the rationale for the O(n)-ness of pop. Maybe I'm missing something?
- felixgallo 12y agoYou fell victim to the confusion in the original post and this thread between what the original poster describes as popping, and what they were apparently actually doing (which involved taking the length, which is O(N) for the reasons explained here and in the documentation). erlang's queue's pop ("out") is amortized O(1), worst case O(N) just like every other immutable double headed queue. Here's the source code: https://github.com/erlang/otp/blob/172e812c491680fbb175f56f7604d4098cdc9de4/lib/stdlib/src/queue.erl#L137 https://github.com/erlang/otp/blob/172e812c491680fbb175f56f7...