Daviddr's Blog

2010年8月3日星期二

消退速度

半年多沒碰程式..
編譯器塵封許久，都快忘記介面的樣子囉..

這半年都在練習腦力外的活動，
發現「學習」這件事，都有個特質，
凡非天生就會的東西，總是要練習到一個質量後，
才能穩定固著下來，退步的速度也才會變慢。

而無論是聰明或駑鈍，
想通達「完全瞭解」的路，都會是一樣「長」....

2010年1月3日星期日

2009年12月27日星期日

閉路搜尋


#include <conio.h>
#include <cstdarg>
#include <cstdio>
#include "global.h"


#define _STACK_CHECK_BOUNDARY_
template <class T, int N=512>
class Stack
{
    T& err (int n) {
        static char* s[] = {
            "Overflow","Underflow",
            "Out of range","Empty"
        };
        puts (s[n]); getch(); 
        return d[0];
    }
public:
    T d[N];                //資料項
    int n;                 //元素個數  
    Stack()      { reset(); } 
    void reset() { n = 0; }

#ifdef _STACK_CHECK_BOUNDARY_
    void push (T x)       { if (n<N) d[n++] = x; else err(0);}
    T pop()               { return n? d[--n]: err(1); }
    T& operator*()        { return n>0? d[n-1]: err(3); }
    T& operator[] (int i) { return 0<=i&&i<n? d[i]: err(2); }
#else
    void push (T x)       { d[n++] = x; }
    T pop()               { return n? d[--n]: *d; }
    T& operator*()        { return d[n-1]; }
    T& operator[] (int i) { return d[i]; }
#endif
};


//------------------------------------------------------------
// 使用方式:
//
//   1. 先 reset
//   2. 以 add_vertex 依序由 0~N 號配置頂點
//   3. 用 add_edge 加入目前點的外接點群
//   4. 重複 2 3 步直到配置完畢
//
//------------------------------------------------------------

struct Graph                        //圖形結構
{
    enum {
        MAX_V  = 256,               //節點最大個數
        MAX_ES = 4096               //Edge Stack 的容量
    };
    struct Vertex {
        int* edge;                  //鄰接點群
        int  nEdge;                 //鄰接邊數 (接出去的邊數)
    };
    
    Vertex  V [MAX_V];              //Vertex stack
    int     nV;                     //目前的頂點數
    int     curV;                   //目前正在做設置的頂點編號
    int     ES[MAX_ES];             //Edge Stack
    int     nES;                    //目前的邊線數

    void reset ()
    {
        nV = nES = 0;
    }

    void add_vertex (int id)        //id 為欲設置的頂點編號
    {
        curV = id;
        if (id != nV) 
            ERROR_MSG3_("頂點設置錯誤: %d 應為 %d", id, nV);
        V[curV].edge  = &ES[nES];
        V[curV].nEdge = 0;
        nV++;
    }

    void add_edge (int id)          //id 為欲外接的頂點編號
    {
        V[curV].nEdge++;
        ES[nES++] = id;
    }

    void add_edges (int v, int n...)
    {
        add_vertex (v);
        va_list p;
        va_start (p, n);
        while (n-- > 0) 
            add_edge (va_arg (p, int));
    }

    void print_edges ()
    {
        int i, j;
        for (i=0; i<nV; ++i) {
            printf ("\n %2d: ", i); 
            for (j=0; j<V[i].nEdge; ++j)
                printf ("%2d ", V[i].edge[j]); 
        }
    }
};



//------------------------------------------------------------
// 閉路搜尋: 
//
//     使用 Tarjan 算法尋找 strongly connected nodes
//     並略去元素個數為 1 或 2 的解 
//
//------------------------------------------------------------

class FindLoops                         //閉路搜尋算法
{
    typedef Stack<int,Graph::MAX_ES> TStack; 

    Graph::Vertex* V; 
    TStack  stack;                      //保存正被遍歷的頂點群
    int     visit    [Graph::MAX_V];    //存放頂點的 DFS 拜訪次序
    bool    bInStack [Graph::MAX_V];    //標示頂點是否在 stack 中
    int     order;                      //目前的拜訪次序

    void tarjan (int v)                 //傳入起始節點編號
    {
        static int cur;
        int  min = visit[v] = order++;  //min 存放頂點可追溯到的
                                        //最前頂點的拜訪次序
        int  t;
        int  n = V[v].nEdge;
        int* e = V[v].edge;
        
        stack.push (v);
        bInStack[v] = true;

        while (n-- > 0) {
            t = *e++;                   //取出鄰接點編號
            if (visit[t] == -1)         //以 DFS 拜訪鄰接點
                tarjan (t);
            else cur = visit[t];
            if (bInStack[t] && cur < min) 
                min = cur;
        }
        if (visit[v] == min) {
            puts ("");
            do printf ("%2d ", t=stack.pop()),
               bInStack[t] = false;
            while (t != v);
        }
    }
public:

