9

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

对于整数 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% 的程序运行时间都花在了这个函数上，不，我不想有一个预先计算值的表。

除此之外，欢迎提出任何建议。

4

4 回答 4

2

不知道这是否有帮助，但这是另一种解决方案：

int lexic_ix(int* A, int n){ //n = last index = number of digits - 1
    int value = 0;
    int x = 0;
    for(int i=0 ; i<n ; i++){
        int diff = (A[i] - x); //pb1
        if(diff > 0)
        {
            for(int j=0 ; j<i ; j++)//pb2
            {
                if(A[j]<A[i] && A[j] > x)
                {
                    if(A[j]==x+1)
                    {
                      x++;
                    }
                    diff--;
                }
            }
            value += diff;
        }
        else
        {
          x++;
        }
        value *= n - i;
    }
    return value;
}

我无法摆脱内部循环，因此在最坏的情况下复杂度为 o(n log(n))，但在最好的情况下为 o(n)，而您的解决方案总共为 o(n log(n))案例。

或者，您可以通过以下方式替换内部循环，以消除一些最坏的情况，但代价是内部循环中的另一个验证：

int j=0;
while(diff>1 && j<i)
{
  if(A[j]<A[i])
  {
    if(A[j]==x+1)
    {
      x++;
    }
    diff--;
  }
  j++;
}

说明：

（或者更确切地说“我是如何用那个代码结束的”，我认为它与你的没有什么不同，但它可以让你有想法，也许）（为了减少混淆，我使用字符而不是数字和只有四个字符）

abcd 0  = ((0 * 3 + 0) * 2 + 0) * 1 + 0
abdc 1  = ((0 * 3 + 0) * 2 + 1) * 1 + 0
acbd 2  = ((0 * 3 + 1) * 2 + 0) * 1 + 0
acdb 3  = ((0 * 3 + 1) * 2 + 1) * 1 + 0
adbc 4  = ((0 * 3 + 2) * 2 + 0) * 1 + 0
adcb 5  = ((0 * 3 + 2) * 2 + 1) * 1 + 0 //pb1
bacd 6  = ((1 * 3 + 0) * 2 + 0) * 1 + 0
badc 7  = ((1 * 3 + 0) * 2 + 1) * 1 + 0
bcad 8  = ((1 * 3 + 1) * 2 + 0) * 1 + 0 //First reflexion
bcda 9  = ((1 * 3 + 1) * 2 + 1) * 1 + 0
bdac 10 = ((1 * 3 + 2) * 2 + 0) * 1 + 0
bdca 11 = ((1 * 3 + 2) * 2 + 1) * 1 + 0
cabd 12 = ((2 * 3 + 0) * 2 + 0) * 1 + 0
cadb 13 = ((2 * 3 + 0) * 2 + 1) * 1 + 0
cbad 14 = ((2 * 3 + 1) * 2 + 0) * 1 + 0
cbda 15 = ((2 * 3 + 1) * 2 + 1) * 1 + 0 //pb2
cdab 16 = ((2 * 3 + 2) * 2 + 0) * 1 + 0
cdba 17 = ((2 * 3 + 2) * 2 + 1) * 1 + 0
[...]
dcba 23 = ((3 * 3 + 2) * 2 + 1) * 1 + 0

第一个“反思”：

熵的观点。abcd 的“熵”最少。如果一个角色在一个它“不应该”的地方，它就会产生熵，而熵越早变得最大。

例如，对于 bcad，词典索引为 8 = (( 1 * 3 + 1 ) * 2 + 0 ) * 1 + 0并且可以这样计算：

value = 0;
value += max(b - a, 0); // = 1; (a "should be" in the first place [to create the less possible entropy] but instead it is b)
value *= 3 - 0; //last index - current index
value += max(c - b, 0); // = 1; (b "should be" in the second place but instead it is c)
value *= 3 - 1;
value += max(a - c, 0); // = 0; (a "should have been" put earlier, so it does not create entropy to put it there)
value *= 3 - 2;
value += max(d - d, 0); // = 0;

请注意，最后一个操作总是什么都不做，这就是为什么“i

第一个问题（pb1）：

例如，对于 adcb，第一个逻辑不起作用（它导致 ((0* 3+ 2) * 2+ 0) * 1 = 4 的字典索引），因为 cd = 0 但它会创建熵来放置 c在 b 之前 因此，我添加了 x，它表示尚未放置的第一个数字/字符。对于 x，diff 不能为负数。对于 adcb，词典索引是 5 = (( 0 * 3 + 2 ) * 2 + 1 ) * 1 + 0 并且可以这样计算：

