最近寫了點rankboost相關的代碼，發現當weaklearner比較多且數據量巨大的時候，單純的利用python+sklearn+numpy來fit是非常慢的，就想到了之前用過的cython，寫完之後果然效率飛起啊。但是為什麼python如此之慢呢？我這個菜雞還是需要學習一下的。。。
Why python is slow?歸根結底，python是一種動態類型的解釋性語言，它的值並不是存儲在密集的buffer中，而是在分散的對象中。
python是動態類型的，而不是靜態的每次當程序執行時，解釋器並不清楚所定義的數據類型。python變量和C語言變量的不同可以用下圖來表示：
對於C語言來說，一個變量在定義時編譯器就知道它的數據類型。而對於一個python變量來說，你在程序運行時只知道它時一個python的object。
舉個例子，對於下面的c語言程序:
/* C code */
int a = 1;
int b = 2;
int c = a + b;此時，C編譯器知道
// C Addition
1. Assign <int> 1 to a
2. Assign <int> 2 to b
3. call binary_add<int, int>(a, b)
4. Assign the result to c同樣的，對於python來說:
# python code
a = 1
b = 2
c = a + b這裡，python解釋器僅僅知道1和2是兩個object，但是並不知道這兩個object是什麼類型的！ 為此，解釋器必須檢查每個object的PyObject_HEAD來確定他們的類型，然後調用適合這兩個object類型的加法routine。加法完成後，它還必須創建和初始化一個python obbject來保存返回值。整個過程粗略的表示為:
# Python Addition
1. Assign 1 to a
1). Set a->PyObject_HEAD->typecode to integer
2). Set a->val = 1
2. Assign 2 to b
1). Set b->PyObject_HEAD->typecode to integer
2). Set b->val = 2
3. call binary_add(a, b)
1) 3a. find typecode in a->PyObject_HEAD
2) a is an integer; value is a->val
3) find typecode in b->PyObject_HEAD
4) b is an integer; value is b->val
5) call binary_add<int, int>(a->val, b->val)
6) result of this is result, and is an integer.
4. Create a Python object c
1) set c->PyObject_HEAD->typecode to integer
2) set c->val to result動態類型意味著任何操作都涉及到更多的步驟。這是Python對數值數據的操作比C慢的主要原因。
Python is interpreted rather than compiled我們在上面看到了解釋代碼和編譯代碼之間的一個區別。智能的編譯器可以向前看，並針對重複或不需要的操作進行優化，從而加快速度。所以對於python，也有很多成熟和有效的package對齊進行優化，比如numpy,numba,cython等，後面有時間會單獨寫出來比較一下他們的速度關係，以及簡單介紹一點點用法。比如某大佬的這篇文章.
Python's object model can lead to inefficient memory access上面我們看到了C和Python再進行整數加法時他們之間的差別。現在假設你有非常非常多的整數，並希望對它們執行某種批處理操作。在python裡你會使用list object，而在C裡你會使用buffer-based 數列。
最簡單形式的NumPy數組是圍繞C數組構建的Python對象。也就是說，它有一個指向值的連續數據緩衝區的指針。
Python list 有一個指向一個連續的指針緩衝區的指針，每個指針指向一個Python對象，該對象又指向了它的數據：
很容易看出，如果您正在執行一些按順序遍歷數據的操作，numpy布局將比Python布局更高效，無論是存儲成本還是訪問成本。
So Why Use Python?動態類型使Python比C更容易上手。它非常靈活和寬容，這種靈活性可以有效地利用開發時間，在那些您真正需要優化C或Fortran的情況下，Python為編譯後的庫提供了簡單的hooks。這就是為什麼Python在許多科學界的使用一直在不斷增長。所有這些加在一起，Python最終成為一種非常高效的語言，可以完成用代碼進行科學研究的整個任務。
Python meta-hacking: Don't take my word for it下面所有的分析都是基於python3.4的!
Digging into Python Integerspython中很容易創建和使用整數：
x = 42
print(x)但是這個界面的簡單性掩蓋了幕後發生的事情的複雜性。 我們在上面簡要討論了Python整數的內存布局。在這裡，我們將使用Python的內置ctypes模塊從Python解釋器本身來看Python的integer類型。但是首先，我們需要確切地知道Python整數在C語言的API級別上是什麼樣子。
CPython中實際的x變量存儲在CPython原始碼中定義的結構中，https://hg.python.org/cpython/file/3.4/Include/longintrepr.h/#l89
struct _longobject {
PyObject_VAR_HEAD
digit ob_digit[1];
};PyObject_VAR_HEAD是一個宏，它用以下結構啟動對象,Include/object.h
typedef struct {
PyObject ob_base;
Py_ssize_t ob_size; /* Number of items in variable part */
} PyVarObject;還包括一個PyObject，Include/object.h
typedef struct _object {
_PyObject_HEAD_EXTRA
Py_ssize_t ob_refcnt;
struct _typeobject *ob_type;
} PyObject;這裡的_PyObject_HEAD_EXTRA是一個通常在Python構建中不使用的宏。將所有這些放在一起，integer對象的結構如下：
struct _longobject {
long ob_refcnt;
PyTypeObject *ob_type;
size_t ob_size;
long ob_digit[1];
};ob_refcnt變量是對象的引用計數，ob_type變量是指向包含對象所有類型信息和方法定義的結構的指針，ob_digit保存實際的數值。
有了這些知識，我們將使用ctypes模塊開始研究實際的對象結構並提取上面的一些信息。
我們從定義C結構的Python表示開始：
import ctypes
class IntStruct(ctypes.Structure):
_fields_ = [("ob_refcnt", ctypes.c_long),
("ob_type", ctypes.c_void_p),
("ob_size", ctypes.c_ulong),
("ob_digit", ctypes.c_long)]
def __repr__(self):
return ("IntStruct(ob_digit={self.ob_digit}, "
"refcount={self.ob_refcnt})").format(self=self)現在讓我們看看某個數的內部表示，比如42。在CPython中，id函數提供對象的內存位置：
num = 42
IntStruct.from_address(id(42))
# Output:
# IntStruct(ob_digit=42, refcount=35)ob_digit屬性指向內存中的正確位置！
回顧一下「ob_refcnt變量是對象的引用計數」，但是為什麼這裡refcount比1大這麼多???
事實證明Python經常使用小整數。如果為每個整數創建一個新的PyObject，則需要大量內存。因此，Python將公共整數值實現為"singletons"：也就是說，內存中只存在這些數字的一個副本。換句話說，每次在這個範圍內創建一個新的Python整數，您只需創建一個對具有該值的singleton的引用：
x = 42
y = 42
id(x) == id(y)
# Output: True這兩個變量只是指向同一內存地址的指針。當你得到更大的整數（在Python 3.4中大於255）時，情況就不再是這樣了：
x = 1234
y = 1234
id(x) == id(y)
# Output: False只需啟動Python解釋器就可以創建許多整數對象；看看每個對象有多少個引用是很有趣的：
%matplotlib inline
import matplotlib.pyplot as plt
import sys
plt.loglog(range(1000), [sys.getrefcount(i) for i in range(1000)])
plt.xlabel('integer value')
plt.ylabel('reference count')從上圖可以看出，0被引用了很多次，而且隨著數的不斷增大，引用次數開始下降。
為了進一步確保它的行為符合我們的預期，讓我們確保ob_digit欄位包含正確的值：
all(i == IntStruct.from_address(id(i)).ob_digit
for i in range(256))
# Output: True如果你再深入一點，你可能會注意到，對於大於256的數字來說，這並不成立：事實證明，一些位移位操作是在Objects/longobject.c中執行的，這些操作改變了大整數在內存中的表示方式。
我不能說我完全理解為什麼會發生這種情況，但我想這與Python高效處理超過long int數據類型溢出限制的整數的能力有關，我們可以在這裡看到：
2 ** 100
# Output: 1267650600228229401496703205376這個數字太長了，已經超過了long，它只能保存64位的值（即最多∼
Digging into Python Lists讓我們將上述思想應用到更複雜的類型：Python列表。與整數類似，我們在Include/listobject.h中找到了列表對象本身的定義:
typedef struct {
PyObject_VAR_HEAD
PyObject **ob_item;
Py_ssize_t allocated;
} PyListObject;同樣，我們可以展開宏並對類型進行模糊處理，以確保結構有效地變為：
typedef struct {
long ob_refcnt;
PyTypeObject *ob_type;
Py_ssize_t ob_size;
PyObject **ob_item;
long allocated;
} PyListObject;這裡PyObject **ob_item是指向列表的內容，ob_size的值告訴我們在這個list中有多少item。
class ListStruct(ctypes.Structure):
_fields_ = [("ob_refcnt", ctypes.c_long),
("ob_type", ctypes.c_void_p),
("ob_size", ctypes.c_ulong),
("ob_item", ctypes.c_long), # PyObject** pointer cast to long
("allocated", ctypes.c_ulong)]
def __repr__(self):
return ("ListStruct(len={self.ob_size}, "
"refcount={self.ob_refcnt})").format(self=self)L = [1,2,3,4,5]
ListStruct.from_address(id(L))
# Output:
# ListStruct(len=5, refcount=1)為了確保操作正確，讓我們創建一些對列表的額外引用，看看它如何影響引用計數：
tup = [L, L] # two more references to L
ListStruct.from_address(id(L))
# Output:
ListStruct(len=5, refcount=3)現在讓我們看看如何在列表中查找實際的元素。正如我們在上面看到的，元素是通過一個連續的PyObject指針數組存儲的。使用ctypes，我們實際上可以創建一個由以前的IntStruct對象組成的複合結構：
# get a raw pointer to our list
Lstruct = ListStruct.from_address(id(L))
# create a type which is an array of integer pointers the same length as L
PtrArray = Lstruct.ob_size * ctypes.POINTER(IntStruct)
# instantiate this type using the ob_item pointer
L_values = PtrArray.from_address(Lstruct.ob_item)現在讓我們看一下每個item中的值：
[ptr[0] for ptr in L_values] # ptr[0] dereferences the pointer
'''
Output:
[IntStruct(ob_digit=1, refcount=5296),
IntStruct(ob_digit=2, refcount=2887),
IntStruct(ob_digit=3, refcount=932),
IntStruct(ob_digit=4, refcount=1049),
IntStruct(ob_digit=5, refcount=808)]
'''我們已經恢復了列表中的PyObject整數！您可能希望花點時間回顧一下上面的列表內存布局的示意圖，並確保您了解這些ctypes操作是如何映射到該圖表上的。
Digging into NumPy arrays現在，為了進行比較，讓我們對numpy數組進行類似的操作。這裡將跳過對NumPy C-API數組定義的詳細介紹；如果您想了解它，可以在NumPy/core/include/NumPy/ndarraytypes.h中找到它。
請注意，我在這裡使用的是NumPy版本1.8；這些內部結構可能在版本之間發生了變化。先來創建一個numpy array結構：
class NumpyStruct(ctypes.Structure):
_fields_ = [("ob_refcnt", ctypes.c_long),
("ob_type", ctypes.c_void_p),
("ob_data", ctypes.c_long), # char* pointer cast to long
("ob_ndim", ctypes.c_int),
("ob_shape", ctypes.c_voidp),
("ob_strides", ctypes.c_voidp)]
@property
def shape(self):
return tuple((self.ob_ndim * ctypes.c_int64).from_address(self.ob_shape))
@property
def strides(self):
return tuple((self.ob_ndim * ctypes.c_int64).from_address(self.ob_strides))
def __repr__(self):
return ("NumpyStruct(shape={self.shape}, "
"refcount={self.ob_refcnt})").format(self=self)x = np.random.random((10, 20))
xstruct = NumpyStruct.from_address(id(x))
xstruct
# Output:
NumpyStruct(shape=(10, 20), refcount=1)我們發現我們已經提取了正確的形狀信息。讓我們確保引用計數正確：
L = [x,x,x] # add three more references to x
xstruct
# Output:
NumpyStruct(shape=(10, 20), refcount=4)現在我們可以完成提取數據緩衝區這一棘手的部分。為了簡單起見，我們將忽略strides並假設它是一個C-連續數組；這可以通過一些工作來實現。
x = np.arange(10)
xstruct = NumpyStruct.from_address(id(x))
size = np.prod(xstruct.shape)
# assume an array of integers
arraytype = size * ctypes.c_long
data = arraytype.from_address(xstruct.ob_data)
[d for d in data]
# Output: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]數據變量現在是NumPy數組中定義的連續內存塊的視圖！為了顯示這一點，我們將更改數組中的一個值:
x[4] = 555
[d for d in data]
# Output: [0, 1, 2, 3, 555, 5, 6, 7, 8, 9]並觀察數據視圖也發生了變化。x和data都指向同一個連續內存塊。比較Python list和NumPy ndarray的內部結構，很明顯NumPy的數組對於表示同類型數據的列表要簡單得多。這個事實與編譯器處理效率更高的因素有關。
致謝本文整體算是對此文的翻譯和學習，非常感謝作者的高質量文章！翻譯水平有限，看英文的更香。。。