リストルックアップが設定されたルックアップよりも遅い

Question

私は現在、特定の2Dポイントが "合法"である場合、つまりグリッドの境界内にあるかどうかを複数回チェックしなければならないプロジェクトを行っています。前に訪問された。グリッドは固定されたH x Wのサイズを持っているので、私はおそらくセットではなく2Dのルックアップテーブルを格納できると思いました。驚いたことに、単純な配列検索でO(1)とは対照的に、（理論的には）O(logn)操作であっても、セットに表示されているかどうかを確認するよりもかなり遅いです。

まず試してみてください。

class PointSet: 
    def __init__(self, h, w): 
     if h <= 0 or w <= 0: 
      raise ValueError("Invalid size") 
     self.h = h 
     self.w = w 
     self.lookup = [[False for _ in range(w)] for _ in range(h)] 
     self.size = 0 

    def add(self, point): 
     r, c = point 
     self.lookup[r][c] = True 
     self.size += 1 

    def remove(self, point): 
     r, c = point 
     self.lookup[r][c] = False 
     self.size -= 1 

    def __contains__(self, point): 
     r, c = point 
     return 0 <= r < self.h and 0 <= c < self.w and self.lookup[r][c] 

    def __bool__(self): 
     return self.size != 0 

    def __len__(self): 
     return self.size 

# H, W = ... 
# pointset = PointSet(H, W) 
# if (3, 5) in pointset: 
# ... 

2回目の試行：

# pointset = set() 
# if (3, 5) in pointset: 
# ... 

第二のコードがかなり速く実行されます。それはなぜですか？

Answer 1

まず、あなたは__contains__メソッドの実装は二回（あなたはリストのリストを持っているので）、それぞれが0（1）複雑さを有する、および2つの連鎖の比較（0 <= r < self.hと0 <= c < self.w）を評価します__getitem__を呼び出すことを考慮しなければなりません;最悪の場合、andは最初のFalseでのみ短絡するため、すべての式が評価されます。前の行のiterable展開から来る追加のオーバーヘッドがあります。属性ルックアップからのマイナーな追加もあります。

セットのメンバーシップルックアップは単純な0（1）なので、あなたのコードがどうやってそれを打ち負かすかはわかりません。