摘要: 無聊之際用C#寫了一個(gè)彈性物體碰撞模擬玩玩。這個(gè)想法源自與前幾天上機(jī)課有人想我在機(jī)房做一個(gè)透視投影的程序，于是就立刻寫了個(gè)投影并弄了個(gè)線框球上去跳。結(jié)果我就想，如果物體有彈性會怎么樣呢？回到宿舍就實(shí)踐想法。

這個(gè)程序是2D的，用C#主要是因?yàn)镚DI+寫起來比較方便，至少比可憐的MFC好用，雖然C#的東西又慢又占用CPU使用率。我發(fā)誓.NET的Timer肯定不是用WM_TIMER消息搞的，空轉(zhuǎn)占用CPU都那么高，而且用Sleep還降低不了。過高的CPU占用率持續(xù)過久會導(dǎo)致CPU溫度升高……

程序現(xiàn)在還有點(diǎn)問題。譬如物理引擎經(jīng)典問題：浮點(diǎn)誤差和碰撞穿透。現(xiàn)在還沒100%處理好，雖然絕大多數(shù)情況下是沒什么事。第二個(gè)就是因?yàn)閺椥猿隽宋业奈锢碇R范圍，所以碰撞的速度更高暫時(shí)亂寫，等過幾天有空解一個(gè)三元二次方程組之后再改改代碼。

先放截圖三張，等程序改好了之后再把代碼弄出來。這個(gè)東西很好玩的，嘿嘿。考慮了重力哦。  閱讀全文      摘要:     依然是上一篇文章的程序，換了C#寫。    在Vczh Free Script 2.0的接口里面，我力求讓C++和.NET兩種語言的接口都趨于一致。目前達(dá)到了這個(gè)目標(biāo)，C#僅僅比C++多了兩個(gè)輔助函數(shù)。插件那一部分是相當(dāng)難寫啊。Vczh Free Script 2.0的C++接口允許插件和腳本交替調(diào)用。腳本引擎是本地代碼，做到跟C...  閱讀全文     今天做好了Vczh Free Script 2.0的一個(gè)新插件，這個(gè)插件可以直接插入class并接管成員調(diào)用、構(gòu)造函數(shù)和析構(gòu)函數(shù)等調(diào)用。

    一、在C++中插入一個(gè)類VczhClass和函數(shù)write、writeln、read和collect：
    二、書寫測試用的腳本代碼：     這里構(gòu)造了一個(gè)VczhClass并調(diào)用了三個(gè)成員函數(shù)。結(jié)束之后，這種寫法保證a再也不可被訪問到，于是調(diào)用collect進(jìn)行垃圾收集（垃圾收集是自動的，但是要觸發(fā)條件很難，所以給了個(gè)函數(shù)進(jìn)行強(qiáng)制收集）的時(shí)候就可以把a(bǔ)手機(jī)掉。

    三、運(yùn)行結(jié)果：
    四、如果a的成員被保存起來了怎么辦呢？
    五、結(jié)果是因?yàn)閎還能繼續(xù)使用，所以a就不會銷毀（垃圾收集器解決了這個(gè)問題）：
    到了這里，一個(gè)直接往腳本中插入類的演示就結(jié)束了。接下來就是對這個(gè)插件進(jìn)行測試，并且在相應(yīng)的.NET接口上添加這樣的支持。     各位讀者們，《構(gòu)造正則表達(dá)式引擎》新鮮出爐啦！

    《構(gòu)造正則表達(dá)式引擎》
    這篇文章描述了純匹配正則表達(dá)式和具有高級功能（正向預(yù)查，反向預(yù)查，匿名捕獲，命名捕獲，命名檢查和貪婪循環(huán)等）的正則表達(dá)式各自用來匹配正則表達(dá)式的算法。如果大家在書寫好的正則表達(dá)式的時(shí)候出現(xiàn)了麻煩，或者在開發(fā)自己的正則表達(dá)式的時(shí)候遇到障礙，那不妨讀一讀這篇文章。不過對于沒讀過下面這篇文章的朋友，如果不是很熟悉編譯原理關(guān)于DFA和NFA的知識，那么建議首先閱讀下面這篇文章。

    《構(gòu)造可配置詞法分析器》
    這篇文章描述了如何從簡單的正則表達(dá)式構(gòu)造ε-NFA，并且一步一步轉(zhuǎn)換到DFA的算法，而且還提出了一種可配置詞法分析器的可能的實(shí)現(xiàn)方法。學(xué)習(xí)《編譯原理》的朋友們，如果在狀態(tài)機(jī)那里遇到什么問題的話，那么不妨讀一讀這篇文章。

    上面這兩篇文章是我在學(xué)習(xí)《編譯原理》之后開發(fā)正則表達(dá)式引擎的心得體會，在這里與大家分享，共同進(jìn)步。      摘要: 這篇短文的Idea來源于一篇論文。這篇論文的題目是Higier-Order Functions for Parsing，Graham Hutton寫的。論文中使用了一種叫Miranda的函數(shù)式語言來講述如何使用高階函數(shù)開發(fā)語法分析器。

