时间戳

首页 > 解决方案 > 为什么相似的代码有不同的运行时和内存使用？

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

问题描述

我 使用递归在 leetcode 上解决了这个问题。我尝试了不同版本的解决方案，我发现运行时间和内存使用量随几个参数而变化。当我从 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 的空间。即使我的最终版本几乎与这个相似，这可能是什么原因。

 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 的额外副本，这可以理解。

标签： c++loopscompiler-optimization

解决方案

关键区别很可能是通过引用permute获取candidatesand向量。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)

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

推荐阅读