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

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

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

先放截圖三張，等程序改好了之后再把代碼弄出來(lái)。這個(gè)東西很好玩的，嘿嘿。考慮了重力哦。  閱讀全文      摘要:     依然是上一篇文章的程序，換了C#寫(xiě)。    在Vczh Free Script 2.0的接口里面，我力求讓C++和.NET兩種語(yǔ)言的接口都趨于一致。目前達(dá)到了這個(gè)目標(biāo)，C#僅僅比C++多了兩個(gè)輔助函數(shù)。插件那一部分是相當(dāng)難寫(xiě)啊。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：
    二、書(shū)寫(xiě)測(cè)試用的腳本代碼：     這里構(gòu)造了一個(gè)VczhClass并調(diào)用了三個(gè)成員函數(shù)。結(jié)束之后，這種寫(xiě)法保證a再也不可被訪問(wèn)到，于是調(diào)用collect進(jìn)行垃圾收集（垃圾收集是自動(dòng)的，但是要觸發(fā)條件很難，所以給了個(gè)函數(shù)進(jìn)行強(qiáng)制收集）的時(shí)候就可以把a(bǔ)手機(jī)掉。

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

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

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

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

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

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

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

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

Vczh Free Script 2.0的Syngram庫(kù)完成

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

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

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

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

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

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

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

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

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

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

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

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

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

    敬請(qǐng)等待。

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

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

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

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

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

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

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

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

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

筆試

    今天經(jīng)營(yíng)著世界最大的搜索業(yè)務(wù)的某公司在位于廣州市海珠區(qū)珠江河畔的某著名大學(xué)開(kāi)了一次招聘會(huì)，申請(qǐng)實(shí)習(xí)軟件工程師的都要筆試。于是我也去寫(xiě)了，雖然我不是位于廣州市海珠區(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的勢(shì)最大
        ·置換ai和am

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

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

    以上純屬YY。

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

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

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

僅列出標(biāo)題

共35頁(yè): First 27 28 29 30 31 32 33 34 35