次のコードは、ベクトルのタイランクを計算するための関数(パフォーマンスクリティカル)です。
//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))よりも数倍高速であり、他の部分との大幅な改善の余地があることを示唆しています。コード、アドバイスはありますか?