value = 0; x=0;
diff = a - a; // = 0; (a is in the right place)
diff == 0 => x++; //x=b now and we don't modify value
value *= 3 - 0; //last index - current index
diff = d - b; // = 2; (b "should be" there (it's x) but instead it is d)
diff > 0 => value += diff; //we add diff to value and we don't modify x
diff = c - b; // = 1; (b "should be" there but instead it is c) This is where it differs from the first reflexion
diff > 0 => value += diff;
value *= 3 - 2;

第二个问题（pb2）：

例如，对于 cbda，词典索引是 15 = ((2 * 3 + 1) * 2 + 1) * 1 + 0，但第一个反射给出：((2 * 3 + 0) * 2 + 1) * 1 + 0 = 13 并且 pb1 的解决方案给出 ((2 * 3 + 1) * 2 + 3) * 1 + 0 = 17。pb1 的解决方案不起作用，因为要放置的最后两个字符是 d 和 a，所以 d - “意味着” 1 而不是 3。我必须计算在该字符之前放置的字符，但在 x 之后，所以我必须添加一个内部循环。

把它们放在一起：

然后我意识到 pb1 只是 pb2 的一个特例，如果你删除 x，并且你只取 diff = A[i]，我们最终会得到你的解决方案的未嵌套版本（逐步计算阶乘，并且我的差异对应于你的 x）。

所以，基本上，我的“贡献”（我认为）是添加一个变量 x，它可以避免在 diff 等于 0 或 1 时执行内部循环，但代价是检查是否必须增加 x 并在需要时执行.

我还检查了是否必须在内部循环中增加 x (if(A[j]==x+1))，因为如果以 badce 为例，x 最后将是 b，因为 a 在 b 之后，而你将再次进入内循环，遇到c。如果在内循环中检查x，当遇到d时只能做内循环，但是x会更新为c，遇到c时不会进入内循环。您可以在不破坏程序的情况下删除此检查

使用替代版本和内部循环中的检查，它产生了 4 个不同的版本。带有检查的替代方法是您输入的内部循环越少，因此就“理论复杂性”而言，它是最好的，但就性能/操作数量而言，我不知道。

希望所有这些都有帮助（因为这个问题相当老了，而且我没有详细阅读所有答案）。如果没有，我仍然玩得很开心。对不起，很长的帖子。另外，我是 Stack Overflow 上的新手（作为成员），而不是母语人士，所以请保持友善，如果我做错了什么，请随时告诉我。

于 2016-01-07T13:14:00.930 回答
0

这是整个分析代码，我只在 Linux 中运行测试，代码使用 G++8.4 编译，带有 '-std=c++11 -O3' 编译器选项。公平地说，我稍微重写了你的代码，预先计算了 N！并将其传递给函数，但这似乎没有多大帮助。

N = 9（362,880 个排列）的性能分析是：

  • 持续时间为：34、30、25 毫秒
  • 持续时间为：34、30、25 毫秒
  • 持续时间为：33、30、25 毫秒

N=10（3,628,800 个排列）的性能分析是：

  • 持续时间为：345、335、275 毫秒
  • 持续时间为：348、334、275 毫秒
  • 持续时间为：345、335、275 毫秒

第一个数字是您的原始函数，第二个是重新编写的函数，得到 N！传入，最后一个数字是我的结果。置换生成函数非常原始，运行缓慢，但只要它生成所有置换作为测试数据集，就可以了。顺便说一句，这些测试是在运行 Ubuntu 14.04 的四核 3.1Ghz、4GBytes 桌面上运行的。

编辑：我忘记了第一个函数可能需要扩展 lexi_numbers 向量的因素，所以我在计时之前放了一个空调用。在此之后，时间是 333、334、275。

编辑：另一个可能影响性能的因素，我在我的代码中使用长整数，如果我将那些 2'long' 更改为 2'int'，运行时间将变为：334、333、264。

