詳解Python字符串對象的實現

PyStringObject 結構體

Python 中的字符串對象在內部對應一個名叫 PyStringObject 的結構體。“ob_shash” 對應字符串經計算過的 hash值， “ob_sval” 指向一段長度為 “ob_size” 的字符串，且該字符串以‘null'結尾（為了兼容C）。“ob_sval”的初始大小為1個字節，且 ob_sval[0]=0（對應空字符串）。若你還想知道“ob_size”被定義的位置，可以看一看 object.h 頭文件中 PyObject_VAR_HEAD 對應部分。“ob_sstate” 用來指示某個字符串是否已經存在于intern機制對應的字典中，后面我們會再次提到這一點。

typedef struct {  PyObject_VAR_HEAD  long ob_shash;  int ob_sstate;  char ob_sval[1];} PyStringObject;

字符串對象的創建

如下所示，當將一個新的字符串賦給一個變量時，發生了什么？

1>>> s1 = 'abc'
運行以上代碼時，內部的 C 函數 “PyString_FromString” 將被調用并生成類似下面的偽代碼：

arguments: string object: 'abc'returns: Python string object with ob_sval = 'abc'PyString_FromString(string):  size = length of string  allocate string object + size for 'abc'. ob_sval will be of size: size + 1  copy string to ob_sval  return object

每次用到新的字符串時，都將分配一個字符串對象。

共享字符串對象

Python 有一個優雅的特性，就是變量之間的短字符串是共享的，這一特性可以節省所需的內存空間。短字符串就是那些長度為 0 個或者 1 個字節的字符串。而全局變量 “interned” 對應一個用于索引這些短字符串的字典。數組 “characters” 也可用于索引那些長度為 1 個字節的字符串，比如單個字母。后面我們將看到數組 “characters” 是如何被使用的。

static PyStringObject *characters[UCHAR_MAX + 1];static PyObject *interned;

下面一起看看：當你在 Python 腳本中將一個短字符串賦值給一個變量時，背后發生了哪些事情。

static PyStringObject *characters[UCHAR_MAX + 1];static PyObject *interned;

內容為 ‘a' 的字符串對象將被添加到 “interned” 字典中。字典中鍵（key）是一個指向該字符串對象的指針，而對應的值就是一個相同的指針。在數組 “characters” 中，這一新的字符串對象在偏移量為 97 的位置被引用，因為字符 ‘a' 的ASCII碼值便是 97。變量 “s2” 也指向了這一字符串對象。

而，當另外一個變量也被相同的字符串 ‘a' 賦值時，又會如何呢？

1>>> s3 = 'a'
上述代碼執行后，將返回之前已創建的內容相同的字符串對象。因此，‘s1' 和 ‘s3' 兩個變量都將指向同一個字符串對象。數組 “characters” 便是用于檢測字符串 ‘a' 是否已經存在，若存在，則返回指向該字符串對象的指針。

if (size == 1 && (op = characters[*str & UCHAR_MAX]) != NULL){  ...  return (PyObject *)op;}

下面我們新建一個內容為 ‘c' 的短字符串：

1>>> s4 = 'c'
那么，我們將得到如下結果：

我們還能發現，當按照下面 Python 腳本中的方式對一個字符串元素進行訪問時，數組 “characters” 仍有用武之地。

>>> s5 = 'abc'>>> s5[0]'a'

上面第二行代碼中，返回的是數組 “characters” 偏移量為 97 的位置內的指針元素，而非新建一個值為 ‘a'的字符串。當我們訪問某個字符串中的元素時，一個名叫 “string_item” d的函數將被調用，下方給出了函數體代碼。其中，參數 ‘a' 便對應著字符串 “abc”，而參數 ‘i' 便是訪問數組的索引值（本例中便為 0 ），函數返回的是指向某個字符串對象的指針。

