Trang 2 trên tổng số 2 Đầu tiênĐầu tiên 12
Từ 11 tới 19 trên tổng số 19 kết quả

Đề tài: Graph structure

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

    Mặc định Graph structure

    Trước hết xin cảm ơn mọi người đã quan tâm.
    Mình thấy rất vui, không ngờ cái Graph cùi mía của mình lại được nhiều người góp ý đến vậy
    Đoạn code trên mình vừa mới kịp hoàn thành chiều qua thì up luôn. do trước đó code với template rồi abstract class mất rất nhiều time.
    Code trên cũng chưa có catch exception gì cả, vì quả thật mình không có nhiều time, sắp phỏng vấn, nên đoạn đó mình tạm ignore. Và hơn nữa để catch exception thật rõ ràng và hiệu quả cũng không phải là chuyên nhỏ
    Đúng là trước đó mình chỉ làm với Java, 2 lần làm game offline cũng sử dụng Graph và thuật toán Dijsktra nên lúc quay sang C+ quản lý cấp phát + giải phóng khiến mình thực sự rối trí.
    Mình sẽ nâng cấp dần dần để có thể implement Graph trên với nhiều dạng Direct, Undirect... tuy nhiên trước đó phải sửa lại phần add + remove cho đúng đã vì mình cũng thấy cứ mỗi lần add/remove lại phải find_if thì bó tay.
    @rr: có vài chỗ mong bạn giải thích giùm
    Nếu constructor/destructor không dùng, tại sao không để default?
    để default là như thế nào?
    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?
    Cái này mình có 2 ý tưởng, 1 là dùng function pointer, 2 là design tốt hơn để có thể implement cho tất cả các đường conic. Tuy nhiên như đã trình bày, trước mắt mình muốn cải thiện cái add/remove đã. Vấn đề performance mình chưa nghĩ tới nhiều, chủ yếu là cứ find_if mình thấy không phải là 1 cách hay.
    Line/Parabol = Geometry, và nó khác graph rất xa.
    Mình không hiểu lắm, 1 đường cong nếu mình implement đúng cách có thể bớt được khá nhiều Vertex bởi để biểu diễn 1 đường cong bởi các đường thẳng thì mình nghĩ parabol sẽ cho kết quả chuẩn xác và đỡ tốn kém hơn chứ.
    Ngoài ra trong 1 số game cần phải sử dụng parabol như 1 viên đạn pháo chẳng hạn, mình cần phải có tọa độ + độ dài + vận tốc thì mới tính được thời điểm viên đạn đó chạm mục tiêu? chưa kể có vật thể lạ dính vào đường bay của nó nữa.
    Hoặc có thể ý bạn là trong game người ta design Graph theo 1 cách khác?
    Thật ra đây chỉ là ý tưởng mới nghĩ ra và xem qua chứ chưa hề làm thực sự
    Dùng new/delete nhưng làm sao user biết khi nào mà delete?
    User tự quản lý new/delete vì khi add vào Graph thì nó đã được new thêm 1 lần nữa để Graph tự giải phóng khi không dùng đến rồi.
    @all: mình vẫn còn rất gà mờ về C+ nên khi bắt đầu design cái Graph trên mình có vài thắc mắc như sau: (cứ tạm bỏ qua exception và coding convention đi đã)
    Với hàm add nói chung. người ta có thể add theo 2 cách: cấp phát động và cấp phát tĩnh.
    Vậy nếu mình không copy vùng nhớ mới vào vector để Graph quản lý thì sao có thể phân biệt được khi giải phóng? tức là làm sao để đảm bảo không bị leak hoặc dangling pointer
    bởi mình có đọc vài quyển sách thì họ khuyên là cố gắng design sao cho cấp phát ở đâu thì giải phóng ở đó.
    ITNP có nói là dùng thẳng vector<Edge> thay vì vector<Edge *>, trước đó mình cũng đã từng nghĩ về việc này, tuy nhiên giả sử người ta cần copy Graph, thì vector<Edge*> chắc sẽ nhanh và dung lượng nhỏ hơn vector<Edge>
    Mình định sửa private của Edge thành **_ppv. tức là con trỏ trỏ tới con trỏ của Vertex. có ổn không nhỉ? cái này giúp khi mình muốn thay đổi 1 Vertex thì chỉ việc cho nó trỏ tới chỗ khác và tính lại weight là xong, không phải chỉnh sửa gì AdjEdge nữa

    Tóm lại: về cách design sẽ còn phải sửa, mình sẽ làm ngay thôi, tuy nhiên chỗ find_if..nên làm thế nào để cải thiện nó? mình chẳng có ý tưởng nào tốt hơn để tránh việc add trùng cả

    p/s: @INTP: làm sao gprof output đẹp vậy. mình vừa thử thì nó dài ngoằng, khó đọc quá
    Đã được chỉnh sửa lần cuối bởi quano1 : 05-09-2013 lúc 12:09 PM.

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

    Trích dẫn Nguyên bản được gửi bởi INTP Xem bài viết
    gì đây cha nội =.=!
    vector::push_back() khi thực hiện có hai trường hợp:
    - Vẫn còn chỗ trống, tức capacity() > size(): chỉ cần chèn vào phần trống chưa dùng là đủ
    - Hết chỗ trống. Lúc này cần phải cấp phát một vùng nhớ động mới lớn hơn cái cũ và copy tất cả các phần tử từ vùng nhớ cũ vào đây, sau đó mới chèn.
    Tổng hợp lại là O(n).




    Tham khảo:
    http://www.codeproject.com/Articles/...eque-Container
    http://www.baptiste-wicht.com/2012/1...or-list-deque/
    http://www.gotw.ca/gotw/054.htm

    Tất nhiên trong trường hợp biết trước số phần tử sẽ dùng thì vector cấp phát sẵn là nhanh nhất. Nếu như mà cái thư viện graph này cho phép chọn container được sử dụng bên trong (giống như std::stack) thì tốt.

    Trích dẫn Nguyên bản được gửi bởi quano1 Xem bài viết
    Tóm lại: về cách design sẽ còn phải sửa, mình sẽ làm ngay thôi, tuy nhiên chỗ find_if..nên làm thế nào để cải thiện nó? mình chẳng có ý tưởng nào tốt hơn để tránh việc add trùng cả
    Sử dụng bảng băm: unordered_set hoặc unordered_map tùy mục đích, thao tác tìm kiếm sẽ là O(1).

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

    @boss14420: Mặc dù worst case là O(n), average case không thể O(n) được, size grows double every time, analysis như vậy không chính xác. Algorithm analysis phải phân tích cả 3 cases:
    1) Worst (+ data analysis)
    2) Best (+ data analysis)
    3) Average (most practical)

    @quano1:
    1) Thường thì C++ nó có generate default constructor & destructor cho class, nếu bạn không có tính dùng thì hãy để compiler nó làm cho. Trong C++11 nó có 1 keyword là "default", bạn đọc về nó mà sử dụng.
    2) Trong C++, add behavior online thì dùng functor là gọn nhất và đẹp nhất. Sau này extend cũng dễ hơn. Kĩ thuật này mặc dù đặc trưng C++, nhưng rất thông dụng. Có nhiều pattern khác cũng có thể làm được điều này, Strategy chẳng hạn.
    3) Graph có vertex/edge... là Graph Data Structure, thằng này implement A* thì ok, tuy nhiên bạn tính gộp nó với những cái kia (đồ họa) thì không đúng. Những thằng kia thuộc domain khác (line, point, vector...) Gượng ép thì chắc cũng được nhưng code sẽ tối nghĩa và khó reuse.
    4) Không ai viết lib mà để user tự handle memory vậy được trừ khi document rõ ràng và low level! C++ có shared_ptr, unique_ptr, tại sao không dùng? Và trong code bạn, có vẻ bạn chưa hiểu mục tiêu của destructor cho lắm. Chưa kể cái này chỉ là internal memory thôi, sau này game load external resources như bitmap, database thì sao?
    5) Muốn leak free phải check kĩ code path, viết destructor để nó handle deallocation, tuy nhiên exception throws vẫn có thể cause leakage, cách tốt nhất là dùng shared_ptr, hoặc vọc cái implementation của shared_ptr mà sử dụng.
    6) Bất cứ khi nào viết software/library/...., bạn search mà dùng O(n) là code đó smells very bad, unless it must be! Như nhiều bạn đã gợi ý, dùng hash là hợp lý nhất.
    7) Correctness >>>>> performance. Viết cho code cho đúng cái đã + test cover rồi hãy optimize.
    8) Nếu dùng vector<Edge>, thì dùng std::move(), tuy nhiên dùng pointer thì sẽ nhẹ hơn. Không thì disallow copy.
    9) Lastly, Graph data structure != Geometry.
    Đã được chỉnh sửa lần cuối bởi rox_rook : 05-09-2013 lúc 01:25 PM.

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

    Trích dẫn Nguyên bản được gửi bởi rox_rook Xem bài viết
    @boss14420: Mặc dù worst case là O(n), average case không thể O(n) được, size grows double every time, analysis như vậy không chính xác. Algorithm analysis phải phân tích cả 3 cases:
    1) Worst (+ data analysis)
    2) Best (+ data analysis)
    3) Average (most practical)
    Ý nghĩa của O() là chặn trên mà, 1 trường hợp Công thức toán học Latex, một trường hợp thì Công thức toán học Latex. Tức là O(n) vẫn đúng. Thậm chỉ nói là O(n^2) cũng chẳng sai.
    Còn theo cppreference thì trung bình là Công thức toán học Latex.

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

    Đúng là chính xác thì có 3 cái big:
    1) big O
    2) big Theta
    3) big Gama
    Tuy nhiên khi nói general term trong thuật toán thì người ta dùng O tương đương với Theta vì khó type. Nếu bạn hiểu O() là strict O() thì cũng chẳng sao, nhưng dễ gây confusion.

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

    Mặc định Graph structure

    Trong C++, add behavior online thì dùng functor là gọn nhất và đẹp nhất
    việc này thì nên design như thế nào? mình hiểu ý của rr nhưng không biết nên làm sao :|
    ví dụ: design lại kiểu như sau:
    C++ Code:
    1. #include <iostream>
    2. #include <stdlib.h>
    3. using namespace std;
    4.  
    5. class Point2D {
    6. public:
    7.     float x, y;
    8.     Point2D():x(0),y(0){};
    9.     Point2D(float x, float y):x(x),y(y) {};
    10.     float getX()const{return x;};
    11.     float getY()const{return y;};
    12.     friend ostream &operator<<(ostream &os, const Point2D  &p) { os<<"("<<p.getX()<<", "<<p.getY()<<")"; return os;};
    13. };
    14.  
    15. class LeftRight { // a left-right comparator
    16. public:
    17.     LeftRight(){};
    18.     bool operator()(const Point2D& p, const Point2D& q) const
    19.     { return p.getX() < q.getX(); }
    20. };
    21.  
    22. class BottomTop { // a bottom-top comparator
    23. public:
    24.     BottomTop(){};
    25.     bool operator()(const Point2D& p, const Point2D& q) const
    26.     { return p.getY() < q.getY(); }
    27. };
    28.  
    29.  
    30.  
    31. template <typename E, typename C> // element type and comparator
    32. void printSmaller(const E& p, const E& q, const C& isLess) {
    33.     cout << (isLess(p, q) ? p : q) << endl; // print the smaller of p and q
    34. }
    35.  
    36. /**/
    37. int main() {
    38.     Point2D p(1.3, 5.7), q(2.5, 0.6); // two points
    39.     //cout<<p.getX();
    40.  
    41.     LeftRight leftRight; // a left-right comparator
    42.     BottomTop bottomTop; // a bottom-top comparator
    43.     //cout<<leftRight(p,q)<<endl;
    44.     //cout<<bottomTop(p,q)<<endl;
    45.     printSmaller<Point2D, LeftRight>(p, q, leftRight); // outputs: (1.3, 5.7)
    46.     printSmaller<>(p, q, bottomTop); // outputs: (2.5, 0.6)
    47.     /**/
    48.     return 0;
    49. }
    tức là dùng template. Mình có ý tưởng khác là dùng abstract class với mẫu:
    C++ Code:
    1. float weightFormula(Vertex *v, Vertex *w)
    nhưng cách này thì chẳng khác gì function pointer
    rr có thể gợi ý chút được không?
    Không ai viết lib mà để user tự handle memory vậy được trừ khi document rõ ràng và low level!
    cái này mình chưa thực sự hiểu lắm. ví dụ như sau:
    C++ Code:
    1. Graph g; //cái này là lib
    2. Vertex *v = new Vertex(1,2);
    3. g.addVertex(*v);
    4. delete v; //ý rr là mình handle việc này?
    Bất cứ khi nào viết software/library/...., bạn search mà dùng O(n) là code đó smells very bad, unless it must be! Như nhiều bạn đã gợi ý, dùng hash là hợp lý nhất
    mình không nghĩ ra hash nhỉ, tệ thật đó.
    unordered_map có vẻ hợp lý trong trường hợp này

    mình tính tự code hashfunction để gen key cho hash (có thể là kiểu int). Tuy nhiên search example thấy hầu như toàn dùng std::string
    cho mình hỏi các bạn là key giữa string và int có sự khác biệt lớn về performance không?
    Đã được chỉnh sửa lần cuối bởi quano1 : 05-09-2013 lúc 06:09 PM.

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

    @boss14420: nó là constant amortized time. Tuy nó có Big-O(n) thật nhưng chỉ xảy ra rất ít, push_back 1024 lần chỉ xảy ra có 10 lần, push_back 2^20 ~ 1 triệu lần chỉ xảy ra có 20 lần. Tổng hợp lại có thể xem là O(1).
    http://en.cppreference.com/w/cpp/con...ctor/push_back

    và deque::push_back cũng là constant amortized time:
    http://en.cppreference.com/w/cpp/con...eque/push_back

    (deque có lẽ là implement bằng 2 vector mảng phải ko nhỉ? Nếu vậy thì push_back của nó cũng có Big-O(n). Làm sao nó luôn luôn Big-O(1) được, trừ phi implement như linked list. Và nếu là linked list thì ko thể sử dụng operator[] được.)



    * implement bằng nhiều mảng có size cố định. Vậy là mỗi lần push_back vào thì tệ nhất chỉ cần cấp phát mảng mới size cố định và ko cần copy cả đống cái có sẵn ròi. vậy thì Big-O(1) thật =.= Nhưng mà vậy thì chắc chắn opertor[] sẽ chậm hơn.
    Đã được chỉnh sửa lần cuối bởi INTP : 05-09-2013 lúc 10:52 PM.

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

    @quano1: bạn từ Java chuyển sang C++ à?

    cái này chắc 90% java @.@ trừ cái phải delete ra.
    Graph g; //cái này là lib
    Vertex *v = new Vertex(1,2);
    g.addVertex(*v);
    delete v; //ý rr là mình handle việc này?

    C++:
    Graph g;
    Vertex v(1,2);
    g.addVertex(v);

    tùy g.addVertex có argument là const ref hay ref mà pass v "khác" nhau. Nếu chỉ reference mà ko có const thì như trên, còn có const ref rồi thì khỏi cần biến v dummy:
    Graph g;
    g.addVertex(Vertex(1,2));


    Nếu v là biến tạm thời thì ko cần cấp phát động cho nó làm gì. Khác với Java, object nào cũng nằm trên heap hết nên phải khai báo new mỗi lần khai báo 1 object trong Java, trừ mấy primitive types ra thôi. Còn C++ thì bạn có 2 lựa chọn, có thể cho object nằm trên stack hoặc heap nên nhiều người nói là C++ luôn luôn nhanh hơn Java là vậy @.@ Vì vậy khi xài C++ thì luôn luôn cấp phát tĩnh, nếu ko được hoặc object/mảng quá lón/ko cố định thì mới xài cấp phát động.
    Đã được chỉnh sửa lần cuối bởi INTP : 05-09-2013 lúc 11:05 PM.

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

    hèn gì, mình cứ thắc mắc sao ông rr nhìn vào cái là phát hiện ra giống Java.
    Nếu v là biến tạm thời thì ko cần cấp phát động cho nó làm gì. Khác với Java, object nào cũng nằm trên heap hết nên phải khai báo new mỗi lần khai báo 1 object trong Java, trừ mấy primitive types ra thôi. Còn C++ thì bạn có 2 lựa chọn, có thể cho object nằm trên stack hoặc heap nên nhiều người nói là C++ luôn luôn nhanh hơn Java là vậy @.@ Vì vậy khi xài C++ thì luôn luôn cấp phát tĩnh, nếu ko được hoặc object/mảng quá lón/ko cố định thì mới xài cấp phát động.
    thank INTP
    mình có vài thắc mắc về vấn đề này. để lập topic mới hỏi cho rõ hơn xem sao.

    sau khi đọc kỹ lại vài lần thì mình rút ra kết luận:
    -sử dụng share_ptr, unique_ptr và unordered_map (C++ có lib nào sinh cho mình perfect hash không?)
    -sửa lại toàn bộ những chỗ cấp phát và giải phóng (tuy nhiên vẫn chưa thực sự hiểu ý nghĩa câu nói của rr: "không để user handle" ^^! )
    -design lại với functor (cái này vẫn chưa có hướng nào khả quan, mọi người có gợi ý gì không? example thì càng hay)
    Đã được chỉnh sửa lần cuối bởi quano1 : 06-09-2013 lúc 03:39 AM.

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