4 ms·
Well, you do need to know that there exists an item in the queue. Knowing that length > 0 is one way to go about it, but certainly it's enough to establish the
by Betelgeuse90 12y ago
Well, you do need to know that there exists an item in the queue. Knowing that length > 0 is one way to go about it, but certainly it's enough to establish the existence of one item and then move on.
If one is unaware of the complexity of the .length() method, one might use it to find out if a dequeue is possible.
- rtpg 12y agoThis 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 agoIf 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 agooh, 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...
- theoh 12y agoIt'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.
- fla 12y agoIf you need to know if it's not empty, shoudn't it be easier to just test if the pointer to the first item is not-null ?
- Betelgeuse90 12y agoDoes erlang have pointers?
- fla 12y agoI honestly don't know a thing about Erlang. But from my humble understanding of the interpreter source in the article: if is_list(list) is true, then the list is not empty. If you ask me, a respectable dequeue operation shoudn't need more than O(1).
- lostcolony 12y agoNo. In Erlang, is_list([]) is true. The correct implementation for checking if a list is empty would have been a pattern match, something akin to case List of [] -> empty; [_ | _] -> not_empty end. Or, you know. Reading the API docs and using queue:is_empty(Queue), which is O(1) instead of O(n) (which queue:len(Queue) is -explicitly stated to be-).
- deleted 12y ago[deleted]
- dangrossman 12y ago> yet you can pick up a Bachelor's without ever hearing the word "allocate" What university has such a program? Programming language design (students write an interpreter and compiler), operating systems (students write a minimal OS including virtual memory management), systems architecture (students design a CPU and write some flavor of ASSEMBLY) and algorithms (students learn about time and memory complexity) are core, required courses in all the CS programs around here. They're required topics for a CS program to be accredited by ABET. Maybe you're confusing actual CS programs with trade school certificate programs; you don't get a bachelors in CS by writing some Java.
- ZanyProgrammer 12y agoHow important is ABET certification in the real world?