7

さまざまなサイズの何百ギガバイトものアセットがある場合、Blu-ray ディスクのセットを満たすための最適なアルゴリズムは何ですか?

多数の古い CDROM、DVD、および小型のハード ドライブを統合し、すべてを MD5 署名によってインデックス化されたデータベースに格納しようとしています。確かに大変な作業です。

私が現在行っていることは、アセット サイズ (通常はディレクトリ サイズ) を降順で並べ替え、塗りつぶしリストに最大のアセットを挿入し始め、アセットがなくなるまで収まらないものをスキップすることです。ほぼ瞬時に実行されますが、必要に応じて 1 回だけ一晩実行してもかまいません。

通常は 95% 以上の使用率が得られますが、他の組み合わせを使用して効率を高める方法があると確信しています。ディスク イメージのような巨大なアイテムの場合、この原始的な方法では使用率が非常に低くなります。

私の考えは、取得したアセットのすべての組み合わせ、1、2、3、... の項目を一度に取得し、合計する配列を指す最大バイト数 < 25,025,314,816 バイトの実行値を維持することです。一度に非常に多くのアセットを取得し、どの組み合わせも適合しないという点に到達したら、実行を停止して、実行中の最も高いカウンターが指す配列を使用します。

これは可能な限り最高のアルゴリズムですか？

Algorithm-Combinatorics と Math-Combinatorics の 2 つの Perl モジュールがタスクに適していると思われます。どちらがより速く、より安定しており、よりクールかについて何かアドバイスはありますか?

私の計画は、多数のディレクトリのサイズを計算するスクリプトを作成し、書き込む数十のディスクの最適な内容を表示することです。

また、同じディスク上にディレクトリ全体が必要なため、ファイルごとに入力するだけでは不十分です。

4

4 に答える 4

5

これは、ビン パッキングとして知られる NP 完全問題です。それを最適に解く既知の多項式時間アルゴリズムはありません。つまり、基本的にすべての解を試してみないと、最適解を見つけることができません。

プラス面としては、「空き容量のある最初のディスクに最大の残りのフォルダーを置く」などの非常に単純なヒューリスティックにより、最良の場合の 2 倍未満のディスクを使用することが保証されます。(問題のウィキペディアの記事で詳細を読むことができます)。

于 2012-07-27T01:21:00.240 に答える
2

このアルゴリズムは 1d ビン パッキングと呼ばれます。アルゴリズムは非常に高速ですが、最適ではありません。ブルート フォース アルゴリズムを使用することもできますが、検索スペースが非常に大きくなります。これは貪欲なアルゴリズムを使用したプログラムです: http://www.phpclasses.org/package/2027-PHP-Pack-files-without-exceeding-a-given-size-limit.html

于 2012-07-27T01:16:01.803 に答える
0

Blu-Ray ディスクを効率的にいっぱいにするために、私がまだ見つけた中で最も実用的な方法です。

書き込み可能なすべてのファイルへの完全修飾パスのリストを作成します。

次に、(任意に) 多数のディレクトリ レベルを検討するか、コマンド ライン オプションを受け入れるかを決定します。これは、同じようなアイテムでいっぱいのディレクトリを 1 つのブルーレイにまとめておくためです。最大のファイルを最初に挿入する STUFF オプションもあり、ファイルがオーバーフローを引き起こす場合は、ファイルまたはスペースがなくなるまで、次に小さいファイルを探します。

各ディレクトリをキーとして、そこに含まれるファイルの合計サイズをデータとしてハッシュを作成します。また、スラックスペースとディレクトリのオーバーヘッドが明らかに加算され、考慮する必要があるため、ディレクトリごとのファイル数を含む並列ハッシュを保持します。

マジック ナンバーとして 22 を選択します。ディレクトリが 22 個以下の場合は、すべての組み合わせを試して、25.025 GB に最も近く、25.025 GB を超えないものを見つけてください。22 を超える場合は、最大の 22 を使用してください。Perl モジュール Algorithm::Combinatorics を使用して、すべての組み合わせを見つけます。試行錯誤の結果、21 個のアイテムを組み合わせるのに数秒しかかからないことがわかりました。23 個のアイテムに何分もかかります。これは私の集中力を超えています。22 には約 35 秒かかります。

出力ディレクトリも受け入れられ、既存のデータがチェックされます。ファイルを移動するオプションがあります (コピー、サイズの確認、リンク解除)。

新しいハード ドライブを購入するたびに、通常、以前のハード ドライブの 2 倍の大きさになるので、すべてをコピーするだけでした。Nikon D800E (Extreme!)、HDR、パノラマで、ついにスペースがなくなりました。

私のプロジェクトは、15 年分の [ほとんどジャンク] の写真、ビデオ、映画、音楽などを特定し、整理し、統合することでした。およそ 12 個のストレージ デバイスのインベントリを作成し、MD5 署名を計算して、それらすべてをデータベースに入れました。私は、写真用とビデオ用のマスターとして 1 つのドライブを選択し、他のすべてを削除しました。あるものの8つのコピーを見つけました！

現在、約 10 TB の空きディスク容量があります!!!

誰かが興味を持っている場合に備えて、実際のすべての作業を行う関数の下。

============================================= おっと！次の理由により、回答を送信できませんでした:

Your post appears to contain code that is not properly formatted as code

ばかげた Web ページが、元のコードを台無しにしてしまいました。ごめん ：（..

于 2012-10-18T22:40:53.410 に答える
-2

「ナップサック」最適化問題のアルゴリズムを使用します。

http://en.wikipedia.org/wiki/Knapsack_problem

  1. ファイルサイズと等しくなるように重みを設定します
  2. 値を「重量」と等しくなるように設定します
  3. パックされる後続のすべてのディスクに対してアルゴリズムを実行します

これは最良の選択ではないかもしれません (必要なディスクの総数を最小化するのではなく、次のディスクのフィル ファクターを最大化します)。スプレッドシートでさえ) ウェブ上で。

于 2012-07-27T01:15:24.310 に答える