🔀 ランダムアクセスデータ構造

ランダムアクセスとは

ランダムアクセスとは、列の中の任意の要素に同じような時間でアクセスできるという性質、またはそのようなアクセスを行うことを指します。 どの要素にアクセスするかを指定するための値はインデックスと呼ばれます。

コマンドにおけるランダムアクセス

コマンドでは以下のようにListTagに対して定数のインデックスを指定して要素にアクセスすることができます。

# listの0番目にアクセスする
data get storage _ list[0]

しかし、この方法ではインデックスを変数にすることができません。 例えば、以下のようにスコアをインデックスとして使うことはできません。

scoreboard players set n _ 0
data get storage _ list[n _]

List-Mapped Trie

このようなスコアによるランダムアクセスを比較的効率良く実現するためのデータ構造の1つがList-Mapped Trie（LMT）です。 LMTを実現するために必要な部品として、マルチプレクサと呼ばれるデータ構造を導入します。 マルチプレクサは複数の要素のうち1つを単一のNBTパスで選択して取得できるデータ構造です。

平坦なマルチプレクサ

マルチプレクサを具体的に理解するために、単純なものを実装してみましょう。

# マルチプレクサを初期化
data modify storage _ mux set value ["off", "on"]

このマルチプレクサは"off"と"on"の2つの要素を持っています。 以下のコマンドを実行することでマルチプレクサが選択している要素を取得できます。

# 結果は"off"
data get storage _ mux[-2]

次に"on"を選択してみましょう。 マルチプレクサは単一のNBTパスで異なる要素を選択できる必要があるため、"on"の取得もmux[-2]で行える必要があります。 マルチプレクサの末尾に適当な要素を追加することでこれを実現できます。

data modify storage _ mux append value ""

これでマルチプレクサの状態は以下のようになります。

["off", "on", ""]

この状態で先程と同様のコマンドを実行すると、期待通り"on"が取得できます。

# 結果は"on"
data get storage _ mux[-2]

末尾に追加した要素を削除することで、マルチプレクサに再び"off"を選択させることができます。

# mux[-1]ではなくmux[2]にすることで、誤ってマルチプレクサの要素を削除しないようにする
data remove storage _ mux[2]

これでマルチプレクサの状態は以下のようになります。

["off", "on"]

この状態で先程と同様のコマンドを実行すると、期待通り"off"が取得できます。

# 結果は"off"
data get storage _ mux[-2]

完全な実装は以下のようになります。

#> init.mcfunction
scoreboard objectives add _ dummy
data modify storage _ mux set value ["off", "on"]

#> select.mcfunction
# マルチプレクサのインデックスを$00で指定
execute if score $00 _ matches 0 run data remove storage _ mux[2]
execute if score $00 _ matches 1 run data modify storage _ mux append value ""

#> example.mcfunction
# 初期化
function init

# 結果は"off"
data get storage _ mux[-2]

# 1番目を選択
scoreboard players set $00 _ 1
function select

# 結果は"on"
data get storage _ mux[-2]

# 0番目を選択
scoreboard players set $00 _ 0
function select

# 結果は"off"
data get storage _ mux[-2]

入れ子のマルチプレクサ

マルチプレクサは入れ子にすることで真価を発揮します。

「"A"と"B"を持つマルチプレクサAB」と「"C"と"D"を持つマルチプレクサCD」を持つマルチプレクサABCDを考えてみましょう。

# マルチプレクサを初期化
data modify storage _ mux set value ["A", "B"], ["C", "D"](/MCJE-Tech-Community/Datapack-WIki/wiki/"A",-"B"],-["C",-"D")

マルチプレクサABCDが最終的に選択している要素を取得するためのNBTパスは以下のようになります。

# 結果は"A"
data get storage _ mux[-2][-2]

最初の[-2]によって["A", "B"], ["C", "D"](/MCJE-Tech-Community/Datapack-WIki/wiki/"A",-"B"],-["C",-"D")の["A", "B"]が選択され、次の[-2]によって["A", "B"]の"A"が選択されます。

マルチプレクサABCDに最終的に"B"を選択させるためには、マルチプレクサABに"B"を選択させる必要があります。

data modify storage _ mux[-2] append value ""

これでマルチプレクサABCDの状態は以下のようになります。

[
  ["A", "B", ""],
  ["C", "D"]
]

