pythonqsort

① 參加ACM大賽應該准備哪些課程

課程：

（1）基本演算法: 二分,分治，貪心

（2） 離散數學離散數學動態規劃

（3） 搜索演算法：深度優先 搜索，廣度優先搜A*演算法 ，阿爾法貝塔剪枝

（4）數據結構:線段樹, 樹狀數組，並查集,Trie圖

（5）圖論問題：最小生成樹 最短路 強連通分量、橋和割點

（6）網路流演算法：基本的網路流演算法，Dinic演算法，帶上下界的網路流，最小費用流

（7）計算幾何：線與線求交，線與面求交，求凸包，半平面求交等

（8） 離散數學，高等數學，線性代數，初等數論，計算幾何

（9）計算機專業英語

（10）C++；基礎的遞歸、枚舉演算法

(1)pythonqsort擴展閱讀：

1.參賽隊伍最多由三名參賽隊員組成。

2.競賽中命題10題左右，試題描述為英文，比賽時間為5個小時，前四個小時可以實時看到排名，最後一小時封榜，無法看到排名。

3.競賽可以使用的語言：Java, C, C++, Kotlin 和 Python。

4.重點考察選手的演算法和程序設計能力，不考察實際工程中常用的系統編程，多線程編程等等；

5.選手可攜帶任何非電子類資料，包括書籍和列印出來的程序等，部分賽區會對選手攜帶的紙質資料做限制。

6.評委負責將結果（正確或出錯的類型）通過網路盡快返回給選手，除此之外不提供任何額外幫助；

7.每個題目對應一種顏色的氣球，通過該題目的隊伍會得到對應顏色氣球。每道題目第一支解決掉它的隊還會額外獲得一個「FIRST PROBLEM SOLVED」的氣球。

② 回調函數(callback)是什麼 ,,

回調函數就是一個被作為參數傳遞的函數。在C語言中，回調函數只能使用函數指針實現，在C++、Python、ECMAScript等更現代的編程語言中還可以使用仿函數或匿名函數。

回調函數的使用可以大大提升編程的效率，這使得它在現代編程中被非常多地使用。同時，有一些需求必須要使用回調函數來實現。

最著名的回調函數調用有C/C++標准庫stdlib.h/cstdlib中的快速排序函數qsort和二分查找函數bsearch中都會要求的一個與strcmp類似的參數，用於設置數據的比較方法。

意義

因為可以把調用者與被調用者分開，所以調用者不關心誰是被調用者。它只需知道存在一個具有特定原型和限制條件的被調用函數。簡而言之，回調函數就是允許用戶把需要調用的函數的指針作為參數傳遞給一個函數，以便該函數在處理相似事件的時候可以靈活的使用不同的方法。

③ 如何讓 Python 像 Julia 一樣快地運行

