Leetcode: количество островов

Я работаю над второй итерацией известной графовой задачи «Число островов» на Leetcode.

https://leetcode.com/problems/number-of-islands/

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.

 

Example 1:

Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1

Example 2:

Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3

Мой подход состоит в том, чтобы перебирать каждую ячейку в сетке, увеличивая счетчик, когда значение == 1. Затем выполните поиск в ширину соседей ячейки, добавляя их в очередь, если их значение == 1. После очереди пусто, продолжайте перебирать все ячейки.

Чтобы избежать бесконечных циклов, я сначала использовал set() для отслеживания списка координат кортежа. Это, похоже, увеличило использование моей памяти, поэтому я затем улучшил алгоритм, удалив набор и просто установив значение посещенных ячеек на 0.

Я прошел все тестовые примеры, но до сих пор не могу понять, как улучшить время выполнения. В настоящее время я медленнее, чем ~ 90% представлений Python.

Буду признателен, если кто-нибудь поможет ускорить это дело!

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        """
        Gets the neighbors of a coordinate in a grid. Returns a list of tuples.
        """
        m = len(grid)
        n = len(grid[0])

        def get_neighbors(coord: Tuple[int, int]) -> List[Tuple]:
            delta_row    = [0, 1, 0, -1]
            delta_column = [1, 0, -1, 0]

            neighbors = []
            for i in range(len(delta_row)):
                new_x = coord[0] + delta_row[i]
                new_y = coord[1] + delta_column[i]

                if -1 < new_x < m and -1 < new_y < n:
                    neighbors.append((new_x, new_y))

            return neighbors

        # loop through the entire grid and set coords to 0 as we visit them 
        # if val == 1, do a breadth-first search for neighbors and increment islands
        # if val == 0, continue to next coordinate.

        islands = 0

        for i in range(len(grid)):
            for j in range(len(grid[0])):
                coord = (i, j)
                if grid[coord[0]][coord[1]] == "1":
                    islands += 1

                    # breadth-first search
                    q = deque([coord])
                    while len(q) > 0:
                        c = q.popleft()
                        grid[c[0]][c[1]] = "0"
                        for neighbor in get_neighbors(c):
                            if grid[neighbor[0]][neighbor[1]] == "1":
                                q.append(neighbor)
                                grid[neighbor[0]][neighbor[1]] = "0"

        return islands

Мои предложения:

• Переменные m и n инициализируются, но никогда не используются

• Функция get_neighbors:

  def get_neighbors(coord: Tuple[int, int]) -> List[Tuple]:
      delta_row    = [0, 1, 0, -1]
      delta_column = [1, 0, -1, 0]
  
      neighbors = []
      for i in range(len(delta_row)):
          new_x = coord[0] + delta_row[i]
          new_y = coord[1] + delta_column[i]
  
          if -1 < new_x < m and -1 < new_y < n:
              neighbors.append((new_x, new_y))
  
      return neighbors
  

  Можно упростить до:

  def get_neighbors(r: int, c: int) -> List[Tuple]:
      neighbors = (r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)
      return [(r, c) for r, c in neighbors if -1 < r < m and -1 < c < n]
  

  Вместо распаковки coord вы можете пройти ряд r и столбец c напрямую. Это также улучшает время работы примерно на 30%.

Альтернативный подход

Альтернативный и более быстрый подход — использовать рекурсию:

def recursive(grid: List[List[str]]) -> int:
    islands = 0
    m, n = len(grid), len(grid[0])

    def sink_neighbors(row, col):
        grid[row][col] = '0'
        if row > 0 and grid[row - 1][col] == '1':
            sink_neighbors(row - 1, col)
        if row < m - 1 and grid[row + 1][col] == '1':
            sink_neighbors(row + 1, col)
        if col > 0 and grid[row][col - 1] == '1':
            sink_neighbors(row, col - 1)
        if col < n - 1 and grid[row][col + 1] == '1':
            sink_neighbors(row, col + 1)

    for r in range(m):
        for c in range(n):
            if grid[r][c] == '1':
                islands += 1
                sink_neighbors(r, c)
    return islands

Запуск рекурсивного решения на LeetCode:

Runtime: 120 ms, faster than 98.12% of Python3 online submissions for Number of Islands

Это время работы исходного решения, улучшенного и рекурсивного на случайной сетке из 1 миллиона элементов:

Runtime original: 1.289 s
Runtime improved: 0.887 s
Runtime recursive: 0.365 s

Полный код

from collections import deque
from typing import List, Tuple
import random
from time import perf_counter as pc


def original(grid: List[List[str]]) -> int:
    m = len(grid)
    n = len(grid[0])

    def get_neighbors(coord: Tuple[int, int]) -> List[Tuple]:
        delta_row = [0, 1, 0, -1]
        delta_column = [1, 0, -1, 0]

        neighbors = []
        for i in range(len(delta_row)):
            new_x = coord[0] + delta_row[i]
            new_y = coord[1] + delta_column[i]

            if -1 < new_x < m and -1 < new_y < n:
                neighbors.append((new_x, new_y))

        return neighbors

    islands = 0

    for i in range(len(grid)):
        for j in range(len(grid[0])):
            coord = (i, j)
            if grid[coord[0]][coord[1]] == "1":
                islands += 1
                q = deque([coord])
                while len(q) > 0:
                    c = q.popleft()
                    grid[c[0]][c[1]] = "0"
                    for neighbor in get_neighbors(c):
                        if grid[neighbor[0]][neighbor[1]] == "1":
                            q.append(neighbor)
                            grid[neighbor[0]][neighbor[1]] = "0"

    return islands


