4 ms·

This seems like a pretty fundamental issue though. I'd feel like any systems programmer worth their weight in salt would know that yo can build an O(1) pop on a

by rtpg 12y ago

This seems like a pretty fundamental issue though. I'd feel like any systems programmer worth their weight in salt would know that yo can build an O(1) pop on a queue.

Betelgeuse90 12y ago
If you don't think about the underlying implementation of erlang:length(), this seems to me like an easy mistake to make. Lots of data structures keep a size field and access it in O(1), so it's not completely unreasonable to expect erlang:length to be O(1) without making sure. At least that's how I understood the context of the problem, I may be wrong of course.
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 ago
  This 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 ago
    You 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...
theoh 12y ago
It's the functional way to believe that the elegance of a singly linked list means that it is the right choice for the implementation, instead of something more complex and unwieldy that can fold both ways in the same time, for example.

by rtpg 12y ago

This seems like a pretty fundamental issue though. I'd feel like any systems programmer worth their weight in salt would know that yo can build an O(1) pop on a queue.

Betelgeuse90 12y ago

If you don't think about the underlying implementation of erlang:length(), this seems to me like an easy mistake to make. Lots of data structures keep a size field and access it in O(1), so it's not completely unreasonable to expect erlang:length to be O(1) without making sure. At least that's how I understood the context of the problem, I may be wrong of course.

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 ago
This 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 ago
  You 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...

theoh 12y ago

It's the functional way to believe that the elegance of a singly linked list means that it is the right choice for the implementation, instead of something more complex and unwieldy that can fold both ways in the same time, for example.