Pythonで実装するスナップショット配列（SnapshotArray）の解説

スナップショット配列とは

本記事では、指定されたインターフェースを満たす「スナップショット配列（SnapshotArray）」をPythonで実装する方法を解説します。このデータ構造は、以下の4つの操作をサポートする必要があります。

• SnapshotArray(int length)：指定された長さで配列状のデータ構造を初期化します。初期状態では、すべての要素が0です。
• set(index, val)：指定されたインデックスの要素を val に設定します。
• snap()：現在の配列全体のスナップショットを取得し、snap_id を返します。snap_id は snap() を呼び出した回数から1を引いた値です。
• get(index, snap_id)：指定された snap_id のスナップショットを取得した時点での、該当インデックスの値を返します。

動作例

例えば、サイズ2の配列に対して set(0, 5) を呼び出した後、snap() を実行すると 0 が返されます。続けて set(0, 6) を呼び出してから get(0, 0) を実行すると、スナップショット0時点の値である 5 が返されます。

解法のアプローチ

毎回 snap() を呼ぶたびに配列全体をコピーすると非効率です。そこで、各インデックスごとに「[スナップショットID, 値]」の履歴リストを持たせる方式を採用します。これにより、過去の任意の時点の値を二分探索で高速に取り出せます。

具体的な手順は以下の通りです。

1. 初期化（__init__）
   • current := 0（スナップショットのカウンタ）
   • arr := 長さ length + 1 のリスト。各要素は [[0, 0]] という二次元配列で初期化します。
2. set() メソッド
   • temp := arr[index] の最後の要素
   • もし temp[0] == current なら、arr[index] の最後の要素の値部分を val で上書きします（同じスナップショット内での更新のため）。
   • そうでなければ、arr[index] に [current, val] を追加します。
3. snap() メソッド
   • current を1増やし、current - 1 を返します。
4. get() メソッド
   • temp := arr[index]、low := 0、high := len(temp) - 1 とします。
   • low < high の間、以下を繰り返します。
     • mid := low + (high - low + 1) // 2
     • temp[mid][0] <= snap_id なら low := mid、そうでなければ high := mid - 1
   • 最後に temp[low][1] を返します。

この二分探索により、「指定された snap_id 以前で最も新しい記録」を効率よく特定できます。

Pythonでの実装例

それでは、実際のコードを見てみましょう。

class SnapshotArray(object):
   def __init__(self, length):
      self.current = 0
      self.arr = [[[0,0]] for i in range(length+1)]
   def set(self, index, val):
      temp = self.arr[index][-1]
      if temp[0] == self.current:
         self.arr[index][-1][1] = val
      else:
         self.arr[index].append([self.current,val])
   def snap(self):
      self.current+=1
      return self.current -1
   def get(self, index, snap_id):
      temp = self.arr[index]
      low = 0
      high = len(temp)-1
      while low < high:
         mid = low + (high - low+1 )//2
         if temp[mid][0]<=snap_id:
            low = mid
         else:
            high = mid -1
      return temp[low][1]
ob = SnapshotArray(3)
ob.set(0,5)
print(ob.snap())
ob.set(0,6)
print(ob.get(0,0))

入力

長さ3で配列を初期化し、set(0,5)、snap()、set(0,6)、get(0, 0) の順に呼び出します。

出力

0
5

まとめ

この実装では、snap() 操作がO(1)で完了する点が大きな特徴です。配列全体をコピーする代わりに、変更があった箇所だけ履歴として記録するため、スナップショット取得が頻繁なケースでも効率的に動作します。また、get() は二分探索により O(log n) の計算量で目的の値を取得できます。