7

データを DVD にアーカイブしていますが、DVD をフルパックしたいと考えています。DVD に入れたいすべてのファイルの名前とサイズはわかっていますが、メタデータがどのくらいの容量を占めているかわかりません。各 DVD にできるだけ多くのファイルを入れたいので、貪欲なビン パッキングを使用した Bubblesearch ヒューリスティックを使用しています。10,000 通りの選択肢を試して、最良の選択肢を見つけます。現在、すべてのファイルのサイズはわかっていますが、ファイルが ISO 9660 ファイルシステムにどのように格納されているかがわからないため、メタデータ用に多くのスロップを追加しています。スロープを減らしたいです。

遅すぎることを除いて、私は使用できgenisoimage -print-sizeました--- 500MB を占める 40,000 個のファイルを考えると、約 3 秒かかります。DVD 1 枚につき 8 時間かかるということはありません。以前にソースを変更したgenisoimageことがありますが、ソース コードからアルゴリズムを絞り出すことにあまり熱心ではありません。誰かが見積もりを取得するためのより良い方法を知っているか、役立つ仕様を教えてくれることを願っています.

問題と質問の明確化:

  • 複数の DVD に分割されたアーカイブを書き込む必要があり、通常は一度に 5 枚程度です。私が解決しようとしている問題は、各 DVD (最後を除く) ができるだけいっぱいになるように、各 DVD にどのファイルを配置するかを決定することです。この問題は NP 困難です。

  • 私は、標準の貪欲なパッキング アルゴリズムを使用しています。このアルゴリズムでは、最大のファイルを最初に配置し、十分なスペースがある最初の DVD に配置します。だからj_random_hacker、私は間違いなくランダムから始めていません. ソート済みから開始し、Bubblesearch を使用してファイルがパックされる順序を乱します。この手順により、パッキングが推定容量の約 80% から推定容量の 99.5% 以上に改善されます。この質問は、容量をより適切に見積もることに関するものです。現在、私の推定容量は実際の容量よりも低くなっています。

  • 私は 10,000 回の摂動を試みるプログラムを作成しました。それぞれの摂動には次の 2 つのステップが含まれます。

    1. ファイルのセットを選択
    2. これらのファイルが DVD で占める容量を見積もる

    ステップ2は私が改善しようとしているステップです。タイラー D が示唆するように、現在、私は「注意を怠っている」。しかし、私はもっとうまくやりたいです。genisomage -print-size遅すぎて使えない。同様に、ファイルをディスクに tar することはできません。これは単に速度が遅すぎるためですが、tar ファイルは ISO 9660 イメージと同じサイズではありません。これは、予測する必要がある ISO 9660 画像のサイズです。原則として、これは完全に正確に行うことができますが、その方法はわかりません。それが問題です。

注: これらのファイルは、3 TB のハード ドライブ ストレージを備えたマシン上にあります。いずれの場合も、ファイルの平均サイズは少なくとも 10MB です。場合によっては大幅に大きくなります。結局のところ、それは十分に高速になる可能性genisomageがありますが、私はそれを疑っています--- ISO イメージを /dev/null に書き込むことで機能するように見えます。 4.7GB。現在、または元の質問を投稿したとき、そのマシンにアクセスできません。夕方にアクセスできるときは、質問のより良い数字を取得しようとします. しかし、これが良い解決策になるとは思いませんgenisomageが、ファイルシステムがどのように機能するかを教えてくれるモデルを学ぶには良い方法かもしれません。ブロック サイズが 2KB であることは、すでに役に立ちます。

