2010年1月31日 星期日

專利,就是科技競爭力

書籍基本資料:專利,就是科技競爭力

這年頭專利盛行,雖說專利申請書是專利工程師在寫,多少懂些專利知識,才能明白何謂專利,想出有用 (防範侵權或授權獲利) 的專利。這本書用白話的方式配合舉例,說明專利是什麼。藉由許多正反例子,幫我釐清不少觀念,總算有種「我好像有點明白專利」的感覺。以下為一些散亂的筆記。

專利的觀念澄清

專利的目的是鼓勵發明,保護發明人的權利。像寫作、程式碼屬於著作權,完成的當下作者就擁有著作權。然而,其他人只要寫法不同,即使概念和我的作法完全一樣,也不會侵犯到著作權。專利則是保護發明人的概念。以最近當紅的 MapReduce 來說,Hadoop 沒用到 Google 的原始碼,所以沒侵犯到 Google 的著作權,但是由於 Google 已申請到 MapReduce 的專利,Hadoop 就侵犯到 Google 的專利權 (Google 要不要告 Hadoop 是另一回事啦)。

但也不是光提概念就能申請專利,比方說申請「讓人類飛在空中」就不會通過,除提出概念外,至少還有提及一種實現方法。不過專利的重點是保護概念,而非實現方法。但這也得看專利的寫法,其他人可能以不同的實現方式迴避專利。我還沒搞清楚這部份差異。

閱讀專利書時,最重要的部份是申請專利範圍 (claim),其它部份只是交代相關知識,並無法律效果。

專利訴訟時會以專利範圍去比對侵權產品,比方說專利 A 包含 A1、A2 兩個元件,產品 B 包含 A1、B2,那麼產品 B 就沒有侵權。若產品 C 包含 A1、A2、C3,那產品 C 有侵權。用數學式來表示就是:

if A ^ B == A, then
B 侵犯到 A 專利
else
無侵權

若從字意上的解讀無法看出 B 包含 A 的專利範圍,可進一步做推論,判斷兩者是否有同意的詞。書中以鐵槌為例,若專利 A 和產品 B 只差在 A 用拉環來掛鐵槌,B 用挖洞。這就看法官是否認為這兩者是同樣的概念。

專利範圍的條件愈多,範圍愈小。所以若有兩個限制 A1、A2,若能拆開各別申請,效果會更好,但也會比較難申請。

由以上的描述可知,專利說明書的品質相當重要。現今廣為使用在滑鼠的滾輪,並不是第一個發明滾輪的人。在那之前也有人申請專利,只是他聲言的專利範圍除「輔助操作件」 (比方滾輪) 外,還多提到「彈性元件」,所以後來為滾輪申請專利就沒有侵權。

即使申請到專利 A,也不見得可以行使專利 A。比方說專利 A 包含 A1、A2 兩點,但可能 A1、A2 各有一個專利,於是要行使專利 A 的話,還得先和 A1、A2 的所有人購買專利權。

那些項目可以申請專利?

去除是否能獲利,申請專利其實是很簡單的事,只要滿足專利三要素即可

  1. 有用性:提出對發明人而言有用的理由即可,比方「狗手錶」聲稱給狗帶的手錶,實際上就是快七倍時間的手錶。申請人聲稱這可讓狗的主人明白狗的生命短暫,更珍惜狗。
  2. 新穎性:過去全世界文獻 (通常是索引專利資料庫) 中沒有出現過的方法。除不重要的細節外,只要有一絲不同,就有新穎性。所以有時即使是相當直覺的東西,沒有文獻就無法退回申請。另外若審查官懶得看他國的專利資料庫,也可能發生日本已有案例,卻仍在台灣申請成功。但這樣的專利也可能無用,事後若有人發現這點,可申請專利無效 (打官司時對手最常幹的事)。
  3. 進步性 (非顯而易見性):新穎性是一對一比方,而進步性是拿過去多件作品和目前的申請比對。申請人要證明過去任何方法都無法組出申請方法能達到的效果。那怕是 90% 的效果變成 90.1%,都可以申請。只要該領域的技術人士無法輕易想出你的作法,就有非顯而易見性。為免事後諸葛,審查時會比較寬鬆。進步性也不是非要「進步」不可,重點是「非顯而易見」。有許多高爾夫球專利,差別在於表面的洞有不同排列方式。到底有沒有飛得比較遠?那不是重點,只要不是「輕易」想到即可。

