python - 'max area of islands' 算法的 3D 实现期间核心转储

Question

我正在尝试使用an algorithm对于 3D 问题中的问题“Max area of island”，因此它更像是岛屿的最大体积。我使用 200x200x200 体素的总体积作为输入，但我遇到了麻烦，因为当我输入的体积中有非常大的“岛屿”时(Ubunut 终端中的“核心转储”)，它不起作用。以下是我为将其应用于 3D 问题而进行的修改后的代码:

class Solution3D:

    def dfs3D(self, grid, r, c, l):
        grid[r][c][l] = 0
        num = 1
        lst = [(r-1, c, l), (r+1, c, l), (r, c-1, l), (r, c+1, l), (r, c, l-1), (r, c, l+1)]
        for row, col, leh in lst:
            if row >= 0 and col >= 0 and leh >= 0\
            and row < len(grid) and col < len(grid[0]) and leh < len(grid[0][0])\
            and grid[row][col][leh] == 1:
                num += self.dfs3D(grid, row, col, leh)
        return num


    def maxAreaOfIsland3D(self, grid):
        area_islands = 0
        for r in range(len(grid)):
            for c in range(len(grid[0])):
                for l in range(len(grid[0][0])):
                    if grid[r][c][l] == 1:
                        area_islands = max(area_islands, self.dfs3D(grid, r, c, l))
        return area_islands

这样的实现效率是不是太低了？我怎样才能减少它对内存的消耗，以便我可以在大岛屿上使用它？

非常感谢!

Answer 1

有东西。大约需要一分钟，需要 6GB RAM

1. 首先，我使用 sklearn.image.grid_to_graph 找到边缘，这非常快
2. 接下来我构建 networkx 图 - 这是计算时间和 RAM 使用的瓶颈
3. 最后，我找到了该图中所有连通的子图并返回

import numpy as np
import networkx as nx
import sklearn.feature_extraction.image

grid_size = 4   # manual check -> for seed 0: 38 nodes, largest subgraph has 37 connected nodes, correct
grid_size = 200


random_grid = np.random.RandomState(seed=0).randint(0, 2, size=(grid_size, grid_size, grid_size))
G = nx.Graph()
print('finding edges...')
graph = sklearn.feature_extraction.image.grid_to_graph(grid_size, grid_size, grid_size, mask=random_grid)
print('buidling graph...')
G.add_edges_from(np.vstack([graph.col, graph.row]).T)
print('finding subgraphs...')
subgraphs = nx.connected_components(G)
sorted_subgraphs = sorted(subgraphs, key=len, reverse=True)
G0 = G.subgraph(sorted_subgraphs[0])
print('Largest subgraph size: ', len(G0))

Largest subgraph size:  3909288