2017-04-05 97 views
0

所用的時間有一組點(100,000個點)。我嘗試做的是東西可以影響通過功能

  1. 發現四個極值點(最小x和y,最大x和y)

  2. 丟棄點前四個極值點內

  3. 查找下一個剩餘點中有四個極端點。 (直到沒有剩下的點,在代碼中停止,當找到第二個四個極端點時)

我以兩種方式實現了這一點。

第一種方式:從設定

方式二點刪除點:只從設定點保存剩餘點指數和使用索引,以便找到下一個極值點。

我的問題是我測量如圖所示的代碼和它似乎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 

} 
+0

你的代碼中有很多未定義的變量(如'main'中的'points'和'start'),並且你刪除了重要的'#include'指令。就像我上次所說的,你應該提供一個[mcve],讓別人可以複製並粘貼你的代碼,編譯它而不必亂搞太多,然後重新創建你的結果。 –

+0

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

回答

1

,當他們走出去的範圍內的任何局部變量將被銷燬(對於未在循環體或條件塊中聲明的變量,這種情況發生你的函數返回時);如果任何這些是複雜的類型(例如struct/class實例不是隱藏的指針或引用後面),它們的destructors將被執行,這可能需要額外的時間。

在這種情況下,您的向量爲PointEquads對象,每個對象可能需要調用其析構函數。您的第一個算法,消除從points矢量元素,因爲它沿(增加總運行時間的函數中,但減少了清理退出時)去,而你的第二個算法不(讓運行速度更快,但需要較長時間才能清理) 。