本文和大家分享的是 python 內(nèi)部管理字符串對象,以及字符串查找操作是如何實(shí)現(xiàn)的相關(guān)內(nèi)容,一起來看看吧,希望對大家學(xué)習(xí)python有所幫助。
PyStringObject 結(jié)構(gòu)體
Python 中的字符串對象在內(nèi)部對應(yīng)一個(gè)名叫 PyStringObject 的結(jié)構(gòu)體。“ob_shash” 對應(yīng)字符串經(jīng)計(jì)算過的 hash值, “ob_sval” 指向一段長度為 “ob_size” 的字符串,且該字符串以‘null’結(jié)尾(為了兼容C)。“ob_sval”的初始大小為1個(gè)字節(jié),且 ob_sval[0]=0(對應(yīng)空字符串)。若你還想知道“ob_size”被定義的位置,可以看一看 object.h 頭文件中 PyObject_VAR_HEAD 對應(yīng)部分。“ob_sstate” 用來指示某個(gè)字符串是否已經(jīng)存在于intern機(jī)制對應(yīng)的字典中,后面我們會(huì)再次提到這一點(diǎn)。
typedef struct {
PyObject_VAR_HEAD
long ob_shash;
int ob_sstate;
char ob_sval[1];
} PyStringObject;
字符串對象的創(chuàng)建
如下所示,當(dāng)將一個(gè)新的字符串賦給一個(gè)變量時(shí),發(fā)生了什么?
1>>> s1 = 'abc'
運(yùn)行以上代碼時(shí),內(nèi)部的 C 函數(shù) “PyString_FromString” 將被調(diào)用并生成類似下面的偽代碼:
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
每次用到新的字符串時(shí),都將分配一個(gè)字符串對象。
共享字符串對象
Python 有一個(gè)優(yōu)雅的特性,就是變量之間的短字符串是共享的,這一特性可以節(jié)省所需的內(nèi)存空間。短字符串就是那些長度為 0 個(gè)或者 1 個(gè)字節(jié)的字符串。而全局變量“interned” 對應(yīng)一個(gè)用于索引這些短字符串的字典。數(shù)組 “characters” 也可用于索引那些長度為 1 個(gè)字節(jié)的字符串,比如單個(gè)字母。后面我們將看到數(shù)組 “characters” 是如何被使用的。
static PyStringObject *characters[UCHAR_MAX + 1];
static PyObject *interned;
下面一起看看:當(dāng)你在 Python 腳本中將一個(gè)短字符串賦值給一個(gè)變量時(shí),背后發(fā)生了哪些事情。
static PyStringObject *characters[UCHAR_MAX + 1];
static PyObject *interned;
內(nèi)容為 ‘a(chǎn)’ 的字符串對象將被添加到 “interned” 字典中。字典中鍵(key)是一個(gè)指向該字符串對象的指針,而對應(yīng)的值 就是一個(gè)相同的指針。在數(shù)組 “characters” 中,這一新的字符串對象在偏移量為 97 的位置被引用,因?yàn)樽址?nbsp;‘a(chǎn)’ 的ASCII碼值便是 97。變量 “s2” 也指向了這一字符串對象。
而,當(dāng)另外一個(gè)變量也被相同的字符串 ‘a(chǎn)’ 賦值時(shí),又會(huì)如何呢?
1>>> s3 = 'a'
上述代碼執(zhí)行后,將返回之前已創(chuàng)建的內(nèi)容相同的字符串對象。因此,‘s1’ 和 ‘s3’ 兩個(gè)變量都將指向同一個(gè)字符串對象。 數(shù)組 “characters” 便是用于檢測字符串 ‘a(chǎn)’ 是否已經(jīng)存在,若存在,則返回指向該字符串對象的指針。
if (size == 1 && (op = characters[*str & UCHAR_MAX]) != NULL)
{
...
return (PyObject *)op;
}
下面我們新建一個(gè)內(nèi)容為 ‘c’ 的短字符串:
1>>> s4 = 'c'
那么,我們將得到如下結(jié)果:
我們還能發(fā)現(xiàn),當(dāng)按照下面 Python 腳本中的方式對一個(gè)字符串元素進(jìn)行訪問時(shí),數(shù)組 “characters” 仍有用武之地。
>>> s5 = 'abc'
>>> s5[0]
'a'
上面第二行代碼中,返回的是數(shù)組 “characters” 偏移量為 97 的位置內(nèi)的指針元素,而非新建一個(gè)值為 ‘a(chǎn)’的字符串。當(dāng)我們訪問某個(gè)字符串中的元素時(shí),一個(gè)名叫 “string_item” d的函數(shù)將被調(diào)用,下方給出了函數(shù)體代碼。其中,參數(shù) ‘a(chǎn)’ 便對應(yīng)著字符串 “abc”,而參數(shù) ‘i’ 便是訪問數(shù)組的索引值(本例中便為 0 ),函數(shù)返回的是指向某個(gè)字符串對象的指針。
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;
}
數(shù)組 “characters” 也可用于函數(shù)名長度為 1 時(shí)的情形,如下所示:
>>> def a(): pass
字符串查找
下面看看,當(dāng)你在如下 Python 代碼中進(jìn)行字符串查找操作時(shí),又會(huì)有那些事情發(fā)生呢?
>>> s = 'adcabcdbdabcabd'
>>> s.find('abcab')
>>> 11
函數(shù) “find” 返回一個(gè)索引值,說明是在字符串 “abcd” 的哪個(gè)位置找到字符串 “s” 的。若字符串未找到,函數(shù)返回值為 -1。
那么,內(nèi)部到底干了些啥事情?內(nèi)部調(diào)用了一個(gè)名為 “fastsearch” 的函數(shù)。這個(gè)函數(shù)是一個(gè)介于 BoyerMoore 和 Horspool 算法之間的混合版本,它兼具兩者的優(yōu)良特性。
我們將 “s”(s = ‘a(chǎn)dcabcdbdabcabd’)稱作主字符串,而將 “p”(p = ‘a(chǎn)bcab’)稱作模式串。n 和 m 分別表示字符串 s 和 字符串 p 的長度,其中,n = 15, m = 5。
在如下代碼段中,明顯看到,程序?qū)⑦M(jìn)行首次判定:若 m > n,我們就知道必然不能找到這樣的索引號(hào),因此函數(shù)直接返回 -1 即可。
w = n - m;
if (w < 0)
return -1;
當(dāng) m = 1 時(shí),程序便在字符串 s 中一個(gè)個(gè)字符地進(jìn)行遍歷,若匹配成功則返回對應(yīng)的索引位置。在本例中,變量 mode 值為 FAST_SEARCH,意味著我們想獲取的是在主字符串中首次匹配的位置,而非模式串在主字符串中成功匹配的次數(shù)。
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。首先創(chuàng)建一個(gè)壓縮的boyer-moore delta 1 table(對應(yīng)BM算法中的壞字符規(guī)則),在此過程中需要聲明兩個(gè)變量:“mask” 和 “skip”。
“mask” 是一個(gè) 32 位的位掩碼(bitmask),將其最低的 5 個(gè)特征位作為開關(guān)位。該掩碼是通過和模式串 “p” 進(jìn)行操作產(chǎn)生的。它設(shè)計(jì)成一個(gè)布隆過濾器(bloom filter),用于檢測一個(gè)字符是否出現(xiàn)在當(dāng)前字符串中。這種機(jī)制使查找操作十分迅速,但是存在偽正的情況(false positives)。關(guān)于布隆過濾器,你想有更多了解的話可以看看 這里 。對于本例,下方說明了位掩碼具體是如何產(chǎn)生的。
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” 的第一個(gè)字符為 ‘a(chǎn)’。字符‘a(chǎn)’的二進(jìn)制表示為 97 = 1100001。保留最低的 5 個(gè)特征位,我們得到了 00001,因此變 “mask” 初次被設(shè)定為 10(1 << 1)。當(dāng)整個(gè)字符串 “p” 都經(jīng)過處理后,mask 值為 1110。那么,我們應(yīng)該如何使用這個(gè)位掩碼呢?通過下方這行代碼,我們用其來檢測字符 “c” 位于字符串 “p” 哪個(gè)位置。
if ((mask & (1 << (c & 0x1F))))
那么,字符 ‘a(chǎn)’ 在字符串 “p”(‘a(chǎn)bcab’)中是否存在呢?1110 & (1 << (‘a(chǎn)’ & 0X1F)) 運(yùn)算結(jié)果的值是否為 true 呢?由于 1110 & (1 << (‘a(chǎn)’ & 0X1F)) = 1110 & 10 = 10,可知 ‘a(chǎn)’ 確實(shí)存在于 ‘a(chǎn)bcab’。當(dāng)檢測字符 ‘d’時(shí),我們得到的是 false,對于其他字符(從 ‘e’ 到 ‘z’)也是同樣結(jié)果。因此,在本例中此類過濾器表現(xiàn)十分出眾。 變量 “skip” 對應(yīng)目標(biāo)字符在主字符串中最后一個(gè)成功匹配的字符的索引位置(從后向前匹配)。假若模式串的最后一個(gè)匹配字符在主字符串中不存在,則 “skip” 值為 模式串 “p” 的長度減去 1。本例中,模式串最后一個(gè)為匹配字符位 ‘b’,由于其在主串查找的當(dāng)前位置向后跳兩個(gè)字符后能夠匹配到,因此變量 “skip” 的值為2。這個(gè)變量應(yīng)用于一種名叫壞字符跳躍(bad-character skip)的規(guī)則。在如下示例中,p = ‘a(chǎn)bcab’,s = ‘a(chǎn)dcabcaba’。從主串 “s” 的 4 號(hào)索引位置(從 0 開始計(jì)算)開始匹配,若字符匹配成功則向前繼續(xù)匹配。第一個(gè)匹配失敗的索引位置為 1(此處 ‘b’ 不等于 ‘d’)。我們可以看到,在模式串和主串最開始匹配的末端位置往后數(shù)三個(gè)字符,主串中也有一個(gè) ‘b’,而字符 ‘c’ 也存在于 “p” 中,因此我們跳過了隨后的‘b’。