34

アルゴリズムでは、値を追加するたびにデータセットの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;
};
4

6 に答える 6

36

2つのヒープでそれを行うことができます。「工夫された」ソリューションが少ないかどうかはわかりませんが、これはO(logn)時間計算量を提供し、ヒープはほとんどのプログラミング言語の標準ライブラリにも含まれています。

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

  1. 要素を追加します。

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

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

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

編集Dolphin
が指摘した ように、nごとに各ヒープの大きさを正確に指定する必要があります（正確な答えが必要な場合）。たとえば、andが残りの場合、すべての、。size(A) = floor(n * 0.75)size(B)n > 0array[array.size * 3/4] = min(B)

于 2010-09-17T19:44:25.417 に答える
16

これには、単純な注文統計ツリーで十分です。

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

75％パーセンタイルに頻繁にアクセスするが、挿入頻度は低い場合は、挿入/削除操作中に75％パーセンタイル要素をいつでもキャッシュできます。

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

于 2010-09-17T23:05:46.870 に答える
3

おおよその答えでできる場合は、値全体をメモリに保持する代わりにヒストグラムを使用できます。

新しい値ごとに、適切なビンに追加します。ビンをトラバースし、人口サイズの75％に達するまでカウントを合計して、75パーセンタイルを計算します。パーセンタイル値は、ビン（停止した場所）の下限から上限までの値です。

これにより、O（B）の複雑さが提供されます。ここで、Bはビンの数、つまりですrange_size/bin_size。（bin_sizeユーザーケースに応じて適切に使用してください）。

このロジックをJVMライブラリに実装しました：https ：//github.com/IBM/HBPEこれを参照として使用できます。

于 2020-05-06T09:13:40.750 に答える
-2

二分探索を使用して、O（log n）内の正しい位置を見つけることができます。ただし、配列を上にシフトしてもO（n）です。

于 2010-09-17T19:29:17.190 に答える
-2

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

データの最大値に等しい要素数で整数の大きな配列を作成します（バイトでも機能します）。たとえば、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を使用することを検討することもできます。

于 2012-09-24T11:48:02.380 に答える
-2

これが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);
于 2016-02-03T06:58:13.080 に答える