    void operator() (Graph& graph)
    {   
        stack.reset();
        V = graph.V;
        order = 0;                //-1 = 未被拜訪
        memset (visit, -1, sizeof visit);
        for (int i=0; i<graph.nV; ++i)
            if (visit[i] < 0)                 
                tarjan (i);            
    }
};

2009年12月26日星期六

前中後序運算式-2

　
以下程式說明了當運算子很多時，
最好用 reverse polish 的 stack 解法，而不要做 recursive descent，
否則 60 幾行可完成的 code 會變成好幾百行...

#include <iostream>
#include <ctype.h>
using namespace std;

template <class T, int N=512>
class Stack
{
    T err (int n)
    {
        static char* s[] = {
            "Overflow","Underflow",
            "Out of range","Empty"
        };
        puts (s[n]); getch(); 
        return d[0];
    }
public:
    T d[N];                //資料項
    int n;                 //元素個數  
    Stack()               { n = 0; }
    void push (T x)       { if (n<N) d[n++] = x; else err(0);}
    T pop()               { return n? d[--n]: err(1); }
    T& operator*()        { return n>0? d[n-1]: err(3); }
    T& operator[] (int i) { return 0<=i&&i<n? d[i]: err(2); }
};
class Expression
{
    char *s, c, *p, buf[512];     

    void next () {c = *s++;}

    void put (char c1, char c2=0) {
        *p++ = c1;
        if (c2 != 0) *p++ = c2;
    }

    int expr ()
    {
        if (!or()) return 0;
        while (c=='|') {
            next(); if(c != '|') return 0;
            next(); if(!or()) return 0;
            put ('|','|');
        }return 1;
    }
    int or ()
    {
        if (!and()) return 0;
        while (c=='&') {
            next(); if(c != '&') return 0;
            next(); if(!and()) return 0;
            put ('&','&');
        }return 1;
    }
    int and ()
    {
        if (!compar()) return 0;
        char op[3] = {0,0,0};
        while (c=='<' || c=='>') {
            op[0] = c;
            next(); if(c == '=') {op[1]='='; next();}
            if(!compar()) return 0;
            put (op[0], op[1]);
        }return 1;
    }
    int compar ()
    {
        if (!term()) return 0;
        for (char op; c=='+' || c=='-';) {
            op = c; next(); if(!term()) return 0;
            put (op);
        }return 1;
    }
    int term ()
    {
        if (!fact()) return 0;
        for (char op; c=='*' || c=='/';) {
            op = c; next(); if (!fact()) return 0;
            put (op);
        }return 1;
    }
    int fact ()
    {
        if (!expo()) return 0;
        while (c=='^') {
            next(); if (!expo()) return 0;
            put ('^');
        }return 1;
    }
    int expo ()
    {
        if (c == '!') {
            next(); if(!invers()) return 0;
            put ('!');
        }
        else if (!invers()) return 0;
        return 1;
    }
    int invers ()
    {
        if (isalpha(c)) {
            put (c);  
            next(); return 1;
        }
        else if (c=='(') {
            next();  
            if (expr() && c == ')') {
                next(); return 1;
            }
        }return 0;
    }
   
    //---------------------------------
    struct Node
    {
        char c[3];
        Node *L,*R;
        Node () { c[1]=c[2]=0; L=R=0; }
        Node (char c1, char c2=0, Node* l=0, Node* r=0) {
            c[0]=c1; c[1]=c2; c[2]=0; L=l; R=r;
        }
        Node (char c1, Node* l, Node* r) {
            c[0]=c1; c[1]=0; L=l; R=r;
        }
    };

    Node* build_exptree (char* postfix)
    {
        Stack <Node*> s;
        Node *o, *L, *R;
        char c1, c2, *p = postfix;
        
        while(*p)
        {
            if(isalpha(*p) || isdigit(*p))
            {
                s.push (new Node(*p));
            }
            else
            {
                c1 = *p; c2 = 0;
                L = 0;               
                R = s.pop();
                if (c1 != '!') L = s.pop();
                if (c1=='&'||c1=='|') c2 = *++p;
                else if ((c1=='<'||c1=='>')&& p[1]=='=')
                    c2 = *++p;
                s.push (new Node (c1, c2, L, R));
            }
            p++;
        }
        return s.pop();
    }

    void preorder (Node *x)
    {
        if(x != NULL) {
            cout << x->c;
            preorder (x->L);
            preorder (x->R);
        }
    }

    void inorder (Node *x)
    {
        if(x != NULL) {
            preorder (x->L);
            cout << x->c;
            preorder (x->R);
        }
    }
    void postorder (char* exp)
    {
        p = buf; s = exp; next();
        expr(); put(0);
    }
    //-----------------------------------

public:
    void postfix (char* exp)
    {
        postorder (exp); cout << buf;
    }

    void prefix (char* exp)
    {
        postorder (exp);
        preorder (build_exptree (buf));
    }        
};


void main (/* daviddr */)
{
    char* s[] = {
        "(a-b*(c+d)^e)&&((f+g^h)-i*j+k/l)",
        "!((a^b-c/d+e/f))||(g-(h^i+j*k)/l+m)",
        "(a-b/c)*d^f<=(g+h*i)/j+k^l-m"
    };
    Expression exp;

    for (int i=0; i<3; i++) {
        puts(""); exp.postfix(s[i]);
        puts(""); exp.prefix (s[i]);
    }
}

2009年12月25日星期五

若頂點總數為 V
所有頂點的鄰接點數總和為 N

常見的結構有:

1. Adjacency Matrix
使用空間 V * V

2. Adjacency List:
    記錄 out edge
    若串列指標總和大小為 N
    使用空間 V * (2*(1+N))

3. Adjacency Multilists:
    用 2 個 list 記錄 out edge 與 in edge
    使用空間 2 * V * (2*(1+N))

4. Sequential Representation 或 Index Table:
    當頂點數多但 edge 少時，相當省空間與時間。
    使用空間 V + (V+N)
    前頭的 V 為索引表大小

2009年12月24日星期四

高維下的 kd-tree

　
http://www.codeproject.com/KB/architecture/KDTree.aspx

Anton Milev 文中寫到：

For small dimensions the KD-tree can be much faster then sequential search, however for 10-dimensional space the checked nodes for rises to about 25% for. It is possible to reduce this number 2-3 times if the tree is balanced but the tendency of exponential rise of the checked nodes makes the KD unpracticle above 15 dimensions. The second curve shows how KD / Brute ratio changes with space dimension, Brute stands for sequential search, it checks all nodes. Practiclly, for 10000 points, the KD tree becomes as fast as the sequential search for dimensions bigger then 10.

With the analyses made in this article I showed that the standard KD-tree is not good for dimensions beyond 10. In my next article about KD trees and the nearest neighbours search in N-dimensions I will introduce an extention of the quad tree for N-dimensional data - QD-tree, it is faster then KD and allows run-time balancing. However for big dimensions it again becomes slow. This problem is well known in the computational geometry, this would be so for any data structure based only on tree. From another hand it is not possible to make a multidimensional linked-list and to include it in the tree. The problem is quite complicated and requires new kinds data structures.

2009年12月23日星期三

Voronoi Diagram

Voronoi Diagram / Delaunay Triangulation
http://www.cs.cornell.edu/Info/People/chew/Delaunay.html
+Crust
http://www.cs.unc.edu/~snoeyink/demos/crust/home.html

訂閱：文章 (Atom)

Daviddr's Blog

2010年8月3日星期二

消退速度

2010年1月3日星期日

Modify k-Means

2009年12月27日星期日

閉路搜尋

2009年12月26日星期六

前中後序運算式-2

2009年12月25日星期五

有向鄰接圖資料結構

2009年12月24日星期四

高維下的 kd-tree

2009年12月23日星期三

Voronoi Diagram

總網頁瀏覽量

內容引用事項

網誌存檔

關於我自己

追蹤者

熱門文章

Daviddr's Blog

2010年8月3日 星期二

消退速度

2010年1月3日 星期日

Modify k-Means

2009年12月27日 星期日

閉路搜尋

2009年12月26日 星期六

前中後序運算式-2

2009年12月25日 星期五

有向鄰接圖資料結構

2009年12月24日 星期四

高維下的 kd-tree

2009年12月23日 星期三

Voronoi Diagram

總網頁瀏覽量

內容引用事項

網誌存檔

關於我自己

追蹤者

熱門文章

2010年8月3日星期二

2010年1月3日星期日

2009年12月27日星期日

2009年12月26日星期六

2009年12月25日星期五

2009年12月24日星期四

2009年12月23日星期三