Julia 與 Python
的比較
我是否應丟棄 Python 和其他語言，使用 Julia 執行技術計算？在看到 http://julialang.org/ 上的基準測試後，人們一定會這么想。Python
和其他高級語言在速度上遠遠有些落後。但是，我想到的第一個問題有所不同：Julia 團隊能否以最適合 Python 的方式編寫 Python 基準測試？
我對這種跨語言比較的觀點是，應該根據要執行的任務來定義基準測試，然後由語言專家編寫執行這些任務的最佳代碼。如果代碼全由一個語言團隊編寫，則存在其他語言未得到最佳使用的風險。
Julia 團隊有一件事做得對，那就是他們將他們使用的代碼發布到了 github 上。具體地講，Python 代碼可在此處找到。
第一眼看到該代碼，就可以證實我所害怕的偏見。該代碼是以 C 風格編寫的，在數組和列表上大量使用了循環。這不是使用 Python 的最佳方式。
我不會責怪 Julia 團隊，因為我很內疚自己也有同樣的偏見。但我受到了殘酷的教訓：付出任何代價都要避免數組或列表上的循環，因為它們確實會拖慢 Python
中的速度，請參閱 Python 不是 C。
考慮到對 C 風格的這種偏見，一個有趣的問題（至少對我而言）是，我們能否改進這些基準測試，更好地使用 Python 及其工具？
在我給出答案之前，我想說我絕不會試圖貶低 Julia。在進一步開發和改進後，Julia 無疑是一種值得關注的語言。我只是想分析 Python
方面的事情。實際上，我正在以此為借口來探索各種可用於讓代碼更快運行的 Python 工具。
在下面的內容中，我使用 Docker 鏡像在 Jupyter Notebook 中使用 Python 3.4.3，其中已安裝了所有的 Python 科學工具組合。我還會通過
Windows 機器上的 Python 2.7.10，使用 Anaconda 來運行代碼。計時是對 Python 3.4.3 執行的。包含下面的所有基準測試的完整代碼的 Notebook 可在此處找到。
鑒於各種社交媒體上的評論，我添加了這樣一句話：我沒有在這里使用 Python 的替代性實現。我沒有編寫任何 C
代碼：如果您不信，可試試尋找分號。本文中使用的所有工具都是 Anaconda 或其他發行版中提供的標準的 Cython 實現。下面的所有代碼都在單個 Notebook中運行。
我嘗試過使用來自 github 的 Julia 微性能文件，但不能使用 Julia 0.4.2 原封不動地運行它。我必須編輯它並將 @timeit 替換為
@time，它才能運行。在對它們計時之前，我還必須添加對計時函數的調用，否則編譯時間也將包含在內。我使用的文件位於此處。我在用於運行 Python 的同一個機器上使用 Julia 命令行介面運行它。
回頁首
計時代碼
Julia 團隊使用的第一項基準測試是 Fibonacci 函數的一段簡單編碼。
def fib(n):
if n<2:
return n
return fib(n-1)+fib(n-2)

此函數的值隨 n 的增加而快速增加，例如：
fib(100) = 354224848179261915075

可以注意到，Python 任意精度 (arbitrary precision) 很方便。在 C 等語言中編寫相同的函數需要花一些編碼工作來避免整數溢出。在 Julia
中，需要使用 BigInt 類型。
所有 Julia 基準測試都與運行時間有關。這是 Julia 中使用和不使用 BigInt 的計時：
0.000080 seconds (149 allocations:10.167 KB)
0.012717 seconds (262.69 k allocations:4.342 MB)

在 Python Notebook 中獲得運行時間的一種方式是使用神奇的 %timeit。例如，在一個新單元中鍵入：
%timeit fib(20)

執行它會獲得輸出：
100 loops, best of 3:3.33 ms per loop

這意味著計時器執行了以下操作：
運行 fib(20) 100 次，存儲總運行時間
運行 fib(20) 100 次，存儲總運行時間
運行 fib(20) 100 次，存儲總運行時間
從 3 次運行中獲取最小的運行時間，將它除以 100，然後輸出結果，該結果就是 fib(20) 的最佳運行時間
這些循環的大小（100 次和 3 次）會由計時器自動調整。可能會根據被計時的代碼的運行速度來更改循環大小。
Python 計時與使用了 BigInt 時的 Julia 計時相比出色得多：3 毫秒與 12 毫秒。在使用任意精度時，Python 的速度是 Julia 的 4
倍。
但是，Python 比 Julia 默認的 64 位整數要慢。我們看看如何在 Python 中強制使用 64 位整數。
回頁首
使用 Cython 編譯
一種編譯方式是使用 Cython 編譯器。這個編譯器是使用 Python
編寫的。它可以通過以下命令安裝：
pip install Cython
如果使用 Anaconda，安裝會有所不同。因為安裝有點復雜，所以我編寫了一篇相關的博客文章：將 Cython For Anaconda 安裝在 Windows 上
安裝後，我們使用神奇的 %load_ext 將 Cython 載入到 Notebook 中：
%load_ext Cython

然後就可以在我們的 Notebook 中編譯代碼。我們只需要將想要編譯的代碼放在一個單元中，包括所需的導入語句，使用神奇的 %%cython 啟動該單元：
%%cython

def fib_cython(n):
if n<2:
return n
return fib_cython(n-1)+fib_cython(n-2)

