diff options
Diffstat (limited to 'meowpp/dsa/KD_Tree.h')
| -rw-r--r-- | meowpp/dsa/KD_Tree.h | 120 |
1 files changed, 73 insertions, 47 deletions
diff --git a/meowpp/dsa/KD_Tree.h b/meowpp/dsa/KD_Tree.h index 2ba81a1..035d6eb 100644 --- a/meowpp/dsa/KD_Tree.h +++ b/meowpp/dsa/KD_Tree.h @@ -8,6 +8,24 @@ #include <utility.h> namespace meow{ + //# + //#=== meow:: *KD_Tree<Vector, Scalar>* (C++ class) + //#==== Description + //# `KD_Tree` 全名k-dimension tree, 用來維護由 *N個K維度向量所成的集合*, + //# 並可於該set中查找 *前i個離給定向量最接近的向量* + //# + //#==== 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`) | bool | 權重比較 + //#|const | Scalar|operator* |(Scalar `s`) | Scalar | 相乘 + //#|const | Scalar|operator+ |(Scalar `s`) | Scalar | 相加 + //#|const | Scalar|operator- |(Scalar `s`) | Scalar | 相差 + //#|const | Scalar|operator< |(Scalar `s`) | bool | 大小比較 + //#|===================================================================== + //# template<class Vector, class Scalar> class KD_Tree{ private: @@ -68,68 +86,76 @@ namespace meow{ std::vector<size_t>* __orders, int __depth); public: + //#==== Custom Type Definitions + //# * `Vectors` <- `std::vector<Vector>` + //# typedef typename std::vector<Vector> Vectors; // KD_Tree(); KD_Tree(size_t __dimension); ~KD_Tree(); - // + + //#==== Support Methods + //# + //# * N <- `this` 中擁有的資料數 + //# * K <- `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中 void insert(Vector const& __vector); + + + //#||erase|(Vector const& `v`)|bool| O(N) + //#|將向量 `v` 從set中移除, '~TODO:可以再優化~' bool erase (Vector const& __vector); + + + //#||build|()|void|O(KN logN) or O(1) + //#|檢查距上一次 `build()` 至今是否有 `insert/erase` 被呼叫, + //# 若有, 重新建樹, 否則不做事 void build(); + + + //#||forceBuild|()|void|O(KN logN) + //#|重新建樹 void forceBuild(); - // + + + //#|const|query|(Vector const& `v`,\size_t `i`,\bool `cmp`)|Vectors + //#|O(KN ^1-1/K^ ) + //#|於set中找尋距離 `v` 前 `i` 近的向量, 並依照由近而遠的順序排序. + //# 如果有兩個向量 `v1`,`v2` 距離一樣, 且 `cmp` 為 `true` , 則直接依照 + //# `v1 < v2` 來決定誰在前面. 最後回傳一陣列包含所有解. Vectors query(Vector const& __vector, size_t __nearestNumber, bool __compareWholeVector) const; - // + + + //#||clear|()|void|O(1) + //#|清空所有資料 void clear(); + + + //#||reset|(size_t `dimension`)|void|O(1) + //#|清空所有資料並且指定維度為 `dimension` void reset(size_t __dimension); + + + //#|===================================================================== }; - /********************************************************* - @asciidoc - === meow:: *KD_Tree<Vector, Scalar>* (C++ class) - .Description - `KD_Tree` is *K-dimension tree*, which is a multiple set contain lots of - vector with K dimension. - - .Template Request - * `Vector` should has `operator[]` to allow the KD_Tree, `operator<` to - compare when two vector are point to the same place, `operator==` - access the k-dimensions - * `Scalar` should has `operator*`, `operator+`, `operator<` - - .Support Methods - * N <- numbers of element in the kd-tree - * K <- dimensions - * `Vector` is the tyepname of the vector - * `Vectors` is the typename of the std::vector<Vector> - [options="header",width="100%",cols="1>,1<s,5<,1<,2<,10<",grid="rows"] - |======================================================================= - |Const?|Name| Parameters| Return Type| Time Complexity| Description - |const|root|(size_t number)|size_t|very fast| - ||insert|(Vector const& v)|void|O(1)|Insert a vector - ||erase |(Vector const& v)|bool|O(N*x)| Find a vector which is the same - as `v` and remove it from the KD_Tree, `x` in the Big-O time complex - is cost by `Vector::operator==`. - || build|()|void|O(KN logN) if need | Build the data structure if need. - || forceBuild|()|void|O(KN logN) | Build the data structure(the `insert()` - method will not build the data structure immediately) - |const|query|(Vector const& v, int k)|Vectors|O(kN ^1-1/k^ ) | - Using Euclidean-Distance to find the 1st to k-th nearest neighbor from `v` . - And return; - ||clear|()|O(1)|Clear all data - ||reset|(size_t dimension)|O(1)|Clear all data and then - set the this->dimension be `dimension` - |======================================================================= -NOTE: O(kN ^1-1/k^ ) is reference from wiki. + -`query()` and `rangeQuery()` will run `build()` first if you called `insert()` -before call them. And `build()` is very slow, so you should not use this class -as a dynamic tree - -''' -@asciidoc- - *********************************************************/ + //# + //#[NOTE] + //#======================================== + //# * 此資料結構只有在 N >> 2 ^K^ 時才比較有優勢, + //# 當 K 逐漸變大時, 所花時間會跟暴搜沒兩樣 + //#======================================== + //# + //# ''' } #include "KD_Tree.hpp" |