Từ 1 tới 10 trên tổng số 10 kết quả

Đề tài: Từ điển Anh-Việt dùng cây 26 phân

  1. #1
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất nhiều sóng gió
    Bài viết
    442

    Mặc định Từ điển Anh-Việt dùng cây 26 phân

    Đây là một phần mình viết hộ một người bạn để giải 1 bài tập. Nội dung là một từ điển Anh-Việt thực hiện bằng một cây 26 phân, tức là cây mà mỗi node có 26 nhánh con, mỗi nhánh tương ứng với 1 chữ cái trong bảng chữ cái Anh, cũng tương tự như cấu trúc dữ liệu tạo ra trong thuật toán sắp xếp theo cơ số (radix sort) 26. Thời gian tìm kiếm, chèn và xóa tỉ lệ thuận với độ dài của từ cần tìm.

    Mình dùng 3 kĩ thuật nho nhỏ để tiết kiệm bộ nhớ. Thứ nhất, node chỉ chứa giá trị (phần giải nghĩa tiếng Việt) chứ không chứa khóa (từ tiếng Anh). Thứ hai, mảng 26 nhánh con là một vector co giãn được tùy theo yêu cầu chứ không nhất thiết có cả 26 nhánh. Thứ ba, để giữ cho vector này càng nhỏ càng tốt, các chữ cái Anh thường dùng nhất (trong tiếng Anh) được đưa lên đầu của bảng mã còn các chữ cái ít dùng thì dồn xuống cuối bảng mã. Nói cách khác, bên trong từ điển, các chữ cái Anh được mã hóa theo thứ tự tần suất sử dụng từ cao đến thấp (kí tự 'e' đứng đầu bảng mã, tiếp theo là kí tự 't', v.v..., kí tự 'z' đứng cuối bảng).

    Mình gửi code lên đây, hi vọng có ích cho các bạn mới học C++ cần giải các bài tập tương tự.

    Code đã được test một phần, xem testTree() trong mã nguồn.

    C++ Code:
    1. #include <string>
    2. #include <vector>
    3. #include <map>
    4. #include <iostream>
    5. #include <fstream>
    6. #include <ctype.h>
    7. #include <assert.h>
    8.  
    9. using namespace std;
    10.  
    11. ////////////////////////////////////////////////////////////////////////////////////
    12. // Tree -- a 26-ary tree
    13.  
    14. class Tree
    15. {
    16. public:
    17.  
    18.     // todo: viet not cac constructor, destructor
    19.     // Tree();
    20.     // Tree(Tree&);
    21.     //~Tree();
    22.  
    23.     string *search(const string& key) const;
    24.     void insert(const string& key, const string& value);
    25.     void remove(const string& key);
    26.     string& operator[](const string& key);  // search and inserts (key,emptystring) to tree, if needed
    27.     void list(ostream& os) const;
    28.     bool isEmpty() const;
    29.     int  nWords() const;                    // number of occupied nodes, i.e. #keywords in this Tree
    30.     int  nNodes() const;
    31.     void takeStat(map<int,int>& stSize, map<int,int>& stCapacity) const; // statistic of memory usage (size)
    32.       // and actual memory usage (capacity) for the overhead (i.e. all except data) of this tree
    33.     static bool isaWord(const string& key); // check that 'key' is a valid word -- must contain letters only
    34.  
    35. private:
    36.     string data;
    37.     vector<Tree*> subtrees;
    38.     bool isOccupied() const;                // this node, not the entire tree, is occupied
    39.     void list(ostream& os, string& stack) const;
    40.     void search(const char *&key,  Tree const *& tree) const;
    41.     void insert(const char *key, const string& s);
    42.     void remove(const char *key);
    43.  
    44.     static const int nLetters = 'z' - 'a' + 1; // 26 letters
    45.  
    46.     static int encode(int x)
    47.     {
    48.         char enc[]=
    49.         //   a  b  c  d  e  f  g  h  i  j  k  l  m  n  o  p  q  r  s  t  u  v  w  x  y  z
    50.             {2,19,11, 9, 0,15,16, 7, 4,22,21,10,13, 5, 3,18,24, 8, 6, 1,12,20,14,23,17,25};
    51.         x = tolower(x);
    52.         assert('a' <= x && x <= 'z' );
    53.         return enc[x - 'a'];
    54.     }
    55.  
    56.     static int decode(int y)
    57.     {
    58.         char dec[]="etaoinshrdlcumwfgypbvkjxqz";
    59.         assert(0 <= y && y < nLetters);
    60.         return dec[y];
    61.     }
    62. };
    63.  
    64. string *Tree::search(const string& key) const
    65. {
    66.     const char *key1 = key.c_str();
    67.     const Tree *tree;
    68.     search(key1,tree);
    69.     if (*key1 || !tree->isOccupied()) return NULL;
    70.     return const_cast<string*>(&tree->data);
    71. }
    72.  
    73. void Tree::search(const char *&key, Tree const* & tree) const
    74. {
    75.     int k = encode(*key);
    76.     if (*key && int(subtrees.size())>k && subtrees[k])
    77.     {
    78.         subtrees[k]->search(++key,tree);
    79.     }
    80.     else tree = this;
    81. }
    82.  
    83. string& Tree::operator[](const string& key)
    84. {
    85.     const char *key1 = key.c_str();
    86.     Tree *tree;
    87.     search(key1,(const Tree*&)tree);
    88.     if (*key1 || !tree->isOccupied()) tree->insert(key1,"");
    89.     return tree->data;
    90. }
    91.  
    92. void Tree::insert(const string& key, const string& s)
    93. {
    94.     insert(key.c_str(),s);
    95. }
    96.  
    97. void Tree::insert(const char *key, const string& s)
    98. {
    99.     if (*key == 0)
    100.     {
    101.         data = s;
    102.     }
    103.     else
    104.     {
    105.         int k = encode(*key);
    106.         if (!(int(subtrees.size())>k))
    107.         {
    108.             subtrees.resize(k+1,NULL);
    109.         }
    110.         if (!subtrees[k])
    111.         {
    112.             subtrees[k] = new Tree;
    113.         }
    114.         subtrees[k]->insert(key+1,s);
    115.     }
    116. }
    117.  
    118. void Tree::remove(const string& key)
    119. {
    120.     remove(key.c_str());
    121. }
    122.  
    123. void Tree::remove(const char *key)
    124. {
    125.     int k;
    126.     if (*key == 0)
    127.     {
    128.         data.clear();
    129.     }
    130.     else if (int(subtrees.size())>(k=encode(*key)) && subtrees[k])
    131.     {
    132.         subtrees[k]->remove(key+1);
    133.         if (subtrees[k]->isEmpty())
    134.         {
    135.             delete subtrees[k];
    136.             subtrees[k] = NULL;
    137.             int lastNonNullSubtree = -1;
    138.             for (k = int(subtrees.size())-1; k>=0; --k)
    139.                 if (subtrees[k])
    140.                 {
    141.                     lastNonNullSubtree = k;
    142.                     break;
    143.                 }
    144.             if(int(subtrees.size()) > lastNonNullSubtree+1)
    145.                 subtrees.resize(lastNonNullSubtree+1);
    146.         }
    147.     }
    148. }
    149.  
    150. void Tree::list(ostream& os) const
    151. {
    152.     string stack("");
    153.     list(os, stack);
    154. }
    155.  
    156. void Tree::list(ostream& os, string& stack) const
    157. {
    158.     if (isOccupied())
    159.     {
    160.         os << stack << ":";
    161.         os << data << endl;
    162.     }
    163.     for (int cx = 'a'; cx <= 'z'; cx++)
    164.     {
    165.         int cy = encode(cx);
    166.         if (int(subtrees.size())>cy && subtrees[cy])
    167.         {
    168.             stack.push_back(cx);
    169.             subtrees[cy]->list(os, stack);
    170.             stack.erase(stack.end()-1);
    171.         }
    172.     }
    173. }
    174.  
    175. bool Tree::isOccupied() const
    176. {
    177.     return !data.empty();
    178. }
    179.  
    180. bool Tree::isEmpty() const
    181. {
    182.     if (isOccupied()) return false;
    183.     for (size_t k=0; k<subtrees.size(); k++)
    184.         if (subtrees[k] && !subtrees[k]->isEmpty()) return false;
    185.     return true;
    186. }
    187.  
    188. int Tree::nWords() const
    189. {
    190.     int n = isOccupied()? 1 : 0;
    191.     for (size_t k=0; k<subtrees.size(); k++)
    192.         if (subtrees[k]) n+=subtrees[k]->nWords();
    193.     return n;
    194. }
    195.  
    196. int Tree::nNodes() const
    197. {
    198.     int n=1;
    199.     for (size_t k=0; k<subtrees.size(); k++)
    200.         if (subtrees[k]) n+=subtrees[k]->nNodes();
    201.     return n;
    202. }
    203.  
    204. void Tree::takeStat(map<int,int>& stSize, map<int,int>& stCapa) const
    205. {
    206.     int dNodeSize = sizeof(*this) - sizeof(data) + sizeof(Tree*) * subtrees.size();
    207.     stSize[dNodeSize]++;
    208.     int dNodeCapa = sizeof(*this) - sizeof(data) + sizeof(Tree*) * subtrees.capacity();
    209.     stCapa[dNodeCapa]++;
    210.     for(size_t k=0; k<subtrees.size(); k++)
    211.         if(subtrees[k]) subtrees[k]->takeStat(stSize,stCapa);
    212. }
    213.  
    214. bool Tree::isaWord(const string& key)
    215. {
    216.     for (size_t i=0; i<key.length(); i++)
    217.         if (!('a' <= tolower(key[i]) && tolower(key[i]) <= 'z')) return false;
    218.     return true;
    219. }
    220.  
    221. //////////////////////////////////////////////////////////////////////////////////////////
    222. // Tests
    223. #include <iostream>
    224. #include <iomanip>
    225. #include <algorithm>
    226. #include <functional>
    227. #include <vector>
    228. #include <set>
    229. #include <sstream>
    230. #include <ctime>
    231. #include <cstdlib>
    232.  
    233. unsigned genRandom(unsigned max) // generates a pseudo-random number in [0,max),
    234. // 'max' and return value may be declared as floats too
    235. {
    236.     static int const IM = 139968, IA = 3877, IC = 29573;
    237.     static int seed = 42;
    238.     return(max * (seed = (seed * IA + IC) % IM) / IM);
    239. }
    240.  
    241. ptrdiff_t random (ptrdiff_t i)
    242. {
    243.     return genRandom(i);
    244. }
    245.  
    246. ptrdiff_t (*p_random)(ptrdiff_t) = random;
    247.  
    248. bool isEqual(Tree const& tr1, Tree const& tr2)
    249. {
    250.     stringstream oss1(stringstream::in|stringstream::out);
    251.     stringstream oss2(stringstream::in|stringstream::out);
    252.     tr1.list(oss1);
    253.     tr2.list(oss2);
    254.     string s1,s2;
    255.     while (oss1 >> s1  &&  oss2 >> s2)
    256.     {
    257.         // cout << s1;
    258.         // cout << s2;
    259.         if (s1 != s2) return false;
    260.     }
    261.     return true;
    262. }
    263.  
    264. int loadWords(vector<string>& v, string const& filename)
    265. {
    266.     ifstream ifs(filename.c_str());
    267.     string w;
    268.     set<string> s;
    269.     while (ifs >> w)
    270.     {
    271.         if (Tree::isaWord(w) && s.find(w)==s.end())
    272.         {
    273.             v.push_back(w);
    274.             s.insert(w);
    275.         }
    276.         else cout << w << " ";
    277.     }
    278.     ifs.close();
    279.     cout << endl << filename << ":" << endl
    280.     << "#words=" << v.size() << " "
    281.     << "#distinct words=" << s.size() << endl;
    282.     return s.size();
    283. }
    284.  
    285. int listStat(map<int,int>& st)
    286. {
    287.     map<int,int>::iterator i;
    288.     int m=0, n=0;
    289.     cout << setw(10) << "nodesize" << setw(10) << "#nodes" << setw(10) << "amount" << endl;
    290.     for(i=st.begin(); i!=st.end(); i++)
    291.     {
    292.  
    293.         cout << setw(10) << i->first << setw(10) << i->second << setw(10) << (i->first * i->second) << endl;
    294.         m += i->first * i->second;
    295.         n += i->second;
    296.     }
    297.     cout << setw(10) << "Total:" << setw(10) << n << setw(10) << m << " bytes." << endl;
    298.     return m;
    299. }
    300.  
    301. void transferData(vector<string>& set0, vector<string>& set01, vector<string>& set1)
    302. {
    303.     // transfer a part of set0 to set1 and construct set01 as a delta list, i.e.
    304.     // set01 = random subset of set0, set0 -= set01, set1 += set01, set01 += random elements from set1
    305.     set01.clear();
    306.     random_shuffle(set0.begin(), set0.end(), p_random);
    307.     for(int n = genRandom(set0.size()+1); n; n--)
    308.     {
    309.         string w = set0.back();
    310.         set0.pop_back();
    311.         set01.push_back(w);
    312.     }
    313.     set1.insert(set1.end(),set01.begin(),set01.end());
    314.     for(int n = genRandom(1000); n; n--)
    315.     {
    316.         string w = set1[genRandom(set1.size())];
    317.         set01.push_back(w);
    318.     }
    319. }
    320.  
    321. void treeInsert(Tree& t, vector<string>& v)
    322. {
    323.     random_shuffle(v.begin(), v.end(), p_random);
    324.     for (size_t i=0; i<v.size(); i++)
    325.         t.insert(v[i],"giai nghia tieng Viet");
    326. }
    327.  
    328. void treeRemove(Tree&t, vector<string>& v)
    329. {
    330.     random_shuffle(v.begin(), v.end(), p_random);
    331.     for (size_t i=0; i<v.size(); i++)
    332.         t.remove(v[i]);
    333. }
    334.  
    335. #define DISPLAYCOUNTS  cout << "set0:" << set0.size() << " set01:" << set01.size() << " set1:" << set1.size() \
    336.                            << " ta:" << ta.nWords() << "/" << ta.nNodes() \
    337.                            << " tb:" << tb.nWords() << "/" << tb.nNodes() << endl;
    338. void testTree()
    339. {
    340.     vector<string> set0, set1, set01; // set0 maintains the list of out-tree words,
    341.                                       // set1 maintains the list of in-tree words,
    342.                                       // set01 is the delta list, ie. list of words
    343.                                       // to be inserted to tree or removed from tree
    344.  
    345.     map<int,int> st200size,st200capa, st2000size,st2000capa;
    346.     int nWords200,nWords2000;
    347.     bool st200taken=false,st2000taken=false;
    348.  
    349.     Tree ta,tb;
    350.  
    351.     loadWords(set0, "english-top1857words.txt");
    352.  
    353.     DISPLAYCOUNTS;
    354.     while(!(st200taken && st2000taken))
    355.     {
    356.         // set01 = random subset of set0, set0 -= set01, set1 += set01, set01 += more words from set1
    357.         transferData(set0,set01,set1);
    358.  
    359.         // ta += set01 shuffle, tb += set01 shuffle
    360.         treeInsert(ta,set01);
    361.         treeInsert(tb,set01);
    362.         if(1800 <= set1.size() && set1.size() <= 2200 && !st2000taken)
    363.         {
    364.             ta.takeStat(st2000size,st2000capa);
    365.             nWords2000=set1.size();
    366.             st2000taken = true;
    367.         }
    368.         DISPLAYCOUNTS;
    369.  
    370.         // set01 = random subset of set1, set1 -= set01, set0 += set01, set01 += more words from set0
    371.         transferData(set1,set01,set0);
    372.  
    373.         // ta -= set01 shuffle, tb -= set01 shuffle
    374.         treeRemove(ta,set01);
    375.         treeRemove(tb,set01);
    376.         if(180 <= set1.size() && set1.size() <= 220 && !st200taken)
    377.         {
    378.             ta.takeStat(st200size,st200capa);
    379.             nWords200=set1.size();
    380.             st200taken = true;
    381.         }
    382.         DISPLAYCOUNTS;
    383.  
    384.         assert(ta.nWords()==int(set1.size()) && tb.nWords()==int(set1.size()));
    385.         assert(isEqual(ta,tb));
    386.     }
    387.  
    388.     // insert the entire set0 to trees, i.e. set01=set0, set0 = emptyset, set1 += set01,
    389.     // ta += set01 shuffle, tb += set01 shuffle
    390.     set01 = set0;    set0.clear();  set1.insert(set1.end(),set01.begin(),set01.end());
    391.     treeInsert(ta,set01);
    392.     treeInsert(tb,set01);
    393.     DISPLAYCOUNTS;
    394.     assert(isEqual(ta,tb));
    395.  
    396.     // remove the entire set1 from trees, i.e. set01=set1, set0 += set01, set1 = emptyset,
    397.     // ta -= set01 shuffle, tb -= set01 shuffle
    398.     set01 = set1;    set1.clear();  set0.insert(set0.end(),set01.begin(),set01.end());
    399.     treeRemove(ta,set01);
    400.     treeRemove(tb,set01);
    401.     DISPLAYCOUNTS;
    402.     assert(isEqual(ta,tb));
    403.  
    404.     assert(ta.nNodes()==1 && tb.nNodes()==1);
    405.     assert(ta.nWords()==0 && tb.nWords()==0);
    406.     assert(ta.isEmpty() && tb.isEmpty());
    407.  
    408.     cout << endl << "Testing completed." << endl << endl;
    409.  
    410.     // display the tree size & capacity statistics taken before
    411.     cout << endl << "Tree size statistic @" << nWords200 << " words:" << endl; listStat(st200size);
    412.     cout << endl << "Tree capa statistic @" << nWords200 << " words:" << endl; listStat(st200capa);
    413.     cout << endl << "Tree size statistic @" << nWords2000<< " words:" << endl; listStat(st2000size);
    414.     cout << endl << "Tree capa statistic @" << nWords2000<< " words:" << endl; listStat(st2000capa);
    415. }
    416.  
    417. int main()
    418. {
    419.     testTree();
    420.     return 0;
    421. }

    Output Code:
    1. english-top1857words.txt:
    2. #words=1857 #distinct words=1857
    3. set0:1857 set01:0 set1:0 ta:0/1 tb:0/1
    4. set0:261 set01:2437 set1:1596 ta:1596/4490 tb:1596/4490
    5. set0:1181 set01:1151 set1:676 ta:676/2144 tb:676/2144
    6. set0:244 set01:1813 set1:1613 ta:1613/4533 tb:1613/4533
    7. set0:907 set01:910 set1:950 ta:950/2839 tb:950/2839
    8. set0:143 set01:1188 set1:1714 ta:1714/4766 tb:1714/4766
    9. set0:216 set01:756 set1:1641 ta:1641/4602 tb:1641/4602
    10. set0:74 set01:814 set1:1783 ta:1783/4923 tb:1783/4923
    11. set0:980 set01:1141 set1:877 ta:877/2708 tb:877/2708
    12. set0:845 set01:996 set1:1012 ta:1012/3054 tb:1012/3054
    13. set0:1025 set01:264 set1:832 ta:832/2591 tb:832/2591
    14. set0:982 set01:180 set1:875 ta:875/2705 tb:875/2705
    15. set0:1019 set01:581 set1:838 ta:838/2595 tb:838/2595
    16. set0:912 set01:293 set1:945 ta:945/2899 tb:945/2899
    17. set0:1078 set01:915 set1:779 ta:779/2455 tb:779/2455
    18. set0:2 set01:1232 set1:1855 ta:1855/5112 tb:1855/5112
    19. set0:723 set01:1294 set1:1134 ta:1134/3366 tb:1134/3366
    20. set0:430 set01:651 set1:1427 ta:1427/4044 tb:1427/4044
    21. set0:626 set01:450 set1:1231 ta:1231/3564 tb:1231/3564
    22. set0:108 set01:1278 set1:1749 ta:1749/4847 tb:1749/4847
    23. set0:1181 set01:1511 set1:676 ta:676/2202 tb:676/2202
    24. set0:909 set01:1034 set1:948 ta:948/2918 tb:948/2918
    25. set0:1513 set01:1480 set1:344 ta:344/1210 tb:344/1210
    26. set0:1383 set01:836 set1:474 ta:474/1597 tb:474/1597
    27. set0:1762 set01:1218 set1:95 ta:95/400 tb:95/400
    28. set0:789 set01:1968 set1:1068 ta:1068/3268 tb:1068/3268
    29. set0:1346 set01:953 set1:511 ta:511/1704 tb:511/1704
    30. set0:929 set01:665 set1:928 ta:928/2819 tb:928/2819
    31. set0:1090 set01:819 set1:767 ta:767/2392 tb:767/2392
    32. set0:540 set01:706 set1:1317 ta:1317/3824 tb:1317/3824
    33. set0:1762 set01:1616 set1:95 ta:95/398 tb:95/398
    34. set0:1199 set01:1506 set1:658 ta:658/2133 tb:658/2133
    35. set0:1377 set01:554 set1:480 ta:480/1598 tb:480/1598
    36. set0:515 set01:1217 set1:1342 ta:1342/3862 tb:1342/3862
    37. set0:732 set01:615 set1:1125 ta:1125/3287 tb:1125/3287
    38. set0:319 set01:702 set1:1538 ta:1538/4351 tb:1538/4351
    39. set0:908 set01:812 set1:949 ta:949/2902 tb:949/2902
    40. set0:174 set01:784 set1:1683 ta:1683/4699 tb:1683/4699
    41. set0:931 set01:1078 set1:926 ta:926/2820 tb:926/2820
    42. set0:604 set01:587 set1:1253 ta:1253/3656 tb:1253/3656
    43. set0:1015 set01:1322 set1:842 ta:842/2601 tb:842/2601
    44. set0:966 set01:617 set1:891 ta:891/2731 tb:891/2731
    45. set0:1001 set01:253 set1:856 ta:856/2635 tb:856/2635
    46. set0:160 set01:1036 set1:1697 ta:1697/4734 tb:1697/4734
    47. set0:583 set01:527 set1:1274 ta:1274/3699 tb:1274/3699
    48. set0:497 set01:966 set1:1360 ta:1360/3920 tb:1360/3920
    49. set0:1094 set01:1252 set1:763 ta:763/2434 tb:763/2434
    50. set0:922 set01:482 set1:935 ta:935/2863 tb:935/2863
    51. set0:1771 set01:1580 set1:86 ta:86/359 tb:86/359
    52. set0:172 set01:1630 set1:1685 ta:1685/4714 tb:1685/4714
    53. set0:1818 set01:2172 set1:39 ta:39/180 tb:39/180
    54. set0:1139 set01:1588 set1:718 ta:718/2323 tb:718/2323
    55. set0:1410 set01:744 set1:447 ta:447/1510 tb:447/1510
    56. set0:722 set01:1338 set1:1135 ta:1135/3367 tb:1135/3367
    57. set0:1071 set01:1090 set1:786 ta:786/2503 tb:786/2503
    58. set0:964 set01:774 set1:893 ta:893/2775 tb:893/2775
    59. set0:1537 set01:1478 set1:320 ta:320/1147 tb:320/1147
    60. set0:1145 set01:1129 set1:712 ta:712/2268 tb:712/2268
    61. set0:1393 set01:1019 set1:464 ta:464/1537 tb:464/1537
    62. set0:888 set01:1256 set1:969 ta:969/2960 tb:969/2960
    63. set0:1219 set01:954 set1:638 ta:638/2087 tb:638/2087
    64. set0:322 set01:1878 set1:1535 ta:1535/4367 tb:1535/4367
    65. set0:342 set01:915 set1:1515 ta:1515/4301 tb:1515/4301
    66. set0:302 set01:617 set1:1555 ta:1555/4401 tb:1555/4401
    67. set0:1421 set01:1444 set1:436 ta:436/1542 tb:436/1542
    68. set0:84 set01:1700 set1:1773 ta:1773/4936 tb:1773/4936
    69. set0:1491 set01:2139 set1:366 ta:366/1230 tb:366/1230
    70. set0:62 set01:2126 set1:1795 ta:1795/4983 tb:1795/4983
    71. set0:1109 set01:1730 set1:748 ta:748/2370 tb:748/2370
    72. set0:25 set01:1408 set1:1832 ta:1832/5052 tb:1832/5052
    73. set0:1768 set01:1771 set1:89 ta:89/381 tb:89/381
    74. set0:1477 set01:1217 set1:380 ta:380/1322 tb:380/1322
    75. set0:1697 set01:893 set1:160 ta:160/613 tb:160/613
    76. set0:229 set01:2084 set1:1628 ta:1628/4586 tb:1628/4586
    77. set0:1049 set01:824 set1:808 ta:808/2564 tb:808/2564
    78. set0:628 set01:553 set1:1229 ta:1229/3609 tb:1229/3609
    79. set0:1646 set01:1955 set1:211 ta:211/806 tb:211/806
    80. set0:0 set01:1646 set1:1857 ta:1857/5116 tb:1857/5116
    81. set0:1857 set01:1857 set1:0 ta:0/1 tb:0/1

    Testing completed.
    Testing Code:
    1. Tree size statistic @211 words:
    2.   nodesize    #nodes    amount
    3.         12       208      2496
    4.         16        77      1232
    5.         20        49       980
    6.         24        32       768
    7.         28        35       980
    8.         32        33      1056
    9.         36        38      1368
    10.         40        32      1280
    11.         44        11       484
    12.         48        57      2736
    13.         52        19       988
    14.         56        47      2632
    15.         60        18      1080
    16.         64        26      1664
    17.         68        19      1292
    18.         72        11       792
    19.         76         9       684
    20.         80        15      1200
    21.         84        22      1848
    22.         88        16      1408
    23.         92         8       736
    24.         96        10       960
    25.        100        10      1000
    26.        108         1       108
    27.        112         1       112
    28.        116         2       232
    29.     Total:       806     30116 bytes.
    30.  
    31. Tree capa statistic @211 words:
    32.   nodesize    #nodes    amount
    33.         12       191      2292
    34.         16        65      1040
    35.         20        42       840
    36.         24        19       456
    37.         28        27       756
    38.         32        28       896
    39.         36        36      1296
    40.         40        27      1080
    41.         44        10       440
    42.         48        44      2112
    43.         52        21      1092
    44.         56        35      1960
    45.         60        16       960
    46.         64        32      2048
    47.         68        16      1088
    48.         72         6       432
    49.         76        10       760
    50.         80        11       880
    51.         84        43      3612
    52.         88        16      1408
    53.         92        13      1196
    54.         96        12      1152
    55.        100        26      2600
    56.        108        13      1404
    57.        112         2       224
    58.        116        11      1276
    59.        124         7       868
    60.        132         5       660
    61.        140         3       420
    62.        148         2       296
    63.        156         1       156
    64.        164         6       984
    65.        172         3       516
    66.        180         5       900
    67.        188         1       188
    68.        204         1       204
    69.     Total:       806     38492 bytes.
    70.  
    71. Tree size statistic @1855 words:
    72.   nodesize    #nodes    amount
    73.         12      1698     20376
    74.         16       596      9536
    75.         20       298      5960
    76.         24       149      3576
    77.         28       136      3808
    78.         32       194      6208
    79.         36       241      8676
    80.         40       156      6240
    81.         44       117      5148
    82.         48       272     13056
    83.         52       135      7020
    84.         56       224     12544
    85.         60       123      7380
    86.         64       120      7680
    87.         68        66      4488
    88.         72        35      2520
    89.         76        33      2508
    90.         80       101      8080
    91.         84       127     10668
    92.         88        85      7480
    93.         92        36      3312
    94.         96        52      4992
    95.        100        83      8300
    96.        104         4       416
    97.        108         8       864
    98.        112         8       896
    99.        116        15      1740
    100.     Total:      5112    173472 bytes.
    101.  
    102. Tree capa statistic @1855 words:
    103.   nodesize    #nodes    amount
    104.         12      1698     20376
    105.         16       596      9536
    106.         20       298      5960
    107.         24       148      3552
    108.         28       133      3724
    109.         32       182      5824
    110.         36       250      9000
    111.         40       151      6040
    112.         44       120      5280
    113.         48       262     12576
    114.         52       138      7176
    115.         56       205     11480
    116.         60       126      7560
    117.         64       110      7040
    118.         68        68      4624
    119.         72        33      2376
    120.         76        27      2052
    121.         80        86      6880
    122.         84       139     11676
    123.         88        66      5808
    124.         92        45      4140
    125.         96        34      3264
    126.        100        90      9000
    127.        104         2       208
    128.        108        24      2592
    129.        112         2       224
    130.        116        19      2204
    131.        124        13      1612
    132.        132        12      1584
    133.        140         4       560
    134.        148         7      1036
    135.        156         3       468
    136.        164        10      1640
    137.        172         5       860
    138.        180         4       720
    139.        188         1       188
    140.        204         1       204
    141.     Total:      5112    179044 bytes.

    Theo thống kê trên, khi cây chứa 211 từ thì chi phí phụ là 38492/211 ~180 byte/từ, khi cây chứa 1855 từ thì chi phí phụ giảm xuống còn 179044/1855 ~100 byte/từ. Nên có cơ sở để hi vọng rằng khi lên đến khoảng 4-5 vạn từ (số lượng từ của một từ điển thông thường) thì chi phí phụ sẽ giảm xuống chỉ còn khoảng 25 byte/từ, nghĩa là tương đương với chi phí phụ của một cây nhị phân (mà chi phí cho 1 từ là 1 node gồm 2 con trỏ và 1 khóa).

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

    Chưa có thời gian đọc hết code nhưng thấy vài chỗ hơi lạ :
    - Nếu cậu không có ý định dùng copy constructor và operator thì tạo definition và bỏ nó vào private. Code cậu không có định nghĩa ko nên để compiler tự quyết định.
    - Code cậu có thể dẫn đến resource leak :
    C++ Code:
    1. vector[COLOR=#000000]<[/COLOR]Tree[COLOR=#000000]*>[/COLOR] subtrees;
    Có chỗ cậu dùng operator new nhưng không có destrutor, nhỡ nếu exception throw thì remove của cậu không bao h được gọi.
    - Cậu nên bỏ using namespace vào scope của hàm hoặc class, tui nghĩ nên dùng std::.
    - Khúc cuối cậu bỏ macro test vào thật là ugly T_T, có cả trăm cách viết 1 đoạn test sáng sủa hơn rất nhiều.
    - Overloading dùng tên sát với STL standard quá và trong khi đó cậu lại dùng namespace std; ngay trên tiêu đề.
    - Cast type dùng luôn C++, có lúc cậu pha vào cast C style rất nguy hiểm, cậu cast bay cả const lúc nào cũng khó biết.
    - Và hàm này tui thấy không mang ý nghĩa nhiều lắm :
    C++ Code:
    1. void Tree::list(ostream& os) const
    2. {
    3.     string stack("");
    4.     list(os, stack);
    5. }
    Tui nghĩ cậu trả về hẳn 1 std::ostream& , thì lúc này cậu có thể dùng đại khái như :
    std::cout << some_object;
    Và cái tên "stack" thật quá nguy hiểm !!!.
    Một vài góp ý, hi vọng có ích cho cậu.

  3. #3
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất nhiều sóng gió
    Bài viết
    442

    Trích dẫn Nguyên bản được gửi bởi rox_rook Xem bài viết
    Chưa có thời gian đọc hết code nhưng thấy vài chỗ hơi lạ :
    Cám ơn RR đã bỏ thời gian đọc code của mình. Mình đã chữa lại hầu hết theo góp í của RR:

    Trích dẫn Nguyên bản được gửi bởi rox_rook Xem bài viết
    - Nếu cậu không có ý định dùng copy constructor và operator thì tạo definition và bỏ nó vào private. Code cậu không có định nghĩa ko nên để compiler tự quyết định.
    - Code cậu có thể dẫn đến resource leak :
    C++ Code:
    1. vector<Tree*> subtrees;
    Có chỗ cậu dùng operator new nhưng không có destrutor, nhỡ nếu exception throw thì remove của cậu không bao h được gọi.
    Constructor, destructor, phép gán và một số thứ khác đều có ích, nhưng chưa cần cho bài test kia. Hơn nữa viết mấy cái đó là công việc máy móc mà mình rất chán. Vì thế mình không viết mà chỉ bỏ 1 comment "//todo:....". Nay mình đã bổ sung đầy đủ.

    Trích dẫn Nguyên bản được gửi bởi rox_rook Xem bài viết
    - Cậu nên bỏ using namespace vào scope của hàm hoặc class, tui nghĩ nên dùng std::.

    - Overloading dùng tên sát với STL standard quá và trong khi đó cậu lại dùng namespace std; ngay trên tiêu đề.
    Với chương trình to thì cần phải để í chuyện này thật. Nhưng chương trình này bé quá nên mình bỏ hết namespace. Còn đặt tên sát với STL bởi vì việc cũng gần giống với STL. Đặt tên khác rất khó coi.

    Trích dẫn Nguyên bản được gửi bởi rox_rook Xem bài viết
    - Cast type dùng luôn C++, có lúc cậu pha vào cast C style rất nguy hiểm, cậu cast bay cả const lúc nào cũng khó biết.
    Mình soát lại và bỏ C cast.

    Trích dẫn Nguyên bản được gửi bởi rox_rook Xem bài viết
    - Và hàm này tui thấy không mang ý nghĩa nhiều lắm :
    C++ Code:
    1. void Tree::list(ostream& os) const
    2. {
    3.     string stack("");
    4.     list(os, stack);
    5. }
    Tui nghĩ cậu trả về hẳn 1 std::ostream& , thì lúc này cậu có thể dùng đại khái như :
    std::cout << some_object;
    Mình chữa thành operator <<.

    Trích dẫn Nguyên bản được gửi bởi rox_rook Xem bài viết
    Và cái tên "stack" thật quá nguy hiểm !!!.
    Mình chữa tên 'stack' thành 'key'.

    Trích dẫn Nguyên bản được gửi bởi rox_rook Xem bài viết
    - Khúc cuối cậu bỏ macro test vào thật là ugly T_T, có cả trăm cách viết 1 đoạn test sáng sủa hơn rất nhiều.
    Mình chưa hiểu í RR lắm. Mình muốn hiện giá trị các biến nhất định của 1 hàm mà mình quan tâm ở những thời điểm nhất định trong hàm. Làm thế nào nếu không dùng macro?

    Trích dẫn Nguyên bản được gửi bởi rox_rook Xem bài viết
    Một vài góp ý, hi vọng có ích cho cậu.
    Rất có ích. Cám ơn RR.


    Code mới đã chữa:
    C++ Code:
    1.  
    2. #include <string>
    3. #include <vector>
    4. #include <map>
    5. #include <iostream>
    6. #include <fstream>
    7. #include <cassert>
    8.  
    9. using namespace std;
    10.  
    11. ////////////////////////////////////////////////////////////////////////////////////
    12. // Tree -- a 26-ary tree
    13.  
    14. class Tree
    15. {
    16. public:
    17.     Tree() {};
    18.     Tree(const Tree&);
    19.     ~Tree();
    20.     Tree& operator=(const Tree&);
    21.     string *find(const string& key) const;
    22.     void insert(const string& key, const string& value);
    23.     void remove(const string& key);
    24.     string& operator[](const string& key);  // find and insert (key,e) to tree if needed
    25.     void compactSubtrees();                 // delete unused nodes
    26.     friend ostream& operator<< (ostream& os, Tree const& t);
    27.     bool isEmpty() const;
    28.     int  nWords() const;                    // #keywords, i.e. #occupied nodes
    29.     void takeStat(map<int,int>& stSize, map<int,int>& stCapacity) const;
    30.                             // take statistic of tree overhead size and capacity
    31.     static const char *firstWord(const char *s);   // find first word in s
    32.     static int wordLength(const char *w);   // find length of word w
    33. // the following should be private; they are public for testing only
    34.     bool isCompact() const;
    35.     bool isLeaf() const;
    36.     bool isLeafOrCompact() { return isLeaf() || isCompact(); }
    37.     int  nNodes() const;
    38.  
    39. private:
    40.     string data;
    41.     vector<Tree*> subtrees;
    42.  
    43.     void clone(const Tree&);
    44.     bool isOccupied() const;                // is this *node* occupied?
    45.     void list(ostream& os, string& key) const;// list to 'os' using 'key' as a working stack
    46.     Tree& find(const char *& key) const;
    47.     Tree& insert(const char *key, const string& s);
    48.     void remove(const char *key);
    49.     void compactSubtreesVector();
    50.  
    51.     static const int nLetters = 'z' - 'a' + 1;// 26
    52.  
    53.     static int encode(int x)
    54.     {
    55.         char enc[]=
    56.         //   a  b  c  d  e  f  g  h  i  j  k  l  m  n  o  p  q  r  s  t  u  v  w  x  y  z
    57.             {2,19,11, 9, 0,15,16, 7, 4,22,21,10,13, 5, 3,18,24, 8, 6, 1,12,20,14,23,17,25};
    58.         assert(isalpha(x));
    59.         return enc[tolower(x) - 'a'];
    60.     }
    61.  
    62.     static int decode(int y)
    63.     {
    64.         char dec[]="etaoinshrdlcumwfgypbvkjxqz";
    65.         assert(0 <= y && y < nLetters);
    66.         return dec[y];
    67.     }
    68. };
    69.  
    70. // Description
    71. // There are two (conceptual) classes of trees:
    72. // T : tree
    73. // T': compact tree, i.e., one using minimal number of nodes to store given words.
    74. //     A tree is _compact_ iff its leaves are all occupied.
    75. //     Although compact tree is nice, it is hard to implement recursively
    76. //     since every tree must have at least one leaf => every compact tree
    77. //     is non-empty => when initialized, a compact tree is just a leaf and must
    78. //     be already occupied, e.g. by (emptykey,somevalue).
    79. //
    80. // T' is a proper subclass of T, i.e., T' < T.
    81. //
    82. // For T', member functions may assume the input tree is T' (and take
    83. // andvantage of the assumption for to write simpler and faster code),
    84. // public mutators (constructor(s), destructor, operator[], insert() etc),
    85. // on the other hand, must guarantee that every output tree is indeed T'.
    86. // For example:
    87. //
    88. // - While T::remove() may use the "lazy" strategy (i.e. no memory cleanup),
    89. //   T'::remove() must cleanup upon remove.
    90. //
    91. // - While T::insert() may insert value e to tree, T'::insert() may not.
    92. //   To save memory, a tree node has no bool member variable indicating
    93. //   its occupation, isOccupied() is implemented by testing for empty value.
    94. //   Thus every node containing (key,e) is considered unoccupied.
    95. //
    96. // - operator[] can be defined for T but not for T', since it inserts
    97. //   (key,e) pairs to tree t to ensure t[key] accessibility.
    98. //
    99. // Although the Tree in this implementation tries to be T', technically it is T,
    100. // i.e.,
    101. //
    102. // - member functions do not assume compact input tree;
    103. //
    104. // - t.compactSubtrees() guarantees compactness on all subtrees; and
    105. //
    106. // - all other public mutators except t.insert(key,e) and t[non-existing key]
    107. //   preserve tree compactness if any.
    108.  
    109. Tree::Tree(const Tree& t)
    110. {
    111.     clone(t);
    112. }
    113.  
    114. Tree& Tree::operator=(const Tree& t)
    115. {
    116.     if (this != &t)
    117.     {
    118.         this->~Tree();
    119.         clone(t);
    120.     }
    121.     return *this;
    122. }
    123.  
    124. void Tree::clone(const Tree& t)
    125. {
    126.     data = t.data;
    127.     assert(subtrees.empty());
    128.     subtrees.resize(t.subtrees.size(),NULL);
    129.     for (size_t k = 0; k < t.subtrees.size(); k++)
    130.         if (t.subtrees[k])
    131.             subtrees[k] = new Tree(*t.subtrees[k]);
    132. }
    133.  
    134. Tree::~Tree()
    135. {
    136.     for (size_t k=0; k<subtrees.size(); k++)
    137.         if (subtrees[k])
    138.             delete subtrees[k];
    139.     subtrees.clear();
    140. }
    141.  
    142. string *Tree::find(const string& key) const
    143. {
    144.     const char *key1 = key.c_str();
    145.     Tree& tree = find(key1);
    146.     if (*key1 || !tree.isOccupied()) return NULL;
    147.     return &tree.data;
    148. }
    149.  
    150. Tree& Tree::find(const char *&key) const
    151. {
    152.     int k;
    153.     if (*key && (k = encode(*key)) < int(subtrees.size()) && subtrees[k])
    154.         return subtrees[k]->find(++key);
    155.     return const_cast<Tree&>(*this);
    156. }
    157.  
    158. string& Tree::operator[](const string& key)
    159. {
    160.     const char *key1 = key.c_str();
    161.     Tree& tree = find(key1);
    162.     if (*key1 == 0) return tree.data;
    163.     return tree.insert(key1,"").data;
    164. }
    165.  
    166. void Tree::insert(const string& key, const string& s)
    167. {
    168.     insert(key.c_str(),s);
    169. }
    170.  
    171. Tree& Tree::insert(const char *key, const string& s)
    172. {
    173.     if (*key == 0)
    174.     {
    175.         data = s;
    176.         return *this;
    177.     }
    178.     else
    179.     {
    180.         int k = encode(*key);
    181.         if (!(k < int(subtrees.size())))
    182.         {
    183.             subtrees.resize(k+1,NULL);
    184.         }
    185.         if (!subtrees[k])
    186.         {
    187.             subtrees[k] = new Tree;
    188.         }
    189.         return subtrees[k]->insert(key+1,s);
    190.     }
    191. }
    192.  
    193. void Tree::remove(const string& key)
    194. {
    195.     remove(key.c_str());
    196. }
    197.  
    198. void Tree::remove(const char *key)
    199. {
    200.     int k;
    201.     if (*key == 0)
    202.     {
    203.         data.clear();
    204.     }
    205.     else if ((k=encode(*key)) < int(subtrees.size()) && subtrees[k])
    206.     {
    207.         subtrees[k]->remove(key+1);
    208.         if (subtrees[k]->isEmpty())
    209.         {
    210.             delete subtrees[k];
    211.             subtrees[k] = NULL;
    212.             compactSubtreesVector();
    213.         }
    214.     }
    215. }
    216.  
    217. void Tree::compactSubtrees()
    218. {
    219.     for(int k=0; k<int(subtrees.size()); k++)
    220.     {
    221.         if (!subtrees[k]) continue;
    222.         subtrees[k]->compactSubtrees();
    223.         if(subtrees[k]->isEmpty())
    224.         {
    225.             delete subtrees[k];
    226.             subtrees[k] = NULL;
    227.         }
    228.     }
    229.     compactSubtreesVector();
    230. }
    231.  
    232. void Tree::compactSubtreesVector()
    233. {   // minimalize size of the vector 'subtrees',
    234.     int k1 = -1;
    235.     for (int k = int(subtrees.size())-1; k>=0; --k)
    236.         if (subtrees[k]) {k1 = k; break;}
    237.     if (int(subtrees.size()) > k1+1)
    238.         subtrees.resize(k1+1);
    239. }
    240.  
    241. ostream& operator << (ostream& os, Tree const& t)
    242. {
    243.     string key("");
    244.     t.list(os, key);
    245.     return os;
    246. }
    247.  
    248. void Tree::list(ostream& os, string& key) const
    249. {
    250.     if (isOccupied())
    251.     {
    252.         os << key << ":";
    253.         os << data << endl;
    254.     }
    255.     for (int cx = 'a'; cx <= 'z'; cx++)
    256.     {
    257.         int cy = encode(cx);
    258.         if (int(subtrees.size())>cy && subtrees[cy])
    259.         {
    260.             key.push_back(cx);
    261.             subtrees[cy]->list(os, key);
    262.             key.erase(key.end()-1);
    263.         }
    264.     }
    265. }
    266.  
    267. bool Tree::isOccupied() const
    268. {
    269.     return !data.empty();
    270. }
    271.  
    272. bool Tree::isEmpty() const
    273. {
    274.     if (isOccupied()) return false;
    275.     for (size_t k=0; k<subtrees.size(); k++)
    276.         if (subtrees[k] && !subtrees[k]->isEmpty()) return false;
    277.     return true;
    278. }
    279.  
    280. bool Tree::isLeaf() const
    281. {
    282.     for (size_t k=0; k<subtrees.size(); k++)
    283.         if(subtrees[k]) return false;
    284.     return true;
    285. }
    286.  
    287. bool Tree::isCompact() const
    288. {
    289.     if (isLeaf()) return isOccupied();
    290.     for (size_t k=0; k<subtrees.size(); k++)
    291.         if (subtrees[k] && !subtrees[k]->isCompact()) return false;
    292.     return true;
    293. }
    294.  
    295. int Tree::nWords() const
    296. {
    297.     int n = isOccupied()? 1 : 0;
    298.     for (size_t k=0; k<subtrees.size(); k++)
    299.         if (subtrees[k]) n+=subtrees[k]->nWords();
    300.     return n;
    301. }
    302.  
    303. int Tree::nNodes() const
    304. {
    305.     int n=1;
    306.     for (size_t k=0; k<subtrees.size(); k++)
    307.         if (subtrees[k]) n+=subtrees[k]->nNodes();
    308.     return n;
    309. }
    310.  
    311. void Tree::takeStat(map<int,int>& stSize, map<int,int>& stCapa) const
    312. {
    313.     int dNodeSize = sizeof(*this) - sizeof(data) + sizeof(Tree*) * subtrees.size();
    314.     stSize[dNodeSize]++;
    315.     int dNodeCapa = sizeof(*this) - sizeof(data) + sizeof(Tree*) * subtrees.capacity();
    316.     stCapa[dNodeCapa]++;
    317.     //if(subtrees.size()==0) cout << this << endl;
    318.     for (size_t k=0; k<subtrees.size(); k++)
    319.         if (subtrees[k]) subtrees[k]->takeStat(stSize,stCapa);
    320. }
    321.  
    322. const char *Tree::firstWord(const char *s)
    323. {
    324.     while (*s && !isalpha(*s)) s++;
    325.     return s;
    326. }
    327.  
    328. int Tree::wordLength(const char *w)
    329. {
    330.     const char *u = w;
    331.     while (isalpha(*u)) u++;
    332.     return u - w;
    333. }
    334.  
    335. //////////////////////////////////////////////////////////////////////////////////////////
    336. // Tests
    337. #include <iostream>
    338. #include <iomanip>
    339. #include <algorithm>
    340. #include <functional>
    341. #include <vector>
    342. #include <sstream>
    343. #include <ctime>
    344. #include <cstdlib>
    345.  
    346. #ifdef __GNUC__
    347. #include <ext/hash_set>
    348. #define set __gnu_cxx::hash_set
    349. namespace __gnu_cxx
    350. {
    351.     template<> struct hash< std::string >
    352.     {
    353.         size_t operator()( const std::string& s ) const
    354.         {
    355.             return hash< const char* >()( s.c_str() );
    356.         }
    357.     };
    358. }
    359. #else
    360. #include <set>
    361. #endif
    362.  
    363. bool operator == (Tree const& tr1, Tree const& tr2)
    364. {
    365.     stringstream oss1(stringstream::in|stringstream::out);
    366.     stringstream oss2(stringstream::in|stringstream::out);
    367.     string s1,s2;
    368.     oss1 << tr1;
    369.     oss2 << tr2;
    370.     while (oss1 >> s1  &&  oss2 >> s2)
    371.     {
    372.         // cout << s1;
    373.         // cout << s2;
    374.         if (s1 != s2) return false;
    375.     }
    376.     return true;
    377. }
    378.  
    379. unsigned genRandom(unsigned max) // generates a pseudo-random number in [0,max),
    380.                                  // 'max' and return value may be declared 'float'
    381. {
    382.     static int const IM = 139968, IA = 3877, IC = 29573;
    383.     static int seed = 42;
    384.     return unsigned(double(max) * (seed = (seed * IA + IC) % IM) / IM);
    385.         // floating-point arithmetic to avoid overflow with large 'max'
    386. }
    387.  
    388. ptrdiff_t random (ptrdiff_t i)
    389. {
    390.     return genRandom(i);
    391. }
    392.  
    393. ptrdiff_t (*p_random)(ptrdiff_t) = random;
    394.  
    395. int loadWords(vector<string>& v, string const& filename)
    396. {
    397.     // parse a text file for words, store words to v uniquely
    398.     ifstream ifs(filename.c_str());
    399.     set<string> s;
    400.     string u, w;
    401.     const char *pw;
    402.     int n=0, k;
    403.     while (ifs >> u)
    404.     {
    405.         for(k = int(u.length()); k>=0; k--)
    406.             u[k] = tolower(u[k]);
    407.         for(pw = u.c_str(); *pw; pw+=k)
    408.         {
    409.             n++;
    410.             pw = Tree::firstWord(pw);
    411.             k  = Tree::wordLength(pw);
    412.             w.assign(pw,k);
    413.             if (s.find(w)==s.end())
    414.             {
    415.                 s.insert(w);
    416.                 v.push_back(w);
    417.             }
    418.             //else cout << w << ":REPEATS ";
    419.         }
    420.     }
    421.     ifs.close();
    422.     cout << endl << filename << ":" << endl
    423.          << "#words=" << n << " "
    424.          << "#distinct words=" << v.size() << endl;
    425.     return s.size();
    426. }
    427.  
    428. int listStat(map<int,int>& st)
    429. {
    430.     map<int,int>::iterator i;
    431.     int m=0, n=0;
    432.     cout << setw(10) << "nodesize" << setw(10) << "#nodes"
    433.          << setw(10) << "amount" << endl;
    434.     for (i=st.begin(); i!=st.end(); i++)
    435.     {
    436.         cout << setw(10) << i->first << setw(10) << i->second
    437.         << setw(10) << (i->first * i->second) << endl;
    438.         m += i->first * i->second;
    439.         n += i->second;
    440.     }
    441.     cout << setw(10) << "Total:" << setw(10) << n
    442.          << setw(10) << m << " bytes." << endl;
    443.     return m;
    444. }
    445.  
    446. void transferData(vector<string>& v0, vector<string>& v01, vector<string>& v1)
    447. {
    448.     // transfer a part of v0 to v1 and construct v01 as a delta list, i.e.
    449.     // v01 = a subset of v0, v0 -= v01, v1 += v01, v01 += some words from v1
    450.     v01.clear();
    451.     random_shuffle(v0.begin(), v0.end(), p_random);
    452.     for (int n = genRandom(v0.size()+1); n; n--)
    453.     {
    454.         string w = v0.back();
    455.         v0.pop_back();
    456.         v01.push_back(w);
    457.     }
    458.     v1.insert(v1.end(),v01.begin(),v01.end());
    459.     for (int n = genRandom(v1.size()/2); n; n--)
    460.     {
    461.         string w = v1[genRandom(v1.size())];
    462.         v01.push_back(w);
    463.     }
    464. }
    465.  
    466. void treeInsert(Tree& t, vector<string>& v)
    467. {
    468.     random_shuffle(v.begin(), v.end(), p_random);
    469.     for (size_t i=0; i<v.size(); i++)
    470.         t.insert(v[i],"giai nghia tieng Viet");
    471. }
    472.  
    473. void treeInsert2(Tree& t, vector<string>& v)
    474. {
    475.     random_shuffle(v.begin(), v.end(), p_random);
    476.     for (size_t i=0; i<v.size(); i++)
    477.         t[v[i]] = "giai nghia tieng Viet";
    478. }
    479.  
    480. void treeRemove(Tree&t, vector<string>& v)
    481. {
    482.     random_shuffle(v.begin(), v.end(), p_random);
    483.     for (size_t i=0; i<v.size(); i++)
    484.         t.remove(v[i]);
    485. }
    486.  
    487. void treeRemove2(Tree&t, vector<string>& v)
    488. {
    489.     random_shuffle(v.begin(), v.end(), p_random);
    490.     for (size_t i=0; i<v.size(); i++)
    491.         t[v[i]] = "";
    492.     t.compactSubtrees();
    493. }
    494.  
    495. #define DISPLAYCOUNTS  \
    496.     cout << "v0:" << v0.size() << " v01:" << v01.size() \
    497.          << " v1:" << v1.size() \
    498.          << " ta:" << ta.nWords() << "/" << ta.nNodes() \
    499.          << " tb:" << tb.nWords() << "/" << tb.nNodes() << endl;
    500.  
    501. void testTree()
    502. {
    503.     vector<string> v0;    // the set of out-tree words
    504.     vector<string> v1;    // the set of in-tree words
    505.     vector<string> v01;   // the delta list, ie. list of words
    506.                           // to be inserted to tree or removed from tree
    507.  
    508.     map<int,int> st10size, st10capa, st90size, st90capa;
    509.     int nWords, nWords10, nWords90;
    510.     bool st10taken=false, st90taken=false;
    511.  
    512.     Tree ta,tb;
    513.  
    514.     //nWords = loadWords(v0, "english-1857w.txt");
    515.     //nWords = loadWords(v0, "english-058kw-corncob.txt");
    516.     //nWords = loadWords(v0, "english-087kw-british.txt");
    517.     //nWords = loadWords(v0, "english-110kw-SIL.txt");
    518.     nWords = loadWords(v0, "english-346kw-raw.txt");
    519.     //nWords = loadWords(v0, "english-spoken-written.txt");
    520.     //nWords = loadWords(v0, "english-british-cap.txt");
    521.  
    522.     DISPLAYCOUNTS;
    523.     while (!(st10taken && st90taken))
    524.     {
    525.         // v01 = a subset of v0, v0 -= v01, v1 += v01,
    526.         // v01 += some words from v1
    527.         transferData(v0,v01,v1);
    528.  
    529.         // ta += v01 shuffle, tb += v01 shuffle
    530.         treeInsert(ta,v01);
    531.         if(genRandom(2)) treeInsert(tb,v01); else treeInsert2(tb,v01);
    532.         if (nWords*0.89 <= v1.size() && v1.size() <= nWords*0.91 && !st90taken)
    533.         {
    534.             ta.takeStat(st90size,st90capa);
    535.             nWords90=v1.size();
    536.             st90taken = true;
    537.         }
    538.         DISPLAYCOUNTS;
    539.  
    540.         // v01 = a subset of v1, v1 -= v01, v0 += v01,
    541.         // v01 += some words from v0
    542.         transferData(v1,v01,v0);
    543.  
    544.         // ta -= v01 shuffle, tb -= v01 shuffle
    545.         treeRemove(ta,v01);
    546.         if(genRandom(2)) treeRemove(tb,v01); else treeRemove2(tb,v01);
    547.         if (nWords*0.09 <= v1.size() && v1.size() <= nWords*0.11 && !st10taken)
    548.         {
    549.             ta.takeStat(st10size,st10capa);
    550.             nWords10=v1.size();
    551.             st10taken = true;
    552.         }
    553.         DISPLAYCOUNTS;
    554.  
    555.         assert(ta.nWords()==int(v1.size()) && tb.nWords()==int(v1.size()));
    556.         assert(ta==tb);
    557.         assert(ta.isLeafOrCompact() && tb.isLeafOrCompact());
    558.     }
    559.  
    560.     // insert the entire v0 to trees, i.e. v01=v0, v0 = emptyset, v1 += v01,
    561.     // ta += v01 shuffle, tb += v01 shuffle
    562.     v01 = v0;
    563.     v0.clear();
    564.     v1.insert(v1.end(),v01.begin(),v01.end());
    565.     treeInsert(ta,v01);
    566.     treeInsert(tb,v01);
    567.     DISPLAYCOUNTS;
    568.     assert(ta==tb);
    569.     assert(ta.isLeafOrCompact() && tb.isLeafOrCompact());
    570.  
    571.     // remove the entire v1 from trees, i.e. v01=v1, v1 = emptyset, v0 += v01,
    572.     // ta -= v01 shuffle, tb -= v01 shuffle
    573.     v01 = v1;
    574.     v1.clear();
    575.     v0.insert(v0.end(),v01.begin(),v01.end());
    576.     treeRemove(ta,v01);
    577.     treeRemove(tb,v01);
    578.     DISPLAYCOUNTS;
    579.     assert(ta==tb);
    580.  
    581.     assert(ta.nWords()==0 && tb.nWords()==0);
    582.     assert(ta.isEmpty() && tb.isEmpty());
    583.     assert(ta.nNodes()==1 && tb.nNodes()==1);
    584.     assert(ta.isLeaf() && tb.isLeaf());
    585.  
    586.     cout << endl << "Testing completed." << endl << endl;
    587.  
    588.     // display the tree size & capacity statistics taken before
    589.     cout << endl << "Tree size statistic @ " << nWords10 << " words:" << endl;
    590.     listStat(st10size);
    591.     cout << endl << "Tree capa statistic @ " << nWords10 << " words:" << endl;
    592.     listStat(st10capa);
    593.     cout << endl << "Tree size statistic @ " << nWords90 << " words:" << endl;
    594.     listStat(st90size);
    595.     cout << endl << "Tree capa statistic @ " << nWords90 << " words:" << endl;
    596.     listStat(st90capa);
    597. }
    598.  
    599. int main()
    600. {
    601.     testTree();
    602.     return 0;
    603. }

    Testing Code:
    1. Tree capa statistic @ 311238 words:
    2.   nodesize    #nodes    amount
    3.         12    235585   2827020
    4.         16     58620    937920
    5.         20     31792    635840
    6.         24     43843   1052232
    7.         28     30784    861952
    8.         32     44745   1431840
    9.         36     53465   1924740
    10.         40     49479   1979160
    11.         44     18140    798160
    12.         48     35323   1695504
    13.         52     24020   1249040
    14.         56     33800   1892800
    15.         60     18955   1137300
    16.         64     17535   1122240
    17.         68     16399   1115132
    18.         72      3416    245952
    19.         76      4960    376960
    20.         80     18981   1518480
    21.         84     25381   2132004
    22.         88      6633    583704
    23.         92      7806    718152
    24.         96      5073    487008
    25.        100     12974   1297400
    26.        104       936     97344
    27.        108      3347    361476
    28.        112       656     73472
    29.        116      5244    608304
    30.        124      1511    187364
    31.        132       628     82896
    32.        140       664     92960
    33.        148       971    143708
    34.        156       578     90168
    35.        164       633    103812
    36.        172       559     96148
    37.        180       224     40320
    38.        188       351     65988
    39.        196        61     11956
    40.        204        56     11424
    41.        212        19      4028
    42.     Total:    814147  30091908 bytes.
    Đến 346 000 từ mà chi phí phụ vẫn cứ đứng ở ~100 byte/từ chứ không chịu giảm xuống nữa. :-( Tốn bộ nhớ quá!
    Đã được chỉnh sửa lần cuối bởi Ada : 08-06-2008 lúc 08:25 PM.

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

    - Đầu tiên sorry cậu là mặc dù tui rất thích thú với giải thuật của bài này nhưng thiệt sự là tui ko có dư lấy 1 tí thời gian để cùng cậu thảo luận để improve nó hơn nữa vì tui đang bị Physics nó hành tui quá cỡ T_T.
    - Còn về cậu nói viết copy construtor và operator assignment = là nhàm chán là hơi bị chủ quan. 2 thằng này rất quan trọng nếu cậu thực sự muốn viết code solid và safety ( robust code ).
    - Còn về code nhỏ hay lớn gì đi chăng nữa thì cậu cũng không nên dùng using namespace std; tại global scope. Thằng C++ ra đời 1 phần lý do là vì thằng macro evil của C. ( Scope trong C++ là cực kì quan trọng ).
    - Có 1 cuốn sách về standard coding rule mà tui rất tâm đắc là 101 Coding Standards : Rules and Guidelines, nó sẽ có rất nhiều thứ mà cậu cần biết khi viết C++, và macro tại sao là evil thì tui trích 1 phần trong sách đó ra ( Trong trường hợp cậu không tìm được cuốn này thì nói với tui, tui sẽ post lại cho cậu ở 1 host nào đó )
    It's hard to find language that's colorful enough to describe macros, but we'll try. To quote from [Sutter04] §31:

    Macros are obnoxious, smelly, sheet-hogging bedfellows for several reasons, most of which are related to the fact that they are a glorified text-substitution facility whose effects are applied during preprocessing, before any C++ syntax and semantic rules can even begin to apply.

    Lest there remain any ambiguity on this point, we note also that Bjarne Stroustrup has written: I dislike most forms of preprocessors and macros. One of C++'s aims is to make C's preprocessor redundant (§4.4, §18) because I consider its actions inherently error prone.

    [Stroustrup94] §3.3.1
    Macros are almost never necessary in C++. Use const (§5.4) or enum (§4.8) to define manifest constants [see Item 15], inline (§7.1.1) to avoid function-calling overhead [but see Item 8], templates (Chapter 13) to specify families of functions and types [see Items 64 through 67], and namespaces (§8.2) to avoid name clashes [see Items 57 through 59].

    [Stroustrup00] §1.6.1
    The first rule about macros is: Don't use them unless you have to. Almost every macro demonstrates a flaw in the programming language, in the program, or in the programmer.

    [Stroustrup00] §7.8
    The main problem with C++ macros is that they seem much better at what they do than they really are. Macros ignore scopes, ignore the type system, ignore all other language features and rules, and hijack the symbols they #define for the remainder of a file. Macro invocations look like symbols or function calls, but are neither. Macros are not "hygienic," meaning that they can expand to significantly and surprisingly different things depending on the context in which they are used. The text substitution that macros perform makes writing even remotely proper macros a black art whose mastery is as unrewarding as it is tedious.

    People who think that template-related errors are the worst to decipher probably haven't seen those caused by badly formed or badly used macros. Templates are part of C++'s type system and thus allow compilers to get better at handling them (which they do), whereas macros are forever divorced from the language and hence intractable. Worse, unlike a template, a macro might expand to some transmission line noise that undesirably compiles by pure chance. Finally, an error in a macro can only be reported after the macro is expanded and not when it is defined.
    Even in the rare cases where you do legitimately write a macro (see Exceptions), never ever even consider starting to think about writing a macro that is a common word or abbreviation. Do #undefine macros as soon as possible, always give them SCREAMING_UPPERCASE_AND_UGLY names, and avoid putting them in headers.
    Nếu 1 dùng namespace thì bỏ nó vào thân hàm, ví dụ :
    C++ Code:
    1. #include <iostream>
    2. #include <vector>
    3.  
    4. int do_sthing()
    5. {
    6.     using namespace std;
    7.  
    8.     vector< int > v;
    9.     int           sumation = 0;
    10.  
    11.     v.reserve( 10 );
    12.     for( int x = 0; x < 10; ++x )
    13.     {
    14.         v.push_back( x );
    15.         sumation += v.at( x );
    16.     }
    17.  
    18.     return sumation;
    19. }
    20.  
    21. int main()
    22. {
    23.     std::cout << do_sthing();
    24. }

    Và còn kĩ thuật mà cậu dùng để xử shrink-to-fit đối với vector ( tui nghĩ cậu dùng resize ) nhưng do chưa đọc kĩ nên tui cũng không rõ idea này có hiệu quả lắm không ( có dịp tui sẽ đọc lại sau ). Nhưng nếu tui viết tui sẽ dùng kĩ thuật sau của Scott Meyers :
    C++ Code:
    1. #include <vector>
    2. #include <iostream>
    3.  
    4. class Something{ };
    5.  
    6. int main()
    7. {
    8.     using namespace std;
    9.  
    10.     vector< Something > v;
    11.  
    12.     for( int x = 0; x < 1000; ++x )
    13.         v.push_back( Something() );
    14.  
    15.     cout << "After init, v.size() = " << v.size();
    16.     cout << ", v.capacity() = " << v.capacity() << endl;
    17.  
    18.     v.erase( v.begin() + 500, v.begin() + 600 );
    19.  
    20.     cout << "After deleting 100, v.size() = " << v.size();
    21.     cout << ", v.capacity() = " << v.capacity() << endl;
    22.  
    23.     vector< Something >( v ).swap( v );
    24.  
    25.     cout << "After shrink-to-fit, v.size() = " << v.size();
    26.     cout << ", v.capacity() = " << v.capacity() << endl;
    27.  
    28.     return 0;
    29. }

    Một chỗ nữa là :
    C++ Code:
    1. static int encode(int x)
    2.     {
    3.         char enc[]=
    4.         //   a  b  c  d  e  f  g  h  i  j  k  l  m  n  o  p  q  r  s  t  u  v  w  x  y  z
    5.             {2,19,11, 9, 0,15,16, 7, 4,22,21,10,13, 5, 3,18,24, 8, 6, 1,12,20,14,23,17,25};
    6.         assert(isalpha(x));
    7.         return enc[tolower(x) - 'a'];
    8.     }
    Tui nghĩ sao cậu không dùng 'a', 'b', 'c'......... nó sẽ rõ nghĩa hơn những magic numbers 2, 19, 11...

    Và destructor của cậu :
    C++ Code:
    1. Tree& Tree::operator=(const Tree& t)
    2. {
    3.     if (this != &t)
    4.     {
    5.         this->~Tree();
    6.         clone(t);
    7.     }
    8.     return *this;
    9. }

    C++ Code:
    1.  
    2. Tree::~Tree()
    3. {
    4.     for (size_t k=0; k<subtrees.size(); k++)
    5.         if (subtrees[k])
    6.             delete subtrees[k];
    7.     subtrees.clear();
    8. }
    Thực sự chỗ này sẽ hoạt động tốt nếu không có exception được throw, còn nếu có thì chắc chắn cậu sẽ bị resource leak.
    Một kĩ thuật tốt hơn cũng của Scott Meyers mà tui ưa thích là dùng function object, ví dụ :
    C++ Code:
    1. #include <vector>
    2. #include <iostream>
    3. #include <algorithm>
    4.  
    5. class Something{ };
    6.  
    7. struct DeleteObject
    8. {
    9.     template< typename T >
    10.     void operator()( const T* ptr ) const
    11.     {
    12.         delete ptr;
    13.     }
    14. };
    15.  
    16. void doSomething()
    17. {
    18.     std::vector< Something* > v;
    19.  
    20.     for( int x = 0; x < 10; ++x )
    21.     {
    22.         v.push_back( new Something );
    23.     }
    24.  
    25.     std::for_each( v.begin(), v.end(), DeleteObject() );
    26. }
    27.  
    28. int main()
    29. {
    30.     doSomething();
    31.     return 0;
    32. }

    Hi vọng sẽ sớm có dịp cùng cậu thảo luận kĩ hơn về giải thuật của bài này, hơn là kĩ thuật .
    [/COLOR]
    Đã được chỉnh sửa lần cuối bởi rox_rook : 09-06-2008 lúc 10:28 AM.

  5. #5
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất nhiều sóng gió
    Bài viết
    442

    Trích dẫn Nguyên bản được gửi bởi rox_rook Xem bài viết
    - Đầu tiên sorry cậu là mặc dù tui rất thích thú với giải thuật của bài này nhưng thiệt sự là tui ko có dư lấy 1 tí thời gian để cùng cậu thảo luận để improve nó hơn nữa vì tui đang bị Physics nó hành tui quá cỡ T_T.
    Cảm ơn RR quan tâm. Bao giờ bạn có thời gian và hứng thú thì ta sẽ thảo luận thêm.

    Trích dẫn Nguyên bản được gửi bởi rox_rook Xem bài viết
    - Có 1 cuốn sách về standard coding rule mà tui rất tâm đắc là 101 Coding Standards : Rules and Guidelines, nó sẽ có rất nhiều thứ mà cậu cần biết khi viết C++, và macro tại sao là evil thì tui trích 1 phần trong sách đó ra ( Trong trường hợp cậu không tìm được cuốn này thì nói với tui, tui sẽ post lại cho cậu ở 1 host nào đó )
    Mình rất thích. Mình sẽ cố tìm, nếu không tìm được sẽ PM nhờ RR share cho mình 1 bản.

    Còn về macro thì mình cũng rất ghét dùng macro nhưng trong bài này quả thật mình không biết cách nào khác. Vấn đề là làm sao display các biến nhất định trong hàm tại những thời điểm nhất định mà không phải kể tên hết tất cả các biến đó ra. Mình nghĩ nếu không dùng macro thì chỉ có cách đưa các biến đó ra ngoài hàm vào trong một class, còn hàm test và hàm display sẽ dùng class này. Nhưng để test một class mà phải viết ra thêm 1 class khác (hay thậm chí nhiều class khác, vì có thể có nhiều test) thì không ổn. Nếu RR nghĩ có cách tốt hơn thì chỉ cho mình.

    Trích dẫn Nguyên bản được gửi bởi rox_rook Xem bài viết
    - Còn về code nhỏ hay lớn gì đi chăng nữa thì cậu cũng không nên dùng using namespace std; tại global scope. Thằng C++ ra đời 1 phần lý do là vì thằng macro evil của C. ( Scope trong C++ là cực kì quan trọng ).

    Nếu 1 dùng namespace thì bỏ nó vào thân hàm, ví dụ :
    C++ Code:
    1. #include <iostream>
    2. #include <vector>
    3.  
    4. int do_sthing()
    5. {
    6.     using namespace std;
    7. ...
    8. }
    OK. Mình tiếp thu kinh nghiệm này. Sẽ sửa code.


    Trích dẫn Nguyên bản được gửi bởi rox_rook Xem bài viết
    Và còn kĩ thuật mà cậu dùng để xử shrink-to-fit đối với vector ( tui nghĩ cậu dùng resize ) nhưng do chưa đọc kĩ nên tui cũng không rõ idea này có hiệu quả lắm không ( có dịp tui sẽ đọc lại sau ). Nhưng nếu tui viết tui sẽ dùng kĩ thuật sau của Scott Meyers :
    C++ Code:
    1. #include <vector>
    2. #include <iostream>
    3.  
    4. class Something{ };
    5.  
    6. int main()
    7. {
    8.     using namespace std;
    9.  
    10.     vector< Something > v;
    11.  
    12.     for( int x = 0; x < 1000; ++x )
    13.         v.push_back( Something() );
    14.  
    15.     cout << "After init, v.size() = " << v.size();
    16.     cout << ", v.capacity() = " << v.capacity() << endl;
    17.  
    18.     v.erase( v.begin() + 500, v.begin() + 600 );
    19.  
    20.     cout << "After deleting 100, v.size() = " << v.size();
    21.     cout << ", v.capacity() = " << v.capacity() << endl;
    22.  
    23.     vector< Something >( v ).swap( v );
    24.  
    25.     cout << "After shrink-to-fit, v.size() = " << v.size();
    26.     cout << ", v.capacity() = " << v.capacity() << endl;
    27.  
    28.     return 0;
    29. }
    Rất hay. Nhưng mình chưa nghĩ đến việc áp dụng kĩ thuật này vào bài này vì

    - Code của mình chỉ co mảng bằng cách xóa đi đoạn cuối chứ không xóa đoạn đầu hay đoạn giữa.

    - Test sơ qua với nhiều file dữ liệu thực tế và số lần insert/remove khá lớn thì mình thấy size chiếm ~97% capacity, tức là cũng có hiệu quả thỏa đáng.


    Trích dẫn Nguyên bản được gửi bởi rox_rook Xem bài viết
    -Một chỗ nữa là :
    C++ Code:
    1. static int encode(int x)
    2.     {
    3.         char enc[]=
    4.         //   a  b  c  d  e  f  g  h  i  j  k  l  m  n  o  p  q  r  s  t  u  v  w  x  y  z
    5.             {2,19,11, 9, 0,15,16, 7, 4,22,21,10,13, 5, 3,18,24, 8, 6, 1,12,20,14,23,17,25};
    6.         assert(isalpha(x));
    7.         return enc[tolower(x) - 'a'];
    8.     }
    Tui nghĩ sao cậu không dùng 'a', 'b', 'c'......... nó sẽ rõ nghĩa hơn những magic numbers 2, 19, 11...
    Code trên có thể viết lại thành:
    C++ Code:
    1.     static int encode(int x)
    2.     {
    3.         char enc[] = "ctljapqhewvknfdsyigbmuoxrz";
    4.         assert(isalpha(x));
    5.         return enc[tolower(x)-'a']-'a';
    6.     }
    Nhưng chuỗi "ctljapqhewvknfdsyigbmuoxrz" cũng không sáng sủa gì hơn. Mặt khác nó còn giấu đi bản chất của encode là map các số của khoảng 97...122 (tức 'a'...'z') thành các số của khoảng 0...25. Và còn nữa, cách này tốn thêm 1 phép tính so với cách kia.

    Trích dẫn Nguyên bản được gửi bởi rox_rook Xem bài viết
    - Còn về cậu nói viết copy construtor và operator assignment = là nhàm chán là hơi bị chủ quan. 2 thằng này rất quan trọng nếu cậu thực sự muốn viết code solid và safety ( robust code ).
    Mình nghĩ rằng muốn viết code tốt thì chỗ nào cũng đều cần phải chú tâm cả. Constructor và assignment quan trọng mấy cũng không thể quan trọng bằng các method chính của class được.

    Trích dẫn Nguyên bản được gửi bởi rox_rook Xem bài viết
    -Và destructor của cậu :
    C++ Code:
    1. Tree& Tree::operator=(const Tree& t)
    2. {
    3.     if (this != &t)
    4.     {
    5.         this->~Tree();
    6.         clone(t);
    7.     }
    8.     return *this;
    9. }

    C++ Code:
    1.  
    2. Tree::~Tree()
    3. {
    4.     for (size_t k=0; k<subtrees.size(); k++)
    5.         if (subtrees[k])
    6.             delete subtrees[k];
    7.     subtrees.clear();
    8. }
    Thực sự chỗ này sẽ hoạt động tốt nếu không có exception được throw, còn nếu có thì chắc chắn cậu sẽ bị resource leak.

    -Một kĩ thuật tốt hơn cũng của Scott Meyers mà tui ưa thích là dùng function object, ví dụ :
    C++ Code:
    1. #include <vector>
    2. #include <iostream>
    3. #include <algorithm>
    4.  
    5. class Something{ };
    6.  
    7. struct DeleteObject
    8. {
    9.     template< typename T >
    10.     void operator()( const T* ptr ) const
    11.     {
    12.         delete ptr;
    13.     }
    14. };
    15.  
    16. void doSomething()
    17. {
    18.     std::vector< Something* > v;
    19.  
    20.     for( int x = 0; x < 10; ++x )
    21.     {
    22.         v.push_back( new Something );
    23.     }
    24.  
    25.     std::for_each( v.begin(), v.end(), DeleteObject() );
    26. }
    27.  
    28. int main()
    29. {
    30.     doSomething();
    31.     return 0;
    32. }
    Chỗ này mình chưa hiểu.

    Code:
    std::for_each( v.begin(), v.end(), DeleteObject() );
    có tác dụng tương đương với

    Code:
    for(i = 0; i < v.size(); v++) delete v[i];
    hay là còn tác dụng nào khác?


    Trích dẫn Nguyên bản được gửi bởi rox_rook Xem bài viết
    -Hi vọng sẽ sớm có dịp cùng cậu thảo luận kĩ hơn về giải thuật của bài này, hơn là kĩ thuật .
    Mình cũng hi vọng được thảo luận nhiều với RR, về mọi vấn đề.

    Thân.
    Đã được chỉnh sửa lần cuối bởi Ada : 10-06-2008 lúc 03:54 AM.

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

    Mặc định Từ điển Anh-Việt dùng cây 26 phân

    Mình nghĩ rằng muốn viết code tốt thì chỗ nào cũng đều cần phải chú tâm cả. Constructor và assignment quan trọng mấy cũng không thể quan trọng bằng các method chính của class được.
    Câu này tui tạm gác lại, nhưng cậu muốn nghĩ theo cách cậu thì tuỳ, còn theo quan điểm của tui thì viết 1 dòng chắc 1 dòng, vì thực sự code có pointer thì 2 thằng này là bắt buộc, nếu không thì sẽ dẫn đến logic error. Nhưng thôi cái này tui không muốn cãi, cậu hiểu theo cách cậu, tui hiểu theo cách tui .
    Chỉ tạm trả lời được 1 vấn đề này cho cậu, mai tui có test rùi, nên có lẽ khi khác tui sẽ đọc lại và trả lời các câu hỏi khác .

  7. #7
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất nhiều sóng gió
    Bài viết
    442

    Phiên bản Tree::clone() có tiềm năng chịu đựng lỗi exception:

    C++ Code:
    1. void Tree::clone(const Tree& t)
    2. {
    3.     data = t.data;
    4.     assert(subtrees.empty());
    5.     subtrees.resize(t.subtrees.size(),NULL);
    6.     for (size_t k = 0; k < t.subtrees.size(); k++)
    7.     {
    8.         if (t.subtrees[k])
    9.         {
    10.             subtrees[k] = new Tree();
    11.             subtrees[k]->clone(*t.subtrees[k]);
    12.         }
    13.     }
    14. }

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

    Có lẽ tui nghĩ Ada hiểu nhầm ý nghĩa throw exception, tui hiểu ý cậu chỗ hàm clone này, vấn đề là nó sẽ được throw khi nào ?
    - Trong đoạn giữa new
    - Sau khi new được hoàn thành
    -> và 2 chỗ này sẽ dẫn đến resource leak tiềm ẩn có thể khi các bất kì các exception nào đó xảy ra chứ không phải cách mà nó construct đối tượng vì dù cậu có assert và recursive call thế này đi chăng nữa nếu có 1 exception được throw trong các hàm con thì 100% resource leak ( destructor never called ). Và đoạn code trên dùng function object vẫn có thể dẫn đến resource leak T_T, lâu rùi không ôn bài nên coi ẩu, srry !. Cách dùng hoàn hảo nhất mà bác Meyers đề cập là boost::shared_ptr< >. Ví dụ :
    C++ Code:
    1. void doSomething()
    2. {
    3.     typedef boost::shared_ptr< Widget > OBJ;
    4.     std::vector< OBJ > v;
    5.     for( int x = 0; x < SOME_NUMBERS; ++x )
    6.     {
    7.         v.push_back( OBJ( new Widget ) );
    8.     ....
    9.     ..
    Thôi có gì gặp cậu sau nhé, cứ ngứa nghề chạy ra chạy vô chưa làm xong bài tập nữa T_T !

  9. #9
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất nhiều sóng gió
    Bài viết
    442

    Trích dẫn Nguyên bản được gửi bởi rox_rook Xem bài viết
    Có lẽ tui nghĩ Ada hiểu nhầm ý nghĩa throw exception, tui hiểu ý cậu chỗ hàm clone này, vấn đề là nó sẽ được throw khi nào ?
    - Trong đoạn giữa new
    Thì cái Tree object nếu đã được cấp và đang được construct sẽ không được destruct nhưng vẫn bị thu hồi (còn nếu nó chưa được cấp thì chẳng có gì mà nói). Và object này chỉ là 1 node thôi chứ nó không có node con nên không phải lo giải quyết các node con kia.

    Trích dẫn Nguyên bản được gửi bởi rox_rook Xem bài viết
    - Sau khi new được hoàn thành
    -> và 2 chỗ này sẽ dẫn đến resource leak tiềm ẩn có thể khi các bất kì các exception nào đó xảy ra chứ không phải cách mà nó construct đối tượng vì dù cậu có assert và recursive call thế này đi chăng nữa nếu có 1 exception được throw trong các hàm con thì 100% resource leak ( destructor never called ).
    Đúng là destructor của các node con không được gọi và sau khi unwind stack một hồi control sẽ trả về đến t0.Tree(Tree&) hoặc t0.operator=(). Tại đó ta đặt exception handler để thanh toán nguyên cả cái cây có gốc tại t0. Sau khi thanh toán xong t0 trở thành 1 lá và trong đa số trường hợp, chỉ còn trơ node gốc.

    Phiên bản này cũng như phiên bản trước đều dùng lối kiến tạo đệ qui, nhưng ở phiên bản trước việc nối cây con vào cây chính xảy ra khi đệ qui lùi ra còn trong phiên bản này, việc nối xảy ra khi đệ qui tiến vào. Nhờ vậy trong phiên bản này, node vừa được hình thành sẽ lập tức được nối vào cây chính.

    Sau exception handling, nếu bộ nhớ cho t0 đã được cấp phát bởi một lệnh pt0 = new Tree(tree) nào đó thì nó sẽ được thu hồi bởi hệ thống (sau khi gọi destructor của t0.data và t0.subtrees) còn trong các trường hợp khác thì không. Trong mọi trường hợp, sau exception handling, nội dung của t0 đã ổn định và có thể dùng tiếp, nhưng mình nghĩ cách xử lí hợp lí hơn vẫn là re-throw.

    Trích dẫn Nguyên bản được gửi bởi rox_rook Xem bài viết
    Và đoạn code trên dùng function object vẫn có thể dẫn đến resource leak T_T, lâu rùi không ôn bài nên coi ẩu, srry !. Cách dùng hoàn hảo nhất mà bác Meyers đề cập là boost::shared_ptr< >. Ví dụ :
    C++ Code:
    1. void doSomething()
    2. {
    3.     typedef boost::shared_ptr< Widget > OBJ;
    4.     std::vector< OBJ > v;
    5.     for( int x = 0; x < SOME_NUMBERS; ++x )
    6.     {
    7.         v.push_back( OBJ( new Widget ) );
    8.     ....
    9.     ..
    Thôi có gì gặp cậu sau nhé, cứ ngứa nghề chạy ra chạy vô chưa làm xong bài tập nữa T_T !
    Mình cũng rất yêu shared_ptr, nhưng mình không muốn dùng trong bài này vì Boost chưa được đưa vào chuẩn C++ và sẽ không thích hợp ở 1 code cho người mới học. Với lại, shared_ptr to gấp đôi pointer bình thường, lại còn thêm 1 cục overhead mấy chục byte nữa, nên dùng cho bài này thì mất hết í nghĩa. :-P

    Thân.
    Đã được chỉnh sửa lần cuối bởi Ada : 10-06-2008 lúc 01:12 PM.

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

    Cậu Ada có thể ghi rõ ra giải thuật hay có tài liệu nào về bài này thì cho tui xin với .
    Đọc code như vậy tốn thời gian quá, do đa phần khi cài đặt tree có quá nhiều lời gọi hàm đệ qui nên trace code cũng khá vất vả.
    Thanks cậu trước !

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

  1. Upload file dùng Ajax mà ko dùng Method Post của Form như thế nào?
    Gửi bởi hieupxd2cntt trong diễn đàn Thắc mắc lập trình ASP.NET
    Trả lời: 8
    Bài viết cuối: 14-09-2014, 10:23 PM
  2. Lập trình C++ trong visual studio có cách nào để dùng winform mà vẫn dùng cách viết trên c++ được ?
    Gửi bởi homgiaouoc trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 2
    Bài viết cuối: 08-10-2013, 12:50 PM
  3. Bài toán quản lí nhân viên dùng dùng danh sách liên kết trong C++. Mong mọi người góp ý!
    Gửi bởi rataki trong diễn đàn Thảo luận, góp ý code C/C++ của bạn
    Trả lời: 1
    Bài viết cuối: 22-11-2012, 11:26 PM
  4. Bài tập C++ Dùng strtok cắt chuỗi và lỗi khi dùng atof() chuyển char sang float
    Gửi bởi salomontong trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 1
    Bài viết cuối: 10-03-2012, 05:18 PM
  5. Tại sao dùng const trong trường hợp dùng biến tham chiếu
    Gửi bởi dinhdoong trong diễn đàn Thảo luận, góp ý code C/C++ của bạn
    Trả lời: 13
    Bài viết cuối: 04-02-2012, 10:45 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