1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
|
#ifndef dsa_VP_Tree_H__
#define dsa_VP_Tree_H__
#include "../math/utility.h"
#include <cstdlib>
#include <list>
#include <vector>
#include <queue>
namespace meow{
//#
//#=== 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 | 大小比較
//#|=====================================================================
//#
template<class Vector, class Scalar>
class VP_Tree{
public:
//#==== Custom Type Definitions
//# * `Vectors` <- `std::vector<Vector>`
//#
typedef typename std::vector<Vector> Vectors;
private:
//
struct Node{
size_t _index;
Scalar _threshold;
Node* _nearChild;
Node* _farChild;
Node(size_t __index);
};
struct Answer{
size_t _index;
Scalar _dist2;
//
Answer(size_t __index, Scalar const& __dist2);
Answer(Answer const& __answer2);
};
class AnswerCompare{
private:
Vectors const* _vectors;
bool _cmpValue;
public:
AnswerCompare(Vectors const* __vectors, bool __cmpValue);
bool operator()(Answer const& __a, Answer const& __b) const;
};
typedef std::vector<Answer> AnswerV;
typedef std::priority_queue<Answer, AnswerV, AnswerCompare> Answers;
//
Vectors _vectors;
Node* _root;
size_t _dimension;
bool _needRebuild;
//
Scalar distance2(Vector const& __v1, Vector const& __v2) const;
int distanceCompare(Scalar const& __a2, Scalar const& __b2,
Scalar const& __c2) const;
Scalar split(ssize_t __first, ssize_t __last, size_t __order,
Vector const& __center);
//
Node* build(ssize_t __first, ssize_t __last);
void query(Vector const& __vector,
size_t __k,
AnswerCompare const& __cmp,
Node const* __node,
Answers* __out) const;
void clear(Node* __root);
Node* dup(Node* __root);
public:
VP_Tree();
VP_Tree(VP_Tree const& __tree2);
VP_Tree(size_t __dimension);
~VP_Tree();
VP_Tree& operator=(VP_Tree const& __tree2);
//#==== 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中
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(logN) ~Expected~
//#|於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`)|size_t|O(1)
//#|清空所有資料並且指定維度為 `max(1, dimension)` 並且回傳指定後的維度
size_t reset(size_t __dimension);
//#|=====================================================================
};
//#
//#[NOTE]
//#========================================
//# * 實測結果發覺, 維度小的時候, 比起中規中矩的 `KD_Tree`, `VP_Tree` 有
//# 'randomp' 於其中, 因此時間複雜度只是期望值 'O(logN)' 但是測資大到
//# 一定程度, `KD_Tree` 效率會一整個大幅掉下, 但 `VP_Tree` 幾乎不受影響
//# * 'TODO' `insert()`, `erase()` 算是未完成功能
//#
//#========================================
//#
//# '''
}
#include "VP_Tree.hpp"
#endif // dsa_VP_Tree_H__
|
