为什么相似的代码有不同的运行时和内存使用？

Question

我使用递归解决了 leetcode 上的 this 问题。我尝试了不同版本的解决方案，发现运行时间和内存使用情况有几个不同 parameters.When 我从 for 循环切换到 while 循环，运行时间从 92 毫秒减少到 56 毫秒。我还使用了一个冗余的 else，当删除它时，运行时间从 56 毫秒进一步减少到 40 毫秒，内存使用保持不变。我看到其他解决方案比我的快得多，而且只使用了三分之一的内存。我的最终版本与我看到的几乎相似，但仍然慢了一倍。我的解决方案：

    class Solution {
public:
      static void solver(vector<int>candidates, int target, vector<int> path, int index, vector<vector<int>>&res){
          if(target == 0){
              if(find(res.begin(), res.end(), path) == res.end())
              res.push_back(path);
              return;
          }
          else if(target < 0){
              return;
          }
  
          else{

            //   both of these work!!! but for loop(92ms) is slower than while loop(56ms) memory usage being 28MB.
            // If I remove else further runtime would improve to 40ms

            //   for(int i = index; i< candidates.size() && target-candidates[i] >= 0; i++){
            //       path.push_back(candidates[i]);
            //       solver(candidates, target-candidates[i], path, i+1, res);
            //       path.pop_back();
            //   }

            while(index < candidates.size() && target-candidates[index] >= 0){
                path.push_back(candidates[index]);
                solver(candidates, target-candidates[index], path, index+1, res);
                index++;
                path.pop_back();
            }
          }
      }

      static vector<vector<int>> combinationSum2(vector<int>&candidates, int target){
          vector<vector<int>> res;
          vector<int> path;
          int index{0};
          sort(candidates.begin(), candidates.end());
          solver(candidates, target, path, index, res);
          return res;
      }


};

我找到的解决方案：它比上面的任何 hack 都快，它花费了 20 毫秒和 10.8MB 的 space。虽然我的最终版本与这个几乎相似，但可能是什么原因。

 vector<vector<int>> combinationSum2(vector<int>& candidates, int target) 
    {
         vector<vector<int>> sol;
         vector<int> v;
        sort(candidates.begin(),candidates.end());
         int i=0;
         permute(candidates,target,i,v,sol);
        return sol;
    }
    void permute(vector<int>& candidates,int target,int i,vector<int> &v,vector<vector<int>> &sol)
    {
        if(target==0)
        {
            if(find(sol.begin(),sol.end(),v)==sol.end())
                sol.push_back(v);
            return;
        }
        if(target<0)
            return;
        while(i<candidates.size() && target-candidates[i]>=0)
        {
            v.push_back(candidates[i]);
             permute(candidates,target-candidates[i],i+1,v,sol);
            i++;
             v.pop_back();
        }
    }

在for循环中会有一个变量i的额外副本，除此之外可以理解。

Answer 1

因为 LeetCode 的基准测量并不准确，你可以忽略这些数据。

这也将通过：

#include <cstdint>
#include <vector>
#include <algorithm>

struct Solution {
    std::vector<std::vector<int>> combinationSum(
                                   std::vector<int>& candidates,
                                   const int target
    ) {
        std::sort(std::begin(candidates), std::end(candidates));
        std::vector<std::vector<int>> combinations;
        std::vector<int> combination;
        depthFirstSearch(candidates, target, combinations, combination, 0);
        return combinations;
    }

private:
    void depthFirstSearch(
        std::vector<int>& candidates,
        int target,
        std::vector<std::vector<int>>& combinations,
        std::vector<int>& combination,
        std::size_t start
    ) {
        if (!target) {
            combinations.push_back(combination);
            return;
        }

        for (std::size_t i = start; i != std::size(candidates) && target >= candidates[i]; ++i) {
            combination.push_back(candidates[i]);
            depthFirstSearch(candidates, target - candidates[i], combinations, combination, i);
            combination.pop_back();
        }
    }
};

参考资料

有关其他详细信息，您可以在其中查看 Discussion Board. There are plenty of accepted solutions with a variety of languages and explanations, efficient algorithms, as well as asymptotic time/space complexity analysis^{1, 2}。

Answer 2

主要区别很可能是 permute 通过引用采用 candidates 和 path 向量。

void permute(vector<int>& candidates,int target,int i,vector<int> &v,vector<vector<int>> &sol)

另一方面，

solver 复制向量。

static void solver(vector<int>candidates, int target, vector<int> path, int index, vector<vector<int>>&res)

由于函数在递归中被重复调用，这会增加大量的内存和时间。

为什么相似的代码有不同的运行时和内存使用？

Why does similar code has different runtime and memory usage?

c++

loops

compiler-optimization

参考资料