- 论坛徽章:
- 0
|
复习了下算法 ，搞到凌晨2点，写了个简陋的线段树
测试发现， 在我提供的例子中，速度是普通版的1. 8倍 左右，
我用vector存储 window id , 添加、删除修改操做比较低效，
换成set 应该能大幅提高修改操作效率，可这样会影响到查询效率,
因为相比与vector ，set的遍历很耗时的。
vc 2008 ,release
- #include <set>
- #include <vector>
- using namespace std;
- #include <stdio.h>
- #include <stdlib.h>
- #include <time.h>
- #include <windows.h>
- #define MAX(a ,b) ((a)>(b)?(a):(b))
- #define MIN(a ,b) ((a)<(b)?(a):(b))
- /*分辨率*/
- #define MAX_WIDTH 1024
- #define MAX_HEIGHT 768
- /*窗口数目*/
- #define WINDOW_CNT 1000000
- /*鼠标点击 测试次数*/
- #define CLICK_CNT 100
- struct window{
- int id;
- int ltX ;//left top x
- int ltY;
- int rbX;//right bottom x;
- int rbY;
- }windows[WINDOW_CNT];
- /*待测鼠标点击数组*/
- struct click{
- int posX;
- int posY;
- }clicks[CLICK_CNT];
- typedef struct{
- int left;
- int right;
- vector<int> windowSet;
- int color;/*if it has childs ,set if to 1*/
- }node;
- /*width and height v-binary-tree*/
- node treeRoot[MAX_WIDTH * 4 + 1];
- void set_left_right(node *head ,int pos ,int left ,int right)
- {
- head[pos].left = left ;
- head[pos].right = right;
- head[pos].color =0;
- if(left == right) return;
- /*else set childs*/
- int middle = (left +right)>>1;
- int lChild = pos<<1;
- set_left_right(head ,lChild ,left ,middle);
- set_left_right(head ,++lChild ,++middle ,right);
- }
- void addNode(node *head ,int nodePos ,int windowId ,int lPos ,int rPos)
- {
- int left = head[nodePos].left;
- int right =head[nodePos].right;
- int middle = (left+right)>>1;
- int lChild = nodePos<<1;
- if(lPos ==left && rPos == right){
- head[nodePos].windowSet.push_back(windowId);
- return ;
- }
- /*else set color flag*/
- head[nodePos].color = 1;
- if(middle >= rPos){
- addNode(head ,lChild ,windowId ,lPos ,rPos);
- }else if(middle < lPos){
- addNode(head ,++lChild,windowId ,lPos ,rPos);
- }else{
- addNode(head ,lChild ,windowId ,lPos ,middle);
- addNode(head ,++lChild ,windowId ,++middle ,rPos);
- }
- }
- void mapWindow2Tree()
- {
- window *pw = NULL;
- for(int i=0 ;i<WINDOW_CNT ;++i){
- pw =windows + i;
- addNode(treeRoot ,1 ,pw->id ,pw->ltX ,pw->rbX);
- }
- }
- void init()
- {
- int i;
- srand(time(0));
- for(i=0 ;i<WINDOW_CNT ;++i){
- windows[i].id = i;
- windows[i].ltX = rand()%MAX_WIDTH;
- windows[i].ltY = rand()%MAX_HEIGHT;
- windows[i].rbX = rand()%MAX_WIDTH;
- windows[i].rbY = rand()%MAX_HEIGHT;
- windows[i].ltX = MIN(windows[i].ltX ,windows[i].rbX);
- windows[i].rbX = MAX(windows[i].ltX ,windows[i].rbX);
- windows[i].ltY = MIN(windows[i].ltY ,windows[i].rbY);
- windows[i].rbY = MAX(windows[i].ltY ,windows[i].rbY);
- }
- for(i=0 ;i<CLICK_CNT ;++i){
- clicks[i].posX = rand()%MAX_WIDTH;
- clicks[i].posY = rand()%MAX_HEIGHT;
- }
- set_left_right(treeRoot ,1 ,0 ,MAX_WIDTH-1);
- mapWindow2Tree();
- }
- void printClicks()
- {
- for(int i=0 ;i<CLICK_CNT ;++i){
- printf("%d\t%d\n" ,clicks[i].posX ,clicks[i].posY);
- }
- }
- static int resultCnt;
- static int results[WINDOW_CNT];
- static int chksize;
- void recur_find(node* head ,int nodePos ,click *event)
- {
- node *pNode = head + nodePos;
- window *pw = NULL;
-
- vector<int> &ws = pNode->windowSet;
- int vSize = ws.size();
- for(int i=0 ;i<vSize ;++i){
- pw = windows + ws[i];
- if(pw->ltY<= event->posY && pw->rbY >=event->posY)
- ++resultCnt;
- }
- chksize += pNode->windowSet.size();
- if(pNode->color != 0 && pNode->left<pNode->right){
- int lChild = nodePos<<1;
- int middle = (pNode->left + pNode->right)>>1;
- if(event->posX <= middle){
- recur_find(head ,lChild ,event);
- }else{
- recur_find(head ,++lChild ,event);
- }
- }
- }
- void click_find(click *event)
- {
- recur_find(treeRoot ,1 ,event);
- }
- static int allCnt ;
- void vtree_find()
- {
- allCnt =0;
- chksize = 0;
- for(int i=0 ;i<CLICK_CNT ;++i){
- resultCnt = 0;
- click_find(clicks + i);
- allCnt += resultCnt;
- }
- printf("allCnt : %d ave chk : %d\n" ,allCnt ,chksize/CLICK_CNT);
- }
- void iter_find()
- {
- allCnt =0;
- window *pw = NULL;
- click *ck = NULL;
- for(int i=0 ;i<CLICK_CNT ;++i){
- ck = clicks + i;
- for(int j=0 ;j<WINDOW_CNT ;++j){
- pw = windows + j;
- if(pw->ltX <= ck->posX && pw->rbX >=ck->posX && pw->ltY<=ck->posY && pw->rbY >=ck->posY)
- ++allCnt;
- }
- }
- printf("allCnt : %d\n" ,allCnt);
- }
- long timeCal(void (*f)())
- {
- long beginTime = GetTickCount();
- f();
- long endTime = GetTickCount();
- return endTime - beginTime;
- }
- void timeTest()
- {
- printf("\nvtree find :\n");
- for(int i=0;i<10 ;i++){
- printf("%d " ,timeCal(vtree_find));
- }
- printf("\niter find :\n");
- for(int i=0 ;i<10 ;i++){
- printf("%d " ,timeCal(iter_find));
- }
- }
- int main()
- {
- init();
- //printClicks();
- timeTest();
- system("pause");
-
- return 0;
- }
[ 本帖最后由 windyrobin 于 2009-3-29 13:44 编辑 ] |
|
免费注册
楼主: 太平绅士
发表于 2009-03-27 10:56
