【ITニュース解説】PWC 391 Median Boxes

このニュース記事は、プログラミングにおける二つの異なる課題と、それらを解決するための複数のアプローチについて解説している。一つ目は、ソート済み配列の中央値を求める課題、二つ目は、寸法が異なる箱を互いに入れ子にして積み重ねる最大の数を求める課題である。

最初の課題は「配列の中央値」だ。ここで求められるのは、二つの既にソートされた配列を結合し、その結果できた新しい配列の中央値を計算することだ。中央値とは、データを小さい順に並べたときにちょうど真ん中にくる値のことである。もしデータの個数が奇数なら、真ん中のただ一つの値が中央値となる。データの個数が偶数なら、真ん中の二つの値を取り出し、その平均を中央値とする。例えば、配列(2)と(4)を結合すると(2, 4)となり、偶数個なので真ん中の2と4の平均である3.0が中央値となる。

この課題にはいくつかの解決策が考えられる。 一つ目の方法は、与えられた二つの配列の全要素を一つの新しい配列にまとめ、その新しい配列を改めて完全にソートするという「単純な結合とソート」だ。ソート後、配列の要素数を調べて、奇数か偶数かに応じて中央値の計算を行う。もし要素が一つもなければ、中央値は存在しないためundefを返す。この方法は理解しやすいが、配列が非常に大きい場合、全体のソートに時間がかかる可能性がある。

二つ目の方法は、統計処理のための既存のプログラミングモジュールやライブラリを利用することだ。Perlを例に取ると、Statistics::Basic::MedianやStatistics::Descriptive、PDLといったモジュールがあり、これらにデータを渡すだけで中央値を計算してくれる機能が提供されている。これらのモジュールも内部的にはソート処理などを行うため、計算コストは発生するが、開発者は詳細なアルゴリズムを自分で実装する手間を省けるという利点がある。

三つ目の方法は、与えられた配列が「既にソートされている」という条件を最大限に活用する「効率的なマージ」だ。この方法では、二つのソート済み配列の先頭要素を比較し、小さい方を新しいマージ済み配列に追加していく。これを、中央値を見つけるのに必要な要素数（全体の長さの半分程度）に達するまで繰り返す。どちらかの配列が先に空になった場合は、残りの配列から必要な数の要素を順にマージ済み配列に追加する。これにより、配列全体をソートすることなく、中央値に必要な部分だけを効率的に抽出できるため、大規模なデータに対して高速な処理が期待できる。

これらの解決策のパフォーマンスを比較したベンチマーク結果では、意外なことに最初の「単純な結合とソート」が最も高速な結果を示した。これは、Perlのようなプログラミング言語が内部に持つソート機能が非常に高度に最適化されており、マージソートのような効率的なアルゴリズムをベースにしているためと考えられる。既に部分的にソートされたデータに対しては、組み込みのソート関数が非常に高速に動作することがあるのだ。

二つ目の課題は「箱の積み重ね」だ。これは、さまざまな寸法の箱が与えられたときに、それらを互いに入れ子にして積み重ねられる最大の箱の数を決定する問題である。箱が別の箱の中に収まるためには、内側の箱の幅と高さが、外側の箱の幅と高さの両方よりも小さくなければならない、という明確な条件がある。箱の回転や、一つの箱に複数の小さい箱を並べることは考慮しない。

この課題を解決するために、まず箱の寸法を管理しやすいようにBoxという専用のオブジェクトとして扱う方法が示されている。Boxクラスは幅と高さという二つの属性を持ち、最も重要な機能として、別の箱をその中に収めることができるか (canHold メソッド) を判定する。このメソッドは、引数として渡された箱の幅と高さが、自身の箱の幅と高さの両方よりも小さい場合に「収められる」と判断する。

メインの解決策は、この問題を「探索問題」として捉えることだ。これは、考えられるすべての積み重ね方を効率的に試していくことで、最適な解（最大の積み重ね数）を見つけ出すアプローチである。 まず、入力された箱の寸法ペアはすべてBoxオブジェクトに変換される。そして、最大の積み重ね数を示す変数（$biggest）を初期値1で設定する。

この探索は、「todoリスト」という考え方を用いて行われる。todoリストは、まだ調べていない積み重ねの候補を格納するリストだ。各候補は、これまでに積み重ねられた箱のリスト（「スタック」）と、現在のスタックの最後の箱にまだ収まる可能性のある残りの箱のリスト（「利用可能リスト」）のペアで構成される。 探索の最初は、どの箱も「一番外側の箱」（スタックの最初の箱）になる可能性があるため、それぞれの箱を最初の箱とした初期スタックを作成し、それに収まる箱を選んで利用可能リストと共にtodoリストに追加する。 todoリストは先入れ先出し（FIFO）方式で処理される。つまり、最初に追加された候補から順に調べていく。 候補を一つ取り出すたびに、現在のスタックの長さがこれまでの$biggestよりも大きければ$biggestを更新する。もし、利用可能リストが空であるか、現在のスタックの長さと利用可能リストの残りの要素数の合計が$biggest以下であれば、これ以上そのスタックから積み重ねを改善する見込みはないため、その候補の探索は打ち切る。 それ以外の場合、利用可能リストに残っているそれぞれの箱について、現在のスタックにその箱を追加した新しいスタックと、その新しい箱にさらに収まる箱（元の利用可能リストの中から選択）のリストを生成し、これを新しい候補としてtodoリストの末尾に追加する。 このプロセスをtodoリストが空になるまで繰り返すことで、最終的に$biggestに格納された値が、最大の積み重ね可能な箱の数となる。この探索アルゴリズムは、すべての可能性を網羅しつつ、途中で無駄な探索を省くことで効率的に最適な解を導き出す。