static PyObject *string_item(PyStringObject *a, register Py_ssize_t i){  char pchar;  PyObject *v;  ...  pchar = a->ob_sval[i];  v = (PyObject *)characters[pchar & UCHAR_MAX];  if (v == NULL)    // allocate string  else {    ...    Py_INCREF(v);  }  return v;}

數組 “characters” 也可用于函數名長度為 1 時的情形，如下所示：

>>> def a(): pass
字符串查找

下面看看，當你在如下 Python 代碼中進行字符串查找操作時，又會有那些事情發生呢？

>>> s = 'adcabcdbdabcabd'>>> s.find('abcab')>>> 11

函數 “find” 返回一個索引值，說明是在字符串 “abcd” 的哪個位置找到字符串 “s” 的。若字符串未找到，函數返回值為 -1。

那么，內部到底干了些啥事情？內部調用了一個名為 “fastsearch” 的函數。這個函數是一個介于 BoyerMoore 和 Horspool 算法之間的混合版本，它兼具兩者的優良特性。

我們將 “s”（s = ‘adcabcdbdabcabd'）稱作主字符串，而將 “p”（p = ‘abcab'）稱作模式串。n 和 m 分別表示字符串 s 和字符串 p 的長度，其中，n = 15, m = 5。

在如下代碼段中，明顯看到，程序將進行首次判定：若 m > n,我們就知道必然不能找到這樣的索引號，因此函數直接返回 -1 即可。

w = n - m;if (w < 0)  return -1;

當 m = 1 時，程序便在字符串 s 中一個個字符地進行遍歷，若匹配成功則返回對應的索引位置。在本例中，變量 mode 值為 FAST_SEARCH，意味著我們想獲取的是在主字符串中首次匹配的位置，而非模式串在主字符串中成功匹配的次數。

if (m <= 1) {  ...  if (mode == FAST_COUNT) {    ...  } else {    for (i = 0; i < n; i++)      if (s[i] == p[0])        return i;  }  return -1;}

考慮其他情況，比如 m > 1。首先創建一個壓縮的boyer-moore delta 1 table（對應BM算法中的壞字符規則）,在此過程中需要聲明兩個變量：“mask” 和 “skip”。

“mask” 是一個 32 位的位掩碼（bitmask），將其最低的 5 個特征位作為開關位。該掩碼是通過和模式串 “p” 進行操作產生的。它設計成一個布隆過濾器（bloom filter），用于檢測一個字符是否出現在當前字符串中。這種機制使查找操作十分迅速，但是存在偽正的情況（false positives）。關于布隆過濾器，你想有更多了解的話可以看看這里。對于本例，下方說明了位掩碼具體是如何產生的。

mlast = m - 1/* process pattern[:-1] */for (mask = i = 0; i < mlast; i++) {  mask |= (1 << (p[i] & 0x1F));}/* process pattern[-1] outside the loop */mask |= (1 << (p[mlast] & 0x1F));

字符串 “p” 的第一個字符為 ‘a'。字符‘a'的二進制表示為 97 = 1100001。保留最低的 5 個特征位，我們得到了 00001，因此變 “mask” 初次被設定為 10（1 << 1）。當整個字符串 “p” 都經過處理后，mask 值為 1110。那么，我們應該如何使用這個位掩碼呢？通過下方這行代碼，我們用其來檢測字符 “c” 位于字符串 “p” 哪個位置。

if ((mask & (1 << (c & 0x1F))))
那么，字符 ‘a' 在字符串 “p”（‘abcab'）中是否存在呢？1110 & (1 << (‘a' & 0X1F)) 運算結果的值是否為 true 呢？由于 1110 & (1 << (‘a' & 0X1F)) = 1110 & 10 = 10，可知 ‘a' 確實存在于 ‘abcab'。當檢測字符 ‘d'時，我們得到的是 false，對于其他字符（從 ‘e' 到 ‘z'）也是同樣結果。因此，在本例中此類過濾器表現十分出眾。變量 “skip” 對應目標字符在主字符串中最后一個成功匹配的字符的索引位置（從后向前匹配）。假若模式串的最后一個匹配字符在主字符串中不存在，則 “skip” 值為模式串 “p” 的長度減去 1。本例中，模式串最后一個為匹配字符位 ‘b',由于其在主串查找的當前位置向后跳兩個字符后能夠匹配到，因此變量 “skip” 的值為2。這個變量應用于一種名叫壞字符跳躍（bad-character skip）的規則。在如下示例中，p = ‘abcab'，s = ‘adcabcaba'。從主串 “s” 的 4 號索引位置（從 0 開始計算）開始匹配，若字符匹配成功則向前繼續匹配。第一個匹配失敗的索引位置為 1（此處 ‘b' 不等于 ‘d'）。我們可以看到，在模式串和主串最開始匹配的末端位置往后數三個字符，主串中也有一個 ‘b',而字符 ‘c' 也存在于 “p” 中，因此我們跳過了隨后的 ‘b'。

下面，看下查找操作的循環部分（真實代碼為 C 實現，而非 Python）：

for i = 0 to n - m = 13:  if s[i+m-1] == p[m-1]:    if s[i:i+mlast] == p[0:mlast]:      return i    if s[i+m] not in p:      i += m    else:      i += skip  else:    if s[i+m] not in p:      i += mreturn -1

“s[i+m] not in p” 這行測試代碼是基于位掩碼實現的，“i += skip” 便對應壞字符跳躍。當主串下一個待匹配的字符在 “p” 中并未找到時，則執行 “i += m” 這行代碼。

下面來看看，對于字符串 “p” 和 “s” 的匹配，算法具體是如何運行的。前三個步驟與上面類似，接著，字符 ‘d' 在字符串 “p” 并未找到，因此我們直接跳過等于“p”字符串長度的字符數，之后便迅速找到了一個匹配。

以上就是帶領大家深入了解Python字符串對象實現的整個學習過程，希望對大家學習Python程序設計有所幫助。