比方說現在已有電視這種東西,只要隨便把電視和另一個不相干的東西組在一起,就能機會申請專利。像是兼具暖爐功能的電視、能養魚的電視等。雖然拆開來看都是習以為常的產品,合起來卻是「沒有人想過」的概念 (無文獻記載)。書中舉了許多有趣的例子,像是避免忘了帶筆,把筆放在鑰匙圈裡、放在手錶裡、放在項鍊裡都被申請成專利。

新用途可以申請專利,像是阿司匹林原本是感冒藥,卻發現也有防治心血管疾病效果。後來這個新用途就被申請成專利。

雖然數學公式無法申請專利,使用數學的應用方式卻可以。所以無法申請傅立葉轉換,但可以申請「讀入一串資料,做傅立葉轉換,接著輸出」。可以歸可以,會不會過是另一回事 (比方說已有論文或書籍提及這種作法,那就不具新穎性了)。

軟體也可以申請專利,像美國賭場的吃角子老虎,以前是各台單獨累積獎金。有人提出讓全部機器連線,統一累積獎金,並用軟體控制產生的結果,確保中獎機率不會過高。這人有成功地申請專利,後來賣給賭場。還有像 Yahoo 也有申請到個人化網頁的專利:Dynamic page generator

An custom page server is provided with user preferences organized into templates stored in compact data structures and the live data used to fill the templates stored local to the page server which is handing user requests for custom pages. One process is executed on the page server for every…

注意,這裡保護的重點仍是概念,不是程式碼。一個大型軟體專案包含許多概念,可能會抽出其中幾點符合專利三要素的元件來申請專利,而不會申請整個軟體專案。作者以 e-mail 系統舉的例子滿不錯的,一個新的 e-mail 系統包含更好的編輯器和更好的偵測機制,編輯器和 Word 相比可能不具進步性 (使用者可以用 Word 編好內容,再用貼到舊的 e-mail 編輯器),然而偵測垃圾郵件的機制可能有進步性。

原本我也挺反對軟體專利 (應該說我還沒搞懂它的含蓋範圍,萬一 design pattern 被專利了,會發生什麼事?),不過作者舉的一些例子也滿有道理的,像是支援附加功能的傳真機,附加功能可能是傳真結束後輸出一張紙表示上個操作有無成功。這不需更新硬體即可達成,是很有用的功能 (現今有電子螢幕就不需要啦)。若沒有軟體專利,競爭對手即可抄走這個概念,違反了專利保護發明人概念的原意。

2010年1月5日 星期二

Python 加速的方法

這一年來用 Python 開發滿爽的,用久後發覺 Python 真的是不夠快啊。雖說這就是 trade-off,拿 CPU 執行時間換工程師開發的時間,但關鍵時刻跑得不夠快,還是得投入時間研究如何加速。程式開發就是一連串的 trade-off,人生也是如此啊!…………………還是少嘴炮,切入正題吧。

用 Profiling 測全體執行時間

去除演算法、資料結構的問題外 (像是 O(N log(N)) vs. O(N^2) 的方法 ),千萬別自己亂猜效能瓶頸就一頭熱地改程式。隨便想想都能舉出一堆自以為聰明的反例。我印象最深的經驗是,有一次我在寫資料結構作業答案,題目是實作 hash table 來統計文章裡單字出現的次數,身為課程助教,程式當然不能跑得太慢啊。所以調了一下效能,結果發覺改了一些演算法 (如 hash table 的 「chain」用 binary tree 而不用 linked-list ),卻沒快多少 (變慢是常有的事),一用 profiler 量,卻發現 1/3 的時間花在把一行文字切成單字上。我原本用 Java 的 split 一次切完回傳一個 List,改用 StringTokenizer 後就省下整體 1/3 的時間。

Python 有內建 profiling 的工具,叫做 profile,可以透過命令列直接下參數使用:

1
python -m cProfile -s time MODULE.py ARGUMENTS

這樣會執行 MODULE 再將測量結果輸出到螢幕,時間依單一函式執行時間來排序。引用官網的例子,cProfile 的輸出格式如下:

