Блог пользователя YouKnowNothing_JonSnow

Python3 Queue is much much slower than list
Автор YouKnowNothing_JonSnow, история, 4 года назад, По-английски

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

  • Проголосовать: нравится
  • +33
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    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.

    → Ответить
    • »
      »
      »
      4 года назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

      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.

      → Ответить