pythonstring实现原理

Z时代
2024-01-10
分类：综合

python string 实现原理

这篇文章讲述python内部如何管理string 字符串对象，并且如何实现字符串对象的搜索

PyStringObject 结构

Python中的字符串对象在内部由结构PyStringObject表示。

ob_shash是字符串的哈希，ob_sval包含字符串的长度ob_size，该字符串以null终止。 ob_sval的初始大小为1个字节，并且ob_sval [0] =0。如果您想知道“ ob_size的定义位置”，请查看源码object.h中的PyObject_VAR_HEAD。 ob_sstate指示字符串对象是否在待查字典中，我们将在后面讲到

typedefstruct {
PyObject_VAR_HEAD
longob_shash;
intob_sstate;
    charob_sval[1];
} PyStringObject;

创建string 字符串对象

将新字符串分配给像这样的变量时会发生什么？

>>>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 ofsize:size + 1
    copy string to ob_sval
    return object

每次使用新字符串时，都会分配一个新的字符串对象。

共享string 字符串对象

通过一个简单优化的特性让变量之间共享小字符串。这减少了使用的内存量。小字符串是大小为0或1个字节的字符串。全局变量“ interned”是引用这些小字符串的字典。数组characters还用于引用长度为1个字节的字符串，即：单个字符。稍后我们将看到如何使用数组characters

staticPyStringObject*characters[UCHAR_MAX+1];
staticPyObject*interned;

让我们看看将新的小字符串分配给Python脚本中的变量后会发生什么。

>>> s2 = "a"

包含a的字符串对象将添加到内部字典中。键是指向字符串对象的指针，值是相同的指针。数组字符中的偏移量97也引用了这个新的字符串对象，因为ASCII中a的值为97。变量s2指向该字符串对象。

将不同的变量分配给相同的字符串“ a”会怎样？

>>> s3 = "a"

返回先前创建的相同字符串对象，因此两个变量都指向相同的字符串对象。在该过程中，将使用characters数组检查字符串是否已存在并将指针返回到字符串对象。

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

让我们创建一个包含字符“ c”的新小字符串。

>>> s4 = "c"

我们最终得到以下结果：

如以下Python脚本中所示，当请求字符串的项目时，我们还会发现使用“字符”数组：

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

而不是创建包含“ a”的新字符串，而是返回“字符”数组偏移量97处的指针。这是函数string_item的代码，当我们从字符串中请求字符时会调用该代码。参数"a"是包含"abc"的字符串对象，参数i是所请求的索引：在本例中为0。返回指向字符串对象的指针。

staticPyObject*
string_item(PyStringObject*a, registerPy_ssize_ti)
{
    charpchar;
    PyObject*v;
    ...
    pchar=a->ob_sval[i];
    v= (PyObject*)characters[pchar&UCHAR_MAX];
    if (v==NULL)
        // allocate string
    else {
        ...
        Py_INCREF(v);
    }
    returnv;
}

“characters”数组还用于长度为1的函数名称：

>>> def a(): pass

字符串查找

让我们看一下执行字符串搜索（如以下Python代码）时会发生什么：

>>>s = "adcabcdbdabcabd"
>>>s.find("abcab")
>>>9

find函数返回在字符串s中找到字符串"abcd"的索引。如果找不到该字符串，则返回-1。那么，内部发生了什么？调用fastsearch方法。它是Boyer-Moore和Horspool算法之间的完美结合，另外还有一些巧妙的技巧。我们将搜索字符串称为s，将搜索字符串称为p。 s = "adcabcdbdabcabd" 和 p ="abcab"。n是s的长度，m是p的长度。 n = 18并且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])
                    returni;
        }
    return-1;
}

对于其他情况，即m>1。第一步是创建一个压缩的 boyer-moore 增量1表。在该步骤中将分配两个变量：mask和skip。 mask是一个32位的位掩码，使用字符的5个最低有效位作为关键字。它是使用字符串搜索p生成的。这是一个布隆筛选器，用于测试此字符串中是否存在字符。这确实非常快，但是有误报。您可以在此处阅读更多有关布隆过滤器的信息。在我们的情况下，这就是位掩码的生成方式：

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设置为：1 << 1 =10。处理完整个字符串p后，mask = 1110。我们如何使用此位掩码？通过使用以下测试，其中“c”是要在字符串p中查找的字符。

if（（mask＆（1 <<（c＆0x1F）））） ，当 p ="abcab" ，是否p中的"a"？ 1110＆（1 <<（"a"＆0X1F））是true吗？ 1110＆（1 <<（"a"＆0X1F））= 1110＆10 =10。因此，确认"a"在"abcab"中。

如果我们用"d"进行测试，则会得到false以及从"e"到"z"的字符，因此此过滤器在我们的情况下效果很好。 “ skip”设置为与要搜索的字符串中的最后一个字符具有相同值的字符索引。如果未找到最后一个字符，则将“ skip”设置为“ p”的长度-1。要搜索的字符串中的最后一个字符为"b"，这意味着“跳过”将设置为2，因为也可以通过向下跳过2个字符来找到该字符。此变量用在称为坏字符跳过方法的跳过方法中。

以下示例中：p ="abcab"和s ="adcabcaba"。搜索从“ s”的索引4开始，并向后检查是否有字符串匹配。第一次测试在索引= 1失败，其中“ b”与“ d”不同。我们知道，“ p”中的字符“ b”也从末尾开始向下3个字符。因为“ c”是“ p”的一部分，所以我们跳到下面的“ b”。这是错误字符跳过。

接下来是搜索循环本身（实际代码是C而不是Python）：

fori=0ton-m=13:
    ifs[i+m-1] ==p[m-1]:
        ifs[i:i+mlast] ==p[0:mlast]:
            returni
        ifs[i+m] notinp:
            i+=m
        else:
            i+=skip
    else:
        ifs[i+m] notinp:
            i+=m
return-1

测试s [i + m]不在p中使用位掩码完成。i + =跳过是错误字符跳过。当在p中找不到下一个字符时，将执行i + = m。让我们看看这种搜索算法如何与字符串p和s一起使用。前三个步骤很熟悉。之后，字符d不在字符串p中，因此我们跳过了p的长度并在此之后快速找到匹配项。