Pythonで最後に使用した要素を末尾へ移動するキューを設計するプログラム

整数 1 から n までの値で初期化されたキューを設計することを考えます。このキューには、引数で指定された位置にある要素を取り出し、キューの末尾へ移動する関数を実装します。この関数は何度も呼び出されることを想定しており、呼び出しごとに移動処理を実行したうえで、その時点でキューの末尾にある値を返します。

たとえば、n = 5 でキューを初期化すると、キューには 1 から 5 までの値が格納されます。ここで移動対象の位置として 5、2、3、1 がこの順で与えられた場合、出力は 5、2、4、1 になります。

解決のための手順

この問題は、リストをおよそ √n 個ずつのブロックに分割して管理する「平方分割(sqrt decomposition)」の考え方を用いることで効率的に解けます。手順は以下のとおりです。

• i := bisect_right(index, k) − 1(ソート済みの index の中で、ソート順を保ったまま k を挿入できる右側の位置から配列インデックスを求める)
• x := data[i] から (k − index[i]) 番目の要素を削除して取得する
• ii を i+1 から index のサイズまで繰り返す:index[ii] を 1 減らす
• data の最後のブロックの要素数が nn 以上の場合:data の末尾に新しい空リストを追加し、index の末尾に n を追加する
• x を data の末尾に追加する
• data[i] が空になった場合:data と index から i 番目の要素を削除する
• x を返す

実装例

理解を深めるために、次の実装を見てみましょう。

from bisect import bisect_right
from math import sqrt
class TestQueue:
    def __init__(self, n):
        self.n = n
        self.nn = int(sqrt(n))
        self.data = []
        self.index = []
        for i in range(1, n+1):
            ii = (i-1)//self.nn
            if ii == len(self.data):
                self.data.append([])
                self.index.append(i)
            self.data[-1].append(i)

    def solve(self, k):
        i = bisect_right(self.index, k)-1
        x = self.data[i].pop(k - self.index[i])
        for ii in range(i+1, len(self.index)):
            self.index[ii] -= 1
        if len(self.data[-1]) >= self.nn:
            self.data.append([])
            self.index.append(self.n)
        self.data[-1].append(x)
        if not self.data[i]:
            self.data.pop(i)
            self.index.pop(i)
        return x

queue = TestQueue(5)
print(queue.solve(5))
print(queue.solve(2))
print(queue.solve(3))
print(queue.solve(1))

入力

queue = TestQueue(5)
print(queue.solve(5))
print(queue.solve(2))
print(queue.solve(3))
print(queue.solve(1))

出力

5
2
4
1

動作の流れ

初期状態のキューは [1, 2, 3, 4, 5] です。各呼び出しでの変化を追うと次のようになります。

• solve(5):位置 5 の値「5」を末尾へ移動 → キューは [1, 2, 3, 4, 5] のまま、戻り値は 5
• solve(2):位置 2 の値「2」を末尾へ移動 → キューは [1, 3, 4, 5, 2]、戻り値は 2
• solve(3):位置 3 の値「4」を末尾へ移動 → キューは [1, 3, 5, 2, 4]、戻り値は 4
• solve(1):位置 1 の値「1」を末尾へ移動 → キューは [3, 5, 2, 4, 1]、戻り値は 1

このように、各ブロックの先頭位置を index リストに記録しておくことで、要素を削除した際には後続ブロックのインデックスを更新するだけで済みます。そのため、キュー全体を毎回走査し直す単純な実装よりも高速に処理でき、呼び出し回数が多いケースでも安定した性能を発揮します。