东西可以影响通过功能

所用的时间有一组点（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 

}

来源

2017-04-05 Q123

你的代码中有很多未定义的变量（如'main'中的'points'和'start'），并且你删除了重要的'＃include'指令。就像我上次所说的，你应该提供一个[mcve]，让别人可以复制并粘贴你的代码，编译它而不必乱搞太多，然后重新创建你的结果。 –

@DavidGrayson好的，我增加了更多 – Q123

，当他们走出去的范围内的任何局部变量将被销毁（对于未在循环体或条件块中声明的变量，这种情况发生你的函数返回时）;如果任何这些是复杂的类型（例如struct/class实例不是隐藏的指针或引用后面），它们的destructors将被执行，这可能需要额外的时间。

在这种情况下，您的向量为Point和Equads对象，每个对象可能需要调用其析构函数。您的第一个算法，消除从points矢量元素，因为它沿（增加总运行时间的函数中，但减少了清理退出时）去，而你的第二个算法不（让运行速度更快，但需要较长时间才能清理）。

来源

2017-04-05 21:13:28 Quietust

东西可以影响通过功能

回答

相关问题