同じディレクトリ内のファイルが同じ DVD に書き込まれることを知っておくと、検索が簡単になる場合もあります。tar-before-burning を除外して、ファイルに直接アクセスしたい。(ほとんどのファイルはオーディオまたはビデオです。つまり、それらにgzip.

4

5 に答える 5

2

詳細な更新ありがとうございます。現在のビンパッキング戦略が非常に効率的であることに満足しています。

質問に関しては、「合計bバイトのn 個のファイルに対して ISO 9660 ファイルシステムがパックする正確なオーバーヘッドはどれくらいですか?」考えられる答えは 2 つだけです。

  1. 正確にこれを測定するための効率的なツールを誰かがすでに書いています。Google で簡単に検索しても何も見つかりませんでしたが、残念です。SO の誰かが自作ツールへのリンクで応答する可能性がありますが、数日間応答がない場合は、おそらくそれもアウトです。
  2. すぐに入手できる ISO 9660 仕様を読んで、そのようなツールを自分で作成する必要があります。

実際には、3 番目の答えがあります。

(3)各 DVDの最後のバイトをすべて使用することはあまり気にしません。その場合、サイズの異なる小さな代表的な一握りのファイル (たとえば 5) を取得し、それらが 2048 バイトの倍数になるまでそれらをパディングし、2^5 の可能なサブセットすべてをgenisoimage -print-size. 次に、式nx + y = iso_size - total_input_sizeをそのデータセットに当てはめます。ここで、n = 特定の実行のファイル数で、ファイルあたりのオーバーヘッドのバイト数であるxと、ファイルの一定量であるyを見つけます。オーバーヘッド (ファイルを含まない ISO 9660 ファイルシステムのサイズ)。xとyを丸めるその式を使用して、特定のファイルセットの ISO ファイルシステムのサイズを見積もります。安全のため、コレクション内のどこにでも現れる最長のファイル名をテスト ファイル名として使用し、それぞれをコレクション内の最も深い階層と同じ深さの別のディレクトリ階層に配置してください。

于 2009-01-22T15:54:18.100 に答える
2

あなたが現在これをどのように行っているのか正確にはわかりません-私のグーグルによると、「バブルサーチ」は、ある意味で貪欲な順序に近いアイテムの順序を選択する方法を指しますが、あなたの場合、ファイルを DVD に追加しても必要なスペースは変わらないため、この方法では複数の異なる注文が同じファイルセットになることを考慮すると時間が無駄になります。

つまり、次のようなことを行って候補ファイル リストを生成するとします。

  1. ファイルのリストをランダムにシャッフルします。
  2. リストの一番上から始めて、DVD に収まると思われるすべてのファイルを貪欲に選択します。

次に、解空間を非効率的に検索しています.n個のファイルの最終候補セットについては、潜在的にすべてのnを検討しています! そのセットの作り方。私のおすすめ：

  1. すべてのファイルをファイル サイズの降順に並べ替えます。
  2. 最上位 (最大) のファイルを「含まれている」とマークし、リストから削除します。(DVD に含まれている必要があるため、今すぐ含めることもできます。)
  3. (推定) ISO ファイルシステムのサイズが DVD の容量を超えることなく、リストの一番上のファイルを含めることができますか? もしそうなら：
    • 確率p (たとえば、 p = 0.5) で、ファイルを「含まれている」とマークします。
  4. リストから一番上のファイルを削除します。
  5. リストが空の場合は、ファイルの候補リストがあります。それ以外の場合は、3 に進みます。

これを何度も繰り返して、最適なファイル リストを選択します。

Tyler D の提案も良いです。合計 500Mb のファイルが 40000 個まである場合、平均ファイル サイズは 12.5Kb になります。ISO 9660 では 2Kb のブロック サイズが使用されます。つまり、これらのファイルは平均で 1Kb のディスク領域、またはサイズの約 8% を浪費しています。したがって、最初に tar でそれらを一緒にパックすると、約 8% のスペースが節約されます。

于 2009-01-22T07:28:19.620 に答える
1

tar を使用してファイルをディスクに保存できませんか? これを行うためのプログラムを作成しているのか、単にバックアップを作成しているのかは不明です。

たぶん、いくつかの実験を行い、注意を怠ってください-ディスク上の空き領域は問題ありません。

どういうわけか、あなたはすでにこれらを検討したか、または私の答えが要点を逃していると思います。

于 2009-01-22T06:39:45.253 に答える
1

私は最近、DVD で同様の充填見積もりを行う式を見つけるための実験を実行し、いくつかの仮定を考慮して単純な式を見つけました...元の投稿から、この式はおそらくあなたにとって低い数値になるでしょう。ディレクトリと長いファイル名。

仮定:

  • すべてのファイルは正確に 8.3 文字です。
  • すべてのファイルはルート ディレクトリにあります。
  • Joliet などの拡張機能はありません。

式：

174 + floor(count / 42) + sum( ceil(file_size / 2048) )
  • count はファイル数です
  • file_size は、各ファイルのバイト単位のサイズです
  • 結果は 2048 バイト ブロックになります。

スクリプト例:

#!/usr/bin/perl -w
use strict;
use POSIX;

sub sum {
    my $out = 0;
    for(@_) {
        $out += $_;
    }
    return $out;
}

my @sizes = ( 2048 ) x 1000;
my $file_count = @sizes;

my $data_size = sum(map { ceil($_ / 2048) } @sizes);
my $dir_size = floor( $file_count / 42 ) + 1;
my $overhead = 173;

my $size = $overhead + $dir_size + $data_size;

$\ = "\n";
print $size;

サイズが 200 バイトから 1 MiB の範囲で、最大 150k ファイルのディスクでこれを確認しました。

于 2009-06-02T17:59:38.910 に答える
0

いい考えですね、J.ランダム。もちろん、すべての最後のバイトを必要とするわけではありません。これは主に楽しみのためです (そして、昼食時に自慢する権利もあります)。CD-ROMに入力duして、4700000000 に非常に近づけたいと思っています。

私は ECMA 仕様を見ましたが、ほとんどの仕様と同様に中程度の苦痛であり、それを正しく行う能力に自信がありません. また、Rock Ridge エクステンションについては議論していないようです。

私はあなたのアイデア #3 が好きで、それをもう少し進めたいと思います。何が起こっているかについてかなり豊富なモデルを構築genisoimage -print-sizeし、いくつかのファイルセットで使用してモデルのパラメーターを推定します。次に、モデルを使用して見積もりを行うことができます。これは趣味のプロジェクトなので、しばらく時間がかかりますが、最終的にはうまくいきます。ここに回答を投稿して、どれだけの無駄が排除されたかを述べます!

于 2009-01-23T03:47:50.250 に答える