星期六, 3月 31, 2007

回憶

很多很多天以前,我就想寫一篇有關孫燕姿的文章,但是苦無時間...

對我而言,聽音樂是一個具有很特殊的回憶之事,孫燕姿對我而言就是一個很特殊的高中回憶。我高一的時候,她的第六張專輯"未完成 To be continued"出來了,我聽一聽之後,不知道有什麼動力,我餓了一兩個月,把她前面五張專輯買齊,現在想想,仍屬一件神奇之事。

照慣例,要說話之前,我們先來看看,她出專輯的記錄(破例記錄到月)

  • 同名專輯 - 2000.06
  • 我要的幸福 - 2000.12
  • 風箏 - 2001.07
  • Start自選輯 - 2002.01
  • Leave - 2002.05
  • 未完成 - 2003.01
  • The Moment - 2003.08
  • Stefanie - 2004.10
  • 完美的一天 - 2005.10
  • 逆光 - 2007.03

就發片速度來看,早期的速度可謂是迅雷不及掩耳,到後來越來越慢(一方面是合約問題,一方面是她真的唱的很累)。

對她歌的感想是什麼呢?Josh Ko對我說了如下的話
剛出道時耳目一新,但是久了就與一般歌手一樣

對我而言
剛出道時耳目一新,但久了就陷入了複製自己的迴圈

何謂陷入複製自已的迴圈?周杰倫是個很好的例子(我直到現在還是只聽同名專輯和范特西,雖然咬字還是模糊,但是創作原味仍在)一般歌手為什麼不敢跳脫既定印象呢?因為怕失去原有的老聽眾群,更害怕無法開發新的聽眾群,如果仍然走一脈的唱風,孫燕姿的確出的每一張專輯都有固定的支持群眾,但是卻很難再吸引新的群眾了。

"逆光"出來時,我一首都沒有聽過,即以掏錢預購之,聽完不出預料的失望,這張專輯的歌曲鑑別度不高(鑑別度高的?我要的幸福),聽了十首歌很像聽了同一首,硬是要聽的話...我頂多只能分出其中三首。事實上孫燕姿後面所出來的專輯都有歌曲鑑別度不高的問題,帶來的就是人氣下滑(The moment的"遇見"或許是例外,與電影"向左走,向右走"結合,事實上很多歌都與電視電影行銷),更別提那奇怪的銷售量數字(或許會有專業的姿迷提出精確的數字反駁,但是我不得不說,歌迷流失是一個事實),其他有關孫燕姿的想法,我想,與大部分人相同。

我是不是姿迷,或許是,早期我與"18度C的孫燕姿"站長、yahoo家族"愛姿病末期病房"的家長 有過接觸(家長都叫我小藍XD),那是我一段很快樂的網路生活(少不更事時,曾經過著每天灌水18度的日子XD),或許是姿迷,我會以較嚴格的標準來看待。

但是就今年而言,"逆光"是不是一張好專輯,是,因為台灣整體的流行音樂界品質也降了不少,不然我不會轉聽外文歌曲和非主流樂團。張惠妹的姊妹不也賣了上百萬張嗎:)

---
看來最近都走懷舊風

星期四, 3月 29, 2007

發現

真的要寫一份說明document的話,用字要嚴謹,這好像不是現在的我所能辦到的,不過願盡力一試,當然,排版要有一定的乾淨程度,這是一必然要求,SIC已經完成,SIC/ XE,我想我會照我自己的意思來寫

星期三, 3月 28, 2007

才能?

才能能當飯吃之外還能做什麼?

當水喝XD

---
為什麼我早起就要那麼冷Orz

星期一, 3月 26, 2007

資料結構與演算法(下)05 by 隨機客

非正題:今天上課算是比較輕鬆的一次(是進入狀況還是課比較好懂呢?我也不知道XD),上課還被隨機客詢問(當然,我答不出來XD),興起了換位子的念頭XD



2007/03/26 資料結構與演算法(下) 呂學一 投影片
今天上課的主題是Shortest-Path Tree Algorithm, 主要分有Bellman-Ford, Dijkstra Algorithm

