12

データのシーケンス（重複している可能性があります）が与えられた場合、固定サイズの移動ウィンドウは、データシーケンスの開始から各反復でウィンドウを移動し、（1）最も古いデータ要素がウィンドウから削除され、新しいデータ要素がウィンドウにプッシュされます（2）移動するたびにウィンドウ内のデータの中央値を見つけます。

次の投稿は役に立ちません。

ランダムシーケンスの中央値を効果的に見つける

Rの移動時間ウィンドウに基づいてデータを結合する

私の考え：

中央値を保持するために2つのヒープを使用します。ウィンドウの横で、最初の反復でウィンドウ内のデータを並べ替えます。最小ヒープは大きい部分を保持し、最大ヒープは小さい部分を保持します。ウィンドウに奇数のデータがある場合、最大ヒープは中央値を返します。それ以外の場合、2つのヒープの上位要素の算術平均は中央値です。

新しいデータがウィンドウにプッシュされたら、ヒープの1つから最も古いデータを削除し、新しいデータを最大ヒープと最小ヒープの上限と比較して、どのヒープにデータを配置するかを決定します。次に、最初の反復と同じように中央値を見つけます。

ただし、ヒープ内のデータ要素を見つける方法は問題です。ヒープは二分木であり、二分探索木ではありません。

O（n）またはO（n * lg m）でそれを解決することは可能ですか？ここで、mはウィンドウのサイズとスペースです：O（1）？

どんな助けでも本当にありがたいです。

ありがとう

4

5 に答える 5

12

O（n * lg m）は簡単です：

ウィンドウを2つに維持しますstd::set。1つは下半分用、もう1つは上半分用です。新しい要素の挿入にはO（lg m）の費用がかかり、古い要素の検索と削除には同じ費用がかかります。質問で説明した方法を使用して中央値を決定するには、O（1）のコストがかかります。

ウィンドウをシーケンス上でスライドさせながら、各反復でウィンドウから落ちるアイテム（O（lg m））を削除し、新しいアイテム（O（lg m））を挿入して、中央値（O（1））を計算します。 、結果として合計O（n lg m）になります。

もちろん、このソリューションはスペースO（m）を使用しますが、ウィンドウの内容を保存せずに逃げることはできないと思います。

于 2012-03-23T15:34:28.640 に答える
7

私はあなたがここで説明するアルゴリズムをほぼ正確に実装しました：http：//ideone.com/8VVEa、そしてそれをここで説明しました： Cでのローリング中央値-Turlachの実装

「最も古いものを見つける」問題を回避する方法は、値を循環バッファーに保持することです。そのため、常に最も古いものへのポインターがあります。ヒープに格納するのはバッファインデックスです。したがって、必要なスペースは2Mであり、各更新はO（lg M）です。

于 2012-03-23T17:09:57.690 に答える
1

hc_と同じ答えですが、ストックBSTを使用する代わりに、すべてのノードがそのサブツリー内の要素の数を持つバージョンを使用します。この方法で中央値を見つけるのはO（log（m））です。

于 2012-03-23T16:57:35.260 に答える
1

「Cでのローリング中央値」の質問に対してこの回答をしました

順序統計量を使用したc++データ構造の最新の実装が見つからなかったため、両方のアイデアをトップコーダーリンクに実装することになりました（編集の一致：FloatingMedianまでスクロールダウン）。

2つのマルチセット

最初のアイデアは、データを2つのデータ構造（ヒープ、マルチセットなど）に分割し、挿入/削除ごとにO（ln N）を使用するため、大きなコストをかけずに分位数を動的に変更することはできません。つまり、ローリング中央値、またはローリング75％を持つことができますが、同時に両方を持つことはできません。

セグメントツリー

2番目のアイデアは、挿入/削除/クエリにO（ln N）であるが、より柔軟なセグメントツリーを使用します。すべての「N」の中で最も良いのは、データ範囲のサイズです。したがって、ローリング中央値に100万アイテムのウィンドウがあり、データが1..65536から変化する場合、100万のローリングウィンドウの移動ごとに必要な操作は16回だけです。（そして、65536 * sizeof（counting_type）バイトのみが必要です（例：65536 * 4））。

GNU注文統計ツリー

諦める直前に、stdlibc++には順序統計ツリーが含まれていることがわかりました!!!

これらには2つの重要な操作があります。

iter = tree.find_by_order(value)
order = tree.order_of_key(value)

libstdc ++の手動policy_based_data_structures_testを参照してください（「分割して結合」を検索してください）。

c ++ 0x / c++11スタイルの部分的なtypedefをサポートするコンパイラの便利なヘッダーで使用するためにツリーをラップしました。

#if !defined(GNU_ORDER_STATISTIC_SET_H)
#define GNU_ORDER_STATISTIC_SET_H
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

// A red-black tree table storing ints and their order
// statistics. Note that since the tree uses
// tree_order_statistics_node_update as its update policy, then it
// includes its methods by_order and order_of_key.
template <typename T>
using t_order_statistic_set = __gnu_pbds::tree<
                                  T,
                                  __gnu_pbds::null_type,
                                  std::less<T>,
                                  __gnu_pbds::rb_tree_tag,
                                  // This policy updates nodes'  metadata for order statistics.
                                  __gnu_pbds::tree_order_statistics_node_update>;

#endif //GNU_ORDER_STATISTIC_SET_H
于 2012-06-27T14:45:42.870 に答える
0

カウントの度数分布を非常に効率的に照会できるようにするセグメントツリー（他の投稿を参照）を添付します。

これにより、次のデータ構造が実装されます。

|-------------------------------|
|---------------|---------------|
|-------|-------|-------|-------|
|---|---|---|---|---|---|---|---|
  0   1   2   3   4   5   6   7

各セグメントは、カバーする範囲内のカウントアイテムの数を保持します。1..Nからの値の範囲に2Nセグメントを使用します。これらは、上記の比喩的に示されているツリー形式ではなく、単一のロールアウトされたベクトルに配置されます。

したがって、1..65536から変化する整数のセットでローリング中央値を計算する場合、それらを格納するために必要なのは128kbだけであり、O（ln N）を使用して挿入/削除/クエリできます。ここでN=範囲のサイズです。 、つまり2**16操作。

データ範囲がローリングウィンドウよりもはるかに小さい場合、これは大きなメリットです。

#if !defined(SEGMENT_TREE_H)
#define SEGMENT_TREE_H
#include <cassert>
#include <array>
#include <algorithm>
#include <set>

#ifndef NDEBUG
#include <set>
#endif

template<typename COUNTS, unsigned BITS>
class t_segment_tree
{
    static const unsigned                       cnt_elements    = (1 << BITS);
    static const unsigned                       cnt_storage     = cnt_elements << 1;
    std::array<COUNTS, cnt_elements * 2 - 1>    counts;
    unsigned                                    count;

#ifndef NDEBUG
    std::multiset<unsigned>                     elements;
#endif
    public:

    //____________________________________________________________________________________

    //  constructor

    //____________________________________________________________________________________
    t_segment_tree(): count(0)
    {
        std::fill_n(counts.begin(), counts.size(),  0);
    }
    //~t_segment_tree();

    //____________________________________________________________________________________

    //  size

    //____________________________________________________________________________________
    unsigned size() const  { return count; }

    //____________________________________________________________________________________

    //  constructor

    //____________________________________________________________________________________
    void insert(unsigned x)
    {
#ifndef NDEBUG
        elements.insert(x);
        assert("...............This element is too large for the number of BITs!!..............." && cnt_elements > x);
#endif
        unsigned ii = x + cnt_elements;
        while (ii)
        {
            ++counts[ii - 1];
            ii >>= 1;
        }
        ++count;
    }

    //____________________________________________________________________________________

    //  erase 

    //      assumes erase is in the set
    //____________________________________________________________________________________
    void erase(unsigned x)
    {
#ifndef NDEBUG
        // if the assertion failed here, it means that x was never "insert"-ed in the first place
        assert("...............This element was not 'insert'-ed before it is being 'erase'-ed!!..............." && elements.count(x));
        elements.erase(elements.find(x));
#endif
        unsigned ii = x + cnt_elements;
        while (ii)
        {
            --counts[ii - 1];
            ii >>= 1;
        }
        --count;
    }

    // 
    //____________________________________________________________________________________

    //  kth element

    //____________________________________________________________________________________
    unsigned operator[](unsigned k)
    {
        assert("...............The kth element: k needs to be smaller than the number of elements!!..............." && k < size());
        unsigned ii = 1;
        while (ii < cnt_storage)
        {
            if (counts[ii - 1] <= k)
               k -= counts[ii++ - 1];
            ii <<= 1;
        }
        return (ii >> 1) - cnt_elements;
    }

};
#endif
于 2012-06-27T15:10:42.697 に答える