c++ - 尝试减少执行时间但失败

Question

假设有一组点，几乎每个点都在一个四边形内。但有一些不是。我想知道哪些点不在四边形内。所以函数看起来像这样。

bool isInside(Point a, Point b, Point c, Point d, Point p) // a,b,c,d are the points consist of the quadrilateral.
{
    if(orientation(a, b, p) < 0)
        return false;
    else if(orientation(b, c, p) < 0)
        return false;
    else if(orientation(c, d, p) < 0)
        return false;
    else if(orientation(d, a, p) < 0)
        return false;
    else 
        return true;
}

我想减少调用方向函数的次数，方向函数看起来像。

int orientation(const Point& p, const Point& q, const Point& r)
{
  double val = (q.x - p.x) * (r.y - p.y) - (q.y - p.y) * (r.x - p.x);

  if (val == 0)
    return 0; // colinear
  return (val < 0) ? -1 : 1; // right or left
}

所以我这样修改了函数isInside。

bool isInside(Point a, Point b, Point c, Point d, Point p) 
{
    int result;

    if(p.x <= b.x)
    {
       result = orientation(a, b, p);
    }

    else
    {
      result = orientation(b, c, p);
    }

    if(result == -1) return false;

    if(p.x <= d.x)
    {
      result = orientation(a, d, p);
    }

    else
    {
       result = orientation(d, c, p);
    }

    return (result == -1) ? true : false;
}

这样，调用方向函数的次数减少了将近一半(如果超过100,000个点，那就是一个巨大的数字)。不过好像不影响用的时间，有时还用的多。我不知道为什么会这样，尽管它减少了很多函数调用。

Answer 1

编译器优化

检查您是否在启用优化的情况下进行构建是个好主意。如果您在 Debug模式下构建应用程序，编译器可能不会优化您的代码。如果是，请尝试以 Release模式运行。它可能会在启用优化或更高级别优化的情况下构建您的应用程序。这样，您就可以保留代码原样，而不必担心优化代码(除非绝对需要快速性能)。

定量结果

您还可以添加测试代码，这将允许您获得量化的性能结果(运行函数 x() n 次需要 m 秒，因此每次 x() 调用需要 m 除以 n 秒)。然后，您应该能够找出哪个代码块花费的时间最多。

如何执行上述操作的示例(无需为您编写)如下所示:

#include <iostream>
#include <chrono>

//Doesn't matter where it is called, just using main as an example
int main(int argc, char *argv[])
{
  int numRuns = 1000000; //Or passed in to allow changing # of runs
                         //without rebuilding: int numRuns = atoi(argv[1]);

  //Code to initialize Point a, b, c, d, and p.

  high_resolution_clock::time_point orien_start_time = high_resolution_clock::now();
  for(int i = 0; i < numRuns; ++i)
  {
    orientation(a, b, p); //Ignore the return value
  }
  high_resolution_clock::time_point orien_end_time = high_resolution_clock::now();

  high_resolution_clock::time_point orien_start_time = high_resolution_clock::now();
  for(int i = 0; i < numRuns; ++i)
  {
    isInside(a, b, c, d, p); //Ignore the return value
  }
  high_resolution_clock::time_point orien_end_time = high_resolution_clock::now();

  //Format and print/log the results
}

然后，根据这些时间点，您可以计算出每个函数运行需要多长时间。然后，您可以使用这些数字来查明您的应用程序到底在哪里变慢了。走这条路，你可以测试你的旧实现与你的新实现，看看新方法是否实际上更快。您甚至可以尝试不同的点集，看看这是否会改变应用程序性能(例如，用点 p1 到 p5 尝试两个函数，然后用 p6 到 p10 再试一次)。

注意:除了您编写的代码之外，还有很多因素会影响应用程序性能，这就是为什么我将一百万用于硬编码的 numRuns。如果您进行少量迭代，则每次函数调用的执行时间可能会大幅波动，具体取决于系统上运行的其他内容。对于收集定量结果，我的建议是在刚重新启动的系统上运行测试，您的应用程序是唯一运行的用户进程，这样它就不必与其他应用程序共享那么多资源。