Python queue like data structure

Question

I'm working on a list that receives new elements once in a while. When these new elements have been added, I want to perform a computation over these elements (to be precise, estimate a KDE). I quickly realized that if this list were to grow unbounded, the computation of the KDE function would take extremely long, so I thought a Queue would be a good data structure to use. The standard Python Queue (https://docs.python.org/2/library/queue.html), however, does not allow for access to individual Queue elements without 'popping' them out of the queue. Is there any alternative?

In other words: is there some Python library that allows me to get a queue element without popping it? (or that allows array-like indexing of the queue elements?)

I don't know what a KDE is, but a queue is something where you add things to the end and pop them at the beginning; with arbitrary access it's not a queue. Is there any reason you can't just use a list? — RemcoGerlich
– RemcoGerlich, Commented Jul 2, 2014 at 12:43
You should think about the other data structure, e.g. list. Queue is not what you are looking for. — myildirim
– myildirim, Commented Jul 2, 2014 at 12:44
@RemcoGerlich well, I could use a list, but I want it to be capped at a maximum number of elements. When the list is full and new elements arrive, I'd like the new elements to be added, and the oldest elements to be removed. Therefore, a queue seemed like the most natural solution — danielvdende
– danielvdende, Commented Jul 2, 2014 at 12:45
@NiklasB. Thanks! Looks good so far :), this should probably work — danielvdende
– danielvdende, Commented Jul 2, 2014 at 12:46

Simon Fraser · Accepted Answer · 2014-07-02 12:45:41Z

5

It sounds like you would get good use from using deque:

https://docs.python.org/2/library/collections.html#collections.deque

answered Jul 2, 2014 at 12:45

Simon Fraser

2,81821 silver badges26 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

danielvdende Over a year ago

@Niklas B (above) suggested the same. Looks good so far, thanks!

RemcoGerlich Over a year ago

But note that it's optimized for access at the ends, so it's probably slower than a list when using indexing to get at data somewhere in the middle.

obayhan · Accepted Answer · 2014-07-02 12:53:05Z

0

I dont understand why u use queue if u dont use the popping mechanism. If u are wondering about to owercrowd in your array u may use 1 array and 1 queue. First is waiting queue and second is processing array.

And u may do some optimizations about your loop to speed it up.

For example u may change

import xxx

for a in b_array:
   xxx.do_something(a)

to this:

import xxx

ds = xxx.do_something  #linking a function in memory speeds up foreach performance very much
for a in b_array:
   ds(a)

I think your problem is not about queue size. If it is, u must check your early code.

answered Jul 2, 2014 at 12:53

obayhan

1,75218 silver badges38 bronze badges

1 Comment

danielvdende Over a year ago

The queue size will be problematic for the dataset I am dealing with. This dataset generates 1000 points per second, so storing them in memory is not feasible, let alone suitable for computation (sorry, didn't mention the exact use case)

danielvdende · Accepted Answer · 2014-07-02 12:57:18Z

0

As @RemcoGerlich suggested, the best way forward (I believe) is to maintain an index pointer that 'memorizes' where the next suitable write position is, modulo the size of the list. This will allow for very fast implementation using numpy and will also allow me to achieve the goals I specified.

answered Jul 2, 2014 at 12:57

danielvdende

7109 silver badges25 bronze badges

2 Comments

Stuart Over a year ago

Won't your list get too long for memory if there are 1000 points per second? Note that the time needed for list operations (adding an item to the end, checking its length and popping an item from the beginning if it's too long) may be negligible compared to the time needed for the KDE computation.

danielvdende Over a year ago

Yes, I intend to cap the size of the list at some fixed number to optimize KDE computation time and ensure that it fits in memory

Collectives™ on Stack Overflow

Python queue like data structure

3 Answers 3

2 Comments

1 Comment

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

1 Comment

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related