BFS探索をするのにキューで値を取り出すよりスタックで値を取り出す方と処理スピードが改善される理由

Question

下記の問題のコードで殆ど差のないコードなのにタイムアウトが出てしまい、完答できません。
大きな差分箇所は、stackかqueueの違いです。queueをstackを利用するように書き換えると、処理スピードが改善されるところまでは確認できています。

しかし、なぜ改善されるのかの理由がいまだにわかりません。もし、お気づきの点ありましたらご教示いただけませんしょうか？

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

200. Number of Islands

タイムアウトしまうコード

from collections import deque


class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        m = len(grid)
        n = len(grid[0])

----------差分箇所
        idx_list = deque()
        for r in range(m):
            for c in range(n):
                if grid[r][c] == "1":
                    idx_list.append((r, c))
-----------
        islands = 0
        while idx_list:
            islands += 1

----------差分箇所
            q = deque([idx_list.popleft()])
----------
            while q:
                r, c = q.popleft()
                edge_index = [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]
                for r, c in edge_index:
                    if (r, c) in idx_list:
                        q.append((r, c))
                        idx_list.remove((r, c))
        return islands

処理スピードが改善されたコード

 from collections import deque

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid:
            return 0

----------差分箇所
        grid_index = set(
            (r, c)
            for r in range(len(grid))
            for c in range(len(grid[0]))
            if grid[r][c] == "1"
        )
----------

        island = 0
        while grid_index:
            island += 1
----------差分箇所
            queue = deque([grid_index.pop()])
----------
            while queue:
                r, c = queue.popleft()

                edge_index = [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]
                for edge in edge_index:
                    if edge in grid_index:
                        grid_index.remove(edge)
                        queue.append(edge)
        return island

Answer 1

stackじゃなくてsetですよね、というのは置いておいて。

見た目、before,after で対応するこの部分が変わるでしょうね。

                    if (r, c) in idx_list:
                        q.append((r, c))
                        idx_list.remove((r, c))

                    if edge in grid_index:
                        grid_index.remove(edge)
                        queue.append(edge)

beforeでは dequeue である idx_list の要素を順に調べていくことになるので、要素数が多ければそれだけ処理時間に響きますが、後者は set に替わっていて、キーがハッシュ化されているはずなので要素数にほぼ影響を受けないはずです。

Comments

[sequelanonymous]

コメントありがとうございます。一点確認させてください。

> 要素数が多ければそれだけ処理時間に響きますが...

の部分は、if-in構文でlistのデータ型の場合は、要素分だけ確認していく処理がpython内部ではしるから遅い、っていう理解であっていますでしょうか？
もし、Python公式ドキュメントにそのあたりの仕様がわかるリンクご存知でしたらご教示いただけませんしょうか？

[angel_p_57]

> if-in構文でlistのデータ型の場合は、要素分だけ確認していく処理がpython内部ではしるから遅い
listでなくて今回はdequeue ( Python的には deque ) ですが…。話としては同じで、その認識で問題ないです。

> Python公式ドキュメントにそのあたりの仕様がわかるリンクご存知でしたら
公式ドキュメントにはわざわざ書いてないんじゃないでしょうか。一般論として、高速に検索かけるなら、ハッシュテーブル ( Python の set 等 )、内部的に sort された木構造 ( C++ の std::set 等 ) くらいしかないので。deque に関して、append, pop が速いというのは明記されてますけどね。
https://docs.python.org/ja/3/library/collections.html
※逆に、順々に調べずに済む方法が思いつきますか?

Answer 2

なぜ改善されるのかの理由がいまだにわかりません。

Pythonにおいて、listが(可変長)配列で実装されているなら、stackの方が速いことの説明がつきます。