Pythonでファイルシステムを設計する方法 ― createPathとget関数の実装

ここでは、次の2つの機能を持つファイルシステムを設計することを考えます。

1. createPath(path, value) ― 新しいパスを作成し、可能であればそのパスに値を関連付けてTrueを返します。パスがすでに存在する場合や、親パスが存在しない場合にはFalseを返します。
2. get(path) ― 指定されたパスに関連付けられた値を検索して返します。パスが存在しない場合は-1を返します。

パスの形式は、スラッシュ「/」に続けて1文字以上の小文字の英字が並んだ文字列を1つ以上連結したものです。たとえば「/programming」や「/programming/problems」は有効なパスですが、空文字列や「/」だけの文字列は無効です。ここでは、これら2つの関数を実装していきます。

入力例として、まずファイルシステムのオブジェクトを作成し、createPath('/a', 1)でパスを登録します。その後、引数'/a'を指定してget()を呼び出すと、出力は1になります。

解決のための手順

この問題を解くために、以下の手順に従います。

• マップ（辞書）d を定義する
• createPathメソッドはpathとvalueを受け取り、次のように動作する
• p := pathを「/」で分割した要素のリスト
• x := d
• iが1からpの長さ−1までの範囲でループ
  • p[i]がxに存在しない場合はFalseを返す
  • x := x[p[i]][1]
• pの最後の要素がxにすでに存在する場合はFalseを返す
• x[pの最後の要素] := 値vと空のマップからなるリストを設定する
• Trueを返す
• get()メソッドはpathを受け取り、次のように動作する
• x := d
• p := pathを「/」で分割した要素のリスト
• iが1からpの長さ−1までの範囲でループ
  • p[i]がxに存在しない場合は-1を返す
  • x := x[p[i]][1]
• pの最後の要素がxに存在すればx[pの最後の要素][0]を返し、そうでなければ-1を返す

Pythonでの実装例

以下の実装を見ると、より理解が深まるでしょう。

class FileSystem(object):
   def __init__(self):
      self.d = {}
   def create(self, p, v):
      p = p.split("/")
      x = self.d
      for i in range(1,len(p)-1):
         if p[i] not in x:
            return False
         x = x[p[i]][1]
      if p[-1] in x:
         return False
      x[p[-1]] = [v,{}]
      return True
   def get(self, p):
      x = self.d
      p = p.split("/")
      for i in range(1,len(p)-1):
         if p[i] not in x:
            return -1
         x= x[p[i]][1]
      if p[-1] in x:
         return x[p[-1]][0]
      else:
         return -1
ob = FileSystem()
print(ob.create("/a", 1))
print(ob.get("/a"))

入力

オブジェクトを初期化した後、createPath("/a", 1)とget("/a")を呼び出す

出力

True
1

仕組みの解説

この実装では、ネストした辞書構造を使ってトライ（接頭辞木）に似たデータ構造を構築しています。各ノードは「[値, 子ノードの辞書]」という形式のリストで表現され、パスの各セグメントが辞書のキーとして格納されます。これにより、パスの作成・取得のどちらも、パスのセグメント数に比例した時間で効率的に処理できます。また、親パスの存在チェックを自然に行えるため、不正なパスの登録も確実に防げるのがポイントです。