Google Code Jam 2010 Qualification C

Problem C: Theme Park

Question: http://code.google.com/codejam/contest/dashboard?c=433101#s=p2&a=2
Answer: http://code.google.com/codejam/contest/dashboard?c=433101#s=a&a=2

這題是最後一題, 應該也算是最簡單的一題

不過有點Tricky, 想答對Large的難度, 要做點最佳化才有辦法

題目是說, 一般遊客去做雲霄飛車的時候, 都習慣一群一群人一起坐上去, 如果有人做不上去的話, 就會等下一班車. 然後, 每個人坐一次會付1元, 我們要算出雲霄飛車一天可以賺多少錢.

例如:

雲霄飛車有 6 個位置, 每天會開 4 次, 遊客有 4 群人, 每群遊客依序有 1, 4, 2, 1 人, 而這些遊客會整天一直排隊坐雲霄飛車.

所以, 第一次雲霄飛車會載 [1, 4] 人 (因為不能插隊, 所以不會把後面一個人的往前補)

第二次會載 [2, 1, 1] 人

第三次會載 [4, 2] 人

最後一次會載 [1, 1, 4] 人

因此, 最後一共賺了 21 元

在解法的方面, 應該都大同小異

我是用一個 Array 存了遊客人數 [1, 4, 2, 1]

另外還有一個相對應的快取 Array 存了計算過的結果 [5, 6, 4, 6]

快取Array, 初始為[?, ?, ?, ?] 
第一次載完 [1, 4] 人, 所以是 [5, ?, ?, ?]
第二次由第三群遊客開始, 載完 [2, 1, 1] 人, 所以是 [5, ?, 4, ?]
第三次載完 [4, 2] 人, 所以是 [5, 6, 4, ?]
第四次載完 [1, 1, 4] 人, 所以是 [5, 6, 4, 6]
第五次之後, 就不需要再計算, 而是直接使用快取的結果
速度上來說, 已經足以解決這個問題

官方提供了三種最佳化, 有興趣的人可以在上去看看

Google Code Jam 2010 Qualification B

Problem B: Fair Warning

Question: http://code.google.com/codejam/contest/dashboard?c=433101#s=p1&a=1
Answer: http://code.google.com/codejam/contest/dashboard?c=433101#s=a&a=1


這一題的題目很有趣, 但是解起來就不是那麼有趣了, 因為牽扯到大數的問題.
還好我是用JAVA解題, 內建就有大數的函式庫可以使用

題目是說, 在Jamcode星球上, 有一種預言, 西元前發生的幾件大事件, 會暗示哪一天是世界末日

例如:
西元前26000, 11000, 6000年發生了大事件, 則西元4000年會導致世界末日.
因為西元4000年, 離這三個事件分別是30000, 15000, 10000年, 都是5000的倍數, 並且, 5000是一個最大的因數

以這個例子來看
(26000+4000) % 5000 = (11000+4000) % 5000 
(11000+4000) % 5000 = (6000+4000) % 5000 
(26000-11000) % 5000 = 0
(11000-6000) % 5000 = 0

所以
(a + y) % T = (b + y) % T
(a - b) % T = 0

因此, 所有年份的相差值中, 去取出最大公因數, 就是解答

Google Code Jam 2010 Qualification A

Problem A: Snapper Chain

Question: http://code.google.com/codejam/contest/dashboard?c=433101#s=p0&a=0
Answer: http://code.google.com/codejam/contest/dashboard?c=433101#s=a&a=0

這題蠻有趣的
題目是說, 有一種聲控的延長線
只要你一拍手, 有插電的延長線就會開啟或者關閉

我們以0代表關閉, 1代表開啟
如果有兩條延長線, 由左至右連接
則一開始的情況依序為
[0 0]
再做了一次拍手之後, 則變成
[1 0]
接著為
[0 1]
[1 1]
則使得延長線為通電的狀況

如果有四條延長線, 則為以下的情況
[0 0 0 0]
[1 0 0 0]
[0 1 0 0]
[1 1 0 0]
[0 0 1 0]
[1 0 1 0]
[0 1 1 0]
[1 1 1 0]
[0 0 0 1]
[1 0 0 1]
[0 1 0 1]
[1 1 0 1]
[0 0 1 1]
[1 0 1 1]
[0 1 1 1]
[1 1 1 1]

所以聰明的你
是不是發現, 每16次會通電一次

因此可以歸納出
每2的N次方, 會通電一次

這個歸納, 應該比官方的快一點

簡單吧!!

YCSB告訴你雲端有多快

Ref: http://research.yahoo.com/files/ycsb.pdf

現在提供雲端運算的服務越來越多了, 有:
    - Apache Hadoop+HBase
    - Apache Cassandra (from Facebook)
    - Yahoo PNUTS
    - Google BigTable
    - Amazon SimpleDB
    - Microsoft Azure

傳統的關聯性資料庫, 大多有相同的規範. 但是, 雲端服務大多都有自己的設計理念, 自己的架構, 甚至大多都捨棄了SQL語法. 所以要對這些不同的雲端服務作公平的比較是非常困難的.