1
2
3
4
5
6
7
8
     2706 function calls (2004 primitive calls) in 4.504 CPU seconds
 
Ordered by: standard name
 
ncalls  tottime  percall  cumtime  percall filename:lineno(function)
    2    0.006    0.003    0.953    0.477 pobject.py:75(save_objects)
 43/3    0.533    0.012    0.749    0.250 pobject.py:99(evaluate)
 ...

前面的 tottime 是該函式自己執行的時間;後面的 cumtime 則是該函式整體 (包含它呼叫其它函式) 的執行時間。

附帶一提,以前試 Java profiling 工具時,執行速度會慢個數倍,但用 Python 的 cProfile 卻只變成一倍多慢而已,也可能我那時用的 Java 工具太糟,或參數沒設好吧。

用 timeit 來量單一 expression 的速度

timeit 也是內建模組,也可以用命令列執行:

1
python -m timeit EXPRESSION

下面是執行的例子:

1
2
3
4
5
$ python -m  timeit 'range(10)'
1000000 loops, best of 3: 0.3 usec per loop
 
$ python -m  timeit 'xrange(10)'
10000000 loops, best of 3: 0.166 usec per loop

我比較常寫程式來測 timeit,透過命令列執行 expression 相當受限,還是自己寫段程式包成函式後,再用 timeit 執行較方便。附上一個例子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#!/usr/bin/env python
# Count numbers in a list.
# Demonstrate built-in functions' efficiency.
 
import timeit
import random
 
# prepare test data
numbers = range(2)
a = []
for n in numbers:
   a += [n] * 10000
random.shuffle(a)
 
def test():
   c = {}
   for x in a:
       c[x] = c.get(x, 0) + 1
 
def test2():
   c = {}
   for n in numbers:
       c[n] = 0
   for x in a:
       c[x] += 1
 
def test3():
   c = {}
   for n in numbers:
       c[n] = a.count(n)
 
 
if __name__=='__main__':
   t = timeit.Timer("test()", "from __main__ import test")
   print 'test', t.timeit(number=1000)
 
   t = timeit.Timer("test2()", "from __main__ import test2")
   print 'test2', t.timeit(number=1000)
 
   t = timeit.Timer("test3()", "from __main__ import test3")
   print 'test3', t.timeit(number=1000)

有興趣的人可以猜猜看那個方法最快 [1]。

找出瓶頸後加速的方法

用 profiling 找出瓶頸後,大概有幾種作法:

  • multiprocessing 平行化:這年頭 CPU 不用錢,隨便買都是 multi-core。若程式可以單純平行化,這個作法比用 C/C++ 方便一些,至少還是在寫 python code。但若程式稍微複雜,寫起來會很辛苦,且容易因 fork 或 lock 的 overhead 而沒快多少。
  • 將 CPU bound 的地方透過 ctypes 改寫成 C/C++:雖說 ctypes 很好用,不過寫 C/C++ 得注意的事比寫 Python 多太多了,所以我滿少這麼幹的。
  • 從 Python interpreter 下手,改用較快的寫法:這個作法需要一些 Python 運作的知識,才知道怎麼改會比較快。比方若不需用到整個 list 可以改用 generator 減少產生 list 的時間、使用 member field 存取資料以減少 function call、改用 built-in 函式組出要做的事 (如上面附的例子)。這時 timeit 就很好用了,可以先測好關鍵部份,減少重跑整個 profiling 的時間。

不勞而獲的加速方法

我只有偶而注意相關消息,還沒試過,只知道各家方法有些不適用的問題,這裡記些關鍵字。

Psyco 是老字號工具,大家都說讚,對數值運算特別有效,但它只支援 32-bit CPU,作者目前在開發 PyPy。另外 Google 開發的 unladen-swallow 也令人期待。也許在不久的將來,兩邊都會有足以實用的成果吧。

延伸閱讀

Victor 告知,Python 官方 Wiki 有幾篇超棒的文件,相當值得一看:

備註

  1. 這是我執行出來的數據:
    1
    2
    3
    
    test 5.41639614105
    test2 2.70715403557
    test3 0.619280815125

    即使走訪 list 兩次,方法三還是比前兩個方法 (只走訪一次) 快上不少,這是因為方法三用 C 實作的程式走訪迴圈,而前兩個方法用到 Python 的迴圈。