-1

以下のことを聞かれました

There are X number of compressed files of different sizes in a single folder.
Where X is 1 to 250.
File size ranges from 1MB to 65MB. The compression ratio varies from 9 to 11.

There are Y number of parser threads. Where Y is between 1 to 8.

Write an application that distributes the files so each thread receives the same amount of data ( or as close as possible ).
Please follow all best coding practices and standards you are familiar with.

For example

If X is 5 and Y is 3 and the files are
File 1 is 1MB, File 2 is 2MB, File 3 is 3MB, File 4 = 4MB, File 5 = 5MB.

Uncompressed File 1,2,5 = compressed file * 9. Files 3,4 = compressed file * 10

Output
Thread <thread number> = Files <file number...> = <total size of all files uncompressed>
...
Data skew = ((max size - min size) / max size ) * 100

答えるのが不可能な質問だと思うのは正しいですか、それは非常に曖昧に思えます。これは 1 時間で答えるのが非常に難しい質問のように思えます。

分布は自明ではないと思います。

編集

問題について私が知っているのは、上記の内容だけです。

私には、それは非常に漠然とした質問に思えます。

4

1 に答える 1

0

したがって、私のコメントによると、これは従来のBin Packing Problemのインスタンスであると考えています。ただし、この場合は、事前にわかっている一連のビン (スレッド) の数があり、ビンが大きくなる可能性があります。計算オフ。Y個のアイテムで満たす必要があるX個のボックスがあると考えてください。ただし、ボックスは高くなる可能性があります。

まず、圧縮されていないファイルのサイズを前もって計算する必要があると思います。圧縮されていないファイルのサイズは、ビン パッキングの問題における「ボリューム」のようなものです。

次に、圧縮されていない値に基づいてファイルをソートすると思います。これにより、リストの検索が高速になります。

実際にそれらを分類するには、ビン パッキング問題でスレッドを「ビン」として扱います。それを行う方法はたくさんあると思いますが、特定のアプローチに落ち着く前に私が抱くであろう質問の 1 つは、次のようなものです。可能ですか、それとも結果のサイズをできるだけ近づけることに関心がありますか?割り当てられたスレッドよりも多くを使用することはできませんか?

問題がすべてのスレッドを使用している場合、私のアプローチは次のようになると思います。

  1. 最大のファイルから始めて、可能な限り最小になるようにビンを埋めます。最大のビン (最大のファイルを含むビン) を超えずにビンにそれ以上入れることができなくなるまで、これを続けます。
  2. 最小のアイテムを最小のビンに入れます。これがあなたの新しい「ウォーターマーク」です
  3. ステップ 1 と同様に、ウォーター マークを超えることなく、最大のファイルを受け入れる最大のビンに最大のファイルを配置し続けます。ファイルがなくなるか、それ以上入れられなくなるまで、これを続けます。前者の場合は完了、はしごの場合はステップ 2 に戻ります。

サイズを合わせることが懸念事項である場合、私のアプローチは多少異なります。

  1. 最大のアイテムを最小のビンに入れます。これがあなたの「ウォーターマーク」です。脇に置く
  2. 最小のビンをつかみます。これが作業中の現在のビンです。
  3. 「ウォーターマーク」を超えないように、作業中のビンに収まる次の最大のアイテムを見つけます。
  4. 現在のビンをいっぱいにできなくなるまで #3 を繰り返します
  5. 最小のファイルを最小のビンに入れます。これがあなたの新しい「ウォーターマーク」です
  6. ちょうど＃2に

ここでの利点は、常に「ビン」を可能な限り互いのサイズに近づけているため、非常に均等な分布が得られることです。問題は、ビンをすべて使い切るよりもビンのサイズに関係していることです。

于 2013-03-28T12:54:53.857 に答える