機能の所要時間に影響を与える可能性のあるもの

Question

ポイント（例：100,000ポイント）があります。私は何をしようとすると、

1. は、4つの端点（最小xとy、最大のxとy）最初の4つの端点

2. は、次を探すの内側

3. 破棄ポイントを見つけることです残りの点のうち4つの極点。 （コードに残っているポイントがなくなるまで、2番目の4つの極点が見つかると停止します）

これを2通り実装しました。

最初の方法：だけセットポイントから残りの点インデックスを保存し、次の極端なポイントを見つけるためにインデックスを使用します。

第二の方法を設定ポイントからポイントを消去します。

私の問題は、コードに示されているように各アルゴリズム（firstAlgorithmとsecondAlgorithm）で取られた時間を測定しています。それはsecondAlgorithmが最初のものより時間がかかりにくいようです。結果は、私はこの2つの関数を呼び出すと、それぞれにかかる時間を測定し、結果は時間secondAlgorithmがとても遅くなっどうして

#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 

であるmain（）関数では、しかし

algorithm1 time taken until second equad found 105181 
algorithm2 time taken until second equad found 63047 

のように見えます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 

} 

Answer 1

彼らはスコープの外に行くときに、任意のローカル変数が破壊されます。複雑なタイプのもの（例えば、struct/classのインスタンスがポインタまたは参照の背後に隠されていない場合）は、destructorsが実行され、余分な時間がかかることがあります。

この場合、ベクトルはPointとEquadsのオブジェクトを持ちます。これらのオブジェクトのそれぞれは、そのデストラクタを呼び出す必要があります。最初のアルゴリズムは、pointsベクトルから要素を消去しています（関数内の合計実行時間を長くしますが、終了時にはクリーンアップを減らします）。一方、2番目のアルゴリズムでは高速化はしません（クリーンアップ時間は長くなりますが） 。