Yahoo提供了一個Framework: YCSB(Yahoo! Cloud Serving Benchmark) 來解決這個問題 .(http://wiki.github.com/brianfrankcooper/YCSB/)

雖然雲端的設計理念有很多不一樣
不過主要的設計方向還是一致的, 都是為了:
1. 提供非常大的使用量
2. 提供彈性的方式, 增加雲端服務的數量, 以提供更多的存取量
3. 容錯性, 可以應付所有可能發生的硬體問題, 網路問題

當然, 魚與熊掌不能兼得, 在同樣的設計方向裡面,
每個雲端服務都有他的預設情境, 所以我們必須對以下的情況做抉擇.

- Read vs Write:
為了Write, Update快速, 大多都會使用在磁碟空間中有連續性的Log架構, 去存放資料差異的Update Log, 所以要去Read經過多次Update的資料, 我們就必須要在Log中取得多筆資料之後, 才能組成一筆我們要的資料.

- 同步 vs 非同步:
因為這些架構, 為了容錯機制, 都會複製多筆資料, 在這種情況下, 修改一筆資料時, 其他的複製資料, 是不是也要做同步呢?

- Row-Based vs Column-Based:
提供Column-Based的架構, 每個Column-Family是存放在不同的檔案中, 所以撈取一整筆資料會比較慢, 但是只抓取某些Column會比Row-Based快很多. 此外, 也提供了比較有彈性的資料結構

- 快速 vs 可靠:
在做Write的時候, 大多的架構只會先暫存在記憶體中, 但是這種情況下如果發生硬體異常, 會導致該筆資料毀損, 所以到底是要為了快速還是可靠呢?

比較特別的是HBase, 雖然他選擇了快速的這個陣營, 但是因為HDFS的複製性, 他預設會複製三份資料在不同的電腦, 所以在作Write的動作時, 也會寫到三台電腦的記憶體中, 除非這三台電腦同時發生異常, 否則資料毀損的機會是很小的.


YCSB由幾個層次去對雲端服務作比較:
Tier 1—Performance :
逐漸增加Loading, 去看效能反應

Tier 2—Scaling:
當增加雲端服務的機器數量時, YCSB也等比增加Loading, 去比較效能反應是不是可以維持不變.
也會測量當雲端服務增加機器數量時, 是否會對效能造成負擔

Tier 3—Availability
當發生硬體異常或者網路問題時, 會對效能造成多大的負擔, 目前YCSB還沒辦法自動模擬這種情況.

Tier 4—Replication
各個雲端服務的資料複製數量是可以自己調整的, 這個參數會造成效能上的變化, 所以也是要作比較的. 不同機房之間的複製性, 也是非常重要的效能指標. 目前YCSB也尚為實作.


在實際評比的時候, YCSB為了公平性,  所以將所有雲端服務資料複製性的參數都調整為1, 也就是使得大家都不做資料複製.
並且提供這幾種資料分布性: Uniform, Zipfian, Latest去比較
也實作了這五種情況:Update heavy, Read heavy, Read only, Read latest, Short ranges 去比較

在架構上YCSB 是以延伸為目的, 所以我們可以自己繼承Workload去實作我們想要做的運算, 也可以實作DB Interface去測量其他的Database

看來起YCSB似乎是很公平的, 其實不然. 我覺得至少有以下的兩個情況要做修改:
1. 資料複製性對於大多數的雲端服務來說,  是一個非常重要的特性. 對於HBase來說, 少了資料複製性, 就等於少了Loading Balance, 這是多麼的重要!

2. 目前YCSB提供的DB Interface一次都是抓取一整個row的資料, 這並不符合現實的應用. 所以對於Column也必須做到, Distribution的探討, 才能客觀的反映出現實應用的效能.

HTML5 = jQuery + Google Gears + Video Player...?

還不了解 HTML5 的時候

覺得 HTML 幹麻要推出新版本

過去的包袱實在太多了

不過看過下面這篇介紹之後, 發現 HTML5 真的很厲害

http://apirocks.com/html5/html5.html

以下幾點是我覺得還蠻重要的

1. 提供了類似 jQuery 的 Selector

2. 提供了 Client 端的 Storage/Database

3. WebGL!!

4. 影音播放功能

尤其是第二點在過去是一個很困擾的問題

想要再 Client 端暫存大量的資料是很困難的

如果把資料存在 Cookie 會使得每次做 request 的時候都一大包, 造成彼此的負擔

就算用 JavaScript 的解法, 也只能生存在 Page 的生命週期

不過

對於 Web Developer 來說

最大的惡夢就在於瀏覽器的相容性

目前各大瀏覽器對於 HTML5 支援度都還不一致

HTML5 會不會是下一個惡夢呢?

這是目前各大瀏覽器的支援度:

http://html5readiness.com/

看起來還是各自為政阿

所以, 以後 jQuery 大概會再一次推出 jQuery5 來整合我們的開發環境吧...