18

私はこの論文を理解しようとしています:線形時間での安定した最小スペースの分割。

主張の重要な部分は、

アルゴリズム Bは、サイズnのビット配列を O(nlog 2 n) 時間と一定の余分なスペースで安定してソートしますが、 O( n )回しか移動しません。

ただし、この論文ではアルゴリズムについては説明されておらず、私がアクセスできない別の論文を参照しているだけです。時間の範囲内で並べ替えを行う方法をいくつか見つけることができますが、一定以上のスペースを必要とせずに O(N) 移動を保証する方法を見つけるのに苦労しています。

このアルゴリズム B は何ですか? 言い換えれば、与えられた

boolean Predicate(Item* a);  //returns result of testing *a for some condition

Predicate を nlog 2 n回未満の呼び出しで Predicate をソートキーとして安定B(Item* a, size_t N);してソートし、 O(N) への書き込みのみを実行する関数はありますか?

4

3 に答える 3

5

それは不可能だと言いたくなる。O(n log n) の量の情報を計算しているが、(1) それを格納する場所 (一定のスペース) がなく、(2) すぐに使用する場所がない (O(n) が移動する) 場合はいつでも、何か奇妙なことが起こっています。スタックの大量使用を伴う可能性があります (これは、スペース分析に含まれるべきではありませんが、含まれない可能性があります)。

一時的な情報を 1 つの整数の多くのビット内に保存する場合、またはそのようなものを保存する場合は可能かもしれません。(つまり、実際には O(1) ですが、理論的には O(log n) です。)

基数の並べ替えでは、述語を呼び出して数字を作成する必要があるため、うまくいきません。比較の推移性を覚えていない場合は、O(n^2) 回呼び出すことになります。（しかし、メモ化するには、アイテムごとにO（log n）の償却スペースが必要だと思います。）

QED - 想像力の欠如による証明 :)

于 2011-03-29T21:11:42.083 に答える
2

これが私がこれまでに持っているものです。ビット配列を使用してパーティションテストの結果を保持し、その場で宛先を計算するサイクルソートのバージョン。これは、N個の比較、<N個のスワップ、および正確に2Nビットの割り当てられたストレージを備えた安定したバイナリパーティションを実行します。 

int getDest(int i, BitArray p, int nz)
{   bool b=BitArrayGet(p,i);
    int below = BitArrayCount1sBelow(p,i);  //1s below
    return (b)?(nz+below):i-below;
}

int BinaryCycleSort(Item* a, int n, BitArray p)
{
   int i, numZeros = n-BitArrayCount1sBelow(p,n);
   BitArray final = BitArrayNew(n);
   for (i=0;i<numZeros;i++)
      if (!BitArrayGet(final,i))
      {  int dest= GetDest(i,p,numZeros);
         while (dest!=i)                
         {  SwapItem(a+i,a+dest); 
            BitArraySet(final,dest);
            dest = getDest(dest,p,numZeros);
         }
         BitArraySet(final,dest);
      }
   return numZeros;
}

int BinaryPartition(Item* a, int n, Predicate pPred)
{ 
   int i;
   BitArray p = BitArrayNew(n);
   for (i=0;i<n;i++)
      if (pPred(a+i)) BitArraySet(p,i);
   return BinaryCycleSort(a,n,p);
}

これらのヘルパーの使用：

typedef uint32_t BitStore;
typedef BitStore* BitArray;
BitArray BitArrayNew(int N); //returns array of N bits, all cleared
void BitArraySet(BitArray ba, int i); //sets ba[i] to 1
bool BitArrayGet(BitArray ba, int i); //returns ba[i]
int BitArrayCount1sBelow(BitArray ba, int i) //counts 1s in ba[0..i)

明らかに、これは一定のスペースではありません。しかし、これは最終的な目標の構成要素として使用される可能性があると思います。配列全体は、Bビットの固定サイズのBitArrayを使用してN/Bブロックに分割できます。安定したマージを実行しながら、それらの同じビットを再利用する方法はありますか？

于 2011-03-30T07:52:15.370 に答える
0

基数ソートではありませんか？

O（kN）

于 2011-03-28T22:24:12.160 に答える