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 
A Python
Queueis quite slow; the correct object to use as a fast queue data structure is thedequeobject fromcollections. 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 adeque: 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 aQueue.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.
Queueis synchronized whereasdequeis not. The overhead in keeping synchronization across threads is likely what makesQueuemuch slower thandeque.Take a look at the official Python documentation for
Queue. It should resolve your queries.