Location : Home > Languages > Perl > Package Title : Algorithm::Bucketizer

名称

　Algorithm::Bucketizer - 決まったサイズのバケツにアイテムを詰め込む

概要

use Algorithm::Bucketizer;

# bucketizer を生成
my $bucketizer = Algorithm::Bucketizer->new(bucketsize => $size);

# アイテムを追加
$bucketizer->add_item($item, $size);

# 分配を最適化
$bucketizer->optimize(maxrounds => 100);

# 追加したときにバケツを追加
# （タイプは Algorithm::Bucketizer::Bucket）
my @buckets = $bucketizer->buckets();

# Algorithm::Bucketizer::Bucket メソッドを使ってバケツの中身を取得
my @items  = $bucket->items();
my $serial = $bucket->serial();

説明

　ハードディスクにMP3のファイルがたくさんあるとして、これをできるだけ余りスペースが小さくなるようCDに焼きたいとしよう。このときどう分配すればよいか？
　画像がフォルダにいっぱいあるとして、それぞれをあるサイズ以下にするにはどうしたらいいだろう？
　Algorithm::Bucketizer はこんなときに役に立つ。

　Algorithm::Bucketizer は定義された保持可能なトータルサイズを与えられ、動的に生成されたバケツ（bucket）にアイテムを分配していく。
　パラメータとしてアイテム（スカラでもオブジェクト参照でもよい）及びサイズをと一緒に $bucketizer->add_item() メソッドを呼び出すことでシステムにアイテムを追加することができる。bucketizer は可能であればどの既存のバケツにアイテムを格納すべきか決定し、もし十分な余地が無ければ（またはバケツがなければ）新たなバケツを生成し、それに格納する。
　全てのアイテムをシステムに追加した後、$bucketizer->items() メソッドで全てのバケツを繰り返し確認し、どれをどこに格納すべきかを決定する。

アルゴリズム

　現時点では Algorithm::Bucketizer には２つのアルゴリズム simple 及び retry が実装されている。

　simple モードでは到着順にアイテムを格納しようとするだけである。もし現在のバケツにアイテムが格納できればそこに入れる。もしできなければ次のバケツで試す。ひょっとしたら入るかも知れないけれども前のバケツに戻ることはない。このモードは元の順序が予約されている場合には有用である。

　retry モードでは新たなバケツで確認する前に、既存の各バケツにで確認する。様々なサイズの多くのアイテムがあれば retry モードは simple モードよりも少ないバケツで足りる。

　new() メソッドでアルゴリズムを選択する。

my $dumb = Algorithm::Bucketizer->new( algorithm => "simple" );
my $smart = Algorithm::Bucketizer->new( algorithm => "retry" );

　これらのアルゴリズムに加えて、必要なバケツを最小にしたければ Optimize をチェックする必要がある。

バケツの予備的充填

　既にバケツが存在している場合には、新たなアイテムを追加する前にアルゴリズムに教える必要がある。prefill_bucket() メソッドはまさにこれを行い、特定のバケツにアイテムを格納しておく。

$b->prefill_bucket($bucket_idx, $item, $itemsize);

　$bucket_idx はバケツのインデクスであり、0 から始まる。存在していないバケツは自動で追加される。予備充填の終了時に連続した値であることを確認する必要がある。

最適化

　いったん全てのアイテムが格納されれば、バケツの数を最小化し、バケツ全体にわたって配分を最適化することができる。
　しかしながら離散数のバケツに離散数のアイテムを最適に分配することは単純な作業ではない。これは「ビン詰め問題（bin-packing problem）」や「ナップザック問題（knapsack problem）と関係し、どちらもNP-完全である。
　Algorithm::Bucketize は他の方法では（未だ）得られない理想的な解を推定するために異なる最適化手法を提供している。現在では random と brute_force を実装している。

　random は時間またはラウンドの限界に達するまで分配をランダムに変換を試みる。

# 100ラウンドまで分配の改善をランダムに試みる
$b->optimize(algorithm => "random", maxrounds => 100);

