6

s のソートされていないリストがあるとしbucketます。(各バケットにはプロパティがあります。)バケットのリスト全体にできるだけ均等に分配しなければならないsize数量があるとします (つまり、最大値を最小限に抑えます)。Q

バケットが大きいサイズで並べ替えられている場合、解決策は明らかです。図に示すように、各バケットをたとえばbuckets[i]まで完全に満たしてからQ/(buckets.length-i) <= buckets[i]->size、残りのバケットを同じ量 で満たしQ/(buckets.length-i)ます。

バケツを充填します。

バケットがソートされていない場合、これを解決する最も効率的な方法は何ですか?

次のように反復することしか考えられません(疑似コード):

while Q > 0
    for i in 0..buckets.length-1
        q = Q/(buckets.length-i)
        if q > buckets[i]->size
            q = buckets[i]->size
        buckets[i]->fill(q)
        Q -= q

しかし、より良い方法があるかどうか、またはリストをソートする方が効率的かどうかはわかりません。

(私が直面している実際の問題はそれ以上のものです。たとえば、この「並べ替えられていない」リストは実際には別のプロパティ「ランク」によって並べ替えられており、数量が均等に分割されない場合にどのバケットが追加の塗りつぶしを取得するかを決定します。たとえば、並べ替えてから埋める方法を使用するには、バケット サイズとランクでリストを並べ替えますが、これに対する答えを知っていれば、残りを理解するのに役立ちます)。

4

6 に答える 6

3

多くの場合、データがソートされていれば解決策は「非常に単純」または「非常に効果的」ですが、ソートされていない場合は非常に複雑または効果的ではありません。最善の解決策は、最初にデータをソートしてから実行することです。シンプルで効果的なソリューションのために。これは、最初にデータをソートするオーバーヘッドがあることを意味しますが、ほとんどすべての目的に使用できる非常に優れたソートアルゴリズムがたくさんあり、多くの場合、「最初にデータをソートし、次に単純で効果的なアルゴリズムを適用する」という総オーバーヘッドがありますそれに」は、「データをソートせず、非常に複雑で効果のないアルゴリズムを適用する」よりもまだ低いです。

異なるキーで並べ替えられたデータが必要であるという事実は、ここでは 2 つのリストが必要であり、それぞれが異なる基準で並べ替えられていることを意味します。ここで数千のバケットについて話している場合を除き、2 番目のリストのメモリ オーバーヘッドは問題にならない可能性が高くなります (結局のところ、両方のリストにはバケット オブジェクトへのポインタしか含まれていないため、ポインタごとに 4/8 バイトを意味します。 32 ビットまたは 64 ビットのコードを使用している場合)。1つのリストにはサイズでソートされたバケットがあり、もう1つのリストには「ランク」でソートされたバケットがあります。質問で説明されているように新しいアイテムを追加するときは、「サイズでソートされたリスト」を使用し、「ランクでソートされた」リストを使用します今までと同じように使用できます。

于 2013-01-08T16:56:30.753 に答える
2

線形時間で可能かもしれないと思いますが、ある時点で立ち往生しています。多分あなたは問題を解決することができます、多分それはこの方法で解決することができません。

次のアルゴリズムを検討してください。

二分探索に基づいて、完全に満たされていない最小のバケットを見つけたいと思います。バケットのリストからそのようなバケットを見つけることは線形時間で可能かもしれませんが、私が言ったように、私はここで立ち往生しています。バケットが見つかったら、残りは簡単になります。小さいバケットはすべてサイズを合計し、配置するアイテムの総数から差し引いて、今見つけたバケット以上のバケットの数で割ります。 。

したがって、以下は問題を解決するための試みです。完全に満たされていない最小のバケツは何ですか？アルゴリズムはQuickSelectによって動機付けられています。

ピボットバケットを選択します。探しているバケットよりも小さいか大きいかを確認してください。（この手順は簡単です。）

  • 小さい場合は、これ以下のすべてのバケットのサイズを合計し、アイテムの総数からこの合計を差し引いて、すべての大きいバケットを含むセットで検索を続行します。

  • それが大きい場合は、同様のことを行う必要がありますが、ここで、これよりも大きいすべてのバケットに配置されているアイテムの数を差し引きます。これらのバケットに配置されるアイテムの数はわかりません。これが問題です...しかし、わかっていれば、すべての小さいバケットを含むセットで検索を続行します。

このアルゴリズムが機能した場合、ランダムピボット要素に対して予想される線形時間で実行されます（QuickSelectを参照）。

于 2013-01-08T17:05:19.570 に答える
2

