Mixing
Efficient implementation of queue - time complexity of enqueue and dequeue
I am currently reading a textbook on data structures/algorithms. One of the exercises is to implement a efficient queue using the python list structure: the time complexity of both enqueue and dequeue needs to be O(1) on average. The book says that the time complexity should only be O(n) for a specific case of dequeue, and the rest of the time it should be O(1). I implemented it such that the rear of the queue is the end of the list and front of the queue is the beginning of the list; when I dequeue an element, I do not delete it from the list, but I simply increment a counter so that the method will know which element in the list represents the front of the queue. Here is my code:
class FasterQueue:
def __init__(self):
self.items =
self.index = 0
def enqueue(self, item):
self.items.append(item)
def dequeue(self):
index = self.index
self.index += 1
return self.items[index]
def isEmpty(self):
return self.items ==
def size(self):
return len(self.items)
My question: the book says that there is some case where dequeue should take O(1). I have no idea what case this is because it seems like dequeue will always just be getting the value at a certain index. Is my implementation of the queue invalid or am I missing something else? Or is the textbook just looking for another more common implementation?
Thank you so much for the help.
python data-structures queue time-complexity
asked Jan 2 at 17:56
davidimdavidim
303
|
show 1 more comment
I am currently reading a textbook on data structures/algorithms. One of the exercises is to implement a efficient queue using the python list structure: the time complexity of both enqueue and dequeue needs to be O(1) on average. The book says that the time complexity should only be O(n) for a specific case of dequeue, and the rest of the time it should be O(1). I implemented it such that the rear of the queue is the end of the list and front of the queue is the beginning of the list; when I dequeue an element, I do not delete it from the list, but I simply increment a counter so that the method will know which element in the list represents the front of the queue. Here is my code:
class FasterQueue:
def __init__(self):
self.items =
self.index = 0
def enqueue(self, item):
self.items.append(item)
def dequeue(self):
index = self.index
self.index += 1
return self.items[index]
def isEmpty(self):
return self.items ==
def size(self):
return len(self.items)
My question: the book says that there is some case where dequeue should take O(1). I have no idea what case this is because it seems like dequeue will always just be getting the value at a certain index. Is my implementation of the queue invalid or am I missing something else? Or is the textbook just looking for another more common implementation?
Thank you so much for the help.
python data-structures queue time-complexity
asked Jan 2 at 17:56
davidimdavidim
303
dequeueshould always remove the item from one end of the queue. That'sO(1)
– JacobIRR
Jan 2 at 18:01
1
@JacobIRR He's not working with a typical python list, the implementation represents a queue. queues are FIFO, and so dequeue should remove from the start of queue, not the end.
– Paritosh Singh
Jan 2 at 18:04
i guess the only thing i can think of is, what happens when you try to dequeue past an "empty" queue so to speak. enqueue once, dequeue twice.
– Paritosh Singh
Jan 2 at 18:17
Wouldn't that still be O(1) since the worst case on get item for lists is O(1)... I guess the textbook just made a mistake?
– davidim
Jan 2 at 18:20
i think it would probably be an index error actually, however yes, i dont really see any "reason" to have an incredibly long list that keeps consuming memory but dequeues as O(1), but i suspect the book expects you to perhaps tidy up the list when you empty it out or something.
– Paritosh Singh
Jan 2 at 18:31
|
show 1 more comment
I am currently reading a textbook on data structures/algorithms. One of the exercises is to implement a efficient queue using the python list structure: the time complexity of both enqueue and dequeue needs to be O(1) on average. The book says that the time complexity should only be O(n) for a specific case of dequeue, and the rest of the time it should be O(1). I implemented it such that the rear of the queue is the end of the list and front of the queue is the beginning of the list; when I dequeue an element, I do not delete it from the list, but I simply increment a counter so that the method will know which element in the list represents the front of the queue. Here is my code:
class FasterQueue:
def __init__(self):
self.items =
self.index = 0
def enqueue(self, item):
self.items.append(item)
def dequeue(self):
index = self.index
self.index += 1
return self.items[index]
def isEmpty(self):
return self.items ==
def size(self):
return len(self.items)
My question: the book says that there is some case where dequeue should take O(1). I have no idea what case this is because it seems like dequeue will always just be getting the value at a certain index. Is my implementation of the queue invalid or am I missing something else? Or is the textbook just looking for another more common implementation?
Thank you so much for the help.
python data-structures queue time-complexity
asked Jan 2 at 17:56
davidimdavidim
303
I am currently reading a textbook on data structures/algorithms. One of the exercises is to implement a efficient queue using the python list structure: the time complexity of both enqueue and dequeue needs to be O(1) on average. The book says that the time complexity should only be O(n) for a specific case of dequeue, and the rest of the time it should be O(1). I implemented it such that the rear of the queue is the end of the list and front of the queue is the beginning of the list; when I dequeue an element, I do not delete it from the list, but I simply increment a counter so that the method will know which element in the list represents the front of the queue. Here is my code:
class FasterQueue:
def __init__(self):
self.items =
self.index = 0
def enqueue(self, item):
self.items.append(item)
def dequeue(self):
index = self.index
self.index += 1
return self.items[index]
def isEmpty(self):
return self.items ==
def size(self):
return len(self.items)
My question: the book says that there is some case where dequeue should take O(1). I have no idea what case this is because it seems like dequeue will always just be getting the value at a certain index. Is my implementation of the queue invalid or am I missing something else? Or is the textbook just looking for another more common implementation?
Thank you so much for the help.
python data-structures queue time-complexity
python data-structures queue time-complexity
asked Jan 2 at 17:56
davidimdavidim
303
asked Jan 2 at 17:56
davidimdavidim
303
asked Jan 2 at 17:56
davidimdavidim
303
asked Jan 2 at 17:56
davidimdavidim
303
asked Jan 2 at 17:56
davidimdavidim
303
303
dequeueshould always remove the item from one end of the queue. That'sO(1)
– JacobIRR
Jan 2 at 18:01
1
@JacobIRR He's not working with a typical python list, the implementation represents a queue. queues are FIFO, and so dequeue should remove from the start of queue, not the end.
– Paritosh Singh
Jan 2 at 18:04
i guess the only thing i can think of is, what happens when you try to dequeue past an "empty" queue so to speak. enqueue once, dequeue twice.
– Paritosh Singh
Jan 2 at 18:17
Wouldn't that still be O(1) since the worst case on get item for lists is O(1)... I guess the textbook just made a mistake?
– davidim
Jan 2 at 18:20
i think it would probably be an index error actually, however yes, i dont really see any "reason" to have an incredibly long list that keeps consuming memory but dequeues as O(1), but i suspect the book expects you to perhaps tidy up the list when you empty it out or something.
– Paritosh Singh
Jan 2 at 18:31
|
show 1 more comment
dequeueshould always remove the item from one end of the queue. That'sO(1)
– JacobIRR
Jan 2 at 18:01
1
@JacobIRR He's not working with a typical python list, the implementation represents a queue. queues are FIFO, and so dequeue should remove from the start of queue, not the end.
– Paritosh Singh
Jan 2 at 18:04
i guess the only thing i can think of is, what happens when you try to dequeue past an "empty" queue so to speak. enqueue once, dequeue twice.
– Paritosh Singh
Jan 2 at 18:17
Wouldn't that still be O(1) since the worst case on get item for lists is O(1)... I guess the textbook just made a mistake?
– davidim
Jan 2 at 18:20
i think it would probably be an index error actually, however yes, i dont really see any "reason" to have an incredibly long list that keeps consuming memory but dequeues as O(1), but i suspect the book expects you to perhaps tidy up the list when you empty it out or something.
– Paritosh Singh
Jan 2 at 18:31
dequeue should always remove the item from one end of the queue. That's O(1)– JacobIRR
Jan 2 at 18:01
dequeue should always remove the item from one end of the queue. That's O(1)– JacobIRR
Jan 2 at 18:01
1
1
@JacobIRR He's not working with a typical python list, the implementation represents a queue. queues are FIFO, and so dequeue should remove from the start of queue, not the end.
– Paritosh Singh
Jan 2 at 18:04
@JacobIRR He's not working with a typical python list, the implementation represents a queue. queues are FIFO, and so dequeue should remove from the start of queue, not the end.
– Paritosh Singh
Jan 2 at 18:04
i guess the only thing i can think of is, what happens when you try to dequeue past an "empty" queue so to speak. enqueue once, dequeue twice.
– Paritosh Singh
Jan 2 at 18:17
i guess the only thing i can think of is, what happens when you try to dequeue past an "empty" queue so to speak. enqueue once, dequeue twice.
– Paritosh Singh
Jan 2 at 18:17
Wouldn't that still be O(1) since the worst case on get item for lists is O(1)... I guess the textbook just made a mistake?
– davidim
Jan 2 at 18:20
Wouldn't that still be O(1) since the worst case on get item for lists is O(1)... I guess the textbook just made a mistake?
– davidim
Jan 2 at 18:20
i think it would probably be an index error actually, however yes, i dont really see any "reason" to have an incredibly long list that keeps consuming memory but dequeues as O(1), but i suspect the book expects you to perhaps tidy up the list when you empty it out or something.
– Paritosh Singh
Jan 2 at 18:31
i think it would probably be an index error actually, however yes, i dont really see any "reason" to have an incredibly long list that keeps consuming memory but dequeues as O(1), but i suspect the book expects you to perhaps tidy up the list when you empty it out or something.
– Paritosh Singh
Jan 2 at 18:31
|
show 1 more comment
4 Answers
4
active
oldest
votes
making this use some more Python-esque features, I'd do something like:
class FasterQueue:
def __init__(self):
self.items =
self.index = 0
def enqueue(self, item):
self.items.append(item)
def dequeue(self):
# do this first so IndexErrors don't cause us ignore items
obj = self.items[self.index]
# release the reference so we don't "leak" memory
self.items[self.index] = None
self.index += 1
return obj
def isEmpty(self):
return self.index == len(self.items)
def size(self):
return len(self.items)
def try_shrink(self):
nactive = len(self.items) - self.index
if nactive + 2 < self.index // 2:
self.items = self.items[self.index:]
self.index = 0
have added a try_shrink method that tries to free up used memory space, and it might be useful to call this at the end of dequeue() — otherwise the list will grow arbitrarily long and waste a large amount of memory. the constants in there aren't amazing, but should prevent it from shrinking too often. this operation would be O(n) and might be what was being alluded to
answered Jan 2 at 18:27
Sam MasonSam Mason
3,35811331
I do have a question about what you did with the references in the dequeue method. I am a little confused about how obj still refers to the original object after you reassign that index in the array None. Why isn't obj None when you return it?
– davidim
Jan 2 at 22:00
@davidim see youtube.com/watch?v=_AEJHKGk9ns for your question. I also just realised I didn't answer your question of "implementation of the queue invalid or am I missing something else"! it's basically fine, as you can tell from the other responses there are various caveats around it, but it looks valid. I'll see if I can put some timings together of the implementations here
– Sam Mason
Jan 2 at 22:04
Thanks for the link and the response!
– davidim
Jan 2 at 22:16
Now, I understand! You are telling obj to refer to the same object that self.items[self.index] refers to. Then you rebind self.items[self.index] to None, but this does not actually modify the object! Thank you very much.
– davidim
Jan 2 at 22:37
add a comment |
As per my understanding, enqueue should insert at the end and dequeue should delete from the start.
So code should be
class FasterQueue:
def __init__(self):
self.items =
def enqueue(self, item):
self.items.append(item)
def dequeue(self):
if self.items:
return self.items.pop(0)
print("Underflow")
def isEmpty(self):
return self.items ==
def size(self):
return len(self.items)
answered Jan 2 at 18:43
infinityinfinity
11
add a comment |
The O(n) is a necessary consequence of managing the list length.
Here is a solution. In general, this runs as O(1), and from time to time it is O(n) as a result of an extra step that occurs inside the dequeue method.
The O(n) step occurs when the list grows too large and triggers the cleanup. Note that in general, this should be done specifically inside the dequeue method. Doing it outside, will tend to be more elaborate and less efficient.
class FasterQueue:
def __init__(self, maxwaste=100):
self.items =
self.nout = 0
self.maxwaste = maxwaste
def enqueue(self, item):
self.items.append(item)
def dequeue(self):
if len(self.items):
retv = self.items[self.nout]
self.nout += 1
if self.nout >= self.maxwaste:
self.items = self.items[self.nout:]
self.nout =0
return retv
else:
print( 'empty' )
raise ValueError
def listQ(self):
return ' '.join( self.items[self.nout:] )
def isEmpty(self):
return self.nout == len(self.items)
def size(self):
return len(self.items) - self.nout
q = FasterQueue(5)
for n in range(10):
q.enqueue( str(n) )
print( 'queue size %d nout %d items %s'%(q.size(),q.nout,q.listQ()) )
print( q.items )
while True:
try:
print( 'dequeue %s'%q.dequeue() )
print( 'queue size %d nout %d items %s'%(q.size(),q.nout,q.listQ()) )
print( q.items )
except:
print( 'empty' )
break
Running the above code produces the following output, note the recovery of wasted memory when maxwaste is exceeded. Maxwaste is set small here for the purpose of demonstrating the operation.
queue size 10 nout 0 items 0 1 2 3 4 5 6 7 8 9
['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
dequeue 0
queue size 9 nout 1 items 1 2 3 4 5 6 7 8 9
['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
dequeue 1
queue size 8 nout 2 items 2 3 4 5 6 7 8 9
['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
dequeue 2
queue size 7 nout 3 items 3 4 5 6 7 8 9
['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
dequeue 3
queue size 6 nout 4 items 4 5 6 7 8 9
['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
dequeue 4
queue size 5 nout 0 items 5 6 7 8 9
['5', '6', '7', '8', '9']
dequeue 5
queue size 4 nout 1 items 6 7 8 9
['5', '6', '7', '8', '9']
dequeue 6
queue size 3 nout 2 items 7 8 9
['5', '6', '7', '8', '9']
dequeue 7
queue size 2 nout 3 items 8 9
['5', '6', '7', '8', '9']
dequeue 8
queue size 1 nout 4 items 9
['5', '6', '7', '8', '9']
dequeue 9
queue size 0 nout 0 items
empty
empty
answered Jan 3 at 14:51
DrMDrM
1,104314
add a comment |
For completeness, here is an answer using a ring buffer.
This example runs as O(1) forever, but it does this by limiting the size of the queue. If you want to allow the queue to grow, or size dynamically, then you again have your O(n) behavior.
In other words, you have O(1) only if you do not manage the size of the list in some way. That is the point of the question.
Okay, here is the ring buffer implementation with fixed queue length.
class FasterQueue:
def __init__(self, nsize=100):
self.items = [0]*nsize
self.nin = 0
self.nout = 0
self.nsize = nsize
def enqueue(self, item):
next = (self.nin+1)%self.nsize
if next != self.nout:
self.items[self.nin] = item
self.nin = next
print self.nin, item
else:
raise ValueError
def dequeue(self):
if self.nout != self.nin:
retv = self.items[self.nout]
self.nout = (self.nout+1)%self.nsize
return retv
else:
raise ValueError
def printQ(self):
if self.nout < self.nin:
print( ' '.join(self.items[self.nout:self.nin]) )
elif self.nout > self.nin:
print( ' '.join(self.items[self.nout:]+self.items[:self.nin]) )
def isEmpty(self):
return self.nin == self.nout
def size(self):
return (self.nin - self.nout + self.nsize)%self.nsize
q = FasterQueue()
q.enqueue( 'a' )
q.enqueue( 'b' )
q.enqueue( 'c' )
print( 'queue items' )
q.printQ()
print( 'size %d'%q.size() )
while True:
try:
print( 'dequeue %s'%q.dequeue() )
print( 'queue items' )
q.printQ()
except:
print( 'empty' )
break
answered Jan 2 at 20:18
DrMDrM
1,104314
@SamMason, here is the answer. I feel pretty sure it has to be a ring or a pool. It's a classic problem. I've dealt with it many times in DSPs and device drivers. My original idea using pop() assumed that python was doing this by reference and using a pool rather than by copying.
– DrM
Jan 2 at 20:55
yes, I've use similar implementations in lower level languages, it could also be implemented in Python via a linked list. going by how the question was stated it seemed like the OP wasn't after a "production-ready" implementation, just trying to understand how all the pieces fit together
– Sam Mason
Jan 2 at 21:50
@SamMason Nonetheless, continuing the list to infinity serves no purpose other than to avoid the O(n) cost of actually removing the item. And that was the pedagogical point of the question
– DrM
Jan 3 at 0:02
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f54010988%2fefficient-implementation-of-queue-time-complexity-of-enqueue-and-dequeue%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
4 Answers
4
active
oldest
votes
4 Answers
4
active
oldest
votes
active
oldest
votes
active
oldest
votes
making this use some more Python-esque features, I'd do something like:
class FasterQueue:
def __init__(self):
self.items =
self.index = 0
def enqueue(self, item):
self.items.append(item)
def dequeue(self):
# do this first so IndexErrors don't cause us ignore items
obj = self.items[self.index]
# release the reference so we don't "leak" memory
self.items[self.index] = None
self.index += 1
return obj
def isEmpty(self):
return self.index == len(self.items)
def size(self):
return len(self.items)
def try_shrink(self):
nactive = len(self.items) - self.index
if nactive + 2 < self.index // 2:
self.items = self.items[self.index:]
self.index = 0
have added a try_shrink method that tries to free up used memory space, and it might be useful to call this at the end of dequeue() — otherwise the list will grow arbitrarily long and waste a large amount of memory. the constants in there aren't amazing, but should prevent it from shrinking too often. this operation would be O(n) and might be what was being alluded to
answered Jan 2 at 18:27
Sam MasonSam Mason
3,35811331
I do have a question about what you did with the references in the dequeue method. I am a little confused about how obj still refers to the original object after you reassign that index in the array None. Why isn't obj None when you return it?
– davidim
Jan 2 at 22:00
@davidim see youtube.com/watch?v=_AEJHKGk9ns for your question. I also just realised I didn't answer your question of "implementation of the queue invalid or am I missing something else"! it's basically fine, as you can tell from the other responses there are various caveats around it, but it looks valid. I'll see if I can put some timings together of the implementations here
– Sam Mason
Jan 2 at 22:04
Thanks for the link and the response!
– davidim
Jan 2 at 22:16
Now, I understand! You are telling obj to refer to the same object that self.items[self.index] refers to. Then you rebind self.items[self.index] to None, but this does not actually modify the object! Thank you very much.
– davidim
Jan 2 at 22:37
add a comment |
making this use some more Python-esque features, I'd do something like:
class FasterQueue:
def __init__(self):
self.items =
self.index = 0
def enqueue(self, item):
self.items.append(item)
def dequeue(self):
# do this first so IndexErrors don't cause us ignore items
obj = self.items[self.index]
# release the reference so we don't "leak" memory
self.items[self.index] = None
self.index += 1
return obj
def isEmpty(self):
return self.index == len(self.items)
def size(self):
return len(self.items)
def try_shrink(self):
nactive = len(self.items) - self.index
if nactive + 2 < self.index // 2:
self.items = self.items[self.index:]
self.index = 0
have added a try_shrink method that tries to free up used memory space, and it might be useful to call this at the end of dequeue() — otherwise the list will grow arbitrarily long and waste a large amount of memory. the constants in there aren't amazing, but should prevent it from shrinking too often. this operation would be O(n) and might be what was being alluded to
answered Jan 2 at 18:27
Sam MasonSam Mason
3,35811331
I do have a question about what you did with the references in the dequeue method. I am a little confused about how obj still refers to the original object after you reassign that index in the array None. Why isn't obj None when you return it?
– davidim
Jan 2 at 22:00
@davidim see youtube.com/watch?v=_AEJHKGk9ns for your question. I also just realised I didn't answer your question of "implementation of the queue invalid or am I missing something else"! it's basically fine, as you can tell from the other responses there are various caveats around it, but it looks valid. I'll see if I can put some timings together of the implementations here
– Sam Mason
Jan 2 at 22:04
Thanks for the link and the response!
– davidim
Jan 2 at 22:16
Now, I understand! You are telling obj to refer to the same object that self.items[self.index] refers to. Then you rebind self.items[self.index] to None, but this does not actually modify the object! Thank you very much.
– davidim
Jan 2 at 22:37
add a comment |
making this use some more Python-esque features, I'd do something like:
class FasterQueue:
def __init__(self):
self.items =
self.index = 0
def enqueue(self, item):
self.items.append(item)
def dequeue(self):
# do this first so IndexErrors don't cause us ignore items
obj = self.items[self.index]
# release the reference so we don't "leak" memory
self.items[self.index] = None
self.index += 1
return obj
def isEmpty(self):
return self.index == len(self.items)
def size(self):
return len(self.items)
def try_shrink(self):
nactive = len(self.items) - self.index
if nactive + 2 < self.index // 2:
self.items = self.items[self.index:]
self.index = 0
have added a try_shrink method that tries to free up used memory space, and it might be useful to call this at the end of dequeue() — otherwise the list will grow arbitrarily long and waste a large amount of memory. the constants in there aren't amazing, but should prevent it from shrinking too often. this operation would be O(n) and might be what was being alluded to
answered Jan 2 at 18:27
Sam MasonSam Mason
3,35811331
making this use some more Python-esque features, I'd do something like:
class FasterQueue:
def __init__(self):
self.items =
self.index = 0
def enqueue(self, item):
self.items.append(item)
def dequeue(self):
# do this first so IndexErrors don't cause us ignore items
obj = self.items[self.index]
# release the reference so we don't "leak" memory
self.items[self.index] = None
self.index += 1
return obj
def isEmpty(self):
return self.index == len(self.items)
def size(self):
return len(self.items)
def try_shrink(self):
nactive = len(self.items) - self.index
if nactive + 2 < self.index // 2:
self.items = self.items[self.index:]
self.index = 0
have added a try_shrink method that tries to free up used memory space, and it might be useful to call this at the end of dequeue() — otherwise the list will grow arbitrarily long and waste a large amount of memory. the constants in there aren't amazing, but should prevent it from shrinking too often. this operation would be O(n) and might be what was being alluded to
answered Jan 2 at 18:27
Sam MasonSam Mason
3,35811331
edited Jan 2 at 18:35
answered Jan 2 at 18:27
Sam MasonSam Mason
3,35811331
answered Jan 2 at 18:27
Sam MasonSam Mason
3,35811331
answered Jan 2 at 18:27
Sam MasonSam Mason
3,35811331
3,35811331
I do have a question about what you did with the references in the dequeue method. I am a little confused about how obj still refers to the original object after you reassign that index in the array None. Why isn't obj None when you return it?
– davidim
Jan 2 at 22:00
@davidim see youtube.com/watch?v=_AEJHKGk9ns for your question. I also just realised I didn't answer your question of "implementation of the queue invalid or am I missing something else"! it's basically fine, as you can tell from the other responses there are various caveats around it, but it looks valid. I'll see if I can put some timings together of the implementations here
– Sam Mason
Jan 2 at 22:04
Thanks for the link and the response!
– davidim
Jan 2 at 22:16
Now, I understand! You are telling obj to refer to the same object that self.items[self.index] refers to. Then you rebind self.items[self.index] to None, but this does not actually modify the object! Thank you very much.
– davidim
Jan 2 at 22:37
add a comment |
I do have a question about what you did with the references in the dequeue method. I am a little confused about how obj still refers to the original object after you reassign that index in the array None. Why isn't obj None when you return it?
– davidim
Jan 2 at 22:00
@davidim see youtube.com/watch?v=_AEJHKGk9ns for your question. I also just realised I didn't answer your question of "implementation of the queue invalid or am I missing something else"! it's basically fine, as you can tell from the other responses there are various caveats around it, but it looks valid. I'll see if I can put some timings together of the implementations here
– Sam Mason
Jan 2 at 22:04
Thanks for the link and the response!
– davidim
Jan 2 at 22:16
Now, I understand! You are telling obj to refer to the same object that self.items[self.index] refers to. Then you rebind self.items[self.index] to None, but this does not actually modify the object! Thank you very much.
– davidim
Jan 2 at 22:37
I do have a question about what you did with the references in the dequeue method. I am a little confused about how obj still refers to the original object after you reassign that index in the array None. Why isn't obj None when you return it?
– davidim
Jan 2 at 22:00
I do have a question about what you did with the references in the dequeue method. I am a little confused about how obj still refers to the original object after you reassign that index in the array None. Why isn't obj None when you return it?
– davidim
Jan 2 at 22:00
@davidim see youtube.com/watch?v=_AEJHKGk9ns for your question. I also just realised I didn't answer your question of "implementation of the queue invalid or am I missing something else"! it's basically fine, as you can tell from the other responses there are various caveats around it, but it looks valid. I'll see if I can put some timings together of the implementations here
– Sam Mason
Jan 2 at 22:04
@davidim see youtube.com/watch?v=_AEJHKGk9ns for your question. I also just realised I didn't answer your question of "implementation of the queue invalid or am I missing something else"! it's basically fine, as you can tell from the other responses there are various caveats around it, but it looks valid. I'll see if I can put some timings together of the implementations here
– Sam Mason
Jan 2 at 22:04
Thanks for the link and the response!
– davidim
Jan 2 at 22:16
Thanks for the link and the response!
– davidim
Jan 2 at 22:16
Now, I understand! You are telling obj to refer to the same object that self.items[self.index] refers to. Then you rebind self.items[self.index] to None, but this does not actually modify the object! Thank you very much.
– davidim
Jan 2 at 22:37
Now, I understand! You are telling obj to refer to the same object that self.items[self.index] refers to. Then you rebind self.items[self.index] to None, but this does not actually modify the object! Thank you very much.
– davidim
Jan 2 at 22:37
add a comment |
As per my understanding, enqueue should insert at the end and dequeue should delete from the start.
So code should be
class FasterQueue:
def __init__(self):
self.items =
def enqueue(self, item):
self.items.append(item)
def dequeue(self):
if self.items:
return self.items.pop(0)
print("Underflow")
def isEmpty(self):
return self.items ==
def size(self):
return len(self.items)
answered Jan 2 at 18:43
infinityinfinity
11
add a comment |
As per my understanding, enqueue should insert at the end and dequeue should delete from the start.
So code should be
class FasterQueue:
def __init__(self):
self.items =
def enqueue(self, item):
self.items.append(item)
def dequeue(self):
if self.items:
return self.items.pop(0)
print("Underflow")
def isEmpty(self):
return self.items ==
def size(self):
return len(self.items)
answered Jan 2 at 18:43
infinityinfinity
11
add a comment |
As per my understanding, enqueue should insert at the end and dequeue should delete from the start.
So code should be
class FasterQueue:
def __init__(self):
self.items =
def enqueue(self, item):
self.items.append(item)
def dequeue(self):
if self.items:
return self.items.pop(0)
print("Underflow")
def isEmpty(self):
return self.items ==
def size(self):
return len(self.items)
answered Jan 2 at 18:43
infinityinfinity
11
As per my understanding, enqueue should insert at the end and dequeue should delete from the start.
So code should be
class FasterQueue:
def __init__(self):
self.items =
def enqueue(self, item):
self.items.append(item)
def dequeue(self):
if self.items:
return self.items.pop(0)
print("Underflow")
def isEmpty(self):
return self.items ==
def size(self):
return len(self.items)
answered Jan 2 at 18:43
infinityinfinity
11
answered Jan 2 at 18:43
infinityinfinity
11
answered Jan 2 at 18:43
infinityinfinity
11
answered Jan 2 at 18:43
infinityinfinity
11
11
add a comment |
add a comment |
The O(n) is a necessary consequence of managing the list length.
Here is a solution. In general, this runs as O(1), and from time to time it is O(n) as a result of an extra step that occurs inside the dequeue method.
The O(n) step occurs when the list grows too large and triggers the cleanup. Note that in general, this should be done specifically inside the dequeue method. Doing it outside, will tend to be more elaborate and less efficient.
class FasterQueue:
def __init__(self, maxwaste=100):
self.items =
self.nout = 0
self.maxwaste = maxwaste
def enqueue(self, item):
self.items.append(item)
def dequeue(self):
if len(self.items):
retv = self.items[self.nout]
self.nout += 1
if self.nout >= self.maxwaste:
self.items = self.items[self.nout:]
self.nout =0
return retv
else:
print( 'empty' )
raise ValueError
def listQ(self):
return ' '.join( self.items[self.nout:] )
def isEmpty(self):
return self.nout == len(self.items)
def size(self):
return len(self.items) - self.nout
q = FasterQueue(5)
for n in range(10):
q.enqueue( str(n) )
print( 'queue size %d nout %d items %s'%(q.size(),q.nout,q.listQ()) )
print( q.items )
while True:
try:
print( 'dequeue %s'%q.dequeue() )
print( 'queue size %d nout %d items %s'%(q.size(),q.nout,q.listQ()) )
print( q.items )
except:
print( 'empty' )
break
Running the above code produces the following output, note the recovery of wasted memory when maxwaste is exceeded. Maxwaste is set small here for the purpose of demonstrating the operation.
queue size 10 nout 0 items 0 1 2 3 4 5 6 7 8 9
['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
dequeue 0
queue size 9 nout 1 items 1 2 3 4 5 6 7 8 9
['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
dequeue 1
queue size 8 nout 2 items 2 3 4 5 6 7 8 9
['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
dequeue 2
queue size 7 nout 3 items 3 4 5 6 7 8 9
['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
dequeue 3
queue size 6 nout 4 items 4 5 6 7 8 9
['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
dequeue 4
queue size 5 nout 0 items 5 6 7 8 9
['5', '6', '7', '8', '9']
dequeue 5
queue size 4 nout 1 items 6 7 8 9
['5', '6', '7', '8', '9']
dequeue 6
queue size 3 nout 2 items 7 8 9
['5', '6', '7', '8', '9']
dequeue 7
queue size 2 nout 3 items 8 9
['5', '6', '7', '8', '9']
dequeue 8
queue size 1 nout 4 items 9
['5', '6', '7', '8', '9']
dequeue 9
queue size 0 nout 0 items
empty
empty
answered Jan 3 at 14:51
DrMDrM
1,104314
add a comment |
The O(n) is a necessary consequence of managing the list length.
Here is a solution. In general, this runs as O(1), and from time to time it is O(n) as a result of an extra step that occurs inside the dequeue method.
The O(n) step occurs when the list grows too large and triggers the cleanup. Note that in general, this should be done specifically inside the dequeue method. Doing it outside, will tend to be more elaborate and less efficient.
class FasterQueue:
def __init__(self, maxwaste=100):
self.items =
self.nout = 0
self.maxwaste = maxwaste
def enqueue(self, item):
self.items.append(item)
def dequeue(self):
if len(self.items):
retv = self.items[self.nout]
self.nout += 1
if self.nout >= self.maxwaste:
self.items = self.items[self.nout:]
self.nout =0
return retv
else:
print( 'empty' )
raise ValueError
def listQ(self):
return ' '.join( self.items[self.nout:] )
def isEmpty(self):
return self.nout == len(self.items)
def size(self):
return len(self.items) - self.nout
q = FasterQueue(5)
for n in range(10):
q.enqueue( str(n) )
print( 'queue size %d nout %d items %s'%(q.size(),q.nout,q.listQ()) )
print( q.items )
while True:
try:
print( 'dequeue %s'%q.dequeue() )
print( 'queue size %d nout %d items %s'%(q.size(),q.nout,q.listQ()) )
print( q.items )
except:
print( 'empty' )
break
Running the above code produces the following output, note the recovery of wasted memory when maxwaste is exceeded. Maxwaste is set small here for the purpose of demonstrating the operation.
queue size 10 nout 0 items 0 1 2 3 4 5 6 7 8 9
['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
dequeue 0
queue size 9 nout 1 items 1 2 3 4 5 6 7 8 9
['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
dequeue 1
queue size 8 nout 2 items 2 3 4 5 6 7 8 9
['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
dequeue 2
queue size 7 nout 3 items 3 4 5 6 7 8 9
['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
dequeue 3
queue size 6 nout 4 items 4 5 6 7 8 9
['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
dequeue 4
queue size 5 nout 0 items 5 6 7 8 9
['5', '6', '7', '8', '9']
dequeue 5
queue size 4 nout 1 items 6 7 8 9
['5', '6', '7', '8', '9']
dequeue 6
queue size 3 nout 2 items 7 8 9
['5', '6', '7', '8', '9']
dequeue 7
queue size 2 nout 3 items 8 9
['5', '6', '7', '8', '9']
dequeue 8
queue size 1 nout 4 items 9
['5', '6', '7', '8', '9']
dequeue 9
queue size 0 nout 0 items
empty
empty
answered Jan 3 at 14:51
DrMDrM
1,104314
add a comment |
The O(n) is a necessary consequence of managing the list length.
Here is a solution. In general, this runs as O(1), and from time to time it is O(n) as a result of an extra step that occurs inside the dequeue method.
The O(n) step occurs when the list grows too large and triggers the cleanup. Note that in general, this should be done specifically inside the dequeue method. Doing it outside, will tend to be more elaborate and less efficient.
class FasterQueue:
def __init__(self, maxwaste=100):
self.items =
self.nout = 0
self.maxwaste = maxwaste
def enqueue(self, item):
self.items.append(item)
def dequeue(self):
if len(self.items):
retv = self.items[self.nout]
self.nout += 1
if self.nout >= self.maxwaste:
self.items = self.items[self.nout:]
self.nout =0
return retv
else:
print( 'empty' )
raise ValueError
def listQ(self):
return ' '.join( self.items[self.nout:] )
def isEmpty(self):
return self.nout == len(self.items)
def size(self):
return len(self.items) - self.nout
q = FasterQueue(5)
for n in range(10):
q.enqueue( str(n) )
print( 'queue size %d nout %d items %s'%(q.size(),q.nout,q.listQ()) )
print( q.items )
while True:
try:
print( 'dequeue %s'%q.dequeue() )
print( 'queue size %d nout %d items %s'%(q.size(),q.nout,q.listQ()) )
print( q.items )
except:
print( 'empty' )
break
Running the above code produces the following output, note the recovery of wasted memory when maxwaste is exceeded. Maxwaste is set small here for the purpose of demonstrating the operation.
queue size 10 nout 0 items 0 1 2 3 4 5 6 7 8 9
['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
dequeue 0
queue size 9 nout 1 items 1 2 3 4 5 6 7 8 9
['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
dequeue 1
queue size 8 nout 2 items 2 3 4 5 6 7 8 9
['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
dequeue 2
queue size 7 nout 3 items 3 4 5 6 7 8 9
['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
dequeue 3
queue size 6 nout 4 items 4 5 6 7 8 9
['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
dequeue 4
queue size 5 nout 0 items 5 6 7 8 9
['5', '6', '7', '8', '9']
dequeue 5
queue size 4 nout 1 items 6 7 8 9
['5', '6', '7', '8', '9']
dequeue 6
queue size 3 nout 2 items 7 8 9
['5', '6', '7', '8', '9']
dequeue 7
queue size 2 nout 3 items 8 9
['5', '6', '7', '8', '9']
dequeue 8
queue size 1 nout 4 items 9
['5', '6', '7', '8', '9']
dequeue 9
queue size 0 nout 0 items
empty
empty
answered Jan 3 at 14:51
DrMDrM
1,104314
The O(n) is a necessary consequence of managing the list length.
Here is a solution. In general, this runs as O(1), and from time to time it is O(n) as a result of an extra step that occurs inside the dequeue method.
The O(n) step occurs when the list grows too large and triggers the cleanup. Note that in general, this should be done specifically inside the dequeue method. Doing it outside, will tend to be more elaborate and less efficient.
class FasterQueue:
def __init__(self, maxwaste=100):
self.items =
self.nout = 0
self.maxwaste = maxwaste
def enqueue(self, item):
self.items.append(item)
def dequeue(self):
if len(self.items):
retv = self.items[self.nout]
self.nout += 1
if self.nout >= self.maxwaste:
self.items = self.items[self.nout:]
self.nout =0
return retv
else:
print( 'empty' )
raise ValueError
def listQ(self):
return ' '.join( self.items[self.nout:] )
def isEmpty(self):
return self.nout == len(self.items)
def size(self):
return len(self.items) - self.nout
q = FasterQueue(5)
for n in range(10):
q.enqueue( str(n) )
print( 'queue size %d nout %d items %s'%(q.size(),q.nout,q.listQ()) )
print( q.items )
while True:
try:
print( 'dequeue %s'%q.dequeue() )
print( 'queue size %d nout %d items %s'%(q.size(),q.nout,q.listQ()) )
print( q.items )
except:
print( 'empty' )
break
Running the above code produces the following output, note the recovery of wasted memory when maxwaste is exceeded. Maxwaste is set small here for the purpose of demonstrating the operation.
queue size 10 nout 0 items 0 1 2 3 4 5 6 7 8 9
['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
dequeue 0
queue size 9 nout 1 items 1 2 3 4 5 6 7 8 9
['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
dequeue 1
queue size 8 nout 2 items 2 3 4 5 6 7 8 9
['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
dequeue 2
queue size 7 nout 3 items 3 4 5 6 7 8 9
['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
dequeue 3
queue size 6 nout 4 items 4 5 6 7 8 9
['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
dequeue 4
queue size 5 nout 0 items 5 6 7 8 9
['5', '6', '7', '8', '9']
dequeue 5
queue size 4 nout 1 items 6 7 8 9
['5', '6', '7', '8', '9']
dequeue 6
queue size 3 nout 2 items 7 8 9
['5', '6', '7', '8', '9']
dequeue 7
queue size 2 nout 3 items 8 9
['5', '6', '7', '8', '9']
dequeue 8
queue size 1 nout 4 items 9
['5', '6', '7', '8', '9']
dequeue 9
queue size 0 nout 0 items
empty
empty
answered Jan 3 at 14:51
DrMDrM
1,104314
edited Jan 4 at 14:25
answered Jan 3 at 14:51
DrMDrM
1,104314
answered Jan 3 at 14:51
DrMDrM
1,104314
answered Jan 3 at 14:51
DrMDrM
1,104314
1,104314
add a comment |
add a comment |
For completeness, here is an answer using a ring buffer.
This example runs as O(1) forever, but it does this by limiting the size of the queue. If you want to allow the queue to grow, or size dynamically, then you again have your O(n) behavior.
In other words, you have O(1) only if you do not manage the size of the list in some way. That is the point of the question.
Okay, here is the ring buffer implementation with fixed queue length.
class FasterQueue:
def __init__(self, nsize=100):
self.items = [0]*nsize
self.nin = 0
self.nout = 0
self.nsize = nsize
def enqueue(self, item):
next = (self.nin+1)%self.nsize
if next != self.nout:
self.items[self.nin] = item
self.nin = next
print self.nin, item
else:
raise ValueError
def dequeue(self):
if self.nout != self.nin:
retv = self.items[self.nout]
self.nout = (self.nout+1)%self.nsize
return retv
else:
raise ValueError
def printQ(self):
if self.nout < self.nin:
print( ' '.join(self.items[self.nout:self.nin]) )
elif self.nout > self.nin:
print( ' '.join(self.items[self.nout:]+self.items[:self.nin]) )
def isEmpty(self):
return self.nin == self.nout
def size(self):
return (self.nin - self.nout + self.nsize)%self.nsize
q = FasterQueue()
q.enqueue( 'a' )
q.enqueue( 'b' )
q.enqueue( 'c' )
print( 'queue items' )
q.printQ()
print( 'size %d'%q.size() )
while True:
try:
print( 'dequeue %s'%q.dequeue() )
print( 'queue items' )
q.printQ()
except:
print( 'empty' )
break
answered Jan 2 at 20:18
DrMDrM
1,104314
@SamMason, here is the answer. I feel pretty sure it has to be a ring or a pool. It's a classic problem. I've dealt with it many times in DSPs and device drivers. My original idea using pop() assumed that python was doing this by reference and using a pool rather than by copying.
– DrM
Jan 2 at 20:55
yes, I've use similar implementations in lower level languages, it could also be implemented in Python via a linked list. going by how the question was stated it seemed like the OP wasn't after a "production-ready" implementation, just trying to understand how all the pieces fit together
– Sam Mason
Jan 2 at 21:50
@SamMason Nonetheless, continuing the list to infinity serves no purpose other than to avoid the O(n) cost of actually removing the item. And that was the pedagogical point of the question
– DrM
Jan 3 at 0:02
add a comment |
For completeness, here is an answer using a ring buffer.
This example runs as O(1) forever, but it does this by limiting the size of the queue. If you want to allow the queue to grow, or size dynamically, then you again have your O(n) behavior.
In other words, you have O(1) only if you do not manage the size of the list in some way. That is the point of the question.
Okay, here is the ring buffer implementation with fixed queue length.
class FasterQueue:
def __init__(self, nsize=100):
self.items = [0]*nsize
self.nin = 0
self.nout = 0
self.nsize = nsize
def enqueue(self, item):
next = (self.nin+1)%self.nsize
if next != self.nout:
self.items[self.nin] = item
self.nin = next
print self.nin, item
else:
raise ValueError
def dequeue(self):
if self.nout != self.nin:
retv = self.items[self.nout]
self.nout = (self.nout+1)%self.nsize
return retv
else:
raise ValueError
def printQ(self):
if self.nout < self.nin:
print( ' '.join(self.items[self.nout:self.nin]) )
elif self.nout > self.nin:
print( ' '.join(self.items[self.nout:]+self.items[:self.nin]) )
def isEmpty(self):
return self.nin == self.nout
def size(self):
return (self.nin - self.nout + self.nsize)%self.nsize
q = FasterQueue()
q.enqueue( 'a' )
q.enqueue( 'b' )
q.enqueue( 'c' )
print( 'queue items' )
q.printQ()
print( 'size %d'%q.size() )
while True:
try:
print( 'dequeue %s'%q.dequeue() )
print( 'queue items' )
q.printQ()
except:
print( 'empty' )
break
answered Jan 2 at 20:18
DrMDrM
1,104314
@SamMason, here is the answer. I feel pretty sure it has to be a ring or a pool. It's a classic problem. I've dealt with it many times in DSPs and device drivers. My original idea using pop() assumed that python was doing this by reference and using a pool rather than by copying.
– DrM
Jan 2 at 20:55
yes, I've use similar implementations in lower level languages, it could also be implemented in Python via a linked list. going by how the question was stated it seemed like the OP wasn't after a "production-ready" implementation, just trying to understand how all the pieces fit together
– Sam Mason
Jan 2 at 21:50
@SamMason Nonetheless, continuing the list to infinity serves no purpose other than to avoid the O(n) cost of actually removing the item. And that was the pedagogical point of the question
– DrM
Jan 3 at 0:02
add a comment |
For completeness, here is an answer using a ring buffer.
This example runs as O(1) forever, but it does this by limiting the size of the queue. If you want to allow the queue to grow, or size dynamically, then you again have your O(n) behavior.
In other words, you have O(1) only if you do not manage the size of the list in some way. That is the point of the question.
Okay, here is the ring buffer implementation with fixed queue length.
class FasterQueue:
def __init__(self, nsize=100):
self.items = [0]*nsize
self.nin = 0
self.nout = 0
self.nsize = nsize
def enqueue(self, item):
next = (self.nin+1)%self.nsize
if next != self.nout:
self.items[self.nin] = item
self.nin = next
print self.nin, item
else:
raise ValueError
def dequeue(self):
if self.nout != self.nin:
retv = self.items[self.nout]
self.nout = (self.nout+1)%self.nsize
return retv
else:
raise ValueError
def printQ(self):
if self.nout < self.nin:
print( ' '.join(self.items[self.nout:self.nin]) )
elif self.nout > self.nin:
print( ' '.join(self.items[self.nout:]+self.items[:self.nin]) )
def isEmpty(self):
return self.nin == self.nout
def size(self):
return (self.nin - self.nout + self.nsize)%self.nsize
q = FasterQueue()
q.enqueue( 'a' )
q.enqueue( 'b' )
q.enqueue( 'c' )
print( 'queue items' )
q.printQ()
print( 'size %d'%q.size() )
while True:
try:
print( 'dequeue %s'%q.dequeue() )
print( 'queue items' )
q.printQ()
except:
print( 'empty' )
break
answered Jan 2 at 20:18
DrMDrM
1,104314
For completeness, here is an answer using a ring buffer.
This example runs as O(1) forever, but it does this by limiting the size of the queue. If you want to allow the queue to grow, or size dynamically, then you again have your O(n) behavior.
In other words, you have O(1) only if you do not manage the size of the list in some way. That is the point of the question.
Okay, here is the ring buffer implementation with fixed queue length.
class FasterQueue:
def __init__(self, nsize=100):
self.items = [0]*nsize
self.nin = 0
self.nout = 0
self.nsize = nsize
def enqueue(self, item):
next = (self.nin+1)%self.nsize
if next != self.nout:
self.items[self.nin] = item
self.nin = next
print self.nin, item
else:
raise ValueError
def dequeue(self):
if self.nout != self.nin:
retv = self.items[self.nout]
self.nout = (self.nout+1)%self.nsize
return retv
else:
raise ValueError
def printQ(self):
if self.nout < self.nin:
print( ' '.join(self.items[self.nout:self.nin]) )
elif self.nout > self.nin:
print( ' '.join(self.items[self.nout:]+self.items[:self.nin]) )
def isEmpty(self):
return self.nin == self.nout
def size(self):
return (self.nin - self.nout + self.nsize)%self.nsize
q = FasterQueue()
q.enqueue( 'a' )
q.enqueue( 'b' )
q.enqueue( 'c' )
print( 'queue items' )
q.printQ()
print( 'size %d'%q.size() )
while True:
try:
print( 'dequeue %s'%q.dequeue() )
print( 'queue items' )
q.printQ()
except:
print( 'empty' )
break
answered Jan 2 at 20:18
DrMDrM
1,104314
edited Jan 4 at 14:34
answered Jan 2 at 20:18
DrMDrM
1,104314
answered Jan 2 at 20:18
DrMDrM
1,104314
answered Jan 2 at 20:18
DrMDrM
1,104314
1,104314
@SamMason, here is the answer. I feel pretty sure it has to be a ring or a pool. It's a classic problem. I've dealt with it many times in DSPs and device drivers. My original idea using pop() assumed that python was doing this by reference and using a pool rather than by copying.
– DrM
Jan 2 at 20:55
yes, I've use similar implementations in lower level languages, it could also be implemented in Python via a linked list. going by how the question was stated it seemed like the OP wasn't after a "production-ready" implementation, just trying to understand how all the pieces fit together
– Sam Mason
Jan 2 at 21:50
@SamMason Nonetheless, continuing the list to infinity serves no purpose other than to avoid the O(n) cost of actually removing the item. And that was the pedagogical point of the question
– DrM
Jan 3 at 0:02
add a comment |
@SamMason, here is the answer. I feel pretty sure it has to be a ring or a pool. It's a classic problem. I've dealt with it many times in DSPs and device drivers. My original idea using pop() assumed that python was doing this by reference and using a pool rather than by copying.
– DrM
Jan 2 at 20:55
yes, I've use similar implementations in lower level languages, it could also be implemented in Python via a linked list. going by how the question was stated it seemed like the OP wasn't after a "production-ready" implementation, just trying to understand how all the pieces fit together
– Sam Mason
Jan 2 at 21:50
@SamMason Nonetheless, continuing the list to infinity serves no purpose other than to avoid the O(n) cost of actually removing the item. And that was the pedagogical point of the question
– DrM
Jan 3 at 0:02
@SamMason, here is the answer. I feel pretty sure it has to be a ring or a pool. It's a classic problem. I've dealt with it many times in DSPs and device drivers. My original idea using pop() assumed that python was doing this by reference and using a pool rather than by copying.
– DrM
Jan 2 at 20:55
@SamMason, here is the answer. I feel pretty sure it has to be a ring or a pool. It's a classic problem. I've dealt with it many times in DSPs and device drivers. My original idea using pop() assumed that python was doing this by reference and using a pool rather than by copying.
– DrM
Jan 2 at 20:55
yes, I've use similar implementations in lower level languages, it could also be implemented in Python via a linked list. going by how the question was stated it seemed like the OP wasn't after a "production-ready" implementation, just trying to understand how all the pieces fit together
– Sam Mason
Jan 2 at 21:50
yes, I've use similar implementations in lower level languages, it could also be implemented in Python via a linked list. going by how the question was stated it seemed like the OP wasn't after a "production-ready" implementation, just trying to understand how all the pieces fit together
– Sam Mason
Jan 2 at 21:50
@SamMason Nonetheless, continuing the list to infinity serves no purpose other than to avoid the O(n) cost of actually removing the item. And that was the pedagogical point of the question
– DrM
Jan 3 at 0:02
@SamMason Nonetheless, continuing the list to infinity serves no purpose other than to avoid the O(n) cost of actually removing the item. And that was the pedagogical point of the question
– DrM
Jan 3 at 0:02
add a comment |
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f54010988%2fefficient-implementation-of-queue-time-complexity-of-enqueue-and-dequeue%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
dequeueshould always remove the item from one end of the queue. That'sO(1)– JacobIRR
Jan 2 at 18:01
1
@JacobIRR He's not working with a typical python list, the implementation represents a queue. queues are FIFO, and so dequeue should remove from the start of queue, not the end.
– Paritosh Singh
Jan 2 at 18:04
i guess the only thing i can think of is, what happens when you try to dequeue past an "empty" queue so to speak. enqueue once, dequeue twice.
– Paritosh Singh
Jan 2 at 18:17
Wouldn't that still be O(1) since the worst case on get item for lists is O(1)... I guess the textbook just made a mistake?
– davidim
Jan 2 at 18:20
i think it would probably be an index error actually, however yes, i dont really see any "reason" to have an incredibly long list that keeps consuming memory but dequeues as O(1), but i suspect the book expects you to perhaps tidy up the list when you empty it out or something.
– Paritosh Singh
Jan 2 at 18:31