3

数字のリストの中央値を見つけるプログラムを作成しました。数値のリストは動的であり、数値を削除および挿入でき（重複する数値を入力できます）、この間に新しい中央値が再評価されて印刷されます。

マルチマップを使用してこのプログラムを作成したのは、

1）すでにソートされていることの利点、
2）簡単な挿入、削除、検索（multimapはバイナリ検索を実装しているため）
3）重複エントリが許可されます。

エントリ数+削除数（Nとして表される）の制約は次のとおりです。0<N<=100,000。

私が書いたプログラムは機能し、正しい中央値を出力しますが、十分な速度ではありません。unsorted_multimapはmultimapよりも高速であることは知っていますが、unsorted_multimapの問題は、並べ替える必要があることです。中央値を見つけるには、ソートされたリストが必要なので、ソートする必要があります。だから私の質問は、unsorted_multimapを使用してからエントリをすばやくソートするのが実用的でしょうか、それともばかげているだけでしょうか？ベクトルを使用し、ベクトルをクイックソートし、バイナリ検索を使用する方が速いでしょうか？あるいは、私が考えもしなかった素晴らしい解決策を忘れているのかもしれません。

私はC++に不慣れではありませんが、時間計算量に関する私のスキルはやや中核的であることを認めます。

自分の質問を見れば見るほど、データ構造は基本的にすでにベクトルを実装しているので、クイックソートと二分探索でベクトルを使用する方が良いと思い始めています。

4

5 に答える 5

5

私自身の質問を見れば見るほど、データ構造は基本的に既にベクターを実装しているため、クイックソートとバイナリ検索でベクターを使用する方が良いと考え始めています。

更新がほとんどない場合は、O(N) であるソートされていない std::vector + std::nth_elementアルゴリズムを使用します。O(N*ln(N)) である完全な並べ替えは必要ありません。

nth_element のライブデモ:

#include <algorithm>
#include <iterator>
#include <iostream>
#include <ostream>
#include <vector>

using namespace std;

template<typename RandomAccessIterator>
RandomAccessIterator median(RandomAccessIterator first,RandomAccessIterator last)
{
   RandomAccessIterator m = first + distance(first,last)/2; // handle even middle if needed
   nth_element(first,m,last);
   return m;
}

int main()
{
   vector<int> values = {5,1,2,4,3};
   cout << *median(begin(values),end(values)) << endl;
}

出力は次のとおりです。

3

多くの更新があり、途中からのみ削除する場合は、comocomocomomomo が示唆するように 2 つのヒープを使用します。fibonacci_heapを使用すると、O(N) が任意の位置から削除されます (ハンドルがない場合)。

多くの更新があり、任意の場所から O(ln(N)) を削除する必要がある場合は、ipc が提案するように 2 つのマルチセットを使用します。

于 2013-03-14T20:03:51.160 に答える
3

要素が挿入/削除されるときに、その場で中央値を追跡することが目的の場合は、最小ヒープと最大ヒープを使用する必要があります。それぞれに要素の半分が含まれます...数日前に関連する質問がありました：中央値ヒープを実装する方法

ただし、要素を削除するために特定の値を検索する必要がある場合でも、何らかのマップが必要です。

あなたはそれが遅いと言いました。中央値が必要になるたびに、マップの先頭から（N / 2）番目の要素まで繰り返しますか？あなたはする必要はありません。常に中央値を指すイテレーターと、中央値より少ない要素数のカウンターを維持することにより、中央値を追跡できます。挿入/削除するたびに、新しい/古い要素を中央値と比較し、イテレーターとカウンターの両方を更新します。

それを見る別の方法は、それぞれ半分の要素を含む2つのマルチマップとしてです。1つは中央値よりも小さい（または等しい）要素を保持し、もう1つはより大きな要素を保持します。ヒープはこれをより効率的に実行しますが、検索をサポートしていません。

中央値が数回だけ必要な場合は、「選択」アルゴリズムを使用できます。それはSedgewickの本に記述されています。平均してO（n）時間かかります。クイックソートに似ていますが、完全にはソートされません。最終的に、片側で小さいm個の要素（m =（n + 1）/ 2）が「選択」されるまで、ランダムなピボットで配列を分割するだけです。次に、これらのm個の要素のうち最大のものを検索します。これが中央値です。

于 2013-03-14T20:28:55.403 に答える
2 
Can any one help me what is Space and Time complexity of my following C# program with details.
//Passing Integer array to Find Extreme from that Integer Array
   public int extreme(int[] A)
        {
            int N = A.Length;
            if (N == 0)
            {
                return -1;
            }
            else
            {
                int average = CalculateAverage(A);
                return FindExtremes(A, average);
            }
        }
// Calaculate Average of integerArray
        private int CalculateAverage(int[] integerArray)
        {
            int sum = 0;
            foreach (int value in integerArray)
            {
                sum += value;
            }
            return Convert.ToInt32(sum / integerArray.Length);
        }
//Find Extreme from that Integer Array
        private int FindExtremes(int[] integerArray, int average) {
            int Index = -1; int ExtremeElement = integerArray[0];
            for (int i = 0; i < integerArray.Length; i++)
            {
                int absolute = Math.Abs(integerArray[i] - average);
                if (absolute > ExtremeElement)
                {
                    ExtremeElement = integerArray[i];
                    Index = i;
                }
            }
            return Index;
        }
于 2013-03-16T13:57:11.973 に答える
2

O(log N)更新ごとにそれを実装する方法は次のとおりです。

template <typename T>
class median_set {
public:
  std::multiset<T> below, above;

  // O(log N)
  void rebalance()
  {
    int diff = above.size() - below.size();
    if (diff > 0) {
      below.insert(*above.begin());
      above.erase(above.begin());
    } else if (diff < -1) {
      above.insert(*below.rbegin());
      below.erase(below.find(*below.rbegin()));
    }
  }

public:
  // O(1)
  bool empty() const { return below.empty() && above.empty(); }

  // O(1)
  T const& median() const
  {
    assert(!empty());
    return *below.rbegin();
  }

  // O(log N)
  void insert(T const& value)
  {
    if (!empty() && value > median())
      above.insert(value);
    else
      below.insert(value);
    rebalance();
  }

  // O(log N)
  void erase(T const& value)
  {
    if (value > median())
      above.erase(above.find(value));
    else
      below.erase(below.find(value));
    rebalance();
  }
};

(テストで実際に作業する)

アイデアは次のとおりです。

  • 中央値の上下の値を 2 セットで追跡する
  • 新しい値が追加された場合は、対応するセットに追加します。下のセットが他のセットより正確に 0 または 1 多いことを常に確認してください
  • 値が削除された場合は、セットから削除し、条件がまだ保持されていることを確認してください。

priority_queue1 つのアイテムを削除できないため、sは使用できません。

于 2013-03-14T20:33:37.733 に答える
1

ベクトルを使用する方がほぼ確実に優れています。中央値の計算の間に削除されるインデックスの補助ベクトルを維持して、バッチで削除できるようにする可能性があります。新しい追加は、補助ベクトルに入れて並べ替えてから、にマージすることもできます。

于 2013-03-14T20:00:01.123 に答える