q (合計が Q になるように各バケットを満たす適切な最小レベル) を決定できれば、線形解は明らかです。

for (bucket b : buckets)
{
    int f = max(b.capacity(), q);
    b.fill(f);
}

問題は、そのレベル q を決定することです。

q をバイナリ検索できます。min(b.capacity)つまり、q はとの間の整数であることがわかっていmax(b.capacity)ます。すなわち:

  1. q'min(capacity) と max(capacity) の中間の候補から始めます
  2. Q'使用した結果の合計金額を計算するバケットを渡しますq'
  3. if ( ) than半分に減らしてQ' > Q繰り返すq'
  4. もし ( ) より半分に増やしてQ' < Q繰り返すq'
  5. 戻るq = q'

ステップ 2 の各パスは O(N) であり、log(L) パスが存在します。L = max(capacity) - min(capacity)

これは、並べ替えよりもうまく機能します。L << N

十分な統計は、バケットをヒストグラムに減らすことです。

unordered_set<int,int> bucket_capacity;

for (bucket b : buckets)
    bucket_capacity[b.capacity]++;

これは依然として線形ですが、最悪の場合、バケットのサイズが異なる可能性があるため、あまり効果がありませんが、通過を制限するLため、効率は次のようになります。O(min(L,N) * logL)

これもまたL << N、効率が O(LlogL) になるとうまく機能します。

次のことは正しいと思いますが、100% ではありませんL >> N:線形解がないことを示すことができる場合。まず、線形解があると仮定します。次に、このソリューションをツールとして使用して、線形時間で比較ソートを行います。比較ソートは線形時間では不可能であることが示されているため、この仮定は間違っているに違いなく、線形解はありません。

于 2013-01-08T17:32:46.363 に答える
1

別のアイデアは次のようになります。バケットごとのアイテムの平均数を決定します。次に、すべてのバケットにその数を入力してみます（通常、すべてのバケットがその数のアイテムを保持できるわけではありません）。

その後、バケットに配置する残りのアイテムの数（前の反復ですべてが収まるわけではないため）と、現在含まれているよりも多くのアイテムを保持できるバケットのリスト（前の反復で計算）があります。

ここでも、配布されるアイテムの残りの数に基づいて、残りのバケットに配布されるアイテムの平均数を計算します。

すべてのアイテムを配置するまで繰り返します。

の実行時間を期待していますがO(n * log n)、分析しませんでした。並べ替えてから埋める方法と同じ実行時間ですが、バケットのサイズが限られている場合（小さいもの、大きいもの、大きいものなど）は短くなると予想されます。

于 2013-01-08T16:54:16.590 に答える
1

1 つのステップで、有限容量の n 個のソートされていないバケット、k 個の無限バケット (これらのリストではなく k を格納し、最初の反復では k=0)、および水の量 w から開始します。O(n) 時間で、定数 c < 1 に対して n' < c * n である n', k', w' を使用して、問題を別のインスタンスに縮小します。この手順を繰り返すと、問題が解決します (n n+c*n+c^2*n+...=O(n) の線形時間で、一定時間で解くことができます。

n 個の有限容量すべての中から、中央値を選択します (つまり、容量の半分が高く、半分が低くなるように 1 つを選択します)。これは O(n) 時間 (選択アルゴリズム) で実行できます。1) 低い容量と 2) 容量の中央値に高い容量のバケットの数 (無限のものを含む) を掛けた値の合計を計算します。

それが w より小さい場合は、バケットをより高く満たす必要があることがわかっているため、特に容量の小さいすべてのバケットが満たされます。それらを削除し、それらの容量の合計を w から削除すると、この反復 n'=n/2 は終了です。

一方、合計が w よりも大きい場合は、バケットの容量が中央値以上になることはありません。したがって、容量の大きいすべてのバケットを削除して、それらの数を無限バケットの数に追加できます。wは相変わらず。繰り返しますが、n'=n/2 で、これで完了です。

簡潔にするために、いくつかの簡単な詳細 (特に、多くのバケットの容量がまったく同じ場合の処理​​方法) は省略しています。また、適切な水のレベルがわかったら、最後にクリーンアップを行って、各「無限」(満杯でない) バケツに設定する必要があります。

于 2013-01-09T19:43:36.963 に答える
-1

バケットのリストをソートする必要があるのはなぜですか? バケットを 2 回反復するだけです。

初めてすべてのサイズを数えます。そのことから、「すべてのバケットに K 個のアイテムが必要です」と言うことができます。

2回目ですが、バケツをいっぱいにしてください。

于 2013-01-08T16:49:33.917 に答える