可能影响功能所花时间的事情 [英] Things that can affect time taken by functions
问题描述
在前四个极端点内舍弃点数
找出剩余点中的下四个极端点。 (直到没有剩下的点,在代码中停止,当发现第二个四个极端点时)
这在两个方面。第一种方法:从点集中删除点数第二种方法:只保存剩余点数的索引从设置的点和使用索引为了找到下一个极端点。
我的问题是我测量了每个算法(firstAlgorithm和secondAlgorithm)所用的时间,如图所示在代码中,它似乎secondAlgorithm比第一个更少的时间。结果看起来像
算法1直到找到第二个公式为止的时间105181
算法2直到找到第二个公式为止的时间63047
然而,在main()函数中,我调用这两个函数并测量每个函数所花费的时间,结果为
#include< iostream>
#include< random>
#include< chrono>
#include< fstream>
#includePoint.h
bool isInside(Equads& eQuad,Point& p)
{
if(orientation(eQuad.extremePoints [0], eQuad.extremePoints [1],p)<0)
{
return false;
}
else if(orientation(eQuad.extremePoints [1],eQuad.extremePoints [2],p)<0)
{
return false;
}
else if(orientation(eQuad.extremePoints [2],eQuad.extremePoints [3],p)<0)
{
return false;
}
else if(orientation(eQuad.extremePoints [3],eQuad.extremePoints [0],p)<0)
{
return false;
}
else
{
return true;
}
}
void main()
{
std :: chrono :: high_resolution_clock :: time_point start;
std :: chrono :: high_resolution_clock :: time_point end;
start = std :: chrono :: high_resolution_clock :: now();
firstAlgorithm(points);
end = std :: chrono :: high_resolution_clock :: now();
std :: cout<< 第一算法的计算时间(微秒)<< chrono :: duration_cast< std :: chrono :: microseconds>(end - start).count()<<的std :: ENDL;
start = std :: chrono :: high_resolution_clock :: now();
secondAlgorithm(points);
end = std :: chrono :: high_resolution_clock :: now();
std :: cout<< 第二算法的计算时间(微秒)<< chrono :: duration_cast< std :: chrono :: microseconds>(end - start).count()<<的std :: ENDL;
}
计算firstAlgorithm的时间(微秒):107282
secondAlgorithm的计算时间(微秒):142401
在main()函数中花费时间时,secondAlgorithm如何变得如此缓慢?
以下是第一种方式的代码。
vector< Point> firstAlgorithm(vector< Point> originalPoint)
{
std :: chrono :: high_resolution_clock :: time_point startTime;
std :: chrono :: high_resolution_clock :: time_point endTime;
startTime = std :: chrono :: high_resolution_clock :: now();
vector< Point> points = originalPoints;
PointSequence结果;
包含firstEquad; // Equads是存储四个极值点的数组
findExtremePoints1(points,firstEquad);
必须prev;
prev = firstEquad;
std :: vector< Equads> eQuads;
包含当前值;
int count = 0;
while(findExtremePoints2(points,prev,current)!= false)
{
eQuads.push_back(current);
prev = current;
if(count == 0)break;
}
endTime = std :: chrono :: high_resolution_clock :: now();
std :: cout<< std :: endl<< 算法1所花费的时间,直到找到第二个等式< std :: chrono :: duration_cast< std :: chrono :: microseconds>(endTime - startTime).count()<<的std :: ENDL;
返回结果;
}
以及findExtremePoints1和findExtremePoints2如下所示
void findExtremePoints1(vector< Point& points,Equads& eQuad)
{
Point minX(points [0]),minY点[0]),maxX的(点[0]),MAXY(点[0]); (size_t i = 1; i< points.size(); i ++)
{
if(points [i] .x< minX.x)
{
minX = points [i];
}
if(points [i] .x> maxX.x)
{
maxX = points [i];
}
if(points [i] .y< minY.y)
{
minY = points [i];
}
if(points [i] .y> maxY.y)
{
maxY = points [i];
}
}
eQuad.extremePoints [0] = minX;
eQuad.extremePoints [1] = minY;
eQuad.extremePoints [2] = maxX;
eQuad.extremePoints [3] = maxY;
//擦除极值点
points.erase(remove(points.begin(),points.end(),eQuad.extremePoints [0]),points.end()) ;
points.erase(删除(points.begin(),points.end(),eQuad.extremePoints [1]),points.end());
points.erase(删除(points.begin(),points.end(),eQuad.extremePoints [2]),points.end());
points.erase(删除(points.begin(),points.end(),eQuad.extremePoints [3]),points.end());
}
//遍历这些点,如果任何点位于先前的公式中(四个极端点)
//然后将它从点集中删除,如果不在里面找到下一个四个极端点。
bool findExtremePoints2(vector< Point> points,Equads& prevEquad,Equads& eQuad)
{
Point minX,minY,maxX,maxY;
bool prevFound = false;
std :: vector< size_t> deletedVal;
for(size_t i = 0; i< points.size(); i ++)
{
if(isInside(prevEquad,points [i]))
{
deletedVal.push_back(i);
}
else
{
if(prevFound)
{
if(points [i] .x< minX.x)
{
minX = points [i];
}
if(points [i] .x> maxX.x)
{
maxX = points [i];
}
if(points [i] .y< minY.y)
{
minY = points [i];
}
if(points [i] .y> maxY.y)
{
maxY = points [i];
}
}
else //不在prev equad和第一个里面。只有在第一时间才符合这个条件。
{
minX = points [i];
minY = points [i];
maxX = points [i];
maxY = points [i];
prevFound = true;
if(prevFound == false)
{
return false;
}
eQuad.extremePoints [0] = minX;
eQuad.extremePoints [1] = minY;
eQuad.extremePoints [2] = maxX;
eQuad.extremePoints [3] = maxY;
$ b $ for(size_t i = deletedVal.size(); i--> 0;)
{
points [deletedVal.at(i)] = points.back();
points.pop_back();
}
//擦除极值点
points.erase(remove(points.begin(),points.end(),eQuad.extremePoints [0]),points 。结束());
points.erase(删除(points.begin(),points.end(),eQuad.extremePoints [1]),points.end());
points.erase(删除(points.begin(),points.end(),eQuad.extremePoints [2]),points.end());
points.erase(删除(points.begin(),points.end(),eQuad.extremePoints [3]),points.end());
返回prevFound;
}
以下是第二种方式的代码。
vector< Point> secondAlgorithm(vector< Point> points)
{
std :: chrono :: high_resolution_clock :: time_point startTime;
std :: chrono :: high_resolution_clock :: time_point endTime;
startTime = std :: chrono :: high_resolution_clock :: now();
vector< Point>结果;
std :: vector< Equads> eQuads,
包含firstEquad;
size_t sizeOfPoints = points.size();
std :: forward_list< size_t> remainedPoints;
findExtremePointsAtFirst(points,firstEquad,sizeOfPoints);
discardInsidePointsAtFirst(points,firstEquad,remainingPoints,sizeOfPoints);
int count = 0;
while(sizeOfPoints> 0)
{
必须等于;
findExtremePoints3(points,equads,remainingPoints,sizeOfPoints);
eQuads.push_back(equads);
if(count == 0)break;
}
endTime = std :: chrono :: high_resolution_clock :: now();
std :: cout<< 算法2所花费的时间直到找到第二个等式< std :: chrono :: duration_cast< std :: chrono :: microseconds>(endTime - startTime).count()<<的std :: ENDL<<的std :: ENDL;
返回结果;
}
和findExtremePointsAtFirst,discardInsidePointsAtFirst和findExtremePoints3如下所示。
void findExtremePointsAtFirst(vector< Point> points,Equads& eQuad,size_t&sizeOfPoints)
{
Point minX [0]),MINY(点[0]),maxX的(点[0]),MAXY(点[0]); (size_t i = 1; i< sizeOfPoints; i ++)
{
if(points [i] .x< minX.x)
{
minX = points [i];
}
if(points [i] .x> maxX.x)
{
maxX = points [i];
}
if(points [i] .y< minY.y)
{
minY = points [i];
}
if(points [i] .y> maxY.y)
{
maxY = points [i];
}
}
eQuad.extremePoints [0] = minX;
eQuad.extremePoints [1] = minY;
eQuad.extremePoints [2] = maxX;
eQuad.extremePoints [3] = maxY;
}
void discardInsidePointsAtFirst(vector< Point> points,Equads& prevEquad,std :: forward_list< size_t&&; remainingPoints,size_t&sizeOfPoints)
{
size_t remainingPointsSize = 0;
for(size_t i = 0; i< points.size(); i ++)
{
if(!isInside(prevEquad,points [i]))
{
remainingPoints.push_front(i + 1);
remainingPointsSize ++;
}
}
sizeOfPoints = remainingPointsSize;
}
void findExtremePoints3(vector< Point& points,Equads& eQuad,std :: forward_list< size_t&& remainingPoints,size_t&sizeOfPoints)
{
Point minX(points [remainingPoints.front() - 1]);
Point minY = minX,maxX = minX,maxY = minX;
for(size_t i:remainingPoints)
{
i--;
if(points [i] .x< minX.x)
{
minX = points [i];
}
if(points [i] .x> maxX.x)
{
maxX = points [i];
}
if(points [i] .y< minY.y)
{
minY = points [i];
}
if(points [i] .y> maxY.y)
{
maxY = points [i];
}
}
eQuad.extremePoints [0] = minX;
eQuad.extremePoints [1] = minY;
eQuad.extremePoints [2] = maxX;
eQuad.extremePoints [3] = maxY;
}
FYI
// Point.h文件
使用CoordinateType = double;
struct Point
{
CoordinateType x;
CoordinateType y;
//找到最左边的点
bool运算符< (const Point& operand);
bool operator ==(const Point& operand)const;
Point& operator =(const Point& p);
朋友std :: ostream&运算符<<(std :: ostream& os,const Point& p);
bool isLower(const Point& p);
bool isHigher(const Point& p);
Point(CoordinateType x = -9999.0,CoordinateType y = -9999.0):x(x),y(y){}
Point(const Point& p):x(px) ,y(py){}
};
使用PointSequence = std :: vector< Point>;
int orientation(const Point& p,const Point& q,const Point& r);
结构要素
{
Point extremePoints [4]; // Xmin,Ymin,Xmax,Ymax order
Equities& operator =(const Equads& e);
};
包含& Equads :: operator =(const Equads& e)
{
std :: copy(std :: begin(e.extremePoints),std :: end(e.extremePoints),std :: begin( extremePoints));
std :: copy(std :: begin(e.subRegions),std :: end(e.subRegions),std :: begin(subRegions));
return * this;
// Point.cpp
#includePoint.h
bool Point :: operator<(const Point& operand)
{
if(this-> x< operand.x)
return true;
else if(this-> x == operand.x&& this-> y< operand.y)
return true;
else
返回false;
bool Point :: operator ==(const Point& operand)const
{
if((this-> x == operand.x) &&(this-> y == operand.y))
return true;
else
返回false;
}
Point& Point :: operator =(const Point& p)
{
x = p.x;
y = p.y;
return * this;
}
std :: ostream&运营商LT;< (std :: ostream& os,const Point& p)
{
os<< p.x<< ,<< p.y<<的std :: ENDL;
return os;
}
bool Point :: isLower(const Point& p)
{
if(this-> y< py)
{
返回true;
}
else if(this-> y == p.y&& this-> x< p.x)
{
return true;
}
返回false;
}
bool Point :: isHigher(const Point& p)
{
if(this-> y> py)
{
返回true;
}
else if(this-> y == p.y&& this-> x> p.x)
{
return true;
}
返回false;
}
//查看它是顺时针还是逆时针旋转
int orientation(const Point& p,const Point& q,const Point& r)
{
double val =(qx - px)*(ry - py) - (qy - py)*(rx - px);
if(val == 0)
return 0; // colinear
return(val <0)? -1:1; // right or left
}
任何局部变量在超出范围时都会被销毁(对于在循环或条件块中未声明的变量,当函数返回时会发生这种变化);如果其中任何一个是复杂类型(例如, struct
/ class
不隐藏在指针或引用后面的实例),则它们的析构函数将被执行,这可能需要额外的时间。 / p>
在这种情况下,您的向量为 Point
和 Equads
对象,每个对象可能需要调用它的析构函数。你的第一个算法是从它的点
向量中删除元素(增加函数中的总运行时间,但在退出时减少清理),而第二个算法不会(运行速度更快但清理时间更长)。
There is a set of points (say 100,000 points). What I try to do is
Find four extreme points (minimum x and y, maximum x and y)
Discard points inside of the first four extreme points
Find the next four extreme points among remaining points. (until there is no points left. in the code it stops when second four extreme points are found)
I implemented this in two ways.
First way : erase the points from the points set
Second way : only save the remaining points' index from the points set and use the index in order to find the next extreme points.
My problem is I measured the time taken by each algorithm (firstAlgorithm and secondAlgorithm) as shown in the codes and it seems secondAlgorithm takes less time than the first one. The result looks like
algorithm1 time taken until second equad found 105181
algorithm2 time taken until second equad found 63047
However, in main() function I call these two functions and measure the time taken by each and the result is
#include <iostream>
#include <random>
#include <chrono>
#include <fstream>
#include "Point.h"
bool isInside(Equads& eQuad, Point& p)
{
if(orientation(eQuad.extremePoints[0], eQuad.extremePoints[1], p) < 0)
{
return false;
}
else if(orientation(eQuad.extremePoints[1], eQuad.extremePoints[2], p) < 0)
{
return false;
}
else if(orientation(eQuad.extremePoints[2], eQuad.extremePoints[3], p) < 0)
{
return false;
}
else if(orientation(eQuad.extremePoints[3], eQuad.extremePoints[0], p) < 0)
{
return false;
}
else
{
return true;
}
}
void main()
{
std::chrono::high_resolution_clock::time_point start;
std::chrono::high_resolution_clock::time_point end;
start = std::chrono::high_resolution_clock::now();
firstAlgorithm(points);
end = std::chrono::high_resolution_clock::now();
std::cout << "compute time of firstAlgorithm (microseconds)" << chrono::duration_cast<std::chrono::microseconds>(end - start).count() << std::endl;
start = std::chrono::high_resolution_clock::now();
secondAlgorithm(points);
end = std::chrono::high_resolution_clock::now();
std::cout << "compute time of secondAlgorithm (microseconds)" << chrono::duration_cast<std::chrono::microseconds>(end - start).count() << std::endl;
}
compute time of firstAlgorithm (microseconds) : 107282
compute time of secondAlgorithm (microseconds) : 142401
How come the secondAlgorithm becomes so slow when time is taken in the main() function?
Below is the code for the first way.
vector<Point> firstAlgorithm(vector<Point>& originalPoint)
{
std::chrono::high_resolution_clock::time_point startTime;
std::chrono::high_resolution_clock::time_point endTime;
startTime = std::chrono::high_resolution_clock::now();
vector<Point> points = originalPoints;
PointSequence result;
Equads firstEquad; // Equads is array of points that store the four extreme points
findExtremePoints1(points, firstEquad);
Equads prev;
prev = firstEquad;
std::vector<Equads> eQuads;
Equads current;
int count = 0 ;
while(findExtremePoints2(points, prev, current) != false)
{
eQuads.push_back(current);
prev = current;
if(count == 0) break;
}
endTime = std::chrono::high_resolution_clock::now();
std::cout << std::endl << "algorithm1 time taken until second equad found " << std::chrono::duration_cast<std::chrono::microseconds>(endTime - startTime).count() << std::endl;
return result;
}
and findExtremePoints1 and findExtremePoints2 look like below
void findExtremePoints1(vector<Point>& points, Equads& eQuad)
{
Point minX(points[0]),minY(points[0]),maxX(points[0]),maxY(points[0]);
for(size_t i = 1; i < points.size(); i++)
{
if(points[i].x < minX.x)
{
minX = points[i];
}
if(points[i].x > maxX.x)
{
maxX = points[i];
}
if(points[i].y < minY.y)
{
minY = points[i];
}
if(points[i].y > maxY.y)
{
maxY = points[i];
}
}
eQuad.extremePoints[0] = minX;
eQuad.extremePoints[1] = minY;
eQuad.extremePoints[2] = maxX;
eQuad.extremePoints[3] = maxY;
// erase the extreme points
points.erase(remove(points.begin(),points.end(), eQuad.extremePoints[0]), points.end());
points.erase(remove(points.begin(),points.end(), eQuad.extremePoints[1]), points.end());
points.erase(remove(points.begin(),points.end(), eQuad.extremePoints[2]), points.end());
points.erase(remove(points.begin(),points.end(), eQuad.extremePoints[3]), points.end());
}
// traverse the points and if any point is inside of previous equad(four extreme points)
//then delete it from points set and if not inside find next four extreme points.
bool findExtremePoints2(vector<Point> points, Equads& prevEquad, Equads& eQuad)
{
Point minX,minY,maxX,maxY;
bool prevFound = false;
std::vector<size_t> deletedVal;
for(size_t i = 0; i < points.size(); i++)
{
if(isInside(prevEquad, points[i]))
{
deletedVal.push_back(i);
}
else
{
if(prevFound)
{
if(points[i].x < minX.x)
{
minX = points[i];
}
if(points[i].x > maxX.x)
{
maxX = points[i];
}
if(points[i].y < minY.y)
{
minY = points[i];
}
if(points[i].y > maxY.y)
{
maxY = points[i];
}
}
else // not inside of the prev equad and the very first one. only meet this condition at very first time.
{
minX = points[i];
minY = points[i];
maxX = points[i];
maxY = points[i];
prevFound = true;
}
}
}
if (prevFound == false)
{
return false;
}
eQuad.extremePoints[0] = minX;
eQuad.extremePoints[1] = minY;
eQuad.extremePoints[2] = maxX;
eQuad.extremePoints[3] = maxY;
for(size_t i = deletedVal.size(); i-- > 0;)
{
points[deletedVal.at(i)] = points.back();
points.pop_back();
}
// erase the extreme points
points.erase(remove(points.begin(),points.end(), eQuad.extremePoints[0]), points.end());
points.erase(remove(points.begin(),points.end(), eQuad.extremePoints[1]), points.end());
points.erase(remove(points.begin(),points.end(), eQuad.extremePoints[2]), points.end());
points.erase(remove(points.begin(),points.end(), eQuad.extremePoints[3]), points.end());
return prevFound;
}
Below is for the code of second way.
vector<Point> secondAlgorithm(vector<Point>& points)
{
std::chrono::high_resolution_clock::time_point startTime;
std::chrono::high_resolution_clock::time_point endTime;
startTime = std::chrono::high_resolution_clock::now();
vector<Point> result;
std::vector<Equads> eQuads;
Equads firstEquad;
size_t sizeOfPoints = points.size();
std::forward_list<size_t> remainedPoints;
findExtremePointsAtFirst(points,firstEquad, sizeOfPoints);
discardInsidePointsAtFirst(points,firstEquad,remainedPoints,sizeOfPoints);
int count = 0 ;
while(sizeOfPoints > 0)
{
Equads equads;
findExtremePoints3(points, equads, remainedPoints, sizeOfPoints);
eQuads.push_back(equads);
if(count == 0 ) break;
}
endTime = std::chrono::high_resolution_clock::now();
std::cout << "algorithm2 time taken until second equad found " << std::chrono::duration_cast<std::chrono::microseconds>(endTime - startTime).count() << std::endl<< std::endl;
return result;
}
and findExtremePointsAtFirst , discardInsidePointsAtFirst and findExtremePoints3 look like below.
void findExtremePointsAtFirst(vector<Point>& points, Equads& eQuad, size_t& sizeOfPoints)
{
Point minX(points[0]),minY(points[0]),maxX(points[0]),maxY(points[0]);
for(size_t i = 1; i < sizeOfPoints; i++)
{
if(points[i].x < minX.x)
{
minX = points[i];
}
if(points[i].x > maxX.x)
{
maxX = points[i];
}
if(points[i].y < minY.y)
{
minY = points[i];
}
if(points[i].y > maxY.y)
{
maxY = points[i];
}
}
eQuad.extremePoints[0] = minX;
eQuad.extremePoints[1] = minY;
eQuad.extremePoints[2] = maxX;
eQuad.extremePoints[3] = maxY;
}
void discardInsidePointsAtFirst(vector<Point>& points, Equads& prevEquad, std::forward_list<size_t>& remainedPoints, size_t& sizeOfPoints)
{
size_t remainedPointsSize = 0;
for(size_t i = 0; i < points.size(); i++)
{
if(!isInside(prevEquad, points[i]))
{
remainedPoints.push_front(i+1);
remainedPointsSize++;
}
}
sizeOfPoints = remainedPointsSize;
}
void findExtremePoints3(vector<Point>& points, Equads& eQuad, std::forward_list<size_t>& remainedPoints, size_t& sizeOfPoints)
{
Point minX(points[remainedPoints.front()-1]);
Point minY = minX, maxX = minX , maxY = minX;
for(size_t i : remainedPoints)
{
i--;
if(points[i].x < minX.x)
{
minX = points[i];
}
if(points[i].x > maxX.x)
{
maxX = points[i];
}
if(points[i].y < minY.y)
{
minY = points[i];
}
if(points[i].y > maxY.y)
{
maxY = points[i];
}
}
eQuad.extremePoints[0] = minX;
eQuad.extremePoints[1] = minY;
eQuad.extremePoints[2] = maxX;
eQuad.extremePoints[3] = maxY;
}
FYI
// Point.h file
using CoordinateType = double;
struct Point
{
CoordinateType x;
CoordinateType y;
// to find the leftmost point
bool operator < (const Point& operand);
bool operator ==(const Point& operand) const;
Point& operator=(const Point& p);
friend std::ostream& operator <<(std::ostream& os, const Point& p);
bool isLower(const Point& p);
bool isHigher(const Point& p);
Point(CoordinateType x = -9999.0, CoordinateType y = -9999.0):x(x),y(y) {}
Point(const Point& p) : x(p.x), y(p.y) {}
};
using PointSequence = std::vector<Point>;
int orientation(const Point& p, const Point& q, const Point& r);
struct Equads
{
Point extremePoints[4]; // Xmin, Ymin, Xmax, Ymax order
Equads& operator=(const Equads& e);
};
Equads& Equads::operator=(const Equads& e)
{
std::copy(std::begin(e.extremePoints), std::end(e.extremePoints), std::begin(extremePoints));
std::copy(std::begin(e.subRegions), std::end(e.subRegions), std::begin(subRegions));
return *this;
}
// Point.cpp
#include "Point.h"
bool Point::operator <(const Point& operand)
{
if(this->x < operand.x)
return true;
else if(this->x == operand.x && this->y < operand.y)
return true;
else
return false;
}
bool Point::operator ==(const Point& operand) const
{
if((this->x == operand.x) && (this->y == operand.y))
return true;
else
return false;
}
Point& Point::operator=(const Point& p)
{
x = p.x;
y = p.y;
return *this;
}
std::ostream& operator<< (std::ostream& os, const Point& p)
{
os << p.x << " , " << p.y << std::endl;
return os;
}
bool Point::isLower(const Point& p)
{
if(this->y < p.y)
{
return true;
}
else if(this->y == p.y && this->x < p.x)
{
return true;
}
return false;
}
bool Point::isHigher(const Point& p)
{
if(this->y > p.y)
{
return true;
}
else if(this->y == p.y && this->x > p.x)
{
return true;
}
return false;
}
// to see if it turns clockwise or counterclockwise
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
}
Any local variables will be destroyed when they go out of scope (for variables that aren't declared inside loops or conditional blocks, that happens when your function returns); if any of those are complex types (e.g. struct
/class
instances not hidden behind pointers or references), their destructors will be executed, which may take extra time.
In this case, you have vectors of Point
and Equads
objects, each of which may need to have its destructor called. Your first algorithm is erasing elements from its points
vector as it goes along (increasing the total run time within the function, but reducing the cleanup when it exits), while your second algorithm does not (making it run faster but take longer to cleanup).
这篇关于可能影响功能所花时间的事情的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!