#include <iostream>
#include <vector>
#include <chrono>
using namespace std::chrono;

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 lexic_ix1(int* arr, int N, int N_fac)
{
    int output = 0;
    int fact = N_fac;
    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 lexic_ix2( int arr[], int N , int coeff_arr[])
{
    for ( int i = 0; i < N - 1; i++ )
    {
        int order = arr [ i ];
        for ( int j = 0; j < i; j++ )
            order -= arr [ j ] < arr [ i ];
        coeff_arr[i] = order;
    }
    long fac = 1;
    long sn = 0;
    for (int i = 1; i < N; ++i)
    {
        fac *= i;
        if (coeff_arr[N - 1 - i])
            sn += coeff_arr[N - 1 - i] * fac;
    }
    return sn;
}

std::vector<std::vector<int>> gen_permutation(const std::vector<int>& permu_base)
{
    if (permu_base.size() == 1)
        return std::vector<std::vector<int>>(1, std::vector<int>(1, permu_base[0]));

    std::vector<std::vector<int>> results;
    for (int i = 0; i < permu_base.size(); ++i)
    {
        int cur_int = permu_base[i];
        std::vector<int> cur_subseq = permu_base;
        cur_subseq.erase(cur_subseq.begin() + i);
        std::vector<std::vector<int>> temp = gen_permutation(cur_subseq);
        for (auto x : temp)
        {
            x.insert(x.begin(), cur_int);
            results.push_back(x);
        }
    }
    return results;
}

int main()
{
    #define N 10
    std::vector<int> arr;
    int buff_arr[N];
    const int length = N;
    int N_fac = factorial(N);
    for(int i=0; i<N; ++i)
        arr.push_back(N-i-1); // for N=10, arr is {9, 8, 7, 6, 5, 4, 3, 2, 1, 0}
    std::vector<std::vector<int>> all_permus = gen_permutation(arr);

    std::vector<int> lexi_numbers;
    // This call is not timed, only to expand the lexi_numbers vector 
    for (auto x : all_permus)
        lexi_numbers.push_back(lexic_ix2(&x[0], length, buff_arr));

    lexi_numbers.clear();
    auto t0 = high_resolution_clock::now();
    for (auto x : all_permus)
        lexi_numbers.push_back(lexic_ix(&x[0], length));
    auto t1 = high_resolution_clock::now();
    lexi_numbers.clear();
    auto t2 = high_resolution_clock::now();
    for (auto x : all_permus)
        lexi_numbers.push_back(lexic_ix1(&x[0], length, N_fac));
    auto t3 = high_resolution_clock::now();
    lexi_numbers.clear();
    auto t4 = high_resolution_clock::now();
    for (auto x : all_permus)
        lexi_numbers.push_back(lexic_ix2(&x[0], length, buff_arr));
    auto t5 = high_resolution_clock::now();

std::cout << std::endl << "Time durations are: " << duration_cast<milliseconds> \
    (t1 -t0).count() << ", " << duration_cast<milliseconds>(t3 - t2).count() << ", " \
        << duration_cast<milliseconds>(t5 - t4).count() <<" milliseconds" << std::endl;
    return 0;
}
于 2014-06-02T09:29:37.540 回答
0

比如说，对于 M 位序列排列，从您的代码中，您可以得到类似于：Am-1*(m-1) 的字典序 SN 公式！+ Am-2*(m-2)！+ ... + A0*(0)！，其中 Aj 的范围从 0 到 j。您可以从 A0*(0)!、A1*(1)!、...、Am-1 * (m-1)! 计算 SN，然后将它们相加（假设您的整数类型不溢出），所以你不需要递归和重复计算阶乘。SN 号是从 0 到 M!-1 的范围（因为 Sum(n*n!, n in 0,1, ...n) = (n+1)!-1）

如果您不递归计算阶乘，我想不出任何可以带来任何重大改进的东西。

抱歉发布代码有点晚了，我只是做了一些研究，发现这个： http : //swortham.blogspot.com.au/2011/10/how-much-faster-is-multiplication-than.html对这位作者来说，整数乘法可以比整数除法快 40 倍。浮点数虽然没有那么戏剧化，但这里是纯整数。

int lexic_ix ( int arr[], int N )
{
    // if this function will be called repeatedly, consider pass in this pointer as parameter
    std::unique_ptr<int[]> coeff_arr = std::make_unique<int[]>(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 ];
        coeff_arr[i] = order; // save this into coeff_arr for later multiplication
    }
    // 
    // There are 2 points about the following code:
    // 1). most modern processors have built-in multiplier, \
    //    and multiplication is much faster than division
    // 2). In your code, you are only the maximum permutation serial number,
    //     if you put in a random sequence, say, when length is 10, you put in
    //     a random sequence, say, {3, 7, 2, 9, 0, 1, 5, 8, 4, 6}; if you look into
    //     the coeff_arr[] in debugger, you can see that coeff_arr[] is:
    //     {3, 6, 2, 6, 0, 0, 1, 2, 0, 0}, the last number will always be zero anyway.
    //     so, you will have good chance to reduce many multiplications.
    //     I did not do any performance profiling, you could have a go, and it will be
    //     much appreciated if you could give some feedback about the result.
    //
    long fac = 1;
    long sn = 0;
    for (int i = 1; i < N; ++i) // start from 1, because coeff_arr[N-1] is always 0 
    {
        fac *= i;
        if (coeff_arr[N - 1 - i])
            sn += coeff_arr[N - 1 - i] * fac;
    }
    return sn;
}

int main()
{
    int arr [ ] = { 3, 7, 2, 9, 0, 1, 5, 8, 4, 6 }; // try this and check coeff_arr

    const int length = 10;
    std::cout << lexic_ix(arr, length ) << std::endl;
    return 0;
}
于 2014-05-31T02:58:36.450 回答
0

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

将8out 作为参数移出。

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;
}
于 2014-05-31T02:00:54.813 回答