3

固定サイズのブロックの束で構成された大きなファイルがあるとします。これらの各ブロックには、いくつかの可変サイズのレコードが含まれています。各レコードは 1 つのブロック内に完全に収まる必要があり、定義上、そのようなレコードは完全なブロックより大きくなることはありません。時間の経過とともに、レコードがこの「データベース」に出入りするにつれて、これらのブロックにレコードが追加されたり、ブロックから削除されたりします。

ある時点で、特に多くのレコードがデータベースに追加され、いくつかが削除された後、ブロックの多くが部分的にしか埋められない場合があります。

このデータベース内のレコードをシャッフルして、部分的に満たされたブロックをより適切に埋めることにより、ファイルの末尾にある不要なブロックを圧縮するための適切なアルゴリズムは何ですか?

アルゴリズムの要件:

  • 圧縮は、元のファイルの代わりに発生する必要があり、その開始サイズからせいぜい数ブロック分以上ファイルを一時的に拡張する必要はありません。
  • アルゴリズムは、すでにほとんどがいっぱいになっているブロックを不必要に妨害してはなりません
  • ブロック全体を一度にファイルから読み書きする必要があり、書き込み操作は比較的高価であると想定する必要があります
  • レコードをあるブロックから別のブロックに移動する場合、操作が中断された場合に「失敗した」圧縮の結果としてレコードが失われないように、開始位置から削除する前に新しい場所に追加する必要があります。(このようなレコードの一時的な重複は、回復時に検出できると仮定します)。
  • この操作に使用できるメモリは、全体のファイル サイズの非常に小さな割合である、おそらく数ブロック程度です。
  • レコードが 10 バイトから 1K バイトのオーダーで、平均サイズがおそらく 100 バイトであると想定します。固定サイズのブロックは 4K または 8K のオーダーであり、ファイルは 1000 のブロックのオーダーです。
4

4 に答える 4

2

オンライン（1回のパスで最適化）の制限付きスペース（メモリ要件）のビンパッキングアルゴリズムの変更は、おそらくここで機能する可能性があります。

Coffman et al。による「ビンパッキング近似アルゴリズム：組み合わせ分析」を参照してください。

于 2008-09-25T08:10:08.807 に答える
2

これは、ビン パッキング問題のバリエーションのように聞こえますが、改善したい下位の割り当てが既にある場合です。したがって、ビンパッキング問題で成功するアプローチのバリエーションを検討することをお勧めします。

まず第一に、「十分に満たされている」(ブロックが触れたくないほど十分に満たされている) と「空っぽすぎる」(ブロックが空のスペースが多すぎるため、さらにレコードを追加する必要があります)。次に、すべてのブロックを十分に満たされている、空すぎる、または部分的に満たされている (十分に満たされておらず、空すぎていないブロック) として分類できます。次に、部分的にいっぱいのブロックの数を最小限に抑えながら、十分にいっぱいのブロックをできるだけ多く作成することによって、空すぎるブロックをすべて排除する方法として問題を再定義します。

また、レコードを可能な限り少ないブロックに入れるか、適切にパックするが読み取りおよび書き込みブロックの量を最小限に抑えることなど、より重要なことを検討する必要があります。

私のアプローチは、すべてのブロックに最初のパスを作成し、それらすべてを上で定義した 3 つのクラスのいずれかに分類することです。ブロックごとに、使用可能な空き領域も追跡する必要があります。空すぎるブロックについては、すべてのレコードとそのサイズのリストが必要です。次に、空すぎるブロックの最大のレコードから始めて、それらを部分的にいっぱいのブロックに移動します。読み取りと書き込みを最小限に抑えたい場合は、それらを現在メモリ内にあるブロックのいずれかに移動します。無駄なスペースを最小限に抑えたい場合は、必要に応じてブロックを読み取り、レコードを保持する空きスペースが最も少ないブロックを見つけます。レコードを保持するブロックがない場合は、新しいブロックを作成します。メモリ内のブロックが「十分にいっぱい」のしきい値に達した場合は、それを書き出します。

いくつかの詳細をスキップしましたが、これでいくつかのアイデアが得られるはずです。ビン パッキング問題はNP 困難であることに注意してください。つまり、実際のアプリケーションでは、自分にとって何が最も重要かを判断する必要があるため、適切な時間内にほぼ最適なソリューションを提供するアプローチを選択できます。

于 2008-09-24T22:54:37.580 に答える
2

これらのレコードに順序付けがない場合は、最後のブロックから抽出されたレコードを先頭からブロックに入力するだけです。これにより、データの移動が最小限に抑えられ、かなり単純になり、データをしっかりとパックする適切な仕事が行われるはずです。

例えば：

// records should be sorted by size in memory (probably in a balanced BST)
records = read last N blocks on disk;

foreach (block in blocks) // read from disk into memory
{
    if (block.hasBeenReadFrom())
    {
        // we read from this into records already
        // all remaining records are already in memory

        writeAllToNewBlocks(records);

        // this will leave some empty blocks on the disk that can either
        // be eliminated programmatically or left alone and filled during
        // normal operation

        foreach (record in records)
        {
            record.eraseFromOriginalLocation();
        }

        break;
    }

    while(!block.full())
    {
        moveRecords = new Array; // list of records we've moved

        size = block.availableSpace();
        record = records.extractBestFit(size);
        if (record == null)
        {
            break;
        }

        moveRecords.add(record);
        block.add(record);

        if (records.gettingLow())
        {
            records.readMoreFromDisk();
        }
    }

    if(moveRecords.size() > 0)
    {
        block.writeBackToDisk();
        foreach (record in moveRecords)
        {
            record.eraseFromOriginalLocation();
        }
    }
}

更新: メモリー内のみブロックなしのルールを維持することを怠りました。これを修正するために疑似コードを更新しました。ループ状態の不具合も修正しました。

于 2008-09-24T22:29:40.857 に答える
0

固定サイズのブロック内のレコードにはもう少し作業が必要になる場合がありますが、利用できる可能性があるアルゴリズムを次に示します。

限られた時間でのヒープの最適化

于 2008-09-25T00:35:22.253 に答える