Python中怎么實(shí)現(xiàn)一個字符串對象

這期內(nèi)容當(dāng)中小編將會給大家?guī)碛嘘P(guān)Python中怎么實(shí)現(xiàn)一個字符串對象，文章內(nèi)容豐富且以專業(yè)的角度為大家分析和敘述，閱讀完這篇文章希望大家可以有所收獲。

PyStringObject 結(jié)構(gòu)體

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

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

字符串對象的創(chuàng)建

如下所示，當(dāng)將一個新的字符串賦給一個變量時，發(fā)生了什么?

1>>> s1 = 'abc'

運(yùn)行以上代碼時，內(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

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

共享字符串對象

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

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

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

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

內(nèi)容為 ‘a’ 的字符串對象將被添加到 “interned” 字典中。字典中鍵(key)是一個指向該字符串對象的指針，而對應(yīng)的值  就是一個相同的指針。在數(shù)組 “characters” 中，這一新的字符串對象在偏移量為 97 的位置被引用，因?yàn)樽址?‘a’ 的ASCII碼值便是 97。變量  “s2” 也指向了這一字符串對象。

而，當(dāng)另外一個變量也被相同的字符串 ‘a’ 賦值時，又會如何呢?

1>>> s3 = 'a'

上述代碼執(zhí)行后，將返回之前已創(chuàng)建的內(nèi)容相同的字符串對象。因此，‘s1’ 和 ‘s3’ 兩個變量都將指向同一個字符串對象。 數(shù)組 “characters”  便是用于檢測字符串 ‘a’ 是否已經(jīng)存在，若存在，則返回指向該字符串對象的指針。

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

下面我們新建一個內(nèi)容為 ‘c’ 的短字符串：

1>>> s4 = 'c'

那么，我們將得到如下結(jié)果：

我們還能發(fā)現(xiàn)，當(dāng)按照下面 Python 腳本中的方式對一個字符串元素進(jìn)行訪問時，數(shù)組 “characters” 仍有用武之地。

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

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

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 時的情形，如下所示：

>>> def a(): pass

字符串查找

下面看看，當(dāng)你在如下 Python 代碼中進(jìn)行字符串查找操作時，又會有那些事情發(fā)生呢?

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

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

那么，內(nèi)部到底干了些啥事情?內(nèi)部調(diào)用了一個名為 “fastsearch” 的函數(shù)。這個函數(shù)是一個介于 BoyerMoore 和 Horspool  算法之間的混合版本，它兼具兩者的優(yōu)良特性。

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

在如下代碼段中，明顯看到，程序?qū)⑦M(jìn)行***判定：若 m > n,我們就知道必然不能找到這樣的索引號，因此函數(shù)直接返回 -1 即可。

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

當(dāng) m = 1 時，程序便在字符串 s 中一個個字符地進(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)建一個壓縮的boyer-moore delta 1  table(對應(yīng)BM算法中的壞字符規(guī)則),在此過程中需要聲明兩個變量：“mask” 和 “skip”。

“mask” 是一個 32 位的位掩碼(bitmask)，將其***的 5 個特征位作為開關(guān)位。該掩碼是通過和模式串 “p”  進(jìn)行操作產(chǎn)生的。它設(shè)計成一個布隆過濾器(bloom  filter)，用于檢測一個字符是否出現(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” 的***個字符為 &lsquo;a&rsquo;。字符&lsquo;a&rsquo;的二進(jìn)制表示為 97 = 1100001。保留***的 5 個特征位，我們得到了 00001，因此變  “mask” 初次被設(shè)定為 10(1 << 1)。當(dāng)整個字符串 “p” 都經(jīng)過處理后，mask 值為  1110。那么，我們應(yīng)該如何使用這個位掩碼呢?通過下方這行代碼，我們用其來檢測字符 “c” 位于字符串 “p” 哪個位置。

if ((mask & (1 << (c & 0x1F))))

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

下面，看下查找操作的循環(huán)部分(真實(shí)代碼為 C 實(shí)現(xiàn)，而非 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” 這行測試代碼是基于位掩碼實(shí)現(xiàn)的，“i += skip” 便對應(yīng)壞字符跳躍。當(dāng)主串下一個待匹配的字符在 “p”  中并未找到時，則執(zhí)行 “i += m” 這行代碼。

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

上述就是小編為大家分享的Python中怎么實(shí)現(xiàn)一個字符串對象了，如果剛好有類似的疑惑，不妨參照上述分析進(jìn)行理解。如果想知道更多相關(guān)知識，歡迎關(guān)注億速云行業(yè)資訊頻道。