c++ - 几乎相同的代码运行速度要慢得多

Question

我正在尝试解决这个问题:

Given a string array words, find the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.

https://leetcode.com/problems/maximum-product-of-word-lengths/

您可以为每个单词创建一个字符位图，以检查它们是否共享相同的字符，然后计算最大乘积。

我有两个几乎相同的方法，但第一个通过检查，而第二个太慢，你能理解为什么吗？

class Solution {
public:

    int maxProduct2(vector<string>& words) {
        int len = words.size();
        int *num = new int[len];
        // compute the bit O(n)
        for (int i = 0; i < len; i ++) {
            int k = 0;
            for (int j = 0; j < words[i].length(); j ++) {
                k = k | (1 <<(char)(words[i].at(j)));
            }
            num[i] = k;
        }
        int c = 0;
        // O(n^2)
        for (int i = 0; i < len - 1; i ++) {
            for (int j = i + 1; j < len; j ++) {
                if ((num[i] & num[j]) == 0) { // if no common letters
                    int x = words[i].length() * words[j].length();
                    if (x > c) {
                        c = x;
                    }
                }
            }
        }
        delete []num;
        return c;
    }

    int maxProduct(vector<string>& words) {
        vector<int> bitmap(words.size());
        for(int i=0;i<words.size();++i) {
            int k = 0;
            for(int j=0;j<words[i].length();++j) {
                 k |= 1 << (char)(words[i][j]);
            }
            bitmap[i] = k;
        }

        int maxProd = 0;
        for(int i=0;i<words.size()-1;++i) {
            for(int j=i+1;j<words.size();++j) {
                if ( !(bitmap[i] & bitmap[j])) {
                    int x = words[i].length() * words[j].length();
                    if ( x > maxProd  )
                        maxProd = x;
                }
            }
        }
        return maxProd;
    }
};

为什么第二个函数 (maxProduct) 对于 leetcode 来说太慢了？

解决方案

第二种方法重复调用 words.size()。如果你把它保存在一个 var 中，它就可以正常工作

Answer 1

由于我的评论被证明是正确的，我会将我的评论变成一个答案，并尝试解释我认为正在发生的事情。

我写了一些简单的代码来在我自己的机器上进行基准测试，每个解决方案有两个循环。唯一的区别是对 words.size() 的调用是在循环内而不是在循环外。第一个解决方案大约为 13.87 秒，而第二个解决方案为 16.65 秒。这不是很大，但速度慢了大约 20%。

尽管 vector.size() 是一个恒定时间操作，但这并不意味着它与检查寄存器中已有的变量一样快。常数时间仍然可以有很大的差异。当在加起来的嵌套循环中时。

可能发生的另一件事(比我聪明得多的人可能会插话并让我们知道)是您正在损害您的 CPU 优化，例如分支和流水线。每次到达循环的末尾时，它都必须停止，等待对 size() 的调用返回，然后根据该返回值检查循环变量。如果 cpu 可以向前看并猜测 j 仍然会小于 len 因为它没有看到 len 变化(len 甚至不在循环内!)它每次都可以做出很好的分支预测，而不必等待。