所用的時間有一組點(100,000個點)。我嘗試做的是東西可以影響通過功能
發現四個極值點(最小x和y,最大x和y)
丟棄點前四個極值點內
查找下一個剩餘點中有四個極端點。 (直到沒有剩下的點,在代碼中停止,當找到第二個四個極端點時)
我以兩種方式實現了這一點。
第一種方式:從設定
方式二點刪除點:只從設定點保存剩餘點指數和使用索引,以便找到下一個極值點。
我的問題是我測量如圖所示的代碼和它似乎secondAlgorithm成爲比第1一次少由每個算法(firstAlgorithm和secondAlgorithm)所花費的時間。結果看起來像
algorithm1 time taken until second equad found 105181
algorithm2 time taken until second equad found 63047
然而,在main()函數我調用這兩個函數,並測量每個所花費的時間,結果是
#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
的secondAlgorithm怎麼會變成當時間這麼慢在main()函數中被採用?
下面是第一種方式的代碼。
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;
}
和findExtremePoints1和findExtremePoints2看起來像下面
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;
}
下面是第二方式的代碼。
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;
}
和findExtremePointsAtFirst,discardInsidePointsAtFirst和findExtremePoints3看起來像下面。
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
}
你的代碼中有很多未定義的變量(如'main'中的'points'和'start'),並且你刪除了重要的'#include'指令。就像我上次所說的,你應該提供一個[mcve],讓別人可以複製並粘貼你的代碼,編譯它而不必亂搞太多,然後重新創建你的結果。 –
@DavidGrayson好的,我增加了更多 – Q123