RB樹插入順序靈敏度

鑑於整數I的間隔，一個RB樹R其具有從In獨特的元素和序列從In的S唯一元件，其值不是R，將插入S到的性能R根據S排序還是隨機排列而有所不同？答案如何根據|I|和n的相對大小而變化？RB樹插入順序靈敏度

鑑於S的元素不在R中，因此不清楚如何分析插入需要維護的不變量以及需要發生的重新平衡操作。 Ruby基準我運行的地方|I|比n大100倍，表明排序後的插入速度快了10％。

來源

2013-04-07 Sim

由於插入時RBT的平均和最壞情況的性能都是log（n），你期望的差異有多大？ – 2013-04-07 02:52:41

大O符號中的常數因子可能會有很大差異，然後硬件（即分支預測器）如何受到算法中特定數據流的影響。例如，處理排序數組的原因之一就是處理未排序數組的速度比處理未排序數組快得多的原因之一，該算法似乎不受輸入數據順序的影響。看到http://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-an-unsorted-array我沒有期望，但我很好奇，因此這個問題。 – Sim 2013-04-07 03:24:04

@AlexeyFrunze用我的基準進行調整以消除GC變異等因素後，我發現排序數據的性能提高了10 +％。 – Sim 2013-04-07 04:15:24

表現會有所不同。

在C樣品測試++（我知道，G ++的map基於紅黑樹，並用它）：

#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秒排序插入vs 5秒未排序插入。

來源

2013-04-07 04:21:38

我相信C++基準測試不僅僅是一個Ruby測試，因爲後臺發生的事情更少。 – Sim 2013-04-07 18:00:34

當然，性能各不相同;如果你插入2，然後1，然後3插入一個空的紅黑樹，你永遠不會執行旋轉;如果您插入1，然後是2，然後是3，則必須執行旋轉。

如果你只是想建立在最快的方式紅黑樹，對列表進行排序，圍在中間元素拆分它，從兩部分構建紅黑樹，使中間元素的父兩半。你在這裏沒有旋轉或其他惡作劇。

就像Alexey Frunze所說，它的變化不能超過一個小的常數因子。

來源

2013-04-07 03:01:02 tmyklebu

問題不在於任何兩個給定的插入序列是否可能具有不同的性能。答案顯然是肯定的。這也不關於如何建立一棵RB樹。問題是關於在具有唯一性限制的現有RB樹中的隨機插入序列。 – Sim 2013-04-07 03:29:04

@Sim：是的。我的意圖是給出一個具體的例子，其中排序的插入序列的性能很差，而所有隨機序列的三分之一相當好。 – tmyklebu 2013-04-07 03:50:33

RB樹插入順序靈敏度

回答

相關問題