Updated 2022-05-21 0
Viewed 1 times
0

I have a list of deque, built from a 2d array:

data = [[4,2,5,23], [3], [4], [9,82,4,3,56,7]]
data_q = [deque(i) for i in data ]

I need to popleft a value from each queue, in order, until all queues have been exhausted. For example:

   4,3,4,9,2,82,5,4,23,3,56,7 for the lists above

another example:

[[1,2,3],[4,5],[6],[1,2,1,2,2],[],[],[7,8,9,122,4,5]] => [1, 4, 6, 1, 7, 2, 5, 2, 8, 3, 1, 9, 2, 122, 2, 4, 5]

because this list can become enormous, I want to skip over empty queues. e.g

[deque([]),deque([]),deque([]),deque([]), ....(60,000 empty queues) ..., deque([1,2,3,54,5,])

my solution is to also have a deque of indexes of the queues that still have values with a loop like this:

    data_i = deque([i for i in range(len(data_q))])

    return_list = []
    while len(data_i) > 0:
        index = data_i.popleft()
        return_list.append(data_q[index].popleft())
        if len(data_q[index]) != 0:
            data_i.append(index)

Loop continuously until we no longer have any dequeues in our queue of indexes to pop from. This will leave the entire list with an empty deque when its done. The alternative is to simply iterate through the list of deque, and remove[index_of_empty_queue] when it is done. This is extremely slow to delete items in a very large list, especially towards the start of the list.

Any thoughts on my approach and if there is a better one? I know popleft and append is O(1) for deque, I just still don't know the overall performant implications of using this method to essentially iterate through a list, with the ability to also remove items in the "list" (deque) with O(1) as well.

🔴 No definitive solution yet