![[A Life pattern called the puffer train]](http://www.radicaleye.com/lifepage/puftrn.gif)
原文:http://www.ibiblio.org/lifepatterns/lifeapplet.html
?當(dāng)前版本0.41d，更新時(shí)間2001-1-31，比0.41c版(199-1-22)上提高了些性能。新版本在計(jì)劃中，只要我的空余時(shí)間允許。
?作者:Alan Hensel,
簡(jiǎn)介：
認(rèn)識(shí)我的人都知道我為什么寫(xiě)這個(gè)程序。不是為了學(xué)習(xí)Java，不是為了提高我的網(wǎng)站的訪(fǎng)問(wèn)量，原因很簡(jiǎn)單：
我收集Life patterns，而且我喜歡展示它們
當(dāng)然，這些patterns中的大部分是別人發(fā)現(xiàn)的。沒(méi)人想要從這些Life patterns中獲利，所以據(jù)我所知這些patterns將留給后代并被賞識(shí)，就象國(guó)際象棋一樣。
請(qǐng)不要給我寫(xiě)信說(shuō)：我喜歡你的程序，卻忘記提起這些patterns。這聽(tīng)起來(lái)會(huì)象是恭維集郵愛(ài)好者他的郵冊(cè)如何漂亮，對(duì)郵票卻只字不提。我的程序只是做了它們?cè)撟龅氖虑槎选?/p>
計(jì)算機(jī)軟件和硬件只是使用者和他的數(shù)據(jù)之間的工具。
這些patterns讓人贊嘆。如果不信，你可以自己去做一個(gè)試試。(我希望這個(gè)挑戰(zhàn)能促成一些發(fā)現(xiàn)。)
給那些寫(xiě)Life程序的學(xué)生：
我沒(méi)有可以給你的源代碼。這里沒(méi)有你找的東西。我提供了這個(gè)程序的源代碼，但它們超出了計(jì)算機(jī)課程的范圍。它們之所以這么復(fù)雜是因?yàn)樗俣葍?yōu)化(這樣我才能運(yùn)行"Breeder"或者其它更大的patterns)。當(dāng)然，你可以試著讀讀源代碼，但不要強(qiáng)迫自己。你寫(xiě)的作業(yè)應(yīng)該比這個(gè)程序簡(jiǎn)單一百倍。
給來(lái)這里學(xué)習(xí)Java applets的讀者:
這是我第一個(gè)真正意義上的applet。最好別打算把我的代碼拷貝到你的程序中。源代碼就在這一頁(yè)的底部，你可以免費(fèi)下載，當(dāng)然，你必須為它付出些東西。若非如此，這將會(huì)是一個(gè)讓人相當(dāng)有學(xué)習(xí)動(dòng)力的applet程序。
你怎么做到這么快的？
好的。沒(méi)有留心的話(huà)也許你不會(huì)發(fā)現(xiàn)我的程序閃電一樣的快。你也許沒(méi)看到"Warp Speed"按鈕，或者你還沒(méi)用過(guò)它，或者你覺(jué)得這無(wú)所謂。這樣的話(huà)你可以跳過(guò)這個(gè)部分。
有人問(wèn)，你究竟是怎么讓它跑得這么快的？！對(duì)于這些好奇者，或者那些打算寫(xiě)自己的超級(jí)細(xì)胞自動(dòng)機(jī)程序的人，我會(huì)解釋的。
我傾向于把細(xì)胞自動(dòng)機(jī)的優(yōu)化和數(shù)據(jù)壓縮聯(lián)系起來(lái)。這也是一個(gè)簡(jiǎn)單的概念卻需要復(fù)雜的方法。究竟什么才是最好的方案取決于數(shù)據(jù)本身。對(duì)于康威的Life，傾向于出現(xiàn)點(diǎn)狀的圖案。
對(duì)于點(diǎn)狀分布的世界，我們應(yīng)該考慮把它分割成近似大小的塊。對(duì)于Life來(lái)說(shuō)，4x4和8x8都是可取的。我選擇了8x8，因?yàn)?剛好8比特1字節(jié)，我曾經(jīng)考慮過(guò)4x4，但運(yùn)行起來(lái)效果不大好。
并且請(qǐng)注意：如果pattern長(zhǎng)大并超過(guò)了塊的范圍，需要引入新的塊。你可以簡(jiǎn)單的線(xiàn)性搜索，也可折半查找，或者維護(hù)某種映射。我的方法是哈希表。這個(gè)表只是用來(lái)查找一個(gè)新塊的鄰居。每個(gè)已存在的塊已經(jīng)有它的鄰居的指針，并且會(huì)被多次使用。
必須有高效的算法來(lái)處理這些塊內(nèi)部的數(shù)據(jù)，我選擇一次處理塊中的所有數(shù)據(jù)。在處理完整個(gè)塊之前不需要跳轉(zhuǎn)語(yǔ)句。換句話(huà)來(lái)說(shuō)：所有內(nèi)部循環(huán)都被unroll了，并使用了高速的查詢(xún)表。
注意：CA(細(xì)胞自動(dòng)機(jī))程序一般性的包含了兩個(gè)主要循環(huán)(加上一個(gè)顯示循環(huán))，因?yàn)镃A規(guī)則要求對(duì)細(xì)胞進(jìn)行并行處理，但微處理器是線(xiàn)性的。這意味著必須有世界的兩分拷貝，這樣創(chuàng)建下一代的時(shí)候本身的信息才不會(huì)被破壞掉。通常這兩個(gè)拷貝是不對(duì)稱(chēng)的。這對(duì)我來(lái)說(shuō)相當(dāng)麻煩，因?yàn)槊看挝覐倪@邊取出些東西進(jìn)行優(yōu)化，不得不在另一邊加點(diǎn)別的什么！幾乎每次，例外的情況導(dǎo)致了最好的優(yōu)化。特別的,需要在位操作：位移，屏蔽和重組之間折中來(lái)找一個(gè)最好的查找表。
有時(shí)塊中的細(xì)胞會(huì)出現(xiàn)穩(wěn)定的情況，不需要進(jìn)一步處理。你可以把塊從隊(duì)列中移出，把它設(shè)置成“冬眠”狀態(tài)，只有當(dāng)鄰近的塊影響到它。這些塊不需要占用處理器的時(shí)間，象空白的區(qū)域一樣。
檢測(cè)周期為2的振蕩器并把它移出處理隊(duì)列并不難。這對(duì)于Life程序是值得的，因?yàn)閎linker是最常見(jiàn)的隨機(jī)的殘余物。更復(fù)雜的振蕩器相對(duì)比較少見(jiàn)。檢測(cè)并模擬滑翔機(jī)也是可能的。這些方面的優(yōu)化會(huì)得到遞減的效果，除非你做到極致。(如HasLife)。
同樣，死亡狀態(tài)：空的塊不必馬上釋放并從哈希表中移走。那樣會(huì)占用更多的處理器時(shí)間，尤其是當(dāng)振蕩器在一定空間內(nèi)移進(jìn)移出的時(shí)候。僅當(dāng)可用內(nèi)存已經(jīng)很少的時(shí)候，才從死亡隊(duì)列中移除最老的死亡的塊。
當(dāng)程序快到一定程度，必須考慮刷新顯示的速度不需要超過(guò)人眼可以感知的速度，或者最少不需要超過(guò)顯示器的刷新頻率。特別是在視窗環(huán)境，顯示時(shí)間會(huì)是效率的瓶頸。
源代碼
以下是我的超級(jí)快速的Game of Life applet源代碼。
很抱歉這些不是百分百面向?qū)ο蟮摹ame of Life并不適合面向?qū)ο蠹夹g(shù)。面向?qū)ο筮m用于你碰到的大多數(shù)問(wèn)題，除了那些效率第一而且相當(dāng)復(fù)雜的項(xiàng)目，康威的Game of Life正好屬于這種情況。
以下是16個(gè)源文件:
LifeButton.java
LifeFrame.java
Life.java
LifeGUI.java
LifeGen.java
LifeCell.java
LifeHash.java
LifeCoordinate.java
LifeRules.java
LoadBox.java
RuleBox.java
SpeedBox.java
OptionsBox.java
LifeQueue.java
LifeCallback.java
DescribeBox.java