0

次のコードは、ベクトルのタイランクを計算するための関数(パフォーマンスクリティカル)です。

//The function here is to compute tied-ranks: answers.com/topic/tied-rank
mergeSort(x,inds,ci);
//mergeSort(): to sort vector x of length ci, also returns keys (inds) of x.

int tj=0;
double xi=x[0];

for (int j = 1; j < ci; ++j)
{
    if (x[j] > xi)
    {
        double rankvalue = 0.5 * (j - 1 + tj);

        for (int k = tj; k < j; ++k)
        {
            ranks[inds[k]] = rankvalue;
        };

        tj = j;
        xi = x[j];
    };      
};

double rankvalue = 0.5 * (ci - 1 + tj);

for (int k = tj; k < ci; ++k)
{
    ranks[inds[k]] = rankvalue;
};

問題は、想定されるパフォーマンスのボトルネックであるmergeSort()(O(NlogN))は、コードの他の部分(O(N))よりも数倍高速であり、他の部分との大幅な改善の余地があることを示唆しています。コード、アドバイスはありますか?

4

1 に答える 1

0

アルゴリズムは 2 次動作をしているようです: ifx[0]がシーケンス内の最大値のtjままで、内部的に反復0まで取得します。とciを使用するつもりでしたか?x[inds[0]]x[inds[j]]

于 2012-12-12T22:40:35.700 に答える