Initialize queue from an existing list

I am writing a code that uses queues and lists, and every time I need to create a queue from a list, what I do is

l = [1, 2, 3, 4, 5] # existing list
q = queue.Queue()
for e in l:
  q.put(e)

This actually works, but this is O(n). How about enhancing queue.XXXQueue classes to accept a list on initializing a queue, which works in O(1) (if possible)? I assume an interface something like:

l = [1, 2, 3, 4, 5] # existing list
q = queue.Queue(l)

In Erlang, there is a method queue:from_list/1 that initialize a queue from a list in O(1). I looked into the implementation of queue module and found that queues in each classes are implemented as the following types:

Except for Queue class, other classes looked straight forward to enhance for this purpose. Let me know what you think.

1 Like

In Python it cannot be done on O(1). Lists are mutable, so you need to copy every item to the internal storage, and it takes linear time. Note also that while PriorityQueue uses a list for internal storage, the order of items in that list does not match the order in the input list.

You can save some time for acquiring/releasing locks in bulk addition, but you will need to copy tens lines of code, and it will make the code less extensible and maintainable.

1 Like

If the speed of addition is of concern, you can make the initialization of the queue from a list quite a bit faster by creating a dedicated method:

import queue
l=list(range(200000))
q=queue.Queue()

def put_sequence(self, sequence):
    assert self.maxsize==0 or self.maxsize >= q.qsize()+len(sequence)
    with self.not_full:
        self.queue.extend(l)
        self.unfinished_tasks += len(sequence)
        self.not_empty.notify()

# 0.268 seconds
_=[q.put(e) for e in l]

# < 0.1 seconds
put_sequence(q, l)

Probably not all corner cases are correct with this example, but it should give a rough idea what is possible. The other types of queues can be handled in a similar way.

Maybe if we make the _put public, there is no need to add much additional code to cpython, but a user create a much such as the above to achieve a fast initialization from a list.
(the self.queue.extend(l) is then replaced by self._put(item) for item in sequence)

Thank you @storchaka and @eendebakpt for the reply.

@storchaka, I didn’t realize that Python doesn’t have methods to copy lists in O(1). I agree the point considering the case:

q = queue.Queue(l)
l.add(6)
# q is unexpectedly modified

To make this safe, I think we need something that delegates the ownership of the list l to the queue, which I don’t come up with how to achieve in Python.

@eendebakpt Thank you for the workaround. I replace my code with your suggestion.