アイランドペリメーションアルゴリズムが遅すぎる

Question

LeetCodeから島周辺の問題に取り組んでいますが、実際の解決策はありますが、5817/5833テストケースのみを渡します。私はそれを成功と見なしますが、明らかに、非常に大きなサイズの "島"を扱うには十分効率的ではなく、パフォーマンス上の問題の原因を突き止めなければ、 "島周辺"の問題に慣れていない人のために、ここにLeetCodeページへのリンクがあります。私は言語で自分自身をrefamiliarizeし、うまくいけば自分自身にいくつかの新しいトリックを教えるためにPythonで問題を解決してきたので、それはちょうど誰かが私を改善する手助けができることを私は非効率的にやっているものになるかもしれ

Island Perimeter Problem

。効率性の点で、以下のアルゴリズムで目に見える問題を誰も見ることができますか？

def islandPerimeter(self, grid): 
    """ 
    :type grid: List[List[int]] 
    :rtype: int 
    """ 
    start = self.locateIsland(grid) 
    return self.islandHelp(grid, start) 

def islandHelp(self, grid, start): 
    # get the perimeter of this position 
    p = self.getPerimeter(grid, start) 
    # mark this position as visited so we don't count it repeatedly 
    grid[start[0]][start[1]] = 2 
    # offsets to current positions to find land to the sides 
    sides = [[-1, 0], [0, 1], [1, 0], [0, -1]] 
    for side in sides: 
     newPos = [(start[0] + side[0]), (start[1] + side[1])] 
     if ((newPos[0] in range(len(grid))) and 
     (newPos[1] in range(len(grid[newPos[0]]))) and 
     (grid[newPos[0]][newPos[1]] == 1)): 
       # recursively find perimeter of connected land 
       p += self.islandHelp(grid, newPos) 
    return p 

def getPerimeter(self, grid, pos): 
    p = 0 
    # offsets to find the neighboring positions 
    sides = [[-1, 0], [0, 1], [1, 0], [0, -1]] 
    for side in sides: 
     if (((pos[0] + side[0]) in range(len(grid))) and 
      ((pos[1] + side[1]) in range(len(grid[pos[0] + side[0]])))): 
      if (grid[pos[0] + side[0]][pos[1] + side[1]] == 0): 
       # in bounds of grid, but not a land mass, add to perimeter 
       p += 1 
     else: 
      # out of bounds means edge of grid, add to perimeter 
      p += 1 
    return p 

def locateIsland(self, grid): 
    # iterate through the grid to find a 1 and use that as start position 
    for r in range(len(grid)): 
     for c in range(len(grid[r])): 
      if (grid[r][c] == 1): 
       return (r, c) 
    return (-1, -1) 

Answer 1

あなたは、このようなチェックです：

(pos[0] + side[0]) in range(len(grid))

次のことが起こっている：

• をPythonは整数を含むサイズLEN（グリッド）のリストを作成し、[ 0,1,2,3、...]
• Pythonはあなたの番号（この場合はpos [0] + side [0]）を受け取り、はすべてリスト内のtegerをとし、その整数と比較して同じかどうかを確認します。

数字がグリッドの長さよりも小さい場合は、これが効率的ではありません。あなたは、はるかに短い時間で、同じ効果を得るために

(pos[0] + side[0]) >= 0 and (pos[0] + side[0]) < len(grid)

でその行を置き換えることができます。私はこれを変更し、これが完了したときにすべてのケースを通過することを確認しました。