diff options
Diffstat (limited to 'README.asciidoc')
-rw-r--r-- | README.asciidoc | 77 |
1 files changed, 77 insertions, 0 deletions
diff --git a/README.asciidoc b/README.asciidoc index 3d93e0a..bdaaeee 100644 --- a/README.asciidoc +++ b/README.asciidoc @@ -32,6 +32,7 @@ ** *KD_Tree.h* `class KD_Tree<Vector, Scalar>` ** *SegemenTree.h* `class SegmentTree<Value>` ** *SplayTree.h* `class SplayTree<Key, Value>` +** *VP_Tree.h* `class VP_Tree<Vector, Scalar>` * *oo/* ** *Register_Implement.h* `class RegisterInterface` , `class ImplementInterface` @@ -264,6 +265,76 @@ size_t `number2`)| size_t | very fast ''' +=== meow:: *VP_Tree<Vector, Scalar>* (C++ class) +==== Description +`VP_Tree` 用來維護由 *N個K維度向量所成的集合*, +並可於該set中查找 *前i個離給定向量最接近的向量*. + +不像 `KD_Tree` 二分樹每次都選擇一個維度去分, 分成小的跟大的, +`VP_Tree` 每次選一個點, 將資料分成 離這個點近的, 跟離這個點遠的. +至於怎麼選呢...., 嘛還沒研究, 先random + +.參考資料連結: +* http://stevehanov.ca/blog/index.php?id=130[link] +* http://pnylab.com/pny/papers/vptree/vptree[link] + +==== Template Class Operators Request +[options="header",width="70%",cols="1>m,1<,3<s,5<,3<,15<",grid="rows"] +|===================================================================== +|Const?|Typename| Operator | Parameters | Return_Type| Description +|const | Vector|operator[] |(size_t `n`) | Scalar | 取得第 `n` 維度量 +|const | Vector|operator= |(Vector `v`) | Vector& | copy operator +|const | Vector|operator< |(Vector `v`) | bool | 權重比較 +|const | Scalar| 'Scalar' |(int `n`) | Scalar | 建構子, +其中一定`n=0 or 4` +|const | Scalar|operator* |(Scalar `s`) | Scalar | 相乘 +|const | Scalar|operator+ |(Scalar `s`) | Scalar | 相加 +|const | Scalar|operator- |(Scalar `s`) | Scalar | 相差 +|const | Scalar|operator- |( ) | Scalar | 取負號 +|const | Scalar|operator< |(Scalar `s`) | bool | 大小比較 +|===================================================================== + +==== Custom Type Definitions +* `Vectors` <- `std::vector<Vector>` + +==== Support Methods + +* N <- `this` 中擁有的資料數 +* D <- `this` 資料維度 + +[options="header",width="100%",cols="1>m,3>s,7<,3<,3^,20<",grid="rows"] +|===================================================================== +|Const?|Name | Parameters | Return_Type| Time_Complexity| Description +||insert|(Vector const& `v`)|void| O(1) +|將向量 `v` 加到set中 +||erase|(Vector const& `v`)|bool| O(N) +|將向量 `v` 從set中移除, '~TODO:可以再優化~' +||build|()|void|O(KN logN) or O(1) +|檢查距上一次 `build()` 至今是否有 `insert/erase` 被呼叫, +若有, 重新建樹, 否則不做事 +||forceBuild|()|void|O(KN logN) +|重新建樹 +|const|query|(Vector const& `v`, + +size_t `i`, + +bool `cmp`)|Vectors +|O(logN) ~Expected~ +|於set中找尋距離 `v` 前 `i` 近的向量, 並依照由近而遠的順序排序. +如果有兩個向量 `v1`,`v2` 距離一樣, 且 `cmp` 為 `true` , 則直接依照 +`v1 < v2` 來決定誰在前面. 最後回傳一陣列包含所有解. +||clear|()|void|O(1) +|清空所有資料 +||reset|(size_t `dimension`)|size_t|O(1) +|清空所有資料並且指定維度為 `max(1, dimension)` 並且回傳指定後的維度 +|===================================================================== + +[NOTE] +======================================== +* 實測結果發覺比 `KD_Tree` 有效率多了... +* 'TODO' `insert()`, `erase()` 算是未完成功能 + +======================================== + +''' + === meow:: *KD_Tree<Vector, Scalar>* (C++ class) ==== Description `KD_Tree` 全名k-dimension tree, 用來維護由 *N個K維度向量所成的集合*, @@ -472,3 +543,9 @@ Value const& `delta`) ''' + +== Test + + +== Bug Report / Contact + * E-Mail: cat.hook31894 \~在~ gmail.com |