執行該單元會無縫地編譯這段代碼。我們為該函數使用一個稍微不同的名稱，以反映出它是使用 Cython
編譯的。當然，一般不需要這么做。我們可以將之前的函數替換為相同名稱的已編譯函數。
對它計時會得到：
1000 loops, best of 3:1.22 ms per loop

哇，幾乎比最初的 Python 代碼快 3 倍！我們現在比使用 BigInt 的 Julia 快 100 倍。
我們還可以嘗試靜態類型。使用關鍵字 cpdef 而不是 def 來聲明該函數。它使我們能夠使用相應的 C 類型來鍵入函數的參數。我們的代碼變成了：
%%cython
cpdef long fib_cython_type(long n):
if n<2:
return n
return fib_cython_type(n-1)+fib_cython_type(n-2)

執行該單元後，對它計時會得到：
10000 loops, best of 3:36 µs per loop

太棒了，我們現在只花費了 36 微秒，比最初的基準測試快約 100 倍！這與 Julia 所花的 80 毫秒相比更出色。
有人可能會說，靜態類型違背了 Python
的用途。一般來講，我比較同意這種說法，我們稍後將查看一種在不犧牲性能的情況下避免這種情形的方法。但我並不認為這是一個問題。Fibonacci
函數必須使用整數來調用。我們在靜態類型中失去的是 Python 所提供的任意精度。對於 Fibonacci，使用 C 類型 long
會限制輸入參數的大小，因為太大的參數會導致整數溢出。
請注意，Julia 計算也是使用 64 位整數執行的，因此將我們的靜態類型版本與 Julia 的對比是公平的。
回頁首
緩存計算
我們在保留 Python 任意精度的情況下能做得更好。fib 函數重復執行同一種計算許多次。例如，fib(20) 將調用 fib(19) 和
fib(18)。fib(19) 將調用 fib(18) 和 fib(17)。結果 fib(18) 被調用了兩次。簡單分析表明，fib(17) 將被調用 3
次，fib(16) 將被調用 5 次，等等。
在 Python 3 中，我們可以使用 functools 標准庫來避免這些重復的計算。
from functools import lru_cache as cache
@cache(maxsize=None)
def fib_cache(n):
if n<2:
return n
return fib_cache(n-1)+fib_cache(n-2)

對此函數計時會得到：
1000000 loops, best of 3:910 ns per loop

速度又增加了 40 倍，比最初的 Python 代碼快約 3,600 倍！考慮到我們僅向遞歸函數添加了一條注釋，此結果非常令人難忘。
Python 2.7 中沒有提供這種自動緩存。我們需要顯式地轉換代碼，才能避免這種情況下的重復計算。
def fib_seq(n):
if n < 2:
return n
a,b = 1,0
for i in range(n-1):
a,b = a+b,a
return a

請注意，此代碼使用了 Python 同時分配兩個局部變數的能力。對它計時會得到：
1000000 loops, best of 3:1.77 µs per loop

我們又快了 20 倍！讓我們在使用和不使用靜態類型的情況下編譯我們的函數。請注意，我們使用了 cdef 關鍵字來鍵入局部變數。
%%cython
def fib_seq_cython(n):
if n < 2:
return n
a,b = 1,0
for i in range(n-1):
a,b = a+b,a
return a
cpdef long fib_seq_cython_type(long n):
if n < 2:
return n
cdef long a,b
a,b = 1,0
for i in range(n-1):
a,b = a+b,b
return a

我們可在一個單元中對兩個版本計時：
%timeit fib_seq_cython(20)
%timeit fib_seq_cython_type(20)

結果為：
1000000 loops, best of 3:953 ns per loop
10000000 loops, best of 3:51.9 ns per loop

靜態類型代碼現在花費的時間為 51.9 納秒，比最初的基準測試快約 60,000（六萬）倍。
如果我們想計算任意輸入的 Fibonacci 數，我們應堅持使用無類型版本，該版本的運行速度快 3,500 倍。還不錯，對吧？
回頁首
使用 Numba 編譯
讓我們使用另一個名為 Numba 的工具。它是針對部分 Python 版本的一個即時
(jit) 編譯器。它不是對所有 Python 版本都適用，但在適用的情況下，它會帶來奇跡。
安裝它可能很麻煩。推薦使用像 Anaconda 這樣的 Python 發行版或一個已安裝了 Numba 的 Docker 鏡像。完成安裝後，我們導入它的 jit 編譯器：
from numba import jit