高階函數(shù)很多語言都支持，譬如JavaScript啊，C#的lambda expression啊，或者是我自己做的語言Vczh Free Script 2.0。不過Miranda是惰性計(jì)算的語言，我們常用的語言都不具有惰性計(jì)算的特性。因此我閱讀了這篇文章之后，自己用Vczh Free Script 2.0寫了一個(gè)等價(jià)的小規(guī)模的語法分析器。結(jié)構(gòu)跟論文中所提到的那個(gè)有所區(qū)別，不過相同的經(jīng)驗(yàn)可以直接應(yīng)用在JavaScript里面或其它語言（例如Python等）的lambda expression里。C#我不知道行不行，沒去考證。

這里首先要解決一個(gè)問題，就是如何引用沒被定義的名字的問題。譬如如下文法：

Term= | "(" Exp ")"
Fa  閱讀全文

posted @ 2008-05-21 00:57 陳梓瀚(vczh) 閱讀(8195) | 評論 (5) | 編輯 收藏

Vczh Free Script 2.0的Syngram庫完成

     摘要: 今天在測試封裝在FreeScript內(nèi)的正則表達(dá)式接口的時(shí)候發(fā)現(xiàn)了一個(gè)垃圾收集器的Bug，不過很容易就看出來了，于是立刻fix掉。出錯(cuò)的原因在于垃圾收集的時(shí)候只標(biāo)記了運(yùn)算堆棧的內(nèi)容，忘了標(biāo)記調(diào)用堆棧的內(nèi)容。

這個(gè)新的Syngram包含了三個(gè)工具，分別是正則表達(dá)式、詞法分析器和語法分析器。

正則表達(dá)式分純、安全和貪婪三種。純正則表達(dá)式僅僅用于匹配，速度非常快（以前的測試表明一秒鐘可以匹配44萬次），但是沒有預(yù)查和捕獲等功能。安全和貪婪兩種正則表達(dá)式則是通過不同的搜索方法來匹配字符串的內(nèi)容，雖然慢了一點(diǎn)，不過有了預(yù)查和捕獲等功能。之前的文章有提到過關(guān)于一個(gè)少回溯多捕獲的測試用例下的速度。安全分析法回溯將會占用很多時(shí)間，而貪婪分析法則回溯基本是沒什么消耗的。

詞法分析器則可以輸入不同的正則表達(dá)式，然后將字符串切割成匹配和不匹配的段落，并告訴你匹配的部分實(shí)際上是匹配了哪一條正則表達(dá)式。這個(gè)功能在分析很多字符串的時(shí)候都是相當(dāng)好用的。

至于語法分析器，則是實(shí)現(xiàn)了一個(gè)上下文無關(guān)文法庫。語法  閱讀全文

posted @ 2008-05-19 00:56 陳梓瀚(vczh) 閱讀(1659) | 評論 (4) | 編輯 收藏

今天使用新的feature為Vczh Free Script 2.0寫了一個(gè)collection庫

     摘要:     自從可以重載除了賦值以外的所有操作符以后，我突然發(fā)現(xiàn)原來【將自己寫的容器跟foreach語句結(jié)合】這個(gè)目標(biāo)自動實(shí)現(xiàn)了。這次寫了一些東西，先貼個(gè)使用的代碼。    Collection庫里面的所有容器都實(shí)現(xiàn)了操作符重載，Set容器更是重載了+、-、*、>、<、>=、<=、==和!=。所有容器都重載了#（用于獲...  閱讀全文

posted @ 2008-05-18 06:42 陳梓瀚(vczh) 閱讀(1700) | 評論 (3) | 編輯 收藏

