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

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

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

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;

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

第一个问题(pb1):

例如，对于 adcb，第一个逻辑不起作用(它导致词典索引为 ((0* 3+ 2) * 2+ 0) * 1 = 4)因为 c-d = 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]，我们最终得到你的解决方案的未嵌套版本(阶乘计算一点点一点点，我的 diff 对应于你的 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 的新成员(作为成员)，不是母语人士，所以请保持友善，如果我做错了什么，请随时告诉我。