2

整数の間隔、からの一意の要素と、値が にない一連の一意の要素を持つIRB ツリーが与えられた場合、への挿入のパフォーマンスは、が並べ替えられているかランダムな順序であるかによって異なりますか? と の相対的なサイズに基づいて、答えはどのように変化しますか?RnISnIRSRS|I|n

Sの要素が含まれていないことを考えると、R挿入が維持する必要がある不変条件と、発生する必要があるリバランス操作を分析する方法が明確ではありません。私が実行した Ruby ベンチマークでは、|I|が 100 倍大きくn、ソートされた挿入が 10+% 高速に実行されることが示唆されています。

4

2 に答える 2

2

出来栄えが変わってきます。

mapC++ でのサンプル テスト (g++は赤黒木に基づいており、それを使用していることを知っています):

#include <iostream>
#include <map>
#include <cstdlib>
#include <ctime>

using namespace std;

const int N = 50000;
const int REPS = 100;
int ints[N];

int main()
{
  time_t t;
  srand(time(0));

  // fill ints[] with ints from 0 to N-1
  for (int i = 0; i < N; i++)
    ints[i] = i;

  // randomly shuffle ints[]
  for (int i = 0; i < N; i++)
  {
    int j = ((unsigned)rand() * rand()) % N;
    int t = ints[i];
    ints[i] = ints[j];
    ints[j] = t;
  }

  cout << "Inserting " << 2 * N << " sorted keys, repeating " << REPS << " times..." << endl;
  time(&t); cout << ctime(&t) << endl;
  for (int n = 0; n < REPS; n++)
  {
    map<int,int> m;
    for (int i = 0; i < N; i++)
      m[i] = i;
    for (int i = 0; i < N; i++)
      m[N + i] = i;
  }
  time(&t); cout << ctime(&t) << endl;

  cout << "Inserting " << N << " sorted keys and then " << N << " unsorted keys, repeating " << REPS << " times..." << endl;
  time(&t); cout << ctime(&t) << endl;
  for (int n = 0; n < REPS; n++)
  {
    map<int,int> m;
    for (int i = 0; i < N; i++)
      m[i] = i;
    for (int i = 0; i < N; i++)
      m[N + ints[i]] = i;
  }
  time(&t); cout << ctime(&t) << endl;

  return 0;
}

出力 ( liveworkspace ):

Inserting 100000 sorted keys, repeating 100 times...
Sun Apr 7 04:14:03 2013

Sun Apr 7 04:14:05 2013

Inserting 50000 sorted keys and then 50000 unsorted keys, repeating 100 times...
Sun Apr 7 04:14:05 2013

Sun Apr 7 04:14:10 2013

ご覧のとおり、パフォーマンスは著しく異なります。並べ替えられた挿入では 2 秒、並べ替えられていない挿入では 5 秒です。

于 2013-04-07T04:21:38.073 に答える
0

もちろん、パフォーマンスはさまざまです。空の赤黒ツリーに 2、次に 1、次に 3 を挿入すると、回転は実行されません。1、2、3 の順に挿入する場合は、ローテーションを実行する必要があります。

可能な限り迅速な方法で赤黒ツリーを構築したい場合は、リストをソートし、中央の要素で分割し、両方の半分から赤黒ツリーを構築し、中央の要素を 2 つの半分の親にします。ここではローテーションやその他の悪ふざけは行いません。

アレクセイ・フルンゼが言ったように、それは小さな一定の係数以上変化することはありません.

于 2013-04-07T03:01:02.177 に答える