diff options
author | cathook <b01902109@csie.ntu.edu.tw> | 2014-04-23 00:19:10 +0800 |
---|---|---|
committer | cathook <b01902109@csie.ntu.edu.tw> | 2014-04-23 00:19:10 +0800 |
commit | 38b23620954f142ccf6653a58c47ff04d516be9c (patch) | |
tree | f02d96c9b4ef27692e404741395f3cb377870c83 | |
parent | 5d4e65d6209a078fce2ef094ff2cb812b040513e (diff) | |
download | meow-38b23620954f142ccf6653a58c47ff04d516be9c.tar meow-38b23620954f142ccf6653a58c47ff04d516be9c.tar.gz meow-38b23620954f142ccf6653a58c47ff04d516be9c.tar.bz2 meow-38b23620954f142ccf6653a58c47ff04d516be9c.tar.lz meow-38b23620954f142ccf6653a58c47ff04d516be9c.tar.xz meow-38b23620954f142ccf6653a58c47ff04d516be9c.tar.zst meow-38b23620954f142ccf6653a58c47ff04d516be9c.zip |
add footer, test
-rw-r--r-- | _test/meowpp_VP_Tree.cpp | 4 | ||||
-rw-r--r-- | footer.asciidoc | 19 | ||||
-rw-r--r-- | meowpp/dsa/VP_Tree.h | 4 | ||||
-rw-r--r-- | meowpp/dsa/VP_Tree.hpp | 31 |
4 files changed, 24 insertions, 34 deletions
diff --git a/_test/meowpp_VP_Tree.cpp b/_test/meowpp_VP_Tree.cpp index 8d5e903..34c979c 100644 --- a/_test/meowpp_VP_Tree.cpp +++ b/_test/meowpp_VP_Tree.cpp @@ -10,8 +10,8 @@ #include <queue> static int N = 100000; -static int D = 64; -static int MAX = 100; +static int D = 32; +static int MAX = 1000; typedef long long lnt; diff --git a/footer.asciidoc b/footer.asciidoc index b6e1ea9..a6301ee 100644 --- a/footer.asciidoc +++ b/footer.asciidoc @@ -1,5 +1,24 @@ == Test +=== ACM 相關題目 +[options="header",width="70%",cols="3<s,3<,4^,1^,1<,2^m",grid="rows"] +|======================================================================= +| Name | Problem | Link | Status | Time | source +| KD_Tree | 'Retrenchment' | +http://acm.csie.org/ntujudge/problem.php?id=1971[NTU-OJ] +https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4052[ACM-ICPC Live] +| Accept | 0.083 | http://codepad.org/U85ruse5[codepad] + + +| VP_Tree | 'Retrenchment' | +http://acm.csie.org/ntujudge/problem.php?id=1971[NTU-OJ] +https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4052[ACM-ICPC Live] +| Accept | 0.516 | http://codepad.org/03dW6ZHV[codepad] + + +|======================================================================= + + == Bug Report / Contact 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() #** /////////////////// |