diff options
Diffstat (limited to 'meowpp')
| -rw-r--r-- | meowpp/dsa/VP_Tree.h | 4 | ||||
| -rw-r--r-- | meowpp/dsa/VP_Tree.hpp | 31 |
2 files changed, 3 insertions, 32 deletions
diff --git a/meowpp/dsa/VP_Tree.h b/meowpp/dsa/VP_Tree.h index 669eb0f..1877b74 100644 --- a/meowpp/dsa/VP_Tree.h +++ b/meowpp/dsa/VP_Tree.h @@ -158,7 +158,9 @@ namespace meow{ //# //#[NOTE] //#======================================== - //# * 實測結果發覺比 `KD_Tree` 有效率多了... + //# * 實測結果發覺, 維度小的時候, 比起中規中矩的 `KD_Tree`, `VP_Tree` 有 + //# 'randomp' 於其中, 因此時間複雜度只是期望值 'O(logN)' 但是測資大到 + //# 一定程度, `KD_Tree` 效率會一整個大幅掉下, 但 `VP_Tree` 幾乎不受影響 //# * 'TODO' `insert()`, `erase()` 算是未完成功能 //# //#======================================== diff --git a/meowpp/dsa/VP_Tree.hpp b/meowpp/dsa/VP_Tree.hpp index a3a0d82..ba97ad7 100644 --- a/meowpp/dsa/VP_Tree.hpp +++ b/meowpp/dsa/VP_Tree.hpp @@ -66,7 +66,6 @@ namespace meow{ inline Scalar VP_Tree<Vector, Scalar>::split(ssize_t __first, ssize_t __last, size_t __order, Vector const& __center){ - //printf("%ld %ld %lu\n", __first, __last, __order); ssize_t first0 = __first; ssize_t last0 = __last; ssize_t order0 = __order; @@ -77,21 +76,6 @@ namespace meow{ while(__first < __last){ size_t threshold_index = __first + rand() % (__last - __first + 1); Scalar threshold(dist2[threshold_index - first0]); - /* - printf("range(%ld, %ld) dist2 = %3lld from %d\n", - __first - first0, __last - first0, - threshold, threshold_index - first0); - for(int i = first0; i <= last0; i++){ - if(i == __first) printf("+"); - if(i == threshold_index) printf("<"); - printf("<%lld,%lld,(%lld)>", _vectors[i][0], _vectors[i][1], - dist2[i - first0]); - if(i == threshold_index) printf(">"); - if(i == __last) printf("+"); - printf(" "); - } - printf("\n"); - // */ size_t large_first = __last + 1; for(size_t i = __first; __first <= large_first - 1; large_first--){ if(threshold < dist2[large_first - 1 - first0]) continue; @@ -121,21 +105,6 @@ namespace meow{ } } } - /* - for(int i = first0; i <= last0; i++){ - if(i == __first) printf("+"); - if(i - first0 == order0) printf("<"); - printf("<%lld,%lld,(%lld)>", _vectors[i][0], _vectors[i][1], - dist2[i - first0]); - if(i - first0 == order0) printf(">"); - if(i == __first) printf("+"); - printf(" "); - } - printf("\n"); - printf("dist2(from<%lld,%lld>) = %lld\n", - __center[0], __center[1], - dist2[__first - first0]); - // */ return dist2[__first - first0]; } ////////////////////// **# build() #** /////////////////// |