深入了解 Python 字元串對象的實現

點擊

上方藍字

，快速關注我們）

編譯：伯樂在線 - 耶魯怕冷

http://python.jobbole.com/83732/

如有好文章投稿，請點擊 → 這裡了解詳情

相關閱讀：《深入 Python 列表的內部實現》《深入 Python 字典的內部實現》

本文介紹了 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

+=

m

return

-

1

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

下面來看看，對於字元串 「p」 和 「s」 的匹配，演算法具體是如何運行的。前三個步驟與上面類似，接著，字元 『d』 在字元串 「p」 並未找到，因此我們直接跳過等於「p」字元串長度的字元數，之後便迅速找到了一個匹配。

有關Python字元串對象完整的代碼實現， 去這裡看看（http://svn.python.org/projects/python/trunk/Objects/stringobject.c） 。

看完本文有收穫？請轉

發分享給更多人

關注「Python開發者」，提升Python技能

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！

本站內容充實豐富，博大精深，小編精選每日熱門資訊，隨時更新，點擊「搶先收到最新資訊」瀏覽吧！

請您繼續閱讀更多來自 Python 的精彩文章: