摘要: 無聊之際用C#寫了一個彈性物體碰撞模擬玩玩。這個想法源自與前幾天上機課有人想我在機房做一個透視投影的程序，于是就立刻寫了個投影并弄了個線框球上去跳。結果我就想，如果物體有彈性會怎么樣呢？回到宿舍就實踐想法。
這個程序是2D的，用C#主要是因為GDI+寫起來比較方便，至少比可憐的MFC好用，雖然C#的東西又慢又占用CPU使用率。我發誓.NET的Timer肯定不是用WM_TIMER消息搞的，空轉占用CPU都那么高，而且用Sleep還降低不了。過高的CPU占用率持續過久會導致CPU溫度升高……
程序現在還有點問題。譬如物理引擎經典問題：浮點誤差和碰撞穿透。現在還沒100%處理好，雖然絕大多數情況下是沒什么事。第二個就是因為彈性超出了我的物理知識范圍，所以碰撞的速度更高暫時亂寫，等過幾天有空解一個三元二次方程組之后再改改代碼。
先放截圖三張，等程序改好了之后再把代碼弄出來。這個東西很好玩的，嘿嘿。考慮了重力哦。
閱讀全文
posted @
2008-06-05 09:30 陳梓瀚(vczh) 閱讀(5740) |
評論 (9) |
編輯 收藏
摘要: 依然是上一篇文章的程序，換了C#寫。 在Vczh Free Script 2.0的接口里面，我力求讓C++和.NET兩種語言的接口都趨于一致。目前達到了這個目標，C#僅僅比C++多了兩個輔助函數。插件那一部分是相當難寫啊。Vczh Free Script 2.0的C++接口允許插件和腳本交替調用。腳本引擎是本地代碼，做到跟C...
閱讀全文
posted @
2008-05-29 19:57 陳梓瀚(vczh) 閱讀(2273) |
評論 (5) |
編輯 收藏
今天做好了Vczh Free Script 2.0的一個新插件，這個插件可以直接插入class并接管成員調用、構造函數和析構函數等調用。
一、在C++中插入一個類VczhClass和函數write、writeln、read和collect：
1 class VczhClass : public FsClass
2 {
3 protected:
4 public:
5 VczhClass(FsPlugin* Plugin):FsClass(Plugin,L"interpreter_debug")
6 {
7 }
8
9 FsePluginInvoke CallConstructor(int ClassID , FsObject* Parameters , int ParamCount , FsObject& ErrorMessage , FsObject& Result)
10 {
11 GetConsole()->Write(L"VczhClass is creating.\r\n");
12 AddExternalMember(ClassID,L"MethodA",0);
13 AddExternalMember(ClassID,L"MethodB",1);
14 AddExternalMember(ClassID,L"MethodC",2);
15 return fsSuccess;
16 }
17
18 FsePluginInvoke CallMember(int ClassID , int ExternalMemberID , FsObject* Parameters , int ParamCount , FsObject& ErrorMessage , FsObject& Result)
19 {
20 switch(GetMemberID(ExternalMemberID))
21 {
22 case 0:
23 GetConsole()->Write(L"VczhClass::MethodA is invoking.\r\n");
24 break;
25 case 1:
26 GetConsole()->Write(L"VczhClass::MethodB is invoking.\r\n");
27 break;
28 case 2:
29 GetConsole()->Write(L"VczhClass::MethodC is invoking.\r\n");
30 break;
31 }
32 return fsSuccess;
33 }
34
35 void CallDestructor(int ClassID)
36 {
37 GetConsole()->Write(L"VczhClass is destroying.\r\n");
38 }
39 };
40
41 class VczhConsole : public FsPlugin
42 {
43 protected:
44 FsObject FWrite;
45 FsObject FWriteLine;
46 FsObject FRead;
47 FsObject FCollect;
48 VczhClass* FVczhClass;
49
50 VUnicodeString Transform(const FsObject& Value)
51 {
52 return Value.GetReadableString().w_str();
53 }
54 public:
55 VczhConsole(FsEngine* Engine , VUnicodeString CodePath):FsPlugin(Engine,L"interpreter")
56 {
57 FWrite =Engine->CreateExternalResource();
58 FWriteLine =Engine->CreateExternalResource();
59 FRead =Engine->CreateExternalResource();
60 FCollect =Engine->CreateExternalResource();
61
62 GetEnvironment().SetFixedVariable(L"write",FWrite);
63 GetEnvironment().SetFixedVariable(L"writeln",FWriteLine);
64 GetEnvironment().SetFixedVariable(L"read",FRead);
65 GetEnvironment().SetFixedVariable(L"collect",FCollect);
66 GetEnvironment().SetVariable(L"apppath",Engine->CreateString(CodePath.Buffer()));
67 GetEnvironment().SetFixedVariable(L"vmpath",Engine->CreateString(GetConsole()->GetAppPath().Buffer()));
68
69 #ifdef _DEBUG
70 FVczhClass=new VczhClass(this);
71 GetEnvironment().SetFixedVariable(L"VczhClass",FVczhClass->GetCtor());
72 #else
73 FVczhClass=0;
74 #endif
75 }
76
77 ~VczhConsole()
78 {
79 if(FVczhClass)
80 {
81 delete FVczhClass;
82 }
83 }
84
85 FsePluginInvoke Invoke(int ExternalID , FsObject* Parameters , int ParamCount , FsObject& ErrorMessage , FsObject& Result)
86 {
87 if(ExternalID==FWrite.GetExternalID())
88 {
89 for(VInt i=0;i<ParamCount;i++)
90 {
91 GetConsole()->Write(Transform(Parameters[i]));
92 }
93 return fsSuccess;
94 }
95 else if(ExternalID==FWriteLine.GetExternalID())
96 {
97 for(VInt i=0;i<ParamCount;i++)
98 {
99 GetConsole()->Write(Transform(Parameters[i]));
100 }
101 GetConsole()->Write(L"\r\n");
102 return fsSuccess;
103 }
104 else if(ExternalID==FRead.GetExternalID())
105 {
106 for(VInt i=0;i<ParamCount;i++)
107 {
108 GetConsole()->Write(Transform(Parameters[i]));
109 }
110 VUnicodeString Read;
111 GetConsole()->Read(Read);
112 Result=GetOwnedEngine()->CreateString(Read.Buffer());
113 return fsSuccess;
114 }
115 else if(ExternalID==FCollect.GetExternalID())
116 {
117 int* Buffer=0;
118 int Count=GetOwnedEngine()->CollectGarbage(Buffer);
119 FsReleaseBuffer(Buffer);
120 return fsSuccess;
121 }
122 else
123 {
124 return fsGiveUp;
125 }
126 }
127 };
二、書寫測試用的腳本代碼：
1 func()
2 {
3 a=VczhClass.new();
4 a.MethodA();
5 a.MethodB();
6 a.MethodC();
7 }();
8 collect();
這里構造了一個VczhClass并調用了三個成員函數。結束之后，這種寫法保證a再也不可被訪問到，于是調用collect進行垃圾收集（垃圾收集是自動的，但是要觸發條件很難，所以給了個函數進行強制收集）的時候就可以把a手機掉。
三、運行結果：
1 VczhClass is creating.
2 VczhClass::MethodA is invoking.
3 VczhClass::MethodB is invoking.
4 VczhClass::MethodC is invoking.
5 VczhClass is destroying.
四、如果a的成員被保存起來了怎么辦呢？
1 b=null;
2 func()
3 {
4 a=VczhClass.new();
5 a.MethodA();
6 a.MethodB();
7 a.MethodC();
8 b=a.constructor;
9 }();
10 collect();
五、結果是因為b還能繼續使用，所以a就不會銷毀（垃圾收集器解決了這個問題）：
1 VczhClass is creating.
2 VczhClass::MethodA is invoking.
3 VczhClass::MethodB is invoking.
4 VczhClass::MethodC is invoking.
到了這里，一個直接往腳本中插入類的演示就結束了。接下來就是對這個插件進行測試，并且在相應的.NET接口上添加這樣的支持。
posted @
2008-05-28 22:50 陳梓瀚(vczh) 閱讀(1649) |
評論 (0) |
編輯 收藏
各位讀者們，《構造正則表達式引擎》新鮮出爐啦！
《構造正則表達式引擎》 這篇文章描述了純匹配正則表達式和具有高級功能（正向預查，反向預查，匿名捕獲，命名捕獲，命名檢查和貪婪循環等）的正則表達式各自用來匹配正則表達式的算法。
如果大家在書寫好的正則表達式的時候出現了麻煩，或者在開發自己的正則表達式的時候遇到障礙，那不妨讀一讀這篇文章。不過對于沒讀過下面這篇文章的朋友，如果不是很熟悉編譯原理關于DFA和NFA的知識，那么建議首先閱讀下面這篇文章。
《構造可配置詞法分析器》 這篇文章描述了如何從簡單的正則表達式構造ε-NFA，并且一步一步轉換到DFA的算法，而且還提出了一種可配置詞法分析器的可能的實現方法。學習《編譯原理》的朋友們，如果在狀態機那里遇到什么問題的話，那么不妨讀一讀這篇文章。
上面這兩篇文章是我在學習《編譯原理》之后
開發正則表達式引擎的心得體會，在這里與大家分享，共同進步。
posted @
2008-05-21 23:06 陳梓瀚(vczh) 閱讀(109994) |
評論 (36) |
編輯 收藏
摘要: 這篇短文的Idea來源于一篇論文。這篇論文的題目是Higier-Order Functions for Parsing，Graham Hutton寫的。論文中使用了一種叫Miranda的函數式語言來講述如何使用高階函數開發語法分析器。
高階函數很多語言都支持，譬如JavaScript啊，C#的lambda expression啊，或者是我自己做的語言Vczh Free Script 2.0。不過Miranda是惰性計算的語言，我們常用的語言都不具有惰性計算的特性。因此我閱讀了這篇文章之后，自己用Vczh Free Script 2.0寫了一個等價的小規模的語法分析器。結構跟論文中所提到的那個有所區別，不過相同的經驗可以直接應用在JavaScript里面或其它語言（例如Python等）的lambda expression里。C#我不知道行不行，沒去考證。
這里首先要解決一個問題，就是如何引用沒被定義的名字的問題。譬如如下文法：
Term=
| "(" Exp ")"
Fa 閱讀全文
posted @
2008-05-21 00:57 陳梓瀚(vczh) 閱讀(8192) |
評論 (5) |
編輯 收藏
這個新的Syngram包含了三個工具，分別是正則表達式、詞法分析器和語法分析器。
正則表達式分純、安全和貪婪三種。純正則表達式僅僅用于匹配，速度非常快（以前的測試表明一秒鐘可以匹配44萬次），但是沒有預查和捕獲等功能。安全和貪婪兩種正則表達式則是通過不同的搜索方法來匹配字符串的內容，雖然慢了一點，不過有了預查和捕獲等功能。之前的文章有提到過關于一個少回溯多捕獲的測試用例下的速度。安全分析法回溯將會占用很多時間，而貪婪分析法則回溯基本是沒什么消耗的。
詞法分析器則可以輸入不同的正則表達式，然后將字符串切割成匹配和不匹配的段落，并告訴你匹配的部分實際上是匹配了哪一條正則表達式。這個功能在分析很多字符串的時候都是相當好用的。
至于語法分析器，則是實現了一個上下文無關文法庫。語法 閱讀全文
posted @
2008-05-19 00:56 陳梓瀚(vczh) 閱讀(1656) |
評論 (4) |
編輯 收藏posted @
2008-05-18 06:42 陳梓瀚(vczh) 閱讀(1697) |
評論 (3) |
編輯 收藏 在撰寫了《構造可配置詞法分析器》之后，我陸續收到了不少讀者的來信，不過大多數都是要求源代碼的。這篇文章原先是發布在自己的百度空間的，不過現在那個地方已經不打算寫技術相關的東西了。而且由于cppblog的一些用戶也轉載了那篇文章，因此不打算再在這里重復貼了。
由于大多數讀者都向我發郵件要求源代碼，因此我想到，上一篇文章雖然把所有的原理都說明白了，不過關于實現相關的數據結構的那些細節卻都沒說出來。對與那些真的想實現自己的正則表達式引擎的人來說，可能還不能從文章中得到所有問題的解決方法。不過鑒于本人一貫來不想把所有的細節問題都說得太過于繁瑣（留點問題給讀者想也是好的，不然文章就沒起到帶動學習的作用了），因此作出決定：接下來的幾天如果有空的話還要撰寫一篇新的文章。
新的文章將著眼于【如何實現正則表達式引擎】這個話題，續《構造可配置詞法分析器》的內容繼續討論。在這篇文章之中，我打算把使用DFA構造的正則表達式引擎的實現方法稍微描述一下（因為實際上難度不大），然后再花比較大的篇幅來講述實現正向預查、反向預查、匿名獲取、命名獲取和子表達式引用的方法。文章中還會描述這篇文章中所提及的優化正則表達式的方法（招太多口水了，看來不寫也會有很多人不高興的，這是文化問題）。
敬請等待。
posted @
2008-05-16 05:11 陳梓瀚(vczh) 閱讀(1921) |
評論 (6) |
編輯 收藏
1：大家在學習數據結構的時候，實踐的方法通過（多選）
A：做習題
B：學習STL和Boost等
C：嘗試自己開發一套模板庫
2：大家在學習編譯原理的時候，實踐的方法通過（多選）
A：做習題
B：學習flex、yacc/bison和ANTLR等
C：嘗試自己開發過編譯器（特別指字符串處理部分，指令部分不在本題目考慮范圍內）
D：嘗試自己開發與flex、yacc/bison或ANTLR等價的工具（不拘泥于形式）
3：如果上面的題目選擇了C或者D，那么（單選，自己獨立開發程序而不是在團隊中開發時）
A：自己需要的時候使用自己的庫
B：自己需要的時候使用別人的庫
4：如果第一題選擇了B，那么（單選，自己獨立開發程序而不是在團隊中開發時）
A：選擇編譯器或IDE推薦的庫（MFC或其他，跟STL或Boost有交集的庫）
B：選擇STL、Boost等
注意：
本人不傾向于向別人建議上面的任何觀點，僅作調查。
勿人身攻擊，歡迎評論。
寫出自己的答案的同時請寫出自己開發的時候經常使用的操作系統和編譯器等工具。
posted @
2008-05-14 19:14 陳梓瀚(vczh) 閱讀(1766) |
評論 (10) |
編輯 收藏
第一道題，把字符串中相連的重復字符處理成一個。例如aaabbcddcc處理成abcdc。因為寒假的時候才往Vczh Free Script 2.0中添加了一個Mark-Compact Collector，因此算法也就模仿了一下Mark-Compact Collector，也就是把所有該刪掉的字符換成'\0'，依次讀取并跟右邊最近的非'\0'字符置換一直到完。
第二道題，已知數列中有1、2、3三種數字，并且可以兩兩置換。求最小置換次數的方法讓數列遞增。
我用了這樣的方法：
·找到并保存每一個位置中應該存放的數字，也就是一1、2、3的數目都跟數列相同的遞增數列bi。
·遍歷ai，找到ai≠bi的i并做如下處理：
·尋找aj使得j>i且bi＝aj且bi≠bj
·在這些j中尋找k使得bk＝ai
·如果k非空則讓m∈k，否則讓m∈j并讓下一步的k的勢最大
·置換ai和am
一個好像很和諧但是事實上不知道和諧不和諧的證明：
j>i且bi＝aj且bi≠bj這個條件是必定滿足的。如果不滿足，則很容易證明ai和bi中1、2、3的數目不完全相同。
k非空使得一次置換產生了兩個正確的結果。
對于每一次置換，如果讓m1∈j且{m1}∩k為空，m2∈k，則有
選擇m1而不是m2有可能減少、保持或增大下一次置換中k的勢；
選擇m2則下一次置換中k的勢不變。
這樣的話，選擇m1最好的結果就是讓這次置換不影響全部的置換，最壞的結果是增加了置換的次數；
選擇m2則不會影響全部的置換。
因此只需每一次都盡量選擇m2中的值，對于k∩j為空的情況，則計算所有j得到的下一步的k的勢dj，選擇最大的j即可。
第三道題，華容道解謎器。只好弄了個寬度優先搜索。
以上純屬YY。
P.S.
·選擇題里面有一道問ABCDEFGHIJ的全排列中滿足A在B前面的數量有多少？答案：因為A和B是對稱的，因此對于任意一個確定的A和B的位置的集合，A在B前的概率是0.5，因此答案為10!/2。
·同時擁有操作系統、開發工具、數據庫引擎、辦公軟件、游戲平臺等多項業務的某著名軟件公司的招聘活動我也參加了一次，結果發現經營著世界最大的搜索業務的某公司和同時擁有操作系統、開發工具、數據庫引擎、辦公軟件、游戲平臺等多項業務的某著名軟件公司【好像】有一個特點。經營著世界最大的搜索業務的某公司喜歡出最優解題目，同時擁有操作系統、開發工具、數據庫引擎、辦公軟件、游戲平臺等多項業務的某著名軟件公司喜歡出最高速題目。而且經營著世界最大的搜索業務的某公司很喜歡去在位于廣州市海珠區珠江河畔的某著名大學，而同時擁有操作系統、開發工具、數據庫引擎、辦公軟件、游戲平臺等多項業務的某著名軟件公司則很喜歡去位于廣州市五山的某著名理工大學。
posted @
2008-05-12 10:59 陳梓瀚(vczh)|
編輯 收藏