它的使用非常簡單。我們僅需要向想要編譯的函數添加一點修飾。我們的代碼變成了：
@jit
def fib_seq_numba(n):
if n < 2:
return n
(a,b) = (1,0)
for i in range(n-1):
(a,b) = (a+b,a)
return a

對它計時會得到：
1000000 loops, best of 3:225 ns per loop

比無類型的 Cython 代碼更快，比最初的 Python 代碼快約 16,000 倍！
回頁首
使用 Numpy
我們現在來看看第二項基準測試。它是快速排序演算法的實現。Julia 團隊使用了以下 Python 代碼：
def qsort_kernel(a, lo, hi):
i = lo
j = hi
while i < hi:
pivot = a[(lo+hi) // 2]
while i <= j:
while a[i] < pivot:
i += 1
while a[j] > pivot:
j -= 1
if i <= j:
a[i], a[j] = a[j], a[i]
i += 1
j -= 1
if lo < j:
qsort_kernel(a, lo, j)
lo = i
j = hi
return a

我將他們的基準測試代碼包裝在一個函數中：
import random
def benchmark_qsort():
lst = [ random.random() for i in range(1,5000) ]
qsort_kernel(lst, 0, len(lst)-1)

對它計時會得到：
100 loops, best of 3:18.3 ms per loop

上述代碼與 C 代碼非常相似。Cython 應該能很好地處理它。除了使用 Cython 和靜態類型之外，讓我們使用 Numpy
數組代替列表。在數組大小較大時，比如數千個或更多元素，Numpy 數組確實比
Python 列表更快。
安裝 Numpy 可能會花一些時間，推薦使用 Anaconda 或一個已安裝了 Python 科學工具組合的 Docker 鏡像。
在使用 Cython 時，需要將 Numpy 導入到應用了 Cython 的單元中。在使用 C 類型時，還必須使用 cimport 將它作為 C 模塊導入。Numpy
數組使用一種表示數組元素類型和數組維數（一維、二維等）的特殊語法來聲明。
%%cython
import numpy as np
cimport numpy as np
cpdef np.ndarray[double, ndim=1] \
qsort_kernel_cython_numpy_type(np.ndarray[double, ndim=1] a, \
long lo, \
long hi):
cdef:
long i, j
double pivot
i = lo
j = hi
while i < hi:
pivot = a[(lo+hi) // 2]
while i <= j:
while a[i] < pivot:
i += 1
while a[j] > pivot:
j -= 1
if i <= j:
a[i], a[j] = a[j], a[i]
i += 1
j -= 1
if lo < j:
qsort_kernel_cython_numpy_type(a, lo, j)
lo = i
j = hi
return a
cpdef benchmark_qsort_numpy_cython():
lst = np.random.rand(5000)
qsort_kernel_cython_numpy_type(lst, 0, len(lst)-1)

對 benchmark_qsort_numpy_cython() 函數計時會得到：
1000 loops, best of 3:1.32 ms per loop

我們比最初的基準測試快了約 15 倍，但這仍然不是使用 Python 的最佳方法。最佳方法是使用 Numpy 內置的 sort()
函數。它的默認行為是使用快速排序演算法。對此代碼計時：
def benchmark_sort_numpy():
lst = np.random.rand(5000)
np.sort(lst)

會得到：
1000 loops, best of 3:350 µs per loop

我們現在比最初的基準測試快 52 倍！Julia 在該基準測試上花費了 419 微秒，因此編譯的 Python 快 20%。
我知道，一些讀者會說我不會進行同類比較。我不同意。請記住，我們現在的任務是使用主機語言以最佳的方式排序輸入數組。在這種情況下，最佳方法是使用一個內置的函數。
http://www.ibm.com/developerworks/cn/opensource/os-make-python-faster-julia/