最有效的计算词典索引的方法

Question

任何人都可以找到任何可能更有效的算法来完成以下任务吗？:

对于整数0到7的任何给定排列,返回按字典顺序描述排列的索引(从0开始索引,而不是1).

例如,

• 数组0 1 2 3 4 5 6 7应返回0的索引.
• 数组0 1 2 3 4 5 7 6应返回索引1.
• 数组0 1 2 3 4 6 5 7应返回索引2.
• 数组1 0 2 3 4 5 6 7应返回5039的索引(即7!-1或factorial(7)-1).
• 数组7 6 5 4 3 2 1 0应该返回40319的索引(即8!-1).这是最大可能的返回值.

我当前的代码如下所示:

int lexic_ix(int* A){
    int value = 0;
    for(int i=0 ; i<7 ; i++){
        int x = A[i];
        for(int j=0 ; j<i ; j++)
            if(A[j]<A[i]) x--;
        value += x*factorial(7-i);  // actual unrolled version doesn't have a function call
    }
    return value;
}

我想知道是否有任何方法可以通过删除内部循环减少操作次数,或者我是否可以以任何方式减少条件分支(除了展开 - 我的当前代码实际上是上述的展开版本),或者如果有任何聪明的按位黑客或肮脏的C技巧来帮助.

我已经尝试过更换了

if(A[j]<A[i]) x--;

同

x -= (A[j]<A[i]);

而且我也试过了

x = A[j]<A[i] ? x-1 : x;

两种替换实际上都导致了更差的性能.

在任何人说出之前 - 是的,这是一个巨大的性能瓶颈:目前大约61%的程序运行时花在了这个函数上,不,我不想有一个预先计算的值表.

除此之外,欢迎任何建议.

Answer 1

线性遍历已经在缓存中的内存实际上根本不需要太多时间。别担心。在 Factorial() 溢出之前，您不会遍历足够的距离。

将其8作为参数移出。

int factorial ( int input )
{
    return input ? input * factorial (input - 1) : 1;
}

int lexic_ix ( int* arr, int N )
{
    int output = 0;
    int fact = factorial (N);
    for ( int i = 0; i < N - 1; i++ )
    {
        int order = arr [ i ];
        for ( int j = 0; j < i; j++ )
            order -= arr [ j ] < arr [ i ];
        output += order * (fact /= N - i);
    }
    return output;
}

int main()
{
    int arr [ ] = { 11, 10, 9, 8, 7 , 6 , 5 , 4 , 3 , 2 , 1 , 0 };

    const int length = 12;
    for ( int i = 0; i < length; ++i )
        std::cout << lexic_ix ( arr + i, length - i  ) << std::endl;
}