meow::VP_Tree< Vector, Scalar > Class Template Reference

跟KD_Tree很像歐 More...

#include "VP_Tree.h"

Public Types
typedef std::vector< Vector >	Vectors

Public Member Functions
	VP_Tree ()
	constructor, with dimension = 1 More...
	VP_Tree (VP_Tree const &tree2)
	constructor, 複製資料 More...
	VP_Tree (size_t dimension)
	constructor, 給定dimension More...
	~VP_Tree ()
	destructor More...
VP_Tree &	copyFrom (VP_Tree const &tree2)
	複製資料 More...
void	insert (Vector const &vector)
	將給定的Vector加到set中 More...
bool	erase (Vector const &vector)
	將給定的Vector從set移除 More...
void	build ()
	檢查至今是否有 insert/erase 被呼叫來決定是否 rebuild() More...
void	forceBuild ()
	重新建樹 More...
Vectors	query (Vector const &vector, size_t nearestNumber, bool compareWholeVector) const
	查找 More...
void	clear ()
	清空所有資料 More...
size_t	reset (size_t dimension)
	清空所有資料並重新給定維度 More...
VP_Tree &	operator= (VP_Tree const &tree2)
	same as copyFrom(tree2) More...

Detailed Description

template<class Vector, class Scalar>
class meow::VP_Tree< Vector, Scalar >

跟KD_Tree很像歐

VP_Tree 用來維護由 N個K維度向量所成的集合 , 並可於該set中查找 前i個離給定向量最接近的向量* . 不像 KD_Tree 二分樹每次都選擇一個維度去分, 分成小的跟大的, VP_Tree 每次選一個點, 將資料分成 離這個點近的, 跟離這個點遠的. 至於怎麼選呢...., 嘛還沒研究, 先random

參考資料連結:

• http://stevehanov.ca/blog/index.php?id=130
• http://pnylab.com/pny/papers/vptree/vptree

Template Class Operators Request

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=0or4 | |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 | 大小比較 |

Note

: -實測結果發覺, 維度小的時候, 比起中規中矩的 KD_Tree, VP_Tree 有 random 於其中, 因此時間複雜度只是期望值 O(logN) 但是測資大到 一定程度, KD_Tree 效率會一整個大幅掉下, 但 VP_Tree 幾乎不受影響 -TODO insert(), erase() 算是未完成功能

Definition at line 51 of file VP_Tree.h.

Member Typedef Documentation

template<class Vector, class Scalar>

typedef std::vector<Vector> meow::VP_Tree< Vector, Scalar >::Vectors

Definition at line 53 of file VP_Tree.h.

Constructor & Destructor Documentation

template<class Vector, class Scalar>

meow::VP_Tree< Vector, Scalar >::VP_Tree ( )

inline

constructor, with dimension = 1

Definition at line 212 of file VP_Tree.h.

template<class Vector, class Scalar>

meow::VP_Tree< Vector, Scalar >::VP_Tree ( VP_Tree< Vector, Scalar > const &  tree2 )

inline

constructor, 複製資料

Definition at line 217 of file VP_Tree.h.

template<class Vector, class Scalar>

meow::VP_Tree< Vector, Scalar >::VP_Tree ( size_t  dimension )

inline

constructor, 給定dimension

Definition at line 225 of file VP_Tree.h.

template<class Vector, class Scalar>

meow::VP_Tree< Vector, Scalar >::~VP_Tree ( )

inline

destructor

Definition at line 234 of file VP_Tree.h.

Member Function Documentation

template<class Vector, class Scalar>

void meow::VP_Tree< Vector, Scalar >::build ( )

inline

檢查至今是否有 insert/erase 被呼叫來決定是否 rebuild()

Definition at line 275 of file VP_Tree.h.

template<class Vector, class Scalar>

void meow::VP_Tree< Vector, Scalar >::clear ( )

inline

清空所有資料

Definition at line 313 of file VP_Tree.h.

template<class Vector, class Scalar>

VP_Tree& meow::VP_Tree< Vector, Scalar >::copyFrom ( VP_Tree< Vector, Scalar > const &  tree2 )

inline

複製資料

Definition at line 241 of file VP_Tree.h.

template<class Vector, class Scalar>

bool meow::VP_Tree< Vector, Scalar >::erase ( Vector const &  vector )

inline

將給定的Vector從set移除

Definition at line 260 of file VP_Tree.h.

template<class Vector, class Scalar>

void meow::VP_Tree< Vector, Scalar >::forceBuild ( )

inline

重新建樹

Definition at line 284 of file VP_Tree.h.

template<class Vector, class Scalar>

void meow::VP_Tree< Vector, Scalar >::insert ( Vector const &  vector )

inline

將給定的Vector加到set中

Definition at line 252 of file VP_Tree.h.

template<class Vector, class Scalar>

VP_Tree& meow::VP_Tree< Vector, Scalar >::operator= ( VP_Tree< Vector, Scalar > const &  tree2 )

inline

same as copyFrom(tree2)

Definition at line 330 of file VP_Tree.h.

template<class Vector, class Scalar>

Vectors meow::VP_Tree< Vector, Scalar >::query ( Vector const &  vector, size_t  nearestNumber, bool  compareWholeVector  ) const

inline

查找

於set中找尋距離指定向量前 i 近的向量, 並依照由近而遠的順序排序. 如果有兩個向量v1,v2 距離一樣, 且 cmp 為true , 則直接依照 v1<v2 來決定誰在前面. 最後回傳一陣列包含所有解.

Definition at line 296 of file VP_Tree.h.

template<class Vector, class Scalar>

size_t meow::VP_Tree< Vector, Scalar >::reset ( size_t  dimension )

inline

清空所有資料並重新給定維度

Definition at line 323 of file VP_Tree.h.

---

The documentation for this class was generated from the following file:

• meowpp/dsa/VP_Tree.h