# 60秒まで分配の改善をランダムに試みる
$b->optimize(algorithm => "random", maxtime => 60);

# brute_force ではあらゆる組み合わせを試みる
# 永遠にかかるかも知れないので注意
$b->optimize(algorithm => "brute_force",
maxtime => ..., 
maxrounds => ...,
);

　数学的に優秀な人からの示唆でもっとよい方法を評価中である :).

関数

my $b = Algorithm::Bucketizer->new(
    bucketsize => $size, 
    algorithm  => $algorithm 
);

　新しい Algorithm::Bucketizer オブジェクトを生成しそれへの参照を返す。
　bucketsize の名前−値という対は義務的である。これは個々のバケツにそれぞれサイズを設定する必要があるからである。デフォルトのサイズは100であるが、たいていの場合は変更される。
　algorithm はそのままおいておくことができる。デフォルトは simple である。もし retry で行いたければ retry と指定すること。（アルゴリズムを見よ。）
　他のオプションのパラメータとしては add_buckets を、詰め込み終了時にバケツを追加したいときに指定する。デフォルトは1であり、これを 0 に設定すると bucketizer は限定したバケツ数で処理を行う。通常は add_bucket の呼び出しで設定する。

$b->add_item($item_name, $item_size);

　指定されたアルゴリズムにしたがって指定した名前とサイズを持つバケツにアイテムを追加する。特定のバケツに格納したければ（例えば指定された順）、以下のように書く代わりに prefill_bucket() を用いる。
　成功時には Algorithm::Bucketizer::Bucket オブジェクトを返し、失敗時には（例えばバケツのサイズがアイテムのサイズよりも小さい、すなわちどうしようもなかったとき）には undef を返す。

my @buckets = $b->buckets();

　バケツの一覧を返す。以下のメソッドを用いることができる Algorithm::Bucketizer::Bucket タイプの要素を含んだリストである。

• my @items = $bucket->items();
  
  バケツ内のアイテムのリストを返す。バケツが空の場合は空のリストを返す。
• my $level = $bucket->level();
  バケツの充填度合いを返す。バケツ内の全アイテムのサイズの和である。
• my $bucket_index = $bucket->idx();
  バケツのインデクスを返す。最初のバケツのインデクスは 0 である。
• my $serial_number = $bucket->serial();
  バケツのシリアル番号を返す。これはバケツのインデクス＋１である。

$b->add_bucket(
    maxsize => $maxsize
);

　バケツを追加する。本メソッドは様々なサイズのバケツを用いる際に有効である。

$b->optimize(
    algorithm  => $algorithm,
    maxtime=> $seconds,
    maxrounds  => $number_of_rounds 
);

　バケツへの配分を最適化する。現在は random と brute_force が実装されている。双方（特に random では必ず）とも秒数（maxtime）または回数（(maxrounds）で制限されている。.

使用例

　100までの重みに耐えるバケツがあるとし、重みがそれぞれ 30, 31, 32, ... 39 の10アイテムがあったときにこれらをバケツに分配せよ。

use Algorithm::Bucketizer;

my $b = Algorithm::Bucketizer->new( bucketsize => 100 );
for my $i (1..10) {
    $b->add_item($i, 30+$i);
}

for my $bucket ($b->buckets()) {
    for my $item ($bucket->items()) {
        print "Bucket ", $bucket->serial(), ": Item $item\n";
    }
    print "\n";
}

　出力は以下の通り。

Bucket 1: Item 1
Bucket 1: Item 2
Bucket 1: Item 3

Bucket 2: Item 4
Bucket 2: Item 5

Bucket 3: Item 6
Bucket 3: Item 7

Bucket 4: Item 8
Bucket 4: Item 9

Bucket 5: Item 10

必要条件

　 brute_force メソッドを利用するなら Algorithm::Permute 0.04 が必要である。

著者

　Mike Schilli, <m@perlmeister.com>

著作権とライセンス

　Copyright 2002 by Mike Schilli

　本ライブラリはフリーソフトウェアであり、Perl 本体と同等の条件で修正／再配布してもよい。

Updated : 2007/05/18