diff options
Diffstat (limited to 'README.html')
| -rw-r--r-- | README.html | 297 |
1 files changed, 286 insertions, 11 deletions
diff --git a/README.html b/README.html index 2addc48..c002ad7 100644 --- a/README.html +++ b/README.html @@ -785,6 +785,11 @@ asciidoc.install(2); <strong>SplayTree.h</strong> <span class="monospaced">class SplayTree<Key, Value></span>
</p>
</li>
+<li>
+<p>
+<strong>VP_Tree.h</strong> <span class="monospaced">class VP_Tree<Vector, Scalar></span>
+</p>
+</li>
</ul></div>
</li>
<li>
@@ -1409,11 +1414,26 @@ width:100%; </div>
</div>
<div class="sect2">
-<h3 id="_meow_strong_kd_tree_lt_vector_scalar_gt_strong_c_class">meow:: <strong>KD_Tree<Vector, Scalar></strong> (C++ class)</h3>
+<h3 id="_meow_strong_vp_tree_lt_vector_scalar_gt_strong_c_class">meow:: <strong>VP_Tree<Vector, Scalar></strong> (C++ class)</h3>
<div class="sect3">
<h4 id="_description_6">Description</h4>
-<div class="paragraph"><p><span class="monospaced">KD_Tree</span> 全名k-dimension tree, 用來維護由 <strong>N個K維度向量所成的集合</strong>,
-並可於該set中查找 <strong>前i個離給定向量最接近的向量</strong></p></div>
+<div class="paragraph"><p><span class="monospaced">VP_Tree</span> 用來維護由 <strong>N個K維度向量所成的集合</strong>,
+並可於該set中查找 <strong>前i個離給定向量最接近的向量</strong>.<br>
+不像 <span class="monospaced">KD_Tree</span> 二分樹每次都選擇一個維度去分, 分成小的跟大的,
+<span class="monospaced">VP_Tree</span> 每次選一個點, 將資料分成 離這個點近的, 跟離這個點遠的.
+至於怎麼選呢…., 嘛還沒研究, 先random</p></div>
+<div class="ulist"><div class="title">參考資料連結:</div><ul>
+<li>
+<p>
+<a href="http://stevehanov.ca/blog/index.php?id=130">link</a>
+</p>
+</li>
+<li>
+<p>
+<a href="http://pnylab.com/pny/papers/vptree/vptree">link</a>
+</p>
+</li>
+</ul></div>
</div>
<div class="sect3">
<h4 id="_template_class_operators_request_2">Template Class Operators Request</h4>
@@ -1449,6 +1469,14 @@ width:70%; <tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Vector</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock"><strong>operator=</strong></p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">(Vector <span class="monospaced">v</span>)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">Vector&</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">copy operator</p></td>
+</tr>
+<tr>
+<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">Vector</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock"><strong>operator<</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(Vector <span class="monospaced">v</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">bool</p></td>
@@ -1457,6 +1485,15 @@ width:70%; <tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Scalar</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock"><strong><em>Scalar</em></strong></p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">(int <span class="monospaced">n</span>)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">Scalar</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">建構子,
+其中一定<span class="monospaced">n=0 or 4</span></p></td>
+</tr>
+<tr>
+<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">Scalar</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock"><strong>operator*</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(Scalar <span class="monospaced">s</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Scalar</p></td>
@@ -1481,6 +1518,14 @@ width:70%; <tr>
<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">Scalar</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock"><strong>operator-</strong></p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">( )</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">Scalar</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">取負號</p></td>
+</tr>
+<tr>
+<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">Scalar</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock"><strong>operator<</strong></p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">(Scalar <span class="monospaced">s</span>)</p></td>
<td class="tableblock halign-left valign-top" ><p class="tableblock">bool</p></td>
@@ -1509,6 +1554,219 @@ N ← <span class="monospaced">this</span> 中擁有的資料數 </li>
<li>
<p>
+D ← <span class="monospaced">this</span> 資料維度
+</p>
+</li>
+</ul></div>
+<table class="tableblock frame-all grid-rows"
+style="
+width:100%;
+">
+<col style="width:2%;">
+<col style="width:8%;">
+<col style="width:18%;">
+<col style="width:8%;">
+<col style="width:8%;">
+<col style="width:54%;">
+<thead>
+<tr>
+<th class="tableblock halign-right valign-top" >Const?</th>
+<th class="tableblock halign-right valign-top" >Name </th>
+<th class="tableblock halign-left valign-top" > Parameters </th>
+<th class="tableblock halign-left valign-top" > Return_Type</th>
+<th class="tableblock halign-center valign-top" > Time_Complexity</th>
+<th class="tableblock halign-left valign-top" > Description</th>
+</tr>
+</thead>
+<tbody>
+<tr>
+<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
+<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>insert</strong></p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">(Vector const& <span class="monospaced">v</span>)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">void</p></td>
+<td class="tableblock halign-center valign-top" ><p class="tableblock">O(1)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">將向量 <span class="monospaced">v</span> 加到set中</p></td>
+</tr>
+<tr>
+<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
+<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>erase</strong></p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">(Vector const& <span class="monospaced">v</span>)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">bool</p></td>
+<td class="tableblock halign-center valign-top" ><p class="tableblock">O(N)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">將向量 <span class="monospaced">v</span> 從set中移除, <em><sub>TODO:可以再優化</sub></em></p></td>
+</tr>
+<tr>
+<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
+<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>build</strong></p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">()</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">void</p></td>
+<td class="tableblock halign-center valign-top" ><p class="tableblock">O(KN logN) or O(1)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">檢查距上一次 <span class="monospaced">build()</span> 至今是否有 <span class="monospaced">insert/erase</span> 被呼叫,
+若有, 重新建樹, 否則不做事</p></td>
+</tr>
+<tr>
+<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
+<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>forceBuild</strong></p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">()</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">void</p></td>
+<td class="tableblock halign-center valign-top" ><p class="tableblock">O(KN logN)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">重新建樹</p></td>
+</tr>
+<tr>
+<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
+<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>query</strong></p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">(Vector const& <span class="monospaced">v</span>,<br>
+size_t <span class="monospaced">i</span>,<br>
+bool <span class="monospaced">cmp</span>)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">Vectors</p></td>
+<td class="tableblock halign-center valign-top" ><p class="tableblock">O(logN) <sub>Expected</sub></p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">於set中找尋距離 <span class="monospaced">v</span> 前 <span class="monospaced">i</span> 近的向量, 並依照由近而遠的順序排序.
+如果有兩個向量 <span class="monospaced">v1</span>,<span class="monospaced">v2</span> 距離一樣, 且 <span class="monospaced">cmp</span> 為 <span class="monospaced">true</span> , 則直接依照
+<span class="monospaced">v1 < v2</span> 來決定誰在前面. 最後回傳一陣列包含所有解.</p></td>
+</tr>
+<tr>
+<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
+<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>clear</strong></p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">()</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">void</p></td>
+<td class="tableblock halign-center valign-top" ><p class="tableblock">O(1)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">清空所有資料</p></td>
+</tr>
+<tr>
+<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced"></p></td>
+<td class="tableblock halign-right valign-top" ><p class="tableblock"><strong>reset</strong></p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">(size_t <span class="monospaced">dimension</span>)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">size_t</p></td>
+<td class="tableblock halign-center valign-top" ><p class="tableblock">O(1)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">清空所有資料並且指定維度為 <span class="monospaced">max(1, dimension)</span> 並且回傳指定後的維度</p></td>
+</tr>
+</tbody>
+</table>
+<div class="admonitionblock">
+<table><tr>
+<td class="icon">
+<div class="title">Note</div>
+</td>
+<td class="content">
+<div class="ulist"><ul>
+<li>
+<p>
+實測結果發覺比 <span class="monospaced">KD_Tree</span> 有效率多了…
+</p>
+</li>
+<li>
+<p>
+<em>TODO</em> <span class="monospaced">insert()</span>, <span class="monospaced">erase()</span> 算是未完成功能
+</p>
+</li>
+</ul></div>
+</td>
+</tr></table>
+</div>
+<hr>
+</div>
+</div>
+<div class="sect2">
+<h3 id="_meow_strong_kd_tree_lt_vector_scalar_gt_strong_c_class">meow:: <strong>KD_Tree<Vector, Scalar></strong> (C++ class)</h3>
+<div class="sect3">
+<h4 id="_description_7">Description</h4>
+<div class="paragraph"><p><span class="monospaced">KD_Tree</span> 全名k-dimension tree, 用來維護由 <strong>N個K維度向量所成的集合</strong>,
+並可於該set中查找 <strong>前i個離給定向量最接近的向量</strong></p></div>
+</div>
+<div class="sect3">
+<h4 id="_template_class_operators_request_3">Template Class Operators Request</h4>
+<table class="tableblock frame-all grid-rows"
+style="
+width:70%;
+">
+<col style="width:3%;">
+<col style="width:3%;">
+<col style="width:10%;">
+<col style="width:17%;">
+<col style="width:10%;">
+<col style="width:53%;">
+<thead>
+<tr>
+<th class="tableblock halign-right valign-top" >Const?</th>
+<th class="tableblock halign-left valign-top" >Typename</th>
+<th class="tableblock halign-left valign-top" > Operator </th>
+<th class="tableblock halign-left valign-top" > Parameters </th>
+<th class="tableblock halign-left valign-top" > Return_Type</th>
+<th class="tableblock halign-left valign-top" > Description</th>
+</tr>
+</thead>
+<tbody>
+<tr>
+<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">Vector</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock"><strong>operator[]</strong></p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">(size_t <span class="monospaced">n</span>)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">Scalar</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">取得第 <span class="monospaced">n</span> 維度量</p></td>
+</tr>
+<tr>
+<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">Vector</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock"><strong>operator<</strong></p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">(Vector <span class="monospaced">v</span>)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">bool</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">權重比較</p></td>
+</tr>
+<tr>
+<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">Scalar</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock"><strong>operator*</strong></p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">(Scalar <span class="monospaced">s</span>)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">Scalar</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">相乘</p></td>
+</tr>
+<tr>
+<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">Scalar</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock"><strong>operator+</strong></p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">(Scalar <span class="monospaced">s</span>)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">Scalar</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">相加</p></td>
+</tr>
+<tr>
+<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">Scalar</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock"><strong>operator-</strong></p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">(Scalar <span class="monospaced">s</span>)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">Scalar</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">相差</p></td>
+</tr>
+<tr>
+<td class="tableblock halign-right valign-top" ><p class="tableblock monospaced">const</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">Scalar</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock"><strong>operator<</strong></p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">(Scalar <span class="monospaced">s</span>)</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">bool</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">大小比較</p></td>
+</tr>
+</tbody>
+</table>
+</div>
+<div class="sect3">
+<h4 id="_custom_type_definitions_2">Custom Type Definitions</h4>
+<div class="ulist"><ul>
+<li>
+<p>
+<span class="monospaced">Vectors</span> ← <span class="monospaced">std::vector<Vector></span>
+</p>
+</li>
+</ul></div>
+</div>
+<div class="sect3">
+<h4 id="_support_methods_4">Support Methods</h4>
+<div class="ulist"><ul>
+<li>
+<p>
+N ← <span class="monospaced">this</span> 中擁有的資料數
+</p>
+</li>
+<li>
+<p>
K ← <span class="monospaced">this</span> 資料維度
</p>
</li>
@@ -1620,12 +1878,12 @@ bool <span class="monospaced">cmp</span>)</p></td> <div class="sect2">
<h3 id="_meow_strong_splaytree_lt_key_value_gt_strong_c_class">meow:: <strong>SplayTree<Key, Value></strong> (C++ class)</h3>
<div class="sect3">
-<h4 id="_description_7">Description</h4>
+<h4 id="_description_8">Description</h4>
<div class="paragraph"><p><span class="monospaced">SplayTree</span> 是一種神乎其技的資料結構, 維護一堆 Key→Value . 並且支援
一些 <span class="monospaced">std::map</span> 難以快速實踐的操作, 如 <span class="monospaced">split</span> , <span class="monospaced">merge</span> , <span class="monospaced">keyOffset</span></p></div>
</div>
<div class="sect3">
-<h4 id="_template_class_operators_request_3">Template Class Operators Request</h4>
+<h4 id="_template_class_operators_request_4">Template Class Operators Request</h4>
<table class="tableblock frame-all grid-rows"
style="
width:70%;
@@ -1683,7 +1941,7 @@ width:70%; </table>
</div>
<div class="sect3">
-<h4 id="_custom_type_definitions_2">Custom Type Definitions</h4>
+<h4 id="_custom_type_definitions_3">Custom Type Definitions</h4>
<div class="ulist"><ul>
<li>
<p>
@@ -1715,7 +1973,7 @@ width:70%; </ul></div>
</div>
<div class="sect3">
-<h4 id="_support_methods_4">Support Methods</h4>
+<h4 id="_support_methods_5">Support Methods</h4>
<div class="ulist"><ul>
<li>
<p>
@@ -1964,11 +2222,11 @@ SplayTree* <span class="monospaced">tree2</span>)</p></td> <div class="sect2">
<h3 id="_meow_strong_segmenttree_lt_value_gt_strong_c_class">meow:: <strong>SegmentTree<Value></strong> (C++ class)</h3>
<div class="sect3">
-<h4 id="_description_8">Description</h4>
+<h4 id="_description_9">Description</h4>
<div class="paragraph"><p>維護一個陣列, 並且讓user可以有區間查詢, 區間修改的小東東</p></div>
</div>
<div class="sect3">
-<h4 id="_template_class_operators_request_4">Template Class Operators Request</h4>
+<h4 id="_template_class_operators_request_5">Template Class Operators Request</h4>
<table class="tableblock frame-all grid-rows"
style="
width:70%;
@@ -2065,7 +2323,7 @@ width:70%; </ul></div>
</div>
<div class="sect3">
-<h4 id="_support_methods_5">Support Methods</h4>
+<h4 id="_support_methods_6">Support Methods</h4>
<div class="ulist"><ul>
<li>
<p>
@@ -2139,11 +2397,28 @@ Value const& <span class="monospaced">delta</span>)</p></td> </div>
</div>
</div>
+<div class="sect1">
+<h2 id="_test">Test</h2>
+<div class="sectionbody">
+</div>
+</div>
+<div class="sect1">
+<h2 id="_bug_report_contact">Bug Report / Contact</h2>
+<div class="sectionbody">
+<div class="ulist"><ul>
+<li>
+<p>
+E-Mail: cat.hook31894 ~在~ gmail.com
+</p>
+</li>
+</ul></div>
+</div>
+</div>
</div>
<div id="footnotes"><hr></div>
<div id="footer">
<div id="footer-text">
-Last updated 2014-04-22 02:34:00 CST
+Last updated 2014-04-22 21:35:29 CST
</div>
</div>
</body>
|