YouKnowNothing_JonSnow's blog

Python3 Queue is much much slower than list
By YouKnowNothing_JonSnow, history, 5 years ago, In English

I was recently trying to solve the Solve the maze using Python3, and for BFS, I was trying to use Python Queue from queue and it was giving TLE, and when I replaced the Queue with list it got Accepted within 300 ms.

Here is the submission with list

Here is the submission with Queue

Any explanation is appreciated.

Thanks, and please be kind, coz me being Jon Snow and everybody keeps saying that to me

  • Vote: I like it
  • +33
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
5 years ago, # |
  Vote: I like it +16 Vote: I do not like it

A Python Queue is quite slow; the correct object to use as a fast queue data structure is the deque object from collections. It is actually a double-ended queue (so you can append and pop from either side) but of course you can use this as a queue. If you use this data structure (here is your code with a deque: 83210553) it becomes fast enough.

In this particular problem, the queue never gets very long. At worst there are about 50 elements in it. As a result, the slow list operation pop(0) becomes quite fast in practice -- faster than a Queue.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Thanks a lot mees, I see what you're saying, but I was expecting some underlying concepts to hear coz of what happened. But anyway, thanks for the alternative sol.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it +10 Vote: I do not like it

      Queue is synchronized whereas deque is not. The overhead in keeping synchronization across threads is likely what makes Queue much slower than deque.

      Take a look at the official Python documentation for Queue. It should resolve your queries.

      → Reply