Trang 1 trên tổng số 2 12 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 19 kết quả

Đề tài: Graph structure

  1. #1
    Ngày gia nhập
    09 2010
    Bài viết
    88

    Mặc định Graph structure

    Vertex.h
    C++ Code:
    1. #ifndef VERTEX_H
    2. #define VERTEX_H
    3. #include <iostream>
    4. #include <vector>
    5. #include <algorithm>
    6.  
    7. #include "Edge.h"
    8. #include "Graph.h"
    9.  
    10. using namespace std;
    11.  
    12. class Graph;
    13. class Edge;
    14.  
    15. class Vertex
    16. {
    17.     public:
    18.         Vertex();
    19.         virtual ~Vertex();
    20.         Vertex(Vertex const &v);
    21.         Vertex(int x, int y);
    22.         int getX() const;
    23.         int getY() const;
    24.  
    25.         int addAdjEdge(Edge &e);
    26.         int rmAdjEdge(Edge const &e);
    27.         Edge * getAdjEdge(Edge const &e);
    28.         int getAdjPos(Edge const &e);
    29.         int getAdjSize() const;
    30.  
    31.         bool operator==(Vertex const &v) const;
    32.         friend ostream &operator<<(ostream &os, Vertex const &v);
    33.         friend int Graph::rmVertex(Vertex const &v);
    34.  
    35.     protected:
    36.     private:
    37.         int _x;
    38.         int _y;
    39.         vector<Edge *> _adjEdge;
    40. };
    41.  
    42. #endif // VERTEX_H

    Vertex.cpp
    C++ Code:
    1. #include "../include/Vertex.h"
    2.  
    3. Vertex::Vertex() : _x(0), _y(0)
    4. {
    5.     //ctor
    6. }
    7.  
    8. Vertex::~Vertex()
    9. {
    10.     //dtor
    11. }
    12.  
    13. Vertex::Vertex(Vertex const &v)
    14. {
    15.     _x=v.getX();
    16.     _y=v.getY();
    17. }
    18.  
    19. Vertex::Vertex(int x, int y):_x(x), _y(y) {
    20.  
    21. }
    22.  
    23. int Vertex::getX() const {
    24.     return _x;
    25. }
    26.  
    27. int Vertex::getY() const {
    28.     return _y;
    29. }
    30.  
    31. ostream &operator<<(ostream &os, Vertex const &v) {
    32.     os<<"Vertex <"<<&v<<"> ("<<v.getX()<<":"<<v.getY()<<")"<<endl;
    33.     os<<"Adjacent Edges ("<<v.getAdjSize()<<") : ";
    34.     vector<Edge *> ve = v._adjEdge;
    35.     for(auto edge : ve)
    36.         os<<edge<<" - ";
    37.     return os;
    38. }
    39.  
    40. bool Vertex::operator==(Vertex const &v) const {
    41.     if(this == &v) return true;
    42.     return _x==v.getX() && _y==v.getY();
    43. }
    44.  
    45. int Vertex::addAdjEdge(Edge &e) {
    46.     if(getAdjEdge(e)==NULL) {
    47.         _adjEdge.push_back(&e);
    48.         return 1;
    49.     }
    50.     return 0;
    51. }
    52.  
    53. int Vertex::rmAdjEdge(Edge const &e) {
    54.     int epos = getAdjPos(e);
    55.     if(epos < getAdjSize()) {
    56.         _adjEdge.erase(_adjEdge.begin()+epos);
    57.         return 1;
    58.     }
    59.     return 0;
    60. }
    61.  
    62. Edge * Vertex::getAdjEdge(Edge const &e) {
    63. //    Edge const * pe = &e;
    64.     vector<Edge * >::iterator iter = find_if(_adjEdge.begin(), _adjEdge.end(), [&,e](Edge * const &param){return *param==e;});
    65.     if(iter != _adjEdge.end()) return *iter;
    66.     return NULL;
    67. }
    68.  
    69. int Vertex::getAdjPos(Edge const &e) {
    70. //    Edge const * pe = &e;
    71.     vector<Edge *>::iterator iter = find_if(_adjEdge.begin(), _adjEdge.end(), [&,e](Edge * const &param){return *param==e;});
    72.     return iter - _adjEdge.begin();
    73. }
    74.  
    75. int Vertex::getAdjSize() const {
    76.     return _adjEdge.size();
    77.     return 0;
    78. }
    Edge.h
    C++ Code:
    1. #ifndef EDGE_H
    2. #define EDGE_H
    3. #include <iostream>
    4. #include <vector>
    5. #include <algorithm>
    6.  
    7. #include "Vertex.h"
    8. #include "Graph.h"
    9.  
    10. using namespace std;
    11.  
    12. class Graph;
    13. class Vertex;
    14.  
    15. class Edge
    16. {
    17.     public:
    18.         Edge();
    19.         virtual ~Edge();
    20.         Edge(Vertex &v, Vertex &w);
    21.         Edge(Edge const &e);
    22.  
    23.         Vertex *getVertex() const ;
    24.         Vertex *getOther(Vertex const &v) const;
    25.         float getWeight() const ;
    26.  
    27.         bool operator==(Edge const &e) const;
    28.         friend ostream &operator<<(ostream &os, Edge const &e);
    29.         friend int Graph::addEdge(Edge &e);
    30.         friend int Graph::rmEdge(Edge const &e);
    31.  
    32.     protected:
    33.         float weightFormula(Vertex const &v, Vertex const &w) const;
    34.     private:
    35.         Vertex *_pv;
    36.         Vertex *_pw;
    37.         float _weight;
    38. };
    39.  
    40. #endif // EDGE_H
    Edge.cpp
    C++ Code:
    1.  
    2. #include "../include/Edge.h"
    3.  
    4. Edge::Edge()
    5. {
    6.     //ctor
    7. }
    8.  
    9. Edge::~Edge()
    10. {
    11.     //dtor
    12. }
    13.  
    14. Edge::Edge(Vertex &v, Vertex &w):_pv(&v),_pw(&w) {
    15.     _weight = weightFormula(v,w);
    16. }
    17.  
    18. Edge::Edge(Edge const &e) {
    19.     _weight = e.getWeight();
    20.     _pv = e.getVertex();
    21.     _pw = e.getOther(*_pv);
    22. }
    23.  
    24. ostream &operator<<(ostream &os, Edge const &e) {
    25.     os<<"Line2D <"<<&e<<"> : "<<e.getWeight()<<" ("<<e._pv<<" : "<<e._pw<<")";
    26.     return os;
    27. }
    28.  
    29. bool Edge::operator==(Edge const &e) const {
    30. //    if(!getOther(e.getVertex())) return false;
    31.     if(this == &e) return true;
    32.     if(e.getOther(*_pv)==NULL || e.getOther(*_pw)==NULL) return false;
    33.     return _weight == e.getWeight();
    34. }
    35.  
    36. Vertex *Edge::getVertex() const {
    37.     return _pv;
    38. }
    39.  
    40. Vertex *Edge::getOther(Vertex const &v) const {
    41.     if(*_pv == v) return _pw;
    42.     if(*_pw == v) return _pv;
    43.     return NULL;
    44. }
    45.  
    46. float Edge::getWeight() const {
    47.     return _weight;
    48. }
    49.  
    50. float Edge::weightFormula(Vertex const &v, Vertex const &w) const {
    51.     float rs = sqrt( pow(v.getX()-w.getX(),2) + pow(v.getY()-w.getY(),2) );
    52.     return rs;
    53. }
    Graph.h
    C++ Code:
    1. #ifndef GRAPH_H
    2. #define GRAPH_H
    3. #include <iostream>
    4. #include <vector>
    5. #include <algorithm>
    6.  
    7. #include "Edge.h"
    8. #include "Vertex.h"
    9.  
    10. using namespace std;
    11.  
    12. class Vertex;
    13. class Edge;
    14.  
    15. class Graph
    16. {
    17.     public:
    18.         Graph();
    19.         virtual ~Graph();
    20.         friend ostream &operator<<(ostream &os, Graph const &g);
    21.         void printEdges();
    22.         void printVertices();
    23.  
    24.         int addVertex(Vertex &v);
    25.         int addEdge(Edge &e);
    26.         int rmVertex(Vertex const &v);
    27.         int rmEdge(Edge const &e);
    28.  
    29.         Vertex * getVertex(Vertex const &v);
    30.         Edge * getEdge(Edge const &e);
    31.         int getPos(Vertex  const &v);
    32.         int getPos(Edge const &e);
    33.         int getVertexSize() const;
    34.         int getEdgeSize() const;
    35.  
    36.         int initialize(int sizeX, int sizeY);
    37.         void clear();
    38.  
    39.     protected:
    40.     private:
    41.         vector<Edge *> _edgeList;
    42.         vector<Vertex *> _vertexList;
    43. };
    44.  
    45. #endif // GRAPH_H
    Graph.cpp
    C++ Code:
    1.  
    2. #include "../include/Edge.h"
    3. #include "../include/Vertex.h"
    4. #include "../include/Graph.h"
    5.  
    6. Graph::Graph()
    7. {
    8.     //ctor
    9. }
    10.  
    11. Graph::~Graph()
    12. {
    13.     //dtor
    14. }
    15.  
    16. ostream &operator<<(ostream &os, Graph const &g) {
    17. //    g.print(os);
    18.     os<<"Graph: "<<endl;
    19.     os<<"Vertices ("<<g._vertexList.size()<<") : ";
    20.     vector<Vertex *> vv = g._vertexList;
    21.     for(auto vertex : vv)
    22.         os<<vertex<<" - ";
    23.     os<<endl<<"Edges ("<<g._edgeList.size()<<") : ";
    24.     vector<Edge *> ve = g._edgeList;
    25.     for(auto edge : ve)
    26.         os<<edge<<" - ";
    27.     return os;
    28. }
    29.  
    30. void Graph::printEdges() {
    31.     cout<<"Edges ("<<_edgeList.size()<<") : "<<endl;
    32.     vector<Edge *> ve = _edgeList;
    33.     for(auto edge : ve)
    34.         cout<<*edge<<endl;
    35. }
    36.  
    37. void Graph::printVertices() {
    38.     cout<<"Vertices ("<<_vertexList.size()<<") : "<<endl;
    39.     vector<Vertex *> vv = _vertexList;
    40.     for(auto vertex : vv)
    41.         cout<<*vertex<<endl;
    42. }
    43.  
    44. int Graph::addVertex(Vertex &v) {
    45.     int vpos = getPos(v);
    46.     if( vpos == getVertexSize()) {
    47.         Vertex *pv = new Vertex(v);
    48.         _vertexList.push_back(pv);
    49. //        cout<<"ADD: ("<<pv->getX()<<":"<<pv->getY()<<")"<<endl;
    50.     }
    51.     return vpos;
    52. }
    53.  
    54. int Graph::addEdge(Edge &e) {
    55.     int epos = getPos(e);
    56.     if(epos == getEdgeSize()) {
    57.         Edge *pe = new Edge(e);             //khoi tao Edge
    58.         int vpos = addVertex(*pe->_pv);     //add vertex vao vertexList vaf lay vi tri 2 Vertex vua add trong vertexList
    59.         int wpos = addVertex(*pe->_pw);
    60.         pe->_pv = _vertexList[vpos];        //cho edge tro vao 2 vertex trong vertexList
    61.         pe->_pw = _vertexList[wpos];
    62.         pe->_pv->addAdjEdge(*pe);           //add adjEdge cho 2 vertex trong vertexList
    63.         pe->_pw->addAdjEdge(*pe);
    64.         _edgeList.push_back(pe);            //them edge vao edgeList
    65.     }
    66.     return epos;
    67. }
    68.  
    69. int Graph::rmVertex(Vertex const &v) {
    70.     int vpos = getPos(v);                               //tim vertex trong vertexList
    71.     if(vpos < getVertexSize()) {                        //tim thay thi bat dau xoa
    72.         Vertex *vp = _vertexList[vpos];                 //lay vertex trong vertexList
    73.         for(auto edge : vp->_adjEdge) {                 //xoa Edge lien quan den vertex bi xoa
    74.             rmEdge(*edge);
    75.         }
    76.         _vertexList.erase(_vertexList.begin()+vpos);    //xoa vertex khoi vertexList
    77.         delete vp;                                      //giai phong vertex
    78.     }
    79.     return 0;
    80. }
    81.  
    82. int Graph::rmEdge(Edge const &e) {
    83.     int epos = getPos(e);                               //tim edge trong edgeList
    84.     if(epos < getEdgeSize()) {                          //tim thay thi xoa
    85.         Edge *pe = _edgeList[epos];                     //lay edge trong edgeList
    86.         pe->_pv->rmAdjEdge(*pe);                        //xoa adjEdge trong 2 vertex
    87.         pe->_pw->rmAdjEdge(*pe);
    88.         _edgeList.erase(_edgeList.begin()+epos);
    89.         delete pe;                                      //giai phong Edge;
    90.     }
    91.     return 0;
    92. }
    93.  
    94. Vertex * Graph::getVertex(Vertex const &v) {
    95.     int vpos = getPos(v);
    96.     return _vertexList[vpos];
    97. }
    98.  
    99. Edge * Graph::getEdge(Edge const &e) {
    100.     int epos = getPos(e);
    101.     return _edgeList[epos];
    102. }
    103.  
    104. int Graph::getPos(Vertex const &v) {
    105. //    Vertex const *pv = &v;
    106.     vector<Vertex *>::iterator iv = find_if( _vertexList.begin(), _vertexList.end(), [&, v](Vertex * const &ve) { return *ve==v; });
    107.     return iv-_vertexList.begin();
    108. }
    109.  
    110. int Graph::getPos(Edge const &e) {
    111. //    Edge const *pe = &e;
    112.     vector<Edge *>::iterator iv = find_if( _edgeList.begin(), _edgeList.end(), [&, e](Edge * const &ed) { return *ed==e; });
    113.     return iv -_edgeList.begin();
    114. }
    115.  
    116. int Graph::getVertexSize() const {
    117.     return _vertexList.size();
    118. }
    119.  
    120. int Graph::getEdgeSize() const {
    121.     return _edgeList.size();
    122. }
    123.  
    124. int Graph::initialize(int sizeX, int sizeY) {
    125.     Vertex *vCenter, *vTop, *vLeft, *vRight, *vBottom;
    126.     Edge *eTop, *eLeft, *eRight, *eBottom;
    127.     clock_t bi, ei, bj, ej;
    128.     float iloop = 0;
    129.     float jloop = 0;
    130.  
    131.     for(int i=0,j; i<sizeX; i++) {
    132.         bi = clock();
    133.         for(j=0; j<sizeY; j++) {
    134.             bj = clock();
    135.             vCenter = new Vertex(i,j);
    136.             if(j>0) {
    137. //                cout<<"("<<i<<":"<<j<<")"<<"TOP"<<endl;
    138.                 vTop = new Vertex(i,j-1);
    139.                 eTop = new Edge(*vCenter, *vTop);
    140.                 addEdge(*eTop);
    141.                 delete vTop;
    142.                 delete eTop;
    143.             }
    144.             if(i>0) {
    145. //                cout<<"("<<i<<":"<<j<<")"<<"LEFT"<<endl;
    146.                 vLeft = new Vertex(i-1, j);
    147.                 eLeft = new Edge(*vCenter, *vLeft);
    148.                 addEdge(*eLeft);
    149.                 delete vLeft;
    150.                 delete eLeft;
    151.             }
    152.             if(i < sizeX-1) {
    153. //                cout<<"("<<i<<":"<<j<<")"<<"RIGHT"<<endl;
    154.                 vRight = new Vertex(i+1,j);
    155.                 eRight = new Edge(*vCenter, *vRight);
    156.                 addEdge(*eRight);
    157.                 delete vRight;
    158.                 delete eRight;
    159.             }
    160.             if(j < sizeY-1) {
    161. //                cout<<"("<<i<<":"<<j<<")"<<"BOTTOM"<<endl;
    162.                 vBottom = new Vertex(i,j+1);
    163.                 eBottom = new Edge(*vCenter, *vBottom);
    164.                 addEdge(*eBottom);
    165.                 delete vBottom;
    166.                 delete eBottom;
    167.             }
    168.             delete vCenter;
    169.             ej = clock();
    170. //            cout<<"J : "<<(ej-bj)*1.f/CLOCKS_PER_SEC<<endl;
    171.             jloop += (ej-bj)*1.f/CLOCKS_PER_SEC;
    172.         }
    173.         ei = clock();
    174.         iloop = (ei - bi)*1.f/1000;
    175. //        if(iloop > 1000)
    176.         cout<<"("<<i<<":"<<getVertexSize()<<":"<<getEdgeSize()<<") "<<iloop<<endl;
    177. //        cout<<"I : "<<(ei-bi)*1.f/CLOCKS_PER_SEC<<endl;
    178. //        iloop += (ei-bi)*1.f/CLOCKS_PER_SEC;
    179.     }
    180. //    cout<<"I: "<<iloop<<" J : "<<jloop<<endl;
    181.     return 1;
    182. }
    183.  
    184. void Graph::clear() {
    185.     for(auto vertex : _vertexList) {
    186.         delete vertex;
    187.         vertex = NULL;
    188.     }
    189.     for(auto edge : _edgeList) {
    190.         delete edge;
    191.         edge = NULL;
    192.     }
    193.     _vertexList.clear();
    194.     _edgeList.clear();
    195. }
    main.cpp
    C++ Code:
    1. #include <iostream>
    2. #include <stdlib.h>
    3. #include "include/Edge.h"
    4. #include "include/Vertex.h"
    5. #include "include/Graph.h"
    6.  
    7. using namespace std;
    8.  
    9. int main()
    10. {
    11.     time_t time1, time2;
    12.     clock_t beginclock, endclock;
    13.     beginclock = clock();
    14.  
    15.     Graph g;
    16.     g.initialize(100,100);
    17.  
    18.     endclock = clock();
    19.     cout<<"TOTAL: "<<(endclock-beginclock)*1.f/CLOCKS_PER_SEC<<endl;
    20.     cout<<CLOCKS_PER_SEC<<endl;
    21.  
    22. //    Vertex v00(0,0);
    23. //    Vertex v01(0,1);
    24. //    Edge e0001(v00,v01);
    25. //    Edge e0100(v01,v00);
    26. //    g.addEdge(e0001);
    27. //    g.addEdge(e0100);
    28. //    cout<<g<<endl;
    29. //    g.printVertices();
    30. //    g.printEdges();
    31.     g.clear();
    32.  
    33.     return 0;
    34. }

    code trên mình chạy mất 12.25s để load xong 1 ma trận 100x100 :|
    không bị leak và dangling pointer

    Lần 1: code template với 2 ý tưởng:
    1. có thể load Vertex 2D hoặc 3D tùy ý
    2. có function pointer để tính weight cho edge
    => quá rắc rối và rườm rà không cần thiết, tuy nhiên học hỏi được khá nhiều

    Lần 2: sử dụng Abstract class với 2 ý tưởng:
    1. tạo Derived class cho Vertex2D và 3D
    2. tạo các Derived Edge (Line, Parabol...) để có công thức tính weight riêng cho từng edge
    => cũng rắc rối và không cần thiết, bởi có thể gộp cả 2D và 3D vào cùng 1 Vertex. Chỉ khác nhau mỗi cái Oz
    => về Edge thì mình có đọc lại 1 số chương của toán giải tích . có thể tóm gọn lại thành các đường conic trong hệ tọa độ => nhưng khá khó vì ngoài việc xác định phương trình của đường conic còn phải tính tích phân và đạo hàm mới ra được độ dài của nó

    tóm lại: phương pháp trên mình chỉ gói gọn trong trục Oxy và chỉ có đúng 1 kiểu Edge là đường thẳng
    về performance thì mình thấy chưa hài lòng lắm. nhưng trình độ chỉ đến vậy chưa biết làm cách nào để boost nó lên :(

    cách xây dựng chính của mình như sau:
    -đảm bảo new ở đâu thì delete ở đó
    -với mỗi lần add Vertex hoặc Edge vào Graph, mình cấp phát cho nó 1 vùng nhớ mới và ném nó vào vector để Graph quản lý (tức là tất cả Vertices và Edges trong Graph đều nằm trên Heap -> có lẽ việc này khiến performance giảm đi rất nhiều )

    mình không rõ là 2 khai báo như sau:
    C++ Code:
    1. Vertex *v = new Vertex(1,1);
    2. ....
    3. delete v;

    C++ Code:
    1. Vertex v(1,1);
    cái nào cho performance tốt hơn?
    và nên dùng cái nào trong trường hợp nào?
    mong các bạn góp ý
    thanks all

    còn thuật toán A* nữa. sau khi hoàn thành mình cũng sẽ up lên.

    p/s: và vô cùng cảm ơn các pro trong diễn đàn đã giúp mình rất nhiều, đặc biệt là về con trỏ. thanks các bạn thêm 1 lần nữa

    còn 1 băn khoăn nữa: mình có đọc nhiều tài liệu thì thấy người ta khuyến khích lập trình viên tự cấp phát và giải phóng, hạn chế dùng smart pointer..việc này có đúng không?
    Đã được chỉnh sửa lần cuối bởi quano1 : 04-09-2013 lúc 07:19 PM.

  2. #2
    Ngày gia nhập
    07 2011
    Bài viết
    474

    chạy thử Release hay Debug mà chậm dữ vậy?

    Trong hàm Graph::initialize phải call new delete vTop vLeft ... 1 lần rồi tại sao Graph::addEdge Graph::addVertex lại phải call 1 lần new nữa?

    trong Graph.h
    vector<Edge *> _edgeList;
    vector<Vertex *> _vertexList;

    ko cần phải vất vả dữ vậy đâu. Xài thẳng
    vector<Edge> _edgeList;
    vector<Vertex> _vertexList;

    luôn. Đừng đụng tới new và delete nữa.


    ồ lý do ko phải ở cấp phát động mà là ở hàm getPos xài find_if() tốn O(N) thời gian nên thành ra initialize tốn O(N^2) nên add 10000 points ~ giây là đúng rồi.
    Đã được chỉnh sửa lần cuối bởi INTP : 05-09-2013 lúc 01:00 AM.

  3. #3
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    @quano1:
    1. Bạn tạo một vector<Vertex*> để sử dụng polymorphism, nhưng nhìn vào thằng Edge và Vertex, liệu chúng có khả năng mở rộng không?
    2. Có quá nhiều concrete class.
    3. Làm sao phân biệt hay thêm vào:
    - Directed Graph
    - Undirected Graph
    - Weighted Undirected/Directed Graph
    4. Tại sao phải weight phải là float? Giả sử user muốn tính weight theo cách riêng của họ theo một công thức nào đó, thì làm sao họ dùng class của bạn được?
    5. Dùng iterator pattern để adapt Graph thì sẽ dễ dàng hơn khi traverse.
    6. Code này có vẻ bị lai giữa Java style & C++.
    7. Naming convention không consistent, API không rõ ràng:
    C++ Code:
    1. int addAdjEdge(Edge &e);
    2. int rmAdjEdge(Edge const &e);
    Tại sao không phải là removeAdjEdge?
    Tại sao kiểu trả về là int, error code là gì? (enum...)
    8. Dùng exception thay vì error code, không thì code path sẽ rất messy.
    9. Quan trọng nhất: bây giờ giả sử mình muốn implement BFS, DFS, Dijsktra, hay Prim/Kruskal.... dùng Graph datastructure của bạn, bao nhiêu chỗ mình phải chỉnh sửa?
    10. Dùng new/delete nhưng làm sao user khi biết khi nào mà delete?
    11. Có *quá nhiều* chỗ không handle exception.
    12. Nếu constructor/destructor không dùng, tại sao không để default? What are these two for?
    C++ Code:
    1. Edge::Edge()
    2. {
    3.     //ctor
    4. }
    5.  
    6. Edge::~Edge()
    7. {
    8.     //dtor
    9. }
    13. Nếu code chưa correct, forget about optimization!
    14. Line/Parabol = Geometry, và nó khác graph rất xa.
    có thể load Vertex 2D hoặc 3D tùy ý
    Graph là data structure cho đồ thị (combinatorics), vertex 2D/3D là cho graphics.
    Đã được chỉnh sửa lần cuối bởi rox_rook : 05-09-2013 lúc 01:24 AM.

  4. #4
    Ngày gia nhập
    01 2013
    Bài viết
    1,479

    Quản lí cửa hàng, bệnh viện... thì OOP mới phát huy được, còn giải toán thì OOP chi cho cồng kềnh.

  5. #5
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    @prog10: Tại sao không được dùng OOP hay design pattern ở đây? Mấy cái library của bạn dùng (STL, boost) nó dùng cái gì nhỉ?
    Cồng kềnh hay không là do cách design, chứ không phải do OOP.

  6. #6
    Ngày gia nhập
    11 2010
    Bài viết
    589

    Mặc định Graph structure

    - về container: Với những cấu trúc dữ liệu mà cần thêm bớt thường xuyên các thành phần thì dùng deque sẽ hiệu quả hơn là vector, vì deque::push_back() là O(1), còn vector::push_back() là O(n). VD như cái _edgeList và _vertextList trong đoạn code này.
    - Cấp phát tĩnh thì luôn nhanh hơn cấp phát động. Với lại trong code của bạn có sự copy dữ liệu một cách dư thừa rất nhiều lần. VD:
    C++ Code:
    1. vTop = new Vertex(i,j-1);
    2. eTop = new Edge(*vCenter, *vTop);
    3. addEdge(*eTop);
    4. delete vTop;
    5. delete eTop;

    Vừa mất công cấp phát động cho vTop, eTop; vừa phải copy dữ liệu từ nó sang các hàm addEdge, Edge(). Quá lãng phí.
    Để giải quyết vấn đề này, thử nghiên cứu về "R-value reference và Move semantic" xem sao.
    - Như có người đã nói trên kia. Chương trình chậm là do hàm find_if, nếu cần phải thực hiện công việc tìm cạnh, đỉnh nhiểu lần thì có thể sử dụng unordered_map.

  7. #7
    Ngày gia nhập
    07 2011
    Bài viết
    474

    gprof cả bài thì thấy rõ là Graph::getPos sử dụng trong Graph::addEdge/Graph::addVer quá lâu. Tìm kiếm find_if thì tốn O(N), ko hiểu xài getPos trước khi addEdge để làm gì? Nếu muốn chắc chắn ko có 2 Vertex/Edge trùng nhau thì có thể sử dụng std::set hoặc std::unordered_set thay thế cho std::vector.

    Code:
    Flat profile:
    
    Each sample counts as 0.01 seconds.
      %   cumulative   self              self     total           
     time   seconds   seconds    calls  us/call  us/call  name    
     43.99      7.46     7.46 392098804     0.02     0.03  Edge::operator==(Edge const&) const
     25.39     11.76     4.30 982439662     0.00     0.00  Vertex::operator==(Vertex const&) const
     13.55     14.06     2.30 392326207     0.01     0.01  Edge::getOther(Vertex const&) const
      7.20     15.28     1.22    39600    30.84   365.74  Graph::getPos(Edge const&)
      5.90     16.28     1.00                             operator<<(std::ostream&, Vertex const&)
      1.71     16.57     0.29    39600     7.33    29.23  Graph::getPos(Vertex const&)
      1.27     16.78     0.22                             Edge::getVertex() const
      1.00     16.95     0.17   178200     0.95     0.97  Edge::Edge(Edge const&)
      0.06     16.96     0.01                             Graph::printVertices()
      0.00     16.96     0.00   217800     0.00     0.00  Edge::~Edge()
      0.00     16.96     0.00   138800     0.00     0.00  Vertex::~Vertex()
      0.00     16.96     0.00    89200     0.00     0.00  Vertex::Vertex(Vertex const&)
      0.00     16.96     0.00    79200     0.00     0.00  Vertex::getX() const
      0.00     16.96     0.00    79200     0.00     0.00  Vertex::getY() const
      0.00     16.96     0.00    49600     0.00     0.00  Vertex::Vertex(int, int)
      0.00     16.96     0.00    39600     0.00     0.00  Edge::Edge(Vertex&, Vertex&)
      0.00     16.96     0.00    39600     0.00   397.45  Graph::addEdge(Edge&)
      0.00     16.96     0.00    39600     0.00    29.23  Graph::addVertex(Vertex&)
      0.00     16.96     0.00    39600     0.00     1.99  Vertex::addAdjEdge(Edge&)
      0.00     16.96     0.00    39600     0.00     1.99  Vertex::getAdjEdge(Edge const&)
      0.00     16.96     0.00    39600     0.00     0.00  Edge::weightFormula(Vertex const&, Vertex const&) const
      0.00     16.96     0.00    29996     0.00     0.00  _ZNSt6vectorIP4EdgeSaIS1_EE19_M_emplace_back_auxIJS1_EEEvDpOT_
      0.00     16.96     0.00       16     0.00     0.00  _ZNSt6vectorIP4EdgeSaIS1_EE19_M_emplace_back_auxIJRKS1_EEEvDpOT_
      0.00     16.96     0.00       15     0.00     0.00  void std::vector<Vertex*, std::allocator<Vertex*> >::_M_emplace_back_aux<Vertex* const&>(Vertex* const&)
      0.00     16.96     0.00        1     0.00     0.00  _GLOBAL__sub_I__ZN4EdgeC2Ev
      0.00     16.96     0.00        1     0.00     0.00  _GLOBAL__sub_I__ZN5GraphC2Ev
      0.00     16.96     0.00        1     0.00     0.00  _GLOBAL__sub_I__ZN6VertexC2Ev
      0.00     16.96     0.00        1     0.00     0.00  _GLOBAL__sub_I_main
    
     %         the percentage of the total running time of the
    time       program used by this function.
    
    cumulative a running sum of the number of seconds accounted
     seconds   for by this function and those listed above it.
    
     self      the number of seconds accounted for by this
    seconds    function alone.  This is the major sort for this
               listing.
    
    calls      the number of times this function was invoked, if
               this function is profiled, else blank.
     
     self      the average number of milliseconds spent in this
    ms/call    function per call, if this function is profiled,
           else blank.
    
     total     the average number of milliseconds spent in this
    ms/call    function and its descendents per call, if this 
           function is profiled, else blank.
    
    name       the name of the function.  This is the minor sort
               for this listing. The index shows the location of
           the function in the gprof listing. If the index is
           in parenthesis it shows where it would appear in
           the gprof listing if it were to be printed.
    
                 Call graph (explanation follows)
    
    
    granularity: each sample hit covers 2 byte(s) for 0.06% of 16.96 seconds
    
    index % time    self  children    called     name
                    0.00   15.74   39600/39600       Graph::initialize(int, int) [2]
    [1]     92.8    0.00   15.74   39600         Graph::addEdge(Edge&) [1]
                    1.22   13.26   39600/39600       Graph::getPos(Edge const&) [3]
                    0.00    1.16   39600/39600       Graph::addVertex(Vertex&) [8]
                    0.00    0.08   39600/39600       Vertex::addAdjEdge(Edge&) [12]
                    0.02    0.00   19800/178200      Edge::Edge(Edge const&) [11]
                    0.00    0.00      16/16          _ZNSt6vectorIP4EdgeSaIS1_EE19_M_emplace_back_auxIJRKS1_EEEvDpOT_ [31]
    -----------------------------------------------
                                                     <spontaneous>
    [2]     92.8    0.00   15.74                 Graph::initialize(int, int) [2]
                    0.00   15.74   39600/39600       Graph::addEdge(Edge&) [1]
                    0.00    0.00   49600/49600       Vertex::Vertex(int, int) [27]
                    0.00    0.00   49600/138800      Vertex::~Vertex() [23]
                    0.00    0.00   39600/39600       Edge::Edge(Vertex&, Vertex&) [28]
                    0.00    0.00   39600/217800      Edge::~Edge() [22]
    -----------------------------------------------
                    1.22   13.26   39600/39600       Graph::addEdge(Edge&) [1]
    [3]     85.4    1.22   13.26   39600         Graph::getPos(Edge const&) [3]
                    7.46    5.73 392040000/392098804     Edge::operator==(Edge const&) const [4]
                    0.08    0.00   79200/178200      Edge::Edge(Edge const&) [11]
                    0.00    0.00   79200/217800      Edge::~Edge() [22]
    -----------------------------------------------
                    0.00    0.00   58804/392098804     Vertex::getAdjEdge(Edge const&) [13]
                    7.46    5.73 392040000/392098804     Graph::getPos(Edge const&) [3]
    [4]     77.7    7.46    5.73 392098804         Edge::operator==(Edge const&) const [4]
                    2.30    3.43 392148007/392326207     Edge::getOther(Vertex const&) const [5]
    -----------------------------------------------
                    0.00    0.00  178200/392326207     Edge::Edge(Edge const&) [11]
                    2.30    3.43 392148007/392326207     Edge::operator==(Edge const&) const [4]
    [5]     33.8    2.30    3.44 392326207         Edge::getOther(Vertex const&) const [5]
                    3.44    0.00 784434812/982439662     Vertex::operator==(Vertex const&) const [6]
    -----------------------------------------------
                    0.87    0.00 198004850/982439662     Graph::getPos(Vertex const&) [7]
                    3.44    0.00 784434812/982439662     Edge::getOther(Vertex const&) const [5]
    [6]     25.4    4.30    0.00 982439662         Vertex::operator==(Vertex const&) const [6]
    -----------------------------------------------
                    0.29    0.87   39600/39600       Graph::addVertex(Vertex&) [8]
    [7]      6.8    0.29    0.87   39600         Graph::getPos(Vertex const&) [7]
                    0.87    0.00 198004850/982439662     Vertex::operator==(Vertex const&) const [6]
                    0.00    0.00   79200/89200       Vertex::Vertex(Vertex const&) [24]
                    0.00    0.00   79200/138800      Vertex::~Vertex() [23]
    -----------------------------------------------
                    0.00    1.16   39600/39600       Graph::addEdge(Edge&) [1]
    [8]      6.8    0.00    1.16   39600         Graph::addVertex(Vertex&) [8]
                    0.29    0.87   39600/39600       Graph::getPos(Vertex const&) [7]
                    0.00    0.00   10000/89200       Vertex::Vertex(Vertex const&) [24]
                    0.00    0.00      15/15          void std::vector<Vertex*, std::allocator<Vertex*> >::_M_emplace_back_aux<Vertex* const&>(Vertex* const&) [32]
    -----------------------------------------------
                                                     <spontaneous>
    [9]      5.9    1.00    0.00                 operator<<(std::ostream&, Vertex const&) [9]
    -----------------------------------------------
                                                     <spontaneous>
    [10]     1.3    0.22    0.00                 Edge::getVertex() const [10]
    -----------------------------------------------
                    0.02    0.00   19800/178200      Graph::addEdge(Edge&) [1]
                    0.08    0.00   79200/178200      Graph::getPos(Edge const&) [3]
                    0.08    0.00   79200/178200      Vertex::getAdjEdge(Edge const&) [13]
    [11]     1.0    0.17    0.00  178200         Edge::Edge(Edge const&) [11]
                    0.00    0.00  178200/392326207     Edge::getOther(Vertex const&) const [5]
    -----------------------------------------------
                    0.00    0.08   39600/39600       Graph::addEdge(Edge&) [1]
    [12]     0.5    0.00    0.08   39600         Vertex::addAdjEdge(Edge&) [12]
                    0.00    0.08   39600/39600       Vertex::getAdjEdge(Edge const&) [13]
                    0.00    0.00   29996/29996       _ZNSt6vectorIP4EdgeSaIS1_EE19_M_emplace_back_auxIJS1_EEEvDpOT_ [30]
    -----------------------------------------------
                    0.00    0.08   39600/39600       Vertex::addAdjEdge(Edge&) [12]
    [13]     0.5    0.00    0.08   39600         Vertex::getAdjEdge(Edge const&) [13]
                    0.08    0.00   79200/178200      Edge::Edge(Edge const&) [11]
                    0.00    0.00   58804/392098804     Edge::operator==(Edge const&) const [4]
                    0.00    0.00   79200/217800      Edge::~Edge() [22]
    -----------------------------------------------
                                                     <spontaneous>
    [14]     0.1    0.01    0.00                 Graph::printVertices() [14]
    -----------------------------------------------
                    0.00    0.00   19800/217800      Graph::clear() [39]
                    0.00    0.00   39600/217800      Graph::initialize(int, int) [2]
                    0.00    0.00   79200/217800      Graph::getPos(Edge const&) [3]
                    0.00    0.00   79200/217800      Vertex::getAdjEdge(Edge const&) [13]
    [22]     0.0    0.00    0.00  217800         Edge::~Edge() [22]
    -----------------------------------------------
                    0.00    0.00   10000/138800      Graph::clear() [39]
                    0.00    0.00   49600/138800      Graph::initialize(int, int) [2]
                    0.00    0.00   79200/138800      Graph::getPos(Vertex const&) [7]
    [23]     0.0    0.00    0.00  138800         Vertex::~Vertex() [23]
    -----------------------------------------------
                    0.00    0.00   10000/89200       Graph::addVertex(Vertex&) [8]
                    0.00    0.00   79200/89200       Graph::getPos(Vertex const&) [7]
    [24]     0.0    0.00    0.00   89200         Vertex::Vertex(Vertex const&) [24]
    -----------------------------------------------
                    0.00    0.00   79200/79200       Edge::weightFormula(Vertex const&, Vertex const&) const [29]
    [25]     0.0    0.00    0.00   79200         Vertex::getX() const [25]
    -----------------------------------------------
                    0.00    0.00   79200/79200       Edge::weightFormula(Vertex const&, Vertex const&) const [29]
    [26]     0.0    0.00    0.00   79200         Vertex::getY() const [26]
    -----------------------------------------------
                    0.00    0.00   49600/49600       Graph::initialize(int, int) [2]
    [27]     0.0    0.00    0.00   49600         Vertex::Vertex(int, int) [27]
    -----------------------------------------------
                    0.00    0.00   39600/39600       Graph::initialize(int, int) [2]
    [28]     0.0    0.00    0.00   39600         Edge::Edge(Vertex&, Vertex&) [28]
                    0.00    0.00   39600/39600       Edge::weightFormula(Vertex const&, Vertex const&) const [29]
    -----------------------------------------------
                    0.00    0.00   39600/39600       Edge::Edge(Vertex&, Vertex&) [28]
    [29]     0.0    0.00    0.00   39600         Edge::weightFormula(Vertex const&, Vertex const&) const [29]
                    0.00    0.00   79200/79200       Vertex::getX() const [25]
                    0.00    0.00   79200/79200       Vertex::getY() const [26]
    -----------------------------------------------
                    0.00    0.00   29996/29996       Vertex::addAdjEdge(Edge&) [12]
    [30]     0.0    0.00    0.00   29996         _ZNSt6vectorIP4EdgeSaIS1_EE19_M_emplace_back_auxIJS1_EEEvDpOT_ [30]
    -----------------------------------------------
                    0.00    0.00      16/16          Graph::addEdge(Edge&) [1]
    [31]     0.0    0.00    0.00      16         _ZNSt6vectorIP4EdgeSaIS1_EE19_M_emplace_back_auxIJRKS1_EEEvDpOT_ [31]
    -----------------------------------------------
                    0.00    0.00      15/15          Graph::addVertex(Vertex&) [8]
    [32]     0.0    0.00    0.00      15         void std::vector<Vertex*, std::allocator<Vertex*> >::_M_emplace_back_aux<Vertex* const&>(Vertex* const&) [32]
    -----------------------------------------------
                    0.00    0.00       1/1           __libc_csu_init [61]
    [33]     0.0    0.00    0.00       1         _GLOBAL__sub_I__ZN4EdgeC2Ev [33]
    -----------------------------------------------
                    0.00    0.00       1/1           __libc_csu_init [61]
    [34]     0.0    0.00    0.00       1         _GLOBAL__sub_I__ZN5GraphC2Ev [34]
    -----------------------------------------------
                    0.00    0.00       1/1           __libc_csu_init [61]
    [35]     0.0    0.00    0.00       1         _GLOBAL__sub_I__ZN6VertexC2Ev [35]
    -----------------------------------------------
                    0.00    0.00       1/1           __libc_csu_init [61]
    [36]     0.0    0.00    0.00       1         _GLOBAL__sub_I_main [36]
    -----------------------------------------------
    
     This table describes the call tree of the program, and was sorted by
     the total amount of time spent in each function and its children.
    
     Each entry in this table consists of several lines.  The line with the
     index number at the left hand margin lists the current function.
     The lines above it list the functions that called this function,
     and the lines below it list the functions this one called.
     This line lists:
         index    A unique number given to each element of the table.
            Index numbers are sorted numerically.
            The index number is printed next to every function name so
            it is easier to look up where the function in the table.
    
         % time    This is the percentage of the `total' time that was spent
            in this function and its children.  Note that due to
            different viewpoints, functions excluded by options, etc,
            these numbers will NOT add up to 100%.
    
         self    This is the total amount of time spent in this function.
    
         children    This is the total amount of time propagated into this
            function by its children.
    
         called    This is the number of times the function was called.
            If the function called itself recursively, the number
            only includes non-recursive calls, and is followed by
            a `+' and the number of recursive calls.
    
         name    The name of the current function.  The index number is
            printed after it.  If the function is a member of a
            cycle, the cycle number is printed between the
            function's name and the index number.
    
    
     For the function's parents, the fields have the following meanings:
    
         self    This is the amount of time that was propagated directly
            from the function into this parent.
    
         children    This is the amount of time that was propagated from
            the function's children into this parent.
    
         called    This is the number of times this parent called the
            function `/' the total number of times the function
            was called.  Recursive calls to the function are not
            included in the number after the `/'.
    
         name    This is the name of the parent.  The parent's index
            number is printed after it.  If the parent is a
            member of a cycle, the cycle number is printed between
            the name and the index number.
    
     If the parents of the function cannot be determined, the word
     `<spontaneous>' is printed in the `name' field, and all the other
     fields are blank.
    
     For the function's children, the fields have the following meanings:
    
         self    This is the amount of time that was propagated directly
            from the child into the function.
    
         children    This is the amount of time that was propagated from the
            child's children to the function.
    
         called    This is the number of times the function called
            this child `/' the total number of times the child
            was called.  Recursive calls by the child are not
            listed in the number after the `/'.
    
         name    This is the name of the child.  The child's index
            number is printed after it.  If the child is a
            member of a cycle, the cycle number is printed
            between the name and the index number.
    
     If there are any cycles (circles) in the call graph, there is an
     entry for the cycle-as-a-whole.  This entry shows who called the
     cycle (as parents) and the members of the cycle (as children.)
     The `+' recursive calls entry shows the number of function calls that
     were internal to the cycle, and the calls entry for each member shows,
     for that member, how many times it was called from other members of
     the cycle.
    
    
    Index by function name
    
      [33] _GLOBAL__sub_I__ZN4EdgeC2Ev [1] Graph::addEdge(Edge&) [4] Edge::operator==(Edge const&) const
      [34] _GLOBAL__sub_I__ZN5GraphC2Ev [8] Graph::addVertex(Vertex&) [25] Vertex::getX() const
      [35] _GLOBAL__sub_I__ZN6VertexC2Ev [12] Vertex::addAdjEdge(Edge&) [26] Vertex::getY() const
      [36] _GLOBAL__sub_I_main    [13] Vertex::getAdjEdge(Edge const&) [6] Vertex::operator==(Vertex const&) const
      [28] Edge::Edge(Vertex&, Vertex&) [24] Vertex::Vertex(Vertex const&) [31] _ZNSt6vectorIP4EdgeSaIS1_EE19_M_emplace_back_auxIJRKS1_EEEvDpOT_
      [11] Edge::Edge(Edge const&) [27] Vertex::Vertex(int, int) [30] _ZNSt6vectorIP4EdgeSaIS1_EE19_M_emplace_back_auxIJS1_EEEvDpOT_
      [22] Edge::~Edge()          [23] Vertex::~Vertex()      [32] void std::vector<Vertex*, std::allocator<Vertex*> >::_M_emplace_back_aux<Vertex* const&>(Vertex* const&)
      [14] Graph::printVertices() [29] Edge::weightFormula(Vertex const&, Vertex const&) const [9] operator<<(std::ostream&, Vertex const&)
       [3] Graph::getPos(Edge const&) [5] Edge::getOther(Vertex const&) const
       [7] Graph::getPos(Vertex const&) [10] Edge::getVertex() const

  8. #8
    Ngày gia nhập
    07 2011
    Bài viết
    474

    vector::push_back() là O(n)
    gì đây cha nội =.=!

  9. #9
    Ngày gia nhập
    01 2013
    Bài viết
    1,479

    Trích dẫn Nguyên bản được gửi bởi rox_rook Xem bài viết
    @prog10: Tại sao không được dùng OOP hay design pattern ở đây? Mấy cái library của bạn dùng (STL, boost) nó dùng cái gì nhỉ?
    Cồng kềnh hay không là do cách design, chứ không phải do OOP.
    Dùng STL để ko phải "reinvent the wheel" (đồng thời tận dụng được hiệu năng).
    Có thể so sánh 1 trình giải PT bậc 2 với C và cũng chương trình đó viết bằng Java.
    Đã được chỉnh sửa lần cuối bởi prog10 : 05-09-2013 lúc 05:50 AM.

  10. #10
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    @prog10: Lung tung quá, ở đây là OOP design, chẳng có liên quan gì tới dùng STL hay không hết.
    Hơn nữa trong STL không có nhiều data-structure ví dụ thằng graph, đó là lý do tại sao có boost.
    Về phần ngôn ngữ, C thì sao, Java thì sao, ngôn ngữ nào cũng là tool thôi, viết bad/elegant thế nào là do người viết.
    Với lại code không phải cứ fully STL là good code, C++ nó powerful với template pattern, tuy nhiên dùng không đúng chỗ thì đẻ ra là một mớ bong bong mà thôi.

Các đề tài tương tự

  1. vẽ Graph theo thời gian thực bằng ZedGraph
    Gửi bởi boy_lonely_0106 trong diễn đàn Nhập môn lập trình C#, ASP.NET
    Trả lời: 0
    Bài viết cuối: 15-09-2013, 10:45 AM
  2. Thử nghiệm công cụ tìm kiếm mới ra mắt của face: Công cụ Graph Search!
    Gửi bởi giacmotuyet trong diễn đàn Công cụ, ebooks C#, ASP.NET, và Windows Mobile
    Trả lời: 1
    Bài viết cuối: 22-01-2013, 03:50 PM
  3. Tìm đường dài nhất trong đồ thị ko hướng (undirected graph)
    Gửi bởi HoangManhHa1991 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 12
    Bài viết cuối: 27-04-2011, 10:43 PM
  4. Tạo class Graph (lớp đồ thị) như thế nào ?
    Gửi bởi newbie.blind trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 2
    Bài viết cuối: 19-10-2010, 09:39 PM
  5. Xin tài liệu về các thuật toán trong graph
    Gửi bởi Red_Man trong diễn đàn Tài liệu, ebooks và công cụ
    Trả lời: 1
    Bài viết cuối: 01-12-2008, 06:16 PM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn