搜尋
首頁後端開發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

if ((mask & (1 那么,字符 ‘a' 在字符串 “p”(‘abcab')中是否存在呢?1110 & (1


下面,看下查找操作的循环部分(真实代码为 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字符串对象实现的整个学习过程,希望对大家学习Python程序设计有所帮助。

陳述
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
Python vs.C:申請和用例Python vs.C:申請和用例Apr 12, 2025 am 12:01 AM

Python适合数据科学、Web开发和自动化任务,而C 适用于系统编程、游戏开发和嵌入式系统。Python以简洁和强大的生态系统著称,C 则以高性能和底层控制能力闻名。

2小時的Python計劃:一種現實的方法2小時的Python計劃:一種現實的方法Apr 11, 2025 am 12:04 AM

2小時內可以學會Python的基本編程概念和技能。 1.學習變量和數據類型,2.掌握控制流(條件語句和循環),3.理解函數的定義和使用,4.通過簡單示例和代碼片段快速上手Python編程。

Python:探索其主要應用程序Python:探索其主要應用程序Apr 10, 2025 am 09:41 AM

Python在web開發、數據科學、機器學習、自動化和腳本編寫等領域有廣泛應用。 1)在web開發中,Django和Flask框架簡化了開發過程。 2)數據科學和機器學習領域,NumPy、Pandas、Scikit-learn和TensorFlow庫提供了強大支持。 3)自動化和腳本編寫方面,Python適用於自動化測試和系統管理等任務。

您可以在2小時內學到多少python?您可以在2小時內學到多少python?Apr 09, 2025 pm 04:33 PM

兩小時內可以學到Python的基礎知識。 1.學習變量和數據類型,2.掌握控制結構如if語句和循環,3.了解函數的定義和使用。這些將幫助你開始編寫簡單的Python程序。

如何在10小時內通過項目和問題驅動的方式教計算機小白編程基礎?如何在10小時內通過項目和問題驅動的方式教計算機小白編程基礎?Apr 02, 2025 am 07:18 AM

如何在10小時內教計算機小白編程基礎?如果你只有10個小時來教計算機小白一些編程知識,你會選擇教些什麼�...

如何在使用 Fiddler Everywhere 進行中間人讀取時避免被瀏覽器檢測到?如何在使用 Fiddler Everywhere 進行中間人讀取時避免被瀏覽器檢測到?Apr 02, 2025 am 07:15 AM

使用FiddlerEverywhere進行中間人讀取時如何避免被檢測到當你使用FiddlerEverywhere...

Python 3.6加載Pickle文件報錯"__builtin__"模塊未找到怎麼辦?Python 3.6加載Pickle文件報錯"__builtin__"模塊未找到怎麼辦?Apr 02, 2025 am 07:12 AM

Python3.6環境下加載Pickle文件報錯:ModuleNotFoundError:Nomodulenamed...

如何提高jieba分詞在景區評論分析中的準確性?如何提高jieba分詞在景區評論分析中的準確性?Apr 02, 2025 am 07:09 AM

如何解決jieba分詞在景區評論分析中的問題?當我們在進行景區評論分析時,往往會使用jieba分詞工具來處理文�...

See all articles

熱AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover

AI Clothes Remover

用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

AI Hentai Generator

AI Hentai Generator

免費產生 AI 無盡。

熱門文章

R.E.P.O.能量晶體解釋及其做什麼(黃色晶體)
3 週前By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.最佳圖形設置
3 週前By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.如果您聽不到任何人,如何修復音頻
3 週前By尊渡假赌尊渡假赌尊渡假赌
WWE 2K25:如何解鎖Myrise中的所有內容
3 週前By尊渡假赌尊渡假赌尊渡假赌

熱工具

SecLists

SecLists

SecLists是最終安全測試人員的伙伴。它是一個包含各種類型清單的集合,這些清單在安全評估過程中經常使用,而且都在一個地方。 SecLists透過方便地提供安全測試人員可能需要的所有列表,幫助提高安全測試的效率和生產力。清單類型包括使用者名稱、密碼、URL、模糊測試有效載荷、敏感資料模式、Web shell等等。測試人員只需將此儲存庫拉到新的測試機上,他就可以存取所需的每種類型的清單。

SublimeText3 Mac版

SublimeText3 Mac版

神級程式碼編輯軟體(SublimeText3)

EditPlus 中文破解版

EditPlus 中文破解版

體積小,語法高亮,不支援程式碼提示功能

記事本++7.3.1

記事本++7.3.1

好用且免費的程式碼編輯器

VSCode Windows 64位元 下載

VSCode Windows 64位元 下載

微軟推出的免費、功能強大的一款IDE編輯器