在進入Algorithm前,先行討論此問題的背景

  • The setting
    • The graph G = (V, E) is directed with edge length w. (此圖必需是個有權重的有向圖)
    • The length of each edge could be negative. (允許圖上的edge 為 negative)


  • The problem
    • Input: A directed Graph G=(V, E) with weight edge w.
      A node r of G
    • Output: A tree T rooted at r such that the path of T from r to each node u of T is a shortest path from r to u in G.(yen3註:一個root 為r 的shortest path tree.)


  • We may assume that each node in the graph is reachable from r.(yen3註:假設r 可以到達每個node)
    那麼在Graph中,有unreachable node,則一開始則remove掉,而不失一般性(Without loss of generality),為什麼呢?
    尋找對r所有的unreachable node只需要花linear time,用DFS(depth First Search)從r開始,把所經過的點編號,而沒有被編號到的node就是unreachable node,而執行DFS只需要linear time,故此假設不失一般性

  • Can a shortest path between node u and v contain a cycle? (是否會有cycle在shortest path tree上呢?)
    答案是否,我們把cycle weight sum分成三種狀況
    • cycle weight sum is positive: 此狀況不可能發生,因為這一定不是shortest path,因為一定不會通過,因為把此cycle 拿掉則path會更短
    • cycle weight sum is negative: u到v根本沒有shortest path,繞了n圈為最短,則繞了n+1圈會更短,則繞不完,所以有negative cycle weight的Graph, 則shortest path 不存在(這是一個if and only if)
    • cycle weight sum is 0: 則不會通過,就沒有cycle,這樣子可把cycle做一個remove的動作,使其cycle不在shortest path上

  • Single-source shortest-path problem
    在此問題上為single path,但是與一般的path定義不同,一般的path定義為該node通過後則不能再通過,但是在此,我們比較確切關心edge weight sum

  • Such a shortest-path tree always exists? 不一定,原因如上
    若r至任何一點u,都是reachable,就找所有可以走到的方法,事實上有可能是無限條,但是限制在G has no negative edge 和remove unreachable node 和 only think about single path ,則shortest path 則會變成有限條

  • The shortest-path tree problem is equivalent to finding the distance from r to each node u in graph G. (尋找shortest distance和shortest path 是等價的問題)
    何謂等價的問題,若A和B是等價的問題,則找到A的答案之後,我們可以在linear time 找到B的答案,且找到B的答案之後,也可以在linear time 找到A的答案
    那麼為什麼shortest distance 和 shortest path是等價的問題?若已知shortest path,則把edge weight求其和即為distance,可在linear time 找到,若是shortest distance呢?從r到v的點,我們從v點找起,把指向v點的edge weight掃描一次,若剛好等於,則是shortest path 的一個解,若小於此weight,則扣掉該重量,進行recursion,由於只有m個邊,我們可以保證在linear time 找到

  • 補充說明:在演算法上所定義的linear time並不是指O(n),而是指執行效率相對於input size,若input size 為O(n^2),而RunTime也是O(n^2),則我們說該演算法是linear time


終於可以描述演算法嘍XD

  • Bellman-Ford Algorithm
    此演算法的方式如下
    • 設一個array d[u]為從r 到u的距離
    • 對其array做初始化的動作
      • Let d[u] = infinty for each node u of G
      • let d[r]=0(自己到自己距離為0)
    • Repeat improve對於d[u] for d(u)的估算

    而Relaxing edge(u,v)為
        If d[v] > d[u]+w(u,v) then
    let d[v] = d[u] + w(u,v)
    那何謂A phase of improvement
        For each edge(u, v) of G do
    relax edge(u, v)
    問題又來了,試問phase of improvement 要跑幾次才能確保答案的正確呢?
    如果node為n個,則跑n-1次就可確保答案正確性,每當我們跑了phase of improvement,則會有一點被改善(yen3註:竟然不會證Orz)
    那麼效率呢,由於有n個node,m個edge,每個點皆跑m個edge,所以Time Complexity = O(mn)

    第二個問題是,若圖中有negative cycle,則我們要怎麼得知?
    問題也很簡單,已知演算跑n-1次已經得解,若跑了第n個phase 而仍然有d[u]被改變的情形,則知道與原先預想的不合,此圖有negative cycle
    為什麼?在s.31說明(yen3註:證明竟然忘了...真神Orz)

    若該Graph 為一個 Directed Acyclic Graph DAG呢? 方法如下
    • 先對該DAG做topological sort
    • 根據topological sort 的順序,由小到大(slight 上寫由for 1 to n)做relaxing動作
    其Running Time 是 O(m+n)

  • Dijkstra Algorithm

    (題外話:Edsger W. Dijkstra 是提出“Goto is considered harmful.”的人)(yen3註:此話真的是powerful,對於現在學assembly language的我而言更是一個有趣的問題。)

    此演算法是一個極具powerful的演算法,此演算法求shortest path是建立在無non-negative weight edge, non-negative-cycle的DAG上,方法如下(此方法不用依靠topological sort做前置作業)
    • 做與Bellman-Ford Algorithm同樣的初始化動作(與對其array做初始化的動作相同)
    • 每一個iteration中,尋找unprocessed node中,尋找到目前為止smallest path做relaxing,直到每一點都做完為止(換句話說,在所有未處理的點找到該點花費最少的來做處理)

    此方法的正確性呢?由s.50得知。假設u是unprocessed minimal node,而在處理到u node時出錯了,而y node 與processed node 的範圍只用一條edge連結,所以我們確信d[y] = d(y),但是我們又說u是unprocessed minimal node,而用y連過去則會讓d[u] > d(u) >=d(y) = d[y] 矛盾(yen3註:證的真爛Orz)

    則Running Time用 Naïve implementation: O(n2 + m).
    With Fibonacci heap: O(n log n + m).




---
聽Josh Ko說明才得知簡報上的數學式是用TeX4PPT做的,來找找做個介紹

塞車

騎摩拖車遇到塞車算是很大的難題之一,雖然演算法學的是圖論,但是關係不大XD 唯一的關係,你得避開車潮,今日六點半起床(上大學以來最早),七點出發...還是躲不了塞車的惡夢,下禮拜決定六點起來好了

---
再塞我前天就睡台大(會不會有兩個人做惡夢XD)

星期日, 3月 25, 2007

XD

家樂福的XD
家福福的XD2

---
是男人就該逛家樂福