def improved(grid: List[List[str]]) -> int:
    m, n = len(grid), len(grid[0])

    def get_neighbors(r: int, c: int) -> List[Tuple]:
        neighbors = (r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)
        return [(r, c) for r, c in neighbors if -1 < r < m and -1 < c < n]

    islands = 0

    for row in range(m):
        for col in range(n):
            if grid[row][col] == "1":
                islands += 1
                q = deque([(row, col)])
                while len(q) > 0:
                    r, c = q.popleft()
                    grid[r][c] = "0"
                    for r, c in get_neighbors(r, c):
                        if grid[r][c] == "1":
                            q.append((r, c))
                            grid[r][c] = "0"

    return islands


def recursive(grid: List[List[str]]) -> int:
    islands = 0
    m, n = len(grid), len(grid[0])

    def sink_neighbors(row, col):
        grid[row][col] = '0'
        if row > 0 and grid[row - 1][col] == '1':
            sink_neighbors(row - 1, col)
        if row < m - 1 and grid[row + 1][col] == '1':
            sink_neighbors(row + 1, col)
        if col > 0 and grid[row][col - 1] == '1':
            sink_neighbors(row, col - 1)
        if col < n - 1 and grid[row][col + 1] == '1':
            sink_neighbors(row, col + 1)

    for r in range(m):
        for c in range(n):
            if grid[r][c] == '1':
                islands += 1
                sink_neighbors(r, c)
    return islands


if __name__ == "__main__":
    N = 1000
    random_grid = [[str(random.randint(0, 1)) for _ in range(N)] for _ in range(N)]
    res = []

    # Benchmark
    for f in original, improved, recursive:
        random_grid_copy = [row[:] for row in random_grid]
        t0 = pc()
        res.append(f(random_grid_copy))
        t1 = pc()
        print(f'Runtime {f.__name__}: {round(t1 - t0, 3)} s')

    # Correctness
    assert res[0] == res[1] == res[2]

Поскольку улучшения производительности уже были предоставлены, я хочу добавить несколько моментов, касающихся удобочитаемости и «питонического» кода.

Именование переменных:

m = len(grid)
n = len(grid[0])
...
for i in range(len(grid)):
    for j in range(len(grid[0])):

Эти имена переменных вообще не описательны. Следующее более читабельно:

height = len(grid)
width = len(grid[0])
...
for row in range(height):
    for column in range(width):

Также обратите внимание, что нам не нужно пересчитывать эти значения для наших циклов for.

Питонический цикл while:

while len(q) > 0: эквивалентно while q:.

get_neighbors:

delta_row = [0, 1, 0, -1]
delta_column = [1, 0, -1, 0]
...
for i in range(len(delta_row)):
    new_x = coord[0] + delta_row[i]
    new_y = coord[1] + delta_column[i]

В Python вам никогда не придется перебирать индекс и получать доступ к элементам списка по этому индексу. Быстрое исправление заключается в следующем:

delta_rows = [0, 1, 0, -1]
delta_columns = [1, 0, -1, 0]
...
for delta_row, delta_column in zip(delta_rows, delta_columns):
    new_x = coord[0] + delta_row
    new_y = coord[1] + delta_column

Также обратите внимание, что именно здесь очень важно именование переменных, чтобы упростить чтение кода и выявление ошибок. В get_neighbors вы смешиваете три разных способа называть свои переменные (m, n — row, column — x, y), которые читатель должен интерпретировать перед пониманием (и, возможно, отладкой) кода. На первый взгляд читателю не очевидно, new_x на самом деле должна быть новая строка (я бы сказал, что другой способ более интуитивно понятен: y = row и x = column) и правильно ли сравнивать ее с m вместо n.

Условия:

if -1 < new_x < m and -1 < new_y < n:

также можно записать как

if new_x in range(m) and new_y in range(n):

или даже лучше как

if new_row in range(height) and new_column in range(width):

Я бы сказал, что в этом случае это еще больше увеличивает удобочитаемость, хотя это зависит от личных предпочтений.

Передача координат:

Я часто нахожу полезным использовать collection. namedtuples как «мини-классы», если определенная структура используется часто. Поскольку вам приходится довольно часто перемещаться и получать доступ к координатам, это может быть применимо здесь.

Используя что-то вроде

Coordinate = namedtuple("Coordinate", "row column")

после этого вы сможете создавать координаты и получать к ним доступ в более удобном для чтения виде. Пример использования:

coordinate = Coordinate(row=row, column=column)
                
row, column = coordinate
row = coordinate.row
column = coordinate.column

grid[coordinate.row][coordinate.column] = "0"

Это также относится к подсказкам типов в заголовках методов. Например в get_neighbors:

def get_neighbors(coord: Tuple[int, int]) -> List[Tuple]:

становится

def get_neighbors(coord: Coordinate) -> List[Coordinate]: