大貓共和國

Meow

台大教授的程式作業批改系統

不知道有沒有人對YouTube上的一首曖昧改編版有印像 (曾經被PO在ptt上面)

笑點可能要修過程式設計課的人才會懂..

我有在ptt2潛水看台大兩位資工系教授的個人版。其中一位教授稱他的程式作業叫『使徒』(於是學生們就得擊敗眾多的使徒 XDXD)

那位教授也開發了一個web-based的程式批改系統(像是ACM judge)，叫做『批改娘』。 『批改娘』的系統好像常常被助教惡搞，於是今天在版上就看到了這樣的畫面

使�

真是有趣的教授和助教啊….XD 有興趣的話前往ptt2應該不難找到那個版

Monte Carlo Integration (蒙地卡羅積分)

蒙地卡羅積分是一個能夠求積分近似值的方法。這個方法應該有很多應用吧，我印像最深刻的是影像合成中的ray tracing演算法(可用於計算一個點受到的照度)。因為學弟的論文可能會用到這個方法，我曾經學過但是有點忘了，而且竟然找不太到中文的資源，所以復習一下順便做一下筆記。

假設有一個對x的定積分式


如下圖，如果f為折線的函式，則黃色區塊的面積即為自0到1積分的結果。

monte1

當然，我們很容易可以利用三角形面積公式，或者對f求定積分，而算出黃色區域的面積。然而，假設我們沒有這樣的先備知識，或者黃色區域的面積是難以求得的，那要怎麼辦呢？

跟據Monte Carlo method的想法，我們可以在包函定積分區域的一個範圍內，均勻取n個點。假設n=100, 且我們取的範圍是


monte2

令[tex]n*[/tex]為落在黃色區域內的點數，V為隨機取點的區域面積，而I為黃色區域面積，我們可以求得I的近似值。<br />[tex]I \approx \frac{n*}{n}V[/tex]<br />
這個應該很容易可以理解，我們在面積為1的區域中，隨機取了1000個點，若有502個點落在黃色區域中，我們可以估計黃色區域的面積近似於0.502。理論上n的數字越大，這個近似值會越準。但是上述的方法太慢了，利用高中數學就可以想到一個更快的方法 :)

令
[tex]g(x) = \left{\begin{array}{ll}
1 & \textrm{,if x is in the domain of f(x)} \
0 & \textrm{,else}
\end{array}
\right .[/tex]
則

[tex]I = \int_abg(x)f(x)dx = \frac{1}{v}\int_abg(x)f(x)Vdx[/tex]<br />
令
[tex]h(x) = f(x)g(x)[/tex]

跟隨上面的推導，可以得到
[tex]I \approx \frac{1}{n} \sum{i}{n}h(x_i) = \frac{V}{n} \sum{i}{n}f(x_i)[/tex]<br />
用一個很簡單的例子舉例，下圖 ((本圖取自英文維基百科此處))大家應該都覺得很眼熟，因為國高中的數學課本就出現過了。要估計一個函數所積分成的面積，我們可以在函數上取一些sample點，然後用sample點的高度和，乘上每個sample的平均寬度，就是這個區域面積的沽計值。事實上Monte Carlo integration就是基於這個想法。

monte3

不僅止於此，這個方法還可以應用到較高維度的空間中。假設f的定議域由x,y…等多個變數所組成。則f的積分值可定義為：

[tex]I = \int{x_l}{x_u} \int{y_l}{y_u} f(x, y, \ldots) \, dx \, dy \ldots =\int{V}f(x, y, \ldots) \, dx \, dy \ldots[/tex]

同樣的
[tex]I \approx V \cdot \langle f \rangle = \frac{V}{n} \sum{i}n f(x_i)[/tex]
只是此處V可能為取樣的體積(或超體積hypervolume)。這樣的方法比前一個方法可以少取樣一個維度，很明顯的可以加快演算法的運算速度。

Monte Carlo integration的方法是無法保證其誤差的error bound的，這一點可以很容易的觀查到。我們僅對空間做一些隨機取樣的動作，甚至不需要知道函數的細節，只要給與input能求的output就好了。因此，如果函數中有一個特別突出的區間，只要取樣點沒有落在那個區間上，就會造成很大的誤差。一般來說，要將誤差縮小n倍，則需要將sample點的數量乘上n平方倍。

在實作上，Monte Carlo integration還可以有不同的變化。例如在偵測到variance較大的區間，可以增加sample的密度以提高準確率等…

參考資料：

下載檔案如何不造成lag?

前言：這篇想要寫的盡量簡單易懂，所以用了一些技術上不太正確的譬喻，高手看到請鞭小力一點。

劇情：小明在外租屋，房東家裡裝了一條ADSL網路，免費分給各位房客用。小明的朋友阿喵架了一個FTP站，在上面放了一些電影。有一天，小明在阿喵的FTP上抓電影時，房東的兒子打網路遊戲突然變的很不順，下達一個攻擊指令後過三秒才會有反應。房東的兒子和房東說了這樣的情況，於是房東就把房客們的網路線拔掉了…如果有在網路上下載檔案(FTP, BT, eMule)的人，應該常常會有這種經驗…打BBS或網路遊戲突然變的很lag(指網路回應時間很慢)。要怎麼避免這種狀況呢？
武器一：使用ping來判斷目前網路lag的狀況要怎樣判斷目前的網路連外有多lag呢？最簡單的方法就是使用ping。ping的原理很簡單，就是去計算一個封包(訊息)傳到另一台電腦，再傳回來的時間。這裡通常ping你所使用的ISP的gateway或網頁，就可以知道目前網路的lag狀態了。

前面那段看不懂沒關係，我舉個更簡單的例子…
小明的電腦：Hinet網頁主機，聽到請快回答！
Hinet網頁主機：收到收到
小明的電腦：嗯嗯，我收對方的回應了，一共經過了30ms (毫秒)

這就是ping所做的事。30ms包括了兩段的時間：小明的電腦傳訊息給hinet的時間，以及Hinet回訊息到小明的電腦收到的時間。一般來說，Hinet的ADSL用戶在網路順暢的情況下會看到8~30ms的。

在Windows下使用ping很簡單。按開始=>執行=>ping -t http://www.hinet.net/ 就會開始不停的ping…

ping

中間那個time=23ms，就是RTT，一般都會在30以下。如果房東的兒子是在玩一般的網路RPG，ping在200ms以下應該沒什麼感覺，200~400ms應該是感覺稍微不順。所以只要設法讓ping不要爆掉，房東就不會來拔你的網路線了喔。

武器二：Windows下的流量限制軟體 (如NetLimiter)

一般的P2P程式(如BT, eMule)都會提供流量限制的功能。然而提供流量限制功能的FTP軟體似乎就很少見。這個時候就要靠其他的軟體來控制流量囉。像是NetLimiter就是一套不錯的軟體。我手邊沒有灌NetLimiter的機器，所以沒辦法寫出詳細的文圖教學。有興趣的可以去看看別人寫的教學，學會怎樣控制上傳和下傳的頻寬。

注意！一般ADSL的上傳及下載頻寬是不一樣的。如果你的下載瀕寬是1MBPS，這不是說你每秒可以抓1MB的東西喔….因為所謂BPS是Bit per second，也就是每秒可以傳輸多少Bit。然而我們通常用Byte的單位來計算檔案大小，而1byte等於8bits。總而言之，把你租用的ADSL線路的頻寬數字除以八就對了。下載1MBPS的ADSL，要是你每秒抓超過0.125MB，也就是128KB的資料的話，就會非常容易lag。結論：把你的頻寬除以八，你設定的上傳/下載頻寬決不可以超過這個數字。

不過這招用在多人分用網路的時候就沒用了，除非大家約定好用的頻寬不超過多少，否則就只好試著調整上/下傳頻寬(在p2p軟體內調、或者用NetLimiter調)，直到ping值在可以接受的範圍內為止。

WordPress忘記密碼的解決方法

此處指自己架的wordpress，並非wordpress.com提供的service。

第一種方法：在login畫面點選forget password，會寄送一封信到你的信箱，附帶一個可以更改密碼的link，但要是這方法失效的話…

進phpmyadmin，修改wp_users table，將使用者的密碼欄位清空 (原本會看到一串16進位的數字)，打上新的密碼，並點選MD5。phpmyadmin會幫你把密碼用MD5 hash後存入資料庫，收工。

事實上sql指令夠熟的話，直接去console下sql…

UPDATE xxx_blog.wp_users SET user_pass = MD5('password') WHERE wp_users.ID=1;

參考http://codex.wordpress.org/Resetting_Your_Password

遊戲中常見的幾種音樂格式

這篇是貼我自己以前寫的文章。


介紹這些格式的文章應該不少，但我想大多過於專業
我試著用自己的話，盡量簡單地描述四種遊戲最常見的音樂格式

  1. MIDI：通常副檔名為mid，MIDI是Music Instrument Digital Interface的簡寫
    特色是檔案很小，非常小

    簡單的這麼解釋好了：

    mid檔就像是樂譜，記錄著「第5.02秒鋼琴要彈下sol、第6.31秒吉他要彈下ra」這樣的資訊
    然而mid檔裡本身並沒有吉他、鋼琴的音色。這也就是為何mid檔案小的原因

    那當我們的電腦撥放mid檔時，怎麼知道吉他、鋼琴的音色呢？
    這是因為mid檔通常遵守一種叫「General MIDI」的格式
    「樂器1」表示鋼琴、「樂器25」表示尼龍弦的古典吉他
    然而我們的音效卡上有一個「MIDI音源器」，負責按照這些樂器編號，把聲音撥放出來
    (當然有軟體音源這個例外，但不在此討論)

    單純使用mid檔的話有一些限制

    1. 音色是看使用者電腦上的音源，不同的電腦撥放出來的效果可能會不同
      (大部份的人應該都是爛爛的AC97音效卡)
    2. 音色有限，只有General MIDI提供的音色 (我記得是128種，不知道有沒有記錯)
    3. 效果有限，沒辦法自由的調整迴音、各種效果(equalizer, echo, reverb, flanger等….多不勝數)


  2. Wave：通常副檔名為wav
    特色是檔案很大，非常大

    大家可以把他想像成忠實的把聲音記錄下來的檔案格式

    音質最好，所以花費的空間多
    (大家可以把他想像成圖檔中的bmp檔)

    許多商業遊戲都是用CD音軌的方式來儲存音樂
    CD音軌其實也是屬於Wave的無失真儲存方式
    (CD音軌的資訊其實就等於Sample rate=44,100Hz 雙聲道的Wave檔)


    很常見的編曲方式就是：使用MIDI編曲軟體+自己的軟/硬體音源 => 混音成wave檔

    然後再看要不要做壓縮之類的
    和單純使用General MIDI比起來，這樣可以使用很多種的效果，處理上也有很大的彈性


    Wave和以下的mp3, ogg…等真正儲存聲音的，通稱為數位音訊檔
    接下來只是把Wave壓縮過的格式，我就不詳細介紹了
    主要的目的只是跟大家講數位音訊和mid檔之間的差別

  3. mp3：
    相信大家都很熟悉吧 XD


    mp3是將wave失真壓縮(註)後的一種格式

  4. ogg：
    可以參考維基百科: Ogg Vorbis

    一樣是失真壓縮
    據說同樣壓縮比下的音質比mp3還好，我自己倒是沒試過
    在一般使用者間這個格式還是沒有比mp3被廣為使用


註：失真壓縮
失真壓縮就是指在壓縮的過程中，損失一些原有的資訊

舉大家比較熟悉的圖片來說，bmp就好像wav的角色
png,gif就是一種非失真壓縮(畫質不會變差)，jpg就是失真壓縮