# 結果は"B"
data get storage _ mux[-2][-2]

マルチプレクサABCDに最終的に"C"を選択させるためには、まずマルチプレクサABCDにCDを選択させる必要があります。

data modify storage _ mux append value []

これでマルチプレクサABCDの状態は以下のようになります。

[
  ["A", "B", ""],
  ["C", "D"],
  []
]

# 結果は"C"
data get storage _ mux[-2][-2]

マルチプレクサABCDに最終的に"D"を選択させるためには、マルチプレクサCDに"D"を選択させる必要があります。

data modify storage _ mux[-2] append value ""

これでマルチプレクサABCDの状態は以下のようになります。

[
  ["A", "B", ""],
  ["C", "D", ""],
  []
]

# 結果は"D"
data get storage _ mux[-2][-2]

マルチプレクサABCDやABやCDに適当な要素を追加・削除することで、単一のNBTパスmux[-2][-2]で全ての要素を取得できることが確認できました。

完全な実装は以下のようになります。

#> init.mcfunction
scoreboard objectives add _ dummy
data modify storage _ mux set value ["A", "B"], ["C", "D"](/MCJE-Tech-Community/Datapack-WIki/wiki/"A",-"B"],-["C",-"D")

#> select.mcfunction
# マルチプレクサABCDのインデックスを$00で指定
execute if score $00 _ matches 0 run data remove storage _ mux[2]
execute if score $00 _ matches 1 run data modify storage _ mux append value []

# マルチプレクサABもしくはCDのインデックスを$01で指定
#                                                          ↓ ここでmux[-2]を使うことで$00で指定された方のマルチプレクサにアクセスしている！
execute if score $01 _ matches 0 run data remove storage _ mux[-2][2]
execute if score $01 _ matches 1 run data modify storage _ mux[-2] append value ""

#> example.mcfunction
# 初期化
function init

# 結果は"A"
data get storage _ mux[-2][-2]

# Bを選択
scoreboard players set $00 _ 0
scoreboard players set $01 _ 1
function select

# 結果は"B"
data get storage _ mux[-2][-2]

# Cを選択
scoreboard players set $00 _ 1
scoreboard players set $01 _ 0
function select

# 結果は"C"
data get storage _ mux[-2][-2]

# Dを選択
scoreboard players set $00 _ 1
scoreboard players set $01 _ 1
function select

# 結果は"D"
data get storage _ mux[-2][-2]

# Aを選択
scoreboard players set $00 _ 0
scoreboard players set $01 _ 0
function select

# 結果は"A"
data get storage _ mux[-2][-2]

ところで、この入れ子のマルチプレクサの実装が既に長さ4のランダムアクセスデータ構造になっていることに気づいたでしょうか。 この実装では2重でしたが、マルチプレクサは好きなだけ入れ子にすることができます。 一般に$N$重にすると$2^N$個の要素を選択できるようになります。 つまり、長さ$2^N$のランダムアクセスデータ構造を実現できるということです。

ここまで来ればLMTを説明するのは非常に簡単です。LMTとは、単に入れ子になったマルチプレクサです。

計算量

$\log{N}$重に入れ子になった長さ$N$のLMTの$i$番目にアクセスする際の計算量について考えてみましょう。 $i$番目に向けて全ての入れ子になったマルチプレクサに正しい要素を選択させるには、$logN$個のマルチプレクサにアクセスする必要があります。 このとき、$k+1$番目のマルチプレクサにアクセスするためには、まず$k$番目のマルチプレクサにアクセスする必要があります。 さらに、最終的な要素にアクセスするためのNBTパスの長さは$\log{N}$になります。 つまり、計算量は次のようになります。

Θ((\sum_{k=1}^{\log{N}} k) + \log{N}) = Θ(\log^2{N})

よって、LMTのランダムアクセスの計算量は$Θ(\log^2{N})$です。

最適化

あるインデックス$i$でLMTに連続でアクセスする際、1回目のアクセスで$i$番目が選択された状態になるので、2回目以降のアクセスで再びLMTを更新する必要はありません。 そのため、最後のアクセスに使用したインデックス$i$を記録しておき、次にインデックス$j$でアクセスする際に$i \neq j$の場合にのみLMTを更新することで、LMTのランダムアクセスの最良計算量を最終的な要素にアクセスするコストだけの$Θ(\log{N})$にすることができます。