私の以前の質問を読んだことがある人は、クイックソートとクイック選択、およびその他の基本的なアルゴリズムを理解して実装するという私の仕事について知っています。
Quickselect は、ソートされていないリストで k 番目に小さい要素を計算するために使用されます。この概念は、ソートされていないリストで中央値を見つけるためにも使用できます。
リストが変更されるたびに再計算する必要があるため、クイック選択は適切な選択ではないため、今回は、実行中の中央値を計算するための効率的な手法を考案するための支援が必要です。クイックセレクトは毎回再起動する必要があるため、以前に行われた計算を利用することはできません。そのため、(おそらく) 類似しているが、実行中の中央値の領域でより効率的な別のアルゴリズムを探しています。
ストリーミングの中央値は、2 つのヒープを使用して計算されます。現在の中央値以下の数値はすべて左側のヒープにあり、最大数がヒープのルートになるように配置されています。現在の中央値以上の数値はすべて右側のヒープにあり、最小数値がヒープのルートになるように配置されています。現在の中央値に等しい数値は、どちらのヒープにもあることに注意してください。2 つのヒープ内の数値の数の差が 1 を超えることはありません。
プロセスが開始されるとき、2 つのヒープは最初は空です。入力シーケンスの最初の数値がヒープの 1 つに追加されます。どのヒープでもかまいません。最初のストリーミング中央値として返されます。次に、入力シーケンスの 2 番目の数値がもう一方のヒープに追加されます。右側のヒープのルートが左側のヒープのルートより小さい場合、2 つのヒープが交換され、2 つの数値の平均が 2 番目のストリーミングとして返されます。中央値。
次に、メインのアルゴリズムが始まります。入力シーケンスの後続の各数値は現在の中央値と比較され、現在の中央値より小さい場合は左側のヒープに追加され、現在の中央値より大きい場合は右側のヒープに追加されます。入力数値が現在の中央値と等しい場合は、カウントが小さい方のヒープに追加されるか、カウントが同じ場合は任意のヒープに追加されます。これにより 2 つのヒープのカウントが 1 を超えて異なる場合は、大きい方のヒープのルートが削除され、小さい方のヒープに挿入されます。次に、現在の中央値は、カウントが異なる場合は大きい方のヒープのルートとして計算され、同じサイズの場合は 2 つのヒープのルートの平均として計算されます。
Scheme と Python のコードは私のブログで入手できます。
Jeff McClintock の実行中の中央値の推定。2 つの値のみを保持する必要があります。この例では、サンプリングされた値 (CPU 消費) の配列を反復処理します。中央値の推定値に比較的早く (約 100 サンプル) 収束するようです。アイデアは、各反復で、入力信号に向かって中央値インチが一定の割合であるということです。率は、中央値を推定する大きさによって異なります。中央値の大きさの推定値として平均を使用して、中央値の各増分のサイズを決定します。約 1% の精度の中央値が必要な場合は、0.01 * 平均のステップ サイズを使用します。
float median = 0.0f;
float average = 0.0f;
// for each sample
{
average += ( sample - average ) * 0.1f; // rough running average.
median += _copysign( average * 0.01, sample - median );
}
1 つの解決策は、順序統計ツリーを維持し、シーケンスの各要素を順番に挿入してから、ツリー内の要素の中央値を計算することです。
これには、挿入あたり O(lg n ) 時間、中央値あたり O(lg n ) 時間、合計 O( n lg n ) 時間と O( n ) スペースが必要です。
以下は、ソートされたリスト内のインデックスによってクエリを実行する機能を提供する C++ のバランスの取れたツリー構造です。すべての値がソートされた順序で維持されるため、これは 2 ヒープ アプローチほど効率的ではありませんが、追加の柔軟性が提供されます。たとえば、実行中の四分位数を与えることもできます。
template <typename T>
class Node
{
public:
T key;
Node* left;
Node* right;
size_t size;
Node(T k) : key(k)
{
isolate();
}
~Node()
{
delete(left);
delete(right);
}
void isolate()
{
left = NULL;
right = NULL;
size = 1;
}
void recount()
{
size = 1 + (left ? left->size : 0) + (right ? right->size : 0);
}
Node<T>* rotateLeft()
{
Node<T>* c = right;
Node<T>* gc = right->left;
right = gc;
c->left = this;
recount();
c->recount();
return c;
}
Node<T>* rotateRight()
{
Node<T>* c = left;
Node<T>* gc = left->right;
left = gc;
c->right = this;
recount();
c->recount();
return c;
}
Node<T>* balance()
{
size_t lcount = left ? left->size : 0;
size_t rcount = right ? right->size : 0;
if((lcount + 1) * 2 < (rcount + 1))
{
size_t lcount2 = right->left ? right->left->size : 0;
size_t rcount2 = right->right ? right->right->size : 0;
if(lcount2 > rcount2)
right = right->rotateRight();
return rotateLeft();
}
else if((rcount + 1) * 2 <= (lcount + 1))
{
size_t lcount2 = left->left ? left->left->size : 0;
size_t rcount2 = left->right ? left->right->size : 0;
if(lcount2 < rcount2)
left = left->rotateLeft();
return rotateRight();
}
else
{
recount();
return this;
}
}
Node<T>* insert(Node<T>* newNode)
{
if(newNode->key < key)
{
if(left)
left = left->insert(newNode);
else
left = newNode;
}
else
{
if(right)
right = right->insert(newNode);
else
right = newNode;
}
return balance();
}
Node<T>* get(size_t index)
{
size_t lcount = left ? left->size : 0;
if(index < lcount)
return left->get(index);
else if(index > lcount)
return right ? right->get(index - lcount - 1) : NULL;
else
return this;
}
Node<T>* find(T k, size_t start, size_t* outIndex)
{
if(k < key)
return left ? left->find(k, start, outIndex) : NULL;
else if(k > key)
return right ? right->find(k, left ? start + left->size + 1 : start + 1, outIndex) : NULL;
else
{
if(outIndex)
*outIndex = start + (left ? left->size : 0);
return this;
}
}
Node<T>* remove_by_index(size_t index, Node<T>** outNode)
{
size_t lcount = left ? left->size : 0;
if(index < lcount)
left = left->remove_by_index(index, outNode);
else if(index > lcount)
right = right->remove_by_index(index - lcount - 1, outNode);
else
{
*outNode = this;
size_t rcount = right ? right->size : 0;
if(lcount < rcount)
return left ? right->insert(left) : right;
else
return right ? left->insert(right) : left;
}
return balance();
}
Node<T>* remove_by_value(T k, Node<T>** outNode)
{
if(k < key)
{
if(!left)
throw "not found";
left = left->remove_by_value(k, outNode);
}
else if(k > key)
{
if(!right)
throw "not found";
right = right->remove_by_value(k, outNode);
}
else
{
*outNode = this;
size_t lcount = left ? left->size : 0;
size_t rcount = right ? right->size : 0;
if(lcount < rcount)
return left ? right->insert(left) : right;
else
return right ? left->insert(right) : left;
}
return balance();
}
};
template <typename T>
class MyReasonablyEfficientRunningSortedIndexedCollection
{
private:
Node<T>* root;
Node<T>* spare;
public:
MyReasonablyEfficientRunningSortedIndexedCollection() : root(NULL), spare(NULL)
{
}
~MyReasonablyEfficientRunningSortedIndexedCollection()
{
delete(root);
delete(spare);
}
void insert(T key)
{
if(spare)
spare->key = key;
else
spare = new Node<T>(key);
if(root)
root = root->insert(spare);
else
root = spare;
spare = NULL;
}
void drop_by_index(size_t index)
{
if(!root || index >= root->size)
throw "out of range";
delete(spare);
root = root->remove_by_index(index, &spare);
spare->isolate();
}
void drop_by_value(T key)
{
if(!root)
throw "out of range";
delete(spare);
root = root->remove_by_value(key, &spare);
spare->isolate();
}
T get(size_t index)
{
if(!root || index >= root->size)
throw "out of range";
return root->get(index)->key;
}
size_t find(T key)
{
size_t outIndex;
Node<T>* node = root ? root->find(key, 0, &outIndex) : NULL;
if(node)
return outIndex;
else
throw "not found";
}
size_t size()
{
return root ? root->size : 0;
}
};