パーセンタイルの繰り返し計算のための高速アルゴリズム？

StackOverflow https://stackoverflow.com/questions/3738349

質問

アルゴリズムでは、計算する必要があります 75パーセンタイル 値を追加するたびにデータセットの。今、私はこれをやっています：

  1. 価値を取得します x
  2. 入れる x 背面の既にソートされた配列で
  3. スワップ x 配列がソートされるまでダウンします
  4. 位置にある要素を読んでください array[array.size * 3/4]

ポイント3はo（n）であり、残りはo（1）ですが、これはまだ非常に遅いです。特に配列が大きくなった場合です。これを最適化する方法はありますか？

アップデート

ニキータありがとう！私はC ++を使用しているので、これは実装が最も簡単なソリューションです。これがコードです：

template<class T>
class IterativePercentile {
public:
  /// Percentile has to be in range [0, 1(
  IterativePercentile(double percentile)
    : _percentile(percentile)
  { }

  // Adds a number in O(log(n))
  void add(const T& x) {
    if (_lower.empty() || x <= _lower.front()) {
      _lower.push_back(x);
      std::push_heap(_lower.begin(), _lower.end(), std::less<T>());
    } else {
      _upper.push_back(x);
      std::push_heap(_upper.begin(), _upper.end(), std::greater<T>());
    }

    unsigned size_lower = (unsigned)((_lower.size() + _upper.size()) * _percentile) + 1;
    if (_lower.size() > size_lower) {
      // lower to upper
      std::pop_heap(_lower.begin(), _lower.end(), std::less<T>());
      _upper.push_back(_lower.back());
      std::push_heap(_upper.begin(), _upper.end(), std::greater<T>());
      _lower.pop_back();
    } else if (_lower.size() < size_lower) {
      // upper to lower
      std::pop_heap(_upper.begin(), _upper.end(), std::greater<T>());
      _lower.push_back(_upper.back());
      std::push_heap(_lower.begin(), _lower.end(), std::less<T>());
      _upper.pop_back();
    }            
  }

  /// Access the percentile in O(1)
  const T& get() const {
    return _lower.front();
  }

  void clear() {
    _lower.clear();
    _upper.clear();
  }

private:
  double _percentile;
  std::vector<T> _lower;
  std::vector<T> _upper;
};
役に立ちましたか？

解決

2つでそれを行うことができます ヒープ. 。 「不自然な」解決策が少ないかどうかはわかりませんが、これは提供します O(logn) 時間の複雑さとヒープは、ほとんどのプログラミング言語の標準ライブラリにも含まれています。

最初のヒープ（ヒープA）には、最小の75％要素、別のヒープ（ヒープB） - 残り（最大25％）が含まれています。最初のものには、上部に最大の要素があり、2番目の要素 - 最小の要素があります。

  1. 要素の追加。

新しい要素があるかどうかを確認します x IS <= max(A). 。もしそうなら、それをヒープに追加します A, それ以外の場合 - ヒープへ B.
さて、追加した場合 x aを積み上げて大きくなりすぎて（要素の75％以上を保持します）、最大の要素を削除する必要があります A （o（logn））、ヒープB（o（logn））に追加します。
ヒープBが大きくなりすぎた場合も同様です。

  1. 「0.75中央値」を見つける

A（またはBから最小）から最大の要素を取得するだけです。ヒープの実装に応じて、o（logn）またはo（1）時間が必要です。

編集
として イルカ 注意するには、各nに対して各ヒープがどれだけ大きいかを正確に指定する必要があります（正確な答えが必要な場合）。たとえば、if size(A) = floor(n * 0.75) と size(B) したがって、残りはすべてです n > 0, array[array.size * 3/4] = min(B).

他のヒント

シンプルな 統計ツリーを注文します これには十分です。

このツリーのバランスの取れたバージョンは、O（logn）時間挿入/削除とランクごとのアクセスをサポートします。したがって、75％パーセンタイルだけでなく、コードを変更することなく、66％または50％または必要なものも取得できます。

頻繁に75％のパーセンタイルにアクセスしますが、頻繁に挿入するだけでは、挿入/削除操作中は常に75％パーセンタイル要素をキャッシュできます。

ほとんどの標準的な実装（JavaのTreemapなど）は、統計統計ツリーです。

バイナリ検索を使用して、O（log n）の正しい位置を見つけることができます。ただし、アレイをシフトアップするのはまだo（n）です。

これがJavaScriptソリューションです。ブラウザコンソールでコピーして動作します。 $scores スコアのリストが含まれています。 $percentile与える n-th percentile リストの。したがって、75パーセンタイルは76.8、99パーセンタイルは87.9です。

function get_percentile($percentile, $array) {
    $array = $array.sort();
    $index = ($percentile/100) * $array.length;
    if (Math.floor($index) === $index) {
         $result = ($array[$index-1] + $array[$index])/2;
    }
    else {
        $result = $array[Math.floor($index)];
    }
    return $result;
}

$scores = [22.3, 32.4, 12.1, 54.6, 76.8, 87.3, 54.6, 45.5, 87.9];

get_percentile(75, $scores);
get_percentile(90, $scores);

既知の値のセットがある場合、フォローは非常に高速になります。

データの最大値に等しい要素の数を持つ整数（バイトでさえも機能します）を作成します。たとえば、Tの最大値が100,000の場合、配列を作成します 

int[] index = new int[100000]; // 400kb

次のように、値のセット全体を反復します

for each (int t : set_of_values) {
  index[t]++;
}

// You can do a try catch on ArrayOutOfBounds just in case :)

次に、パーセンタイルを計算します

int sum = 0, i = 0;
while (sum < 0.9*set_of_values.length) {
  sum += index[i++];
}

return i;

値がこれらの制限を確認しない場合、アレイの代わりにTreeMapの使用を検討することもできます。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top