關(guān)于《構(gòu)造可配置詞法分析器》的后續(xù)

    在撰寫了《構(gòu)造可配置詞法分析器》之后，我陸續(xù)收到了不少讀者的來信，不過大多數(shù)都是要求源代碼的。這篇文章原先是發(fā)布在自己的百度空間的，不過現(xiàn)在那個(gè)地方已經(jīng)不打算寫技術(shù)相關(guān)的東西了。而且由于cppblog的一些用戶也轉(zhuǎn)載了那篇文章，因此不打算再在這里重復(fù)貼了。

    由于大多數(shù)讀者都向我發(fā)郵件要求源代碼，因此我想到，上一篇文章雖然把所有的原理都說明白了，不過關(guān)于實(shí)現(xiàn)相關(guān)的數(shù)據(jù)結(jié)構(gòu)的那些細(xì)節(jié)卻都沒說出來。對與那些真的想實(shí)現(xiàn)自己的正則表達(dá)式引擎的人來說，可能還不能從文章中得到所有問題的解決方法。不過鑒于本人一貫來不想把所有的細(xì)節(jié)問題都說得太過于繁瑣（留點(diǎn)問題給讀者想也是好的，不然文章就沒起到帶動學(xué)習(xí)的作用了），因此作出決定：接下來的幾天如果有空的話還要撰寫一篇新的文章。

    新的文章將著眼于【如何實(shí)現(xiàn)正則表達(dá)式引擎】這個(gè)話題，續(xù)《構(gòu)造可配置詞法分析器》的內(nèi)容繼續(xù)討論。在這篇文章之中，我打算把使用DFA構(gòu)造的正則表達(dá)式引擎的實(shí)現(xiàn)方法稍微描述一下（因?yàn)閷?shí)際上難度不大），然后再花比較大的篇幅來講述實(shí)現(xiàn)正向預(yù)查、反向預(yù)查、匿名獲取、命名獲取和子表達(dá)式引用的方法。文章中還會描述這篇文章中所提及的優(yōu)化正則表達(dá)式的方法（招太多口水了，看來不寫也會有很多人不高興的，這是文化問題）。

    敬請等待。

posted @ 2008-05-16 05:11 陳梓瀚(vczh) 閱讀(1925) | 評論 (6) | 編輯 收藏

做個(gè)投票，大家支持

    因?yàn)樽罱^察到一些很奇怪的現(xiàn)象，因此在此提出調(diào)查。不知道是我不會用cppblog還是cppblog沒這個(gè)功能，總之我沒找到【投票】的工具，因此只好手寫。

    1：大家在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的時(shí)候，實(shí)踐的方法通過（多選）
        A：做習(xí)題
        B：學(xué)習(xí)STL和Boost等
        C：嘗試自己開發(fā)一套模板庫

    2：大家在學(xué)習(xí)編譯原理的時(shí)候，實(shí)踐的方法通過（多選）
        A：做習(xí)題
        B：學(xué)習(xí)flex、yacc/bison和ANTLR等
        C：嘗試自己開發(fā)過編譯器（特別指字符串處理部分，指令部分不在本題目考慮范圍內(nèi)）
        D：嘗試自己開發(fā)與flex、yacc/bison或ANTLR等價(jià)的工具（不拘泥于形式）

    3：如果上面的題目選擇了C或者D，那么（單選，自己獨(dú)立開發(fā)程序而不是在團(tuán)隊(duì)中開發(fā)時(shí)）
        A：自己需要的時(shí)候使用自己的庫
        B：自己需要的時(shí)候使用別人的庫

    4：如果第一題選擇了B，那么（單選，自己獨(dú)立開發(fā)程序而不是在團(tuán)隊(duì)中開發(fā)時(shí)）
        A：選擇編譯器或IDE推薦的庫（MFC或其他，跟STL或Boost有交集的庫）
        B：選擇STL、Boost等

    注意：
        本人不傾向于向別人建議上面的任何觀點(diǎn)，僅作調(diào)查。
        勿人身攻擊，歡迎評論。 
        寫出自己的答案的同時(shí)請寫出自己開發(fā)的時(shí)候經(jīng)常使用的操作系統(tǒng)和編譯器等工具。

posted @ 2008-05-14 19:14 陳梓瀚(vczh) 閱讀(1769) | 評論 (10) | 編輯 收藏

筆試

    今天經(jīng)營著世界最大的搜索業(yè)務(wù)的某公司在位于廣州市海珠區(qū)珠江河畔的某著名大學(xué)開了一次招聘會，申請實(shí)習(xí)軟件工程師的都要筆試。于是我也去寫了，雖然我不是位于廣州市海珠區(qū)珠江河畔的某著名大學(xué)的學(xué)生，反正人人都能去。

    第一道題，把字符串中相連的重復(fù)字符處理成一個(gè)。例如aaabbcddcc處理成abcdc。因?yàn)楹俚臅r(shí)候才往Vczh Free Script 2.0中添加了一個(gè)Mark-Compact Collector，因此算法也就模仿了一下Mark-Compact Collector，也就是把所有該刪掉的字符換成'\0'，依次讀取并跟右邊最近的非'\0'字符置換一直到完。

    第二道題，已知數(shù)列中有1、2、3三種數(shù)字，并且可以兩兩置換。求最小置換次數(shù)的方法讓數(shù)列遞增。

    我用了這樣的方法：
    ·找到并保存每一個(gè)位置中應(yīng)該存放的數(shù)字，也就是一1、2、3的數(shù)目都跟數(shù)列相同的遞增數(shù)列bi。
    ·遍歷ai，找到ai≠bi的i并做如下處理：
        ·尋找aj使得j>i且bi＝aj且bi≠bj
        ·在這些j中尋找k使得bk＝ai
        ·如果k非空則讓m∈k，否則讓m∈j并讓下一步的k的勢最大
        ·置換ai和am

    一個(gè)好像很和諧但是事實(shí)上不知道和諧不和諧的證明：
        j>i且bi＝aj且bi≠bj這個(gè)條件是必定滿足的。如果不滿足，則很容易證明ai和bi中1、2、3的數(shù)目不完全相同。
        k非空使得一次置換產(chǎn)生了兩個(gè)正確的結(jié)果。
        對于每一次置換，如果讓m1∈j且{m1}∩k為空，m2∈k，則有
            選擇m1而不是m2有可能減少、保持或增大下一次置換中k的勢；
            選擇m2則下一次置換中k的勢不變。
        這樣的話，選擇m1最好的結(jié)果就是讓這次置換不影響全部的置換，最壞的結(jié)果是增加了置換的次數(shù)；
        選擇m2則不會影響全部的置換。
        因此只需每一次都盡量選擇m2中的值，對于k∩j為空的情況，則計(jì)算所有j得到的下一步的k的勢dj，選擇最大的j即可。

    第三道題，華容道解謎器。只好弄了個(gè)寬度優(yōu)先搜索。

    以上純屬YY。

    P.S.
    ·選擇題里面有一道問ABCDEFGHIJ的全排列中滿足A在B前面的數(shù)量有多少？答案：因?yàn)锳和B是對稱的，因此對于任意一個(gè)確定的A和B的位置的集合，A在B前的概率是0.5，因此答案為10!/2。

    ·同時(shí)擁有操作系統(tǒng)、開發(fā)工具、數(shù)據(jù)庫引擎、辦公軟件、游戲平臺等多項(xiàng)業(yè)務(wù)的某著名軟件公司的招聘活動我也參加了一次，結(jié)果發(fā)現(xiàn)經(jīng)營著世界最大的搜索業(yè)務(wù)的某公司和同時(shí)擁有操作系統(tǒng)、開發(fā)工具、數(shù)據(jù)庫引擎、辦公軟件、游戲平臺等多項(xiàng)業(yè)務(wù)的某著名軟件公司【好像】有一個(gè)特點(diǎn)。經(jīng)營著世界最大的搜索業(yè)務(wù)的某公司喜歡出最優(yōu)解題目，同時(shí)擁有操作系統(tǒng)、開發(fā)工具、數(shù)據(jù)庫引擎、辦公軟件、游戲平臺等多項(xiàng)業(yè)務(wù)的某著名軟件公司喜歡出最高速題目。而且經(jīng)營著世界最大的搜索業(yè)務(wù)的某公司很喜歡去在位于廣州市海珠區(qū)珠江河畔的某著名大學(xué)，而同時(shí)擁有操作系統(tǒng)、開發(fā)工具、數(shù)據(jù)庫引擎、辦公軟件、游戲平臺等多項(xiàng)業(yè)務(wù)的某著名軟件公司則很喜歡去位于廣州市五山的某著名理工大學(xué)。

posted @ 2008-05-12 10:59 陳梓瀚(vczh)| 編輯 收藏

僅列出標(biāo)題

共35頁: First 27 28 29 30 31 32 33 34 35