DVDを最適に書き込むためのアルゴリズムは何ですか

Question

さまざまなサイズの資産が数百ギガバイトあるBlu-rayディスクのセットに最適なアルゴリズムは何ですか？

古いCDROMS、DVD、小型ハードドライブを多数集約し、すべてをMD5シグネチャでインデックスされたデータベースに格納しようとしています。確かに難しい課題。

現在、資産サイズ（通常はディレクトリサイズ）を降順に並べ替えることで、資産がなくなるまで、満たさないものをスキップして、最も大きなアセットを挿入リストに挿入します。ほとんど瞬時に実行されますが、必要ならば一晩中実行するのは大変です。

これは通常、95％以上の使用率を示しますが、他の組み合わせを使用して効率を上げる方法があると確信しています。ディスクイメージのような巨大なアイテムでは、私はこのプリミティブメソッドで非常に低い利用率を得ることができます。

考えてみたのは、一度に1つ、2つ、3つ、...という項目をすべて取り、最も高いバイト数の実行値を保持することです。< 25,025,314,816バイトは、それ。ある時点で非常に多くの資産を取り込んでいないという点に着くと、実行中の最高カウンタが指す配列を停止して使用してください。

これは最善のアルゴリズムですか？

アルゴリズム - コンビナトリアルと数学 - 組み合わせ論のような2つのPerlモジュールがあります。速い、より安定した、よりクールなアドバイスはありますか？

私の計画は、多数のディレクトリのサイズを計算し、焼くディスク数十枚の最適なコンテンツを表示するスクリプトを作成することです。

また、同じディスク上のディレクトリ全体を欲しいので、ファイル単位でファイルを埋めたいとは思っていません。

Answer 1

"ナップザック"最適化問題のアルゴリズムを使用してください。

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

2. 設定値が「重量」に等しくなるように、ファイルサイズと等しくなるように設定重量
3. 実行

を梱包するための後続のすべてのディスクのためのアルゴリズム

これは最良の選択ではないかもしれません（必要な総ディスク数を最小限に抑える代わりに、次のディスクのフィルファクタを最大にするでしょう）が、文書化されていて簡単に見つけることができますWeb上のあなたが選んだプログラミング言語（スプレッドシートも含む）のための作業コードです。

Answer 2

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

Answer 3

これはbin packingというNP完全な問題です。それを最適に解決する既知の多項式時間アルゴリズムはありません。つまり、基本的にすべてのソリューションを試すことなく、最適なソリューションを見つけることはできません。プラス側では

、のような非常に単純なヒューリスティック「部屋を持っている最初のディスク上の最大の残りのフォルダを置く」あなたが最良の場合の2倍のディスクよりも少ない使用することを保証します。 （問題のWikipediaの記事の詳細を読むことができます）。

Answer 4

私のBlu-rayディスクを効率的に埋め込むために最も実用的な方法を見つけました。

私は、使用可能なすべてのファイルの完全なパスのリストを作成します。

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

は、それがデータとして含まれるファイルのキーと合計サイズとして各ディレクトリとハッシュを確認します。また、スラックスペースとディレクトリオーバーヘッドが明らかに加算され、説明される必要があるため、ディレクトリごとのファイル数をパラレルハッシュにしておきます。

魔法の数字として22を選んでください。 < = 22のディレクトリがある場合は、すべての組み合わせを試して、 が25.025 GBに最も近いものであることを確認してください。あなたは22以上の場合は、最大の22を使用してください。私はPerlモジュールAlgorithm :: Combinatoricsを使ってすべての組み合わせを見つけます。試行錯誤の結果、私は21項目の組み合わせに数秒しかかからないと判断しました。 23項目は、私の注意スパンよりも長い分がかかる。 22は約35秒かかります。

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

私は新しいハードドライブを購入するたびに、それはので、私はすべてを少し超えるコピーする通常二回前のものと同じ大きさでした。ニコンD800E（Extreme！）、HDR、パノラマで、私は最終的にスペースを使い果たしました。

写真、ビデオ、映画、音楽などの15年分のユニークな雑草を集めてまとめることが私のプロジェクトでした。私はおよそ12の記憶装置を計算し、MD5シグネチャを計算してそれらをすべてデータベースに入れました。私は写真のためのマスターとビデオのための1つのドライブを選んで、他のすべてを噛んだ。私はいくつかのものの8つのコピーを見つけた！

私は現在約10 TBの空きディスク容量を持っています！誰もが興味を持っている場合に、実際の作業のすべてを行う機能以下

。

============================================== = おっと！あなたの答えは以下の理由で投稿できませんでした：

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

愚かなウェブページが私の元々のコードを改ざんしました。申し訳ありません:(..