一、概觀
創(chuàng)新互聯(lián)建站-專業(yè)網(wǎng)站定制、快速模板網(wǎng)站建設、高性價比龍山網(wǎng)站開發(fā)、企業(yè)建站全套包干低至880元,成熟完善的模板庫,直接使用。一站式龍山網(wǎng)站制作公司更省心,省錢,快速模板網(wǎng)站建設找我們，業(yè)務覆蓋龍山地區(qū)。費用合理售后完善，十多年實體公司更值得信賴。
scipy中的optimize子包中提供了常用的最優(yōu)化算法函數(shù)實現(xiàn)。我們可以直接調(diào)用這些函數(shù)完成我們的優(yōu)化問題。optimize中函數(shù)最典型的特點就是能夠從函數(shù)名稱上看出是使用了什么算法。下面optimize包中函數(shù)的概覽：
1.非線性最優(yōu)化
fmin -- 簡單Nelder-Mead算法
fmin_powell -- 改進型Powell法
fmin_bfgs -- 擬Newton法
fmin_cg -- 非線性共軛梯度法
fmin_ncg -- 線性搜索Newton共軛梯度法
leastsq -- 最小二乘
2.有約束的多元函數(shù)問題
fmin_l_bfgs_b ---使用L-BFGS-B算法
fmin_tnc ---梯度信息
fmin_cobyla ---線性逼近
fmin_slsqp ---序列最小二乘法
nnls ---解|| Ax - b ||_2 for x=0
3.全局優(yōu)化
anneal ---模擬退火算法
brute --強力法
4.標量函數(shù)
fminbound
brent
golden
bracket
5.擬合
curve_fit-- 使用非線性最小二乘法擬合
6.標量函數(shù)求根
brentq ---classic Brent (1973)
brenth ---A variation on the classic Brent（1980）ridder ---Ridder是提出這個算法的人名
bisect ---二分法
newton ---牛頓法
fixed_point
7.多維函數(shù)求根
fsolve ---通用
broyden1 ---Broyden’s first Jacobian approximation.
broyden2 ---Broyden’s second Jacobian approximationnewton_krylov ---Krylov approximation for inverse Jacobiananderson ---extended Anderson mixing
excitingmixing ---tuned diagonal Jacobian approximationlinearmixing ---scalar Jacobian approximationdiagbroyden ---diagonal Broyden Jacobian approximation8.實用函數(shù)
line_search ---找到滿足強Wolfe的alpha值
check_grad ---通過和前向有限差分逼近比較檢查梯度函數(shù)的正確性二、實戰(zhàn)非線性最優(yōu)化
fmin完整的調(diào)用形式是：
fmin(func, x0, args=(), xtol=0.0001, ftol=0.0001, maxiter=None, maxfun=None, full_output=0, disp=1, retall=0, callback=None)不過我們最常使用的就是前兩個參數(shù)。一個描述優(yōu)化問題的函數(shù)以及初值。后面的那些參數(shù)我們也很容易理解。如果您能用到，請自己研究。下面研究一個最簡單的問題，來感受這個函數(shù)的使用方法：f(x)=x**2-4*x+8，我們知道，這個函數(shù)的最小值是4，在x=2的時候取到。
from scipy.optimize import fmin #引入優(yōu)化包def myfunc(x):
return x**2-4*x+8 #定義函數(shù)
x0 = [1.3] #猜一個初值
xopt = fmin(myfunc, x0) #求解
print xopt #打印結果
運行之后，給出的結果是：
Optimization terminated successfully.
Current function value: 4.000000
Iterations: 16
Function evaluations: 32
[ 2.00001953]
程序準確的計算得出了最小值，不過最小值點并不是嚴格的2，這應該是由二進制機器編碼誤差造成的。
除了fmin_ncg必須提供梯度信息外，其他幾個函數(shù)的調(diào)用大同小異，完全類似。我們不妨做一個對比：
from scipy.optimize import fmin,fmin_powell,fmin_bfgs,fmin_cgdef myfunc(x):
return x**2-4*x+8
x0 = [1.3]
xopt1 = fmin(myfunc, x0)
print xopt1
xopt2 = fmin_powell(myfunc, x0)
print xopt2
xopt3 = fmin_bfgs(myfunc, x0)
print xopt3
xopt4 = fmin_cg(myfunc,x0)
print xopt4
給出的結果是：
Optimization terminated successfully.
Current function value: 4.000000
Iterations: 16
Function evaluations: 32
[ 2.00001953]
Optimization terminated successfully.
Current function value: 4.000000
Iterations: 2
Function evaluations: 53
1.99999999997
Optimization terminated successfully.
Current function value: 4.000000
Iterations: 2
Function evaluations: 12
Gradient evaluations: 4
[ 2.00000001]
Optimization terminated successfully.
Current function value: 4.000000
Iterations: 2
Function evaluations: 15
Gradient evaluations: 5
[ 2.]
我們可以根據(jù)給出的消息直觀的判斷算法的執(zhí)行情況。每一種算法數(shù)學上的問題，請自己看書學習。個人感覺，如果不是純研究數(shù)學的工作，沒必要搞清楚那些推導以及定理云云。不過，必須了解每一種算法的優(yōu)劣以及能力所及。在使用的時候，不妨多種算法都使用一下，看看效果分別如何，同時，還可以互相印證算法失效的問題。
在from scipy.optimize import fmin之后，就可以使用help(fmin)來查看fmin的幫助信息了。幫助信息中沒有例子，但是給出了每一個參數(shù)的含義說明，這是調(diào)用函數(shù)時候的最有價值參考。
有源碼研究癖好的，或者當你需要改進這些已經(jīng)實現(xiàn)的算法的時候，可能需要查看optimize中的每種算法的源代碼。在這里：https:/ / github. com/scipy/scipy/blob/master/scipy/optimize/optimize.py聰明的你肯定發(fā)現(xiàn)了，順著這個鏈接往上一級、再往上一級，你會找到scipy的幾乎所有源碼！
前言
Python 一直以來被大家所詬病的一點就是執(zhí)行速度慢，但不可否認的是 Python 依然是我們學習和工作中的一大利器。本文總結了15個tips有助于提升 Python 執(zhí)行速度、優(yōu)化性能。
關于 Python 如何精確地測量程序的執(zhí)行時間，這個問題看起來簡單其實很復雜，因為程序的執(zhí)行時間受到很多因素的影響，例如操作系統(tǒng)、Python 版本以及相關硬件（CPU 性能、內(nèi)存讀寫速度）等。在同一臺電腦上運行相同版本的語言時，上述因素就是確定的了，但是程序的睡眠時間依然是變化的，且電腦上正在運行的其他程序也會對實驗有干擾，因此嚴格來說這就是實驗不可重復。
我了解到的關于計時比較有代表性的兩個庫就是 time 和 timeit 。
其中， time 庫中有 time() 、 perf_counter() 以及 process_time() 三個函數(shù)可用來計時（以秒為單位），加后綴 _ns 表示以納秒計時（自 Python3.7 始）。在此之前還有 clock() 函數(shù)，但是在 Python3.3 之后被移除了。上述三者的區(qū)別如下：
與 time 庫相比， timeit 有兩個優(yōu)點：
timeit.timeit(stmt='pass', setup='pass', timer= , number=1000000, globals=None) 參數(shù)說明：
本文所有的計時均采用 timeit 方法，且采用默認的執(zhí)行次數(shù)一百萬次。
為什么要執(zhí)行一百萬次呢？因為我們的測試程序很短，如果不執(zhí)行這么多次的話，根本看不出差距。
Exp1：將字符串數(shù)組中的小寫字母轉(zhuǎn)為大寫字母。
測試數(shù)組為 oldlist = ['life', 'is', 'short', 'i', 'choose', 'python']。
方法一
方法二
方法一耗時 0.5267724000000005s ，方法二耗時 0.41462569999999843s ，性能提升 21.29%
Exp2：求兩個 list 的交集。
測試數(shù)組：a = [1,2,3,4,5]，b = [2,4,6,8,10]。
方法一
方法二
方法一耗時 0.9507264000000006s ，方法二耗時 0.6148200999999993s ，性能提升 35.33%
關于 set() 的語法： | 、 、 - 分別表示求并集、交集、差集。
我們可以通過多種方式對序列進行排序，但其實自己編寫排序算法的方法有些得不償失。因為內(nèi)置的 sort() 或 sorted() 方法已經(jīng)足夠優(yōu)秀了，且利用參數(shù) key 可以實現(xiàn)不同的功能，非常靈活。二者的區(qū)別是 sort() 方法僅被定義在 list 中，而 sorted() 是全局方法對所有的可迭代序列都有效。
Exp3：分別使用快排和 sort() 方法對同一列表排序。
測試數(shù)組：lists = [2,1,4,3,0]。
方法一
方法二
方法一耗時 2.4796975000000003s ，方法二耗時 0.05551999999999424s ，性能提升 97.76%
順帶一提， sorted() 方法耗時 0.1339823999987857s 。
可以看出， sort() 作為 list 專屬的排序方法還是很強的， sorted() 雖然比前者慢一點，但是勝在它“不挑食”，它對所有的可迭代序列都有效。
擴展 ：如何定義 sort() 或 sorted() 方法的 key
1.通過 lambda 定義
2.通過 operator 定義
operator 的 itemgetter() 適用于普通數(shù)組排序， attrgetter() 適用于對象數(shù)組排序
3.通過 cmp_to_key() 定義，最為靈活
Exp4：統(tǒng)計字符串中每個字符出現(xiàn)的次數(shù)。
測試數(shù)組：sentence='life is short, i choose python'。
方法一
方法二
方法一耗時 2.8105250000000055s ，方法二耗時 1.6317423000000062s ，性能提升 41.94%
列表推導（list comprehension）短小精悍。在小代碼片段中，可能沒有太大的區(qū)別。但是在大型開發(fā)中，它可以節(jié)省一些時間。
Exp5：對列表中的奇數(shù)求平方，偶數(shù)不變。
測試數(shù)組：oldlist = range(10)。
方法一
方法二
方法一耗時 1.5342976000000021s ，方法二耗時 1.4181957999999923s ，性能提升 7.57%
大多數(shù)人都習慣使用 + 來連接字符串。但其實，這種方法非常低效。因為， + 操作在每一步中都會創(chuàng)建一個新字符串并復制舊字符串。更好的方法是用 join() 來連接字符串。關于字符串的其他操作，也盡量使用內(nèi)置函數(shù)，如 isalpha() 、 isdigit() 、 startswith() 、 endswith() 等。
Exp6：將字符串列表中的元素連接起來。
測試數(shù)組：oldlist = ['life', 'is', 'short', 'i', 'choose', 'python']。
方法一
方法二
方法一耗時 0.27489080000000854s ，方法二耗時 0.08166570000000206s ，性能提升 70.29%
join 還有一個非常舒服的點，就是它可以指定連接的分隔符，舉個例子
life//is//short//i//choose//python
Exp6：交換x，y的值。
測試數(shù)據(jù)：x, y = 100, 200。
方法一
方法二
方法一耗時 0.027853900000010867s ，方法二耗時 0.02398730000000171s ，性能提升 13.88%
在不知道確切的循環(huán)次數(shù)時，常規(guī)方法是使用 while True 進行無限循環(huán)，在代碼塊中判斷是否滿足循環(huán)終止條件。雖然這樣做沒有任何問題，但 while 1 的執(zhí)行速度比 while True 更快。因為它是一種數(shù)值轉(zhuǎn)換，可以更快地生成輸出。
Exp8：分別用 while 1 和 while True 循環(huán) 100 次。
方法一
方法二
方法一耗時 3.679268300000004s ，方法二耗時 3.607847499999991s ，性能提升 1.94%
將文件存儲在高速緩存中有助于快速恢復功能。Python 支持裝飾器緩存，該緩存在內(nèi)存中維護特定類型的緩存，以實現(xiàn)最佳軟件驅(qū)動速度。我們使用 lru_cache 裝飾器來為斐波那契函數(shù)提供緩存功能，在使用 fibonacci 遞歸函數(shù)時，存在大量的重復計算，例如 fibonacci(1) 、 fibonacci(2) 就運行了很多次。而在使用了 lru_cache 后，所有的重復計算只會執(zhí)行一次，從而大大提高程序的執(zhí)行效率。
Exp9：求斐波那契數(shù)列。
測試數(shù)據(jù)：fibonacci(7)。
方法一
方法二
方法一耗時 3.955014900000009s ，方法二耗時 0.05077979999998661s ，性能提升 98.72%
注意事項：
我被執(zhí)行了（執(zhí)行了兩次 demo(1, 2) ，卻只輸出一次）
functools.lru_cache(maxsize=128, typed=False) 的兩個可選參數(shù)：
點運算符( . )用來訪問對象的屬性或方法，這會引起程序使用 __getattribute__() 和 __getattr__() 進行字典查找，從而帶來不必要的開銷。尤其注意，在循環(huán)當中，更要減少點運算符的使用，應該將它移到循環(huán)外處理。
這啟發(fā)我們應該盡量使用 from ... import ... 這種方式來導包，而不是在需要使用某方法時通過點運算符來獲取。其實不光是點運算符，其他很多不必要的運算我們都盡量移到循環(huán)外處理。
Exp10：將字符串數(shù)組中的小寫字母轉(zhuǎn)為大寫字母。
測試數(shù)組為 oldlist = ['life', 'is', 'short', 'i', 'choose', 'python']。
方法一
方法二
方法一耗時 0.7235491999999795s ，方法二耗時 0.5475435999999831s ，性能提升 24.33%
當我們知道具體要循環(huán)多少次時，使用 for 循環(huán)比使用 while 循環(huán)更好。
Exp12：使用 for 和 while 分別循環(huán) 100 次。
方法一
方法二
方法一耗時 3.894683299999997s ，方法二耗時 1.0198077999999953s ，性能提升 73.82%
Numba 可以將 Python 函數(shù)編譯碼為機器碼執(zhí)行，大大提高代碼執(zhí)行速度，甚至可以接近 C 或 FORTRAN 的速度。它能和 Numpy 配合使用，在 for 循環(huán)中或存在大量計算時能顯著地提高執(zhí)行效率。
Exp12：求從 1 加到 100 的和。
方法一
方法二
方法一耗時 3.7199997000000167s ，方法二耗時 0.23769430000001535s ，性能提升 93.61%
矢量化是 NumPy 中的一種強大功能，可以將操作表達為在整個數(shù)組上而不是在各個元素上發(fā)生。這種用數(shù)組表達式替換顯式循環(huán)的做法通常稱為矢量化。
在 Python 中循環(huán)數(shù)組或任何數(shù)據(jù)結構時，會涉及很多開銷。NumPy 中的向量化操作將內(nèi)部循環(huán)委托給高度優(yōu)化的 C 和 Fortran 函數(shù)，從而使 Python 代碼更加快速。
Exp13：兩個長度相同的序列逐元素相乘。
測試數(shù)組：a = [1,2,3,4,5], b = [2,4,6,8,10]
方法一
方法二
方法一耗時 0.6706845000000214s ，方法二耗時 0.3070132000000001s ，性能提升 54.22%
若要檢查列表中是否包含某成員，通常使用 in 關鍵字更快。
Exp14：檢查列表中是否包含某成員。
測試數(shù)組：lists = ['life', 'is', 'short', 'i', 'choose', 'python']
方法一
方法二
方法一耗時 0.16038449999999216s ，方法二耗時 0.04139250000000061s ，性能提升 74.19%
itertools 是用來操作迭代器的一個模塊，其函數(shù)主要可以分為三類：無限迭代器、有限迭代器、組合迭代器。
Exp15：返回列表的全排列。
測試數(shù)組：["Alice", "Bob", "Carol"]
方法一
方法二
方法一耗時 3.867292899999484s ，方法二耗時 0.3875405000007959s ，性能提升 89.98%
根據(jù)上面的測試數(shù)據(jù)，我繪制了下面這張實驗結果圖，可以更加直觀的看出不同方法帶來的性能差異。
從圖中可以看出，大部分的技巧所帶來的性能增幅還是比較可觀的，但也有少部分技巧的增幅較?。ɡ缇幪?、7、8，其中，第 8 條的兩種方法幾乎沒有差異）。
總結下來，我覺得其實就是下面這兩條原則：
內(nèi)置庫函數(shù)由專業(yè)的開發(fā)人員編寫并經(jīng)過了多次測試，很多庫函數(shù)的底層是用 C 語言開發(fā)的。因此，這些函數(shù)總體來說是非常高效的（比如 sort() 、 join() 等），自己編寫的方法很難超越它們，還不如省省功夫，不要重復造輪子了，何況你造的輪子可能更差。所以，如果函數(shù)庫中已經(jīng)存在該函數(shù)，就直接拿來用。
有很多優(yōu)秀的第三方庫，它們的底層可能是用 C 和 Fortran 來實現(xiàn)的，像這樣的庫用起來絕對不會吃虧，比如前文提到的 Numpy 和 Numba，它們帶來的提升都是非常驚人的。類似這樣的庫還有很多，比如Cython、PyPy等，這里我只是拋磚引玉。
原文鏈接：
第一：不需要定義main函數(shù)，直接寫就好。
第二：代碼的邏輯也是有問題的。一般來說，按這樣的框架去寫：
_size, _verbs, A, s = [int(_) for _ in imput().split(' ')], [], ''
for _ in range(_size): A.append(...) # 讀入矩陣所有行
def G:
....實現(xiàn)特征函數(shù)G
for _ in range(_verbs):
....verb = [int(_) for _ in imput().split(' ')]
.... if verb[0] = 1:
........行翻轉(zhuǎn)
....elif verb[0] = 2:
........列翻轉(zhuǎn)
....else:
........s += G()
print(s)
重慶分公司
重慶分公司
