Python和Perl中的基本数据类型（字符串和整数）是如何实现的

Question

最近我在想，像字符串和整数这些基本类型的各种操作在性能上是怎么回事。我觉得如果了解这些基本类型是怎么实现的，我就能更好地理解这一点（比如，我听说在Python中字符串和整数是不可变的。这是不是意味着任何修改字符串中一个字符的操作都是O(n)的，因为必须创建一个全新的字符串？那加数字呢？）

我对这个问题在Python和Perl中都很感兴趣，但觉得问同样的问题两次有点傻，所以就把它合在一起了。

如果你能在回答中举一些操作成本的例子，那就更有帮助了。

Answer 1

Perl中的字符串绝对不是不可变的。每个字符串都有一个缓冲区，里面存储了字符串的起始位置、缓冲区的长度，以及已经使用的缓冲区大小。此外，对于utf8编码的字符串，当需要计算字符长度时，它会缓存这个长度。曾经还缓存过额外的字符偏移到字节偏移的信息，但我不确定现在是否还在使用。

如果缓冲区需要增大，Perl会重新分配一个新的缓冲区。在很多平台上，Perl知道系统内存分配的细节，所以它可以为一个11字节的字符串分配一个14字节的缓冲区，这样实际上不会占用额外的内存。

起始偏移量的存在使得从字符串开头删除数据的操作非常快速，时间复杂度是O(1)。

Answer 2

在Python中，some_string[5] = 'a'会出错，但最接近的操作是some_string = some_string[5:] + 'a' + some_string[6:]，这个操作的时间复杂度是O(n)。不过，这不仅仅适用于不可变对象，连接列表也是一样的：[1,2,3] + [4,5,6]会生成一个新列表，时间复杂度也是O(n)。

加法运算会产生一个新值，但通常这个新值在内存中的大小是固定的，所以时间复杂度是O(1)。当然，这只适用于小整数。当你达到某个阈值（在我这台机器上是20位数字）时，整数的内存占用会变得不固定。我不太清楚这对渐进性能有什么影响。

不过，我发现即使在log10(n) == 1000附近，这种影响似乎也不明显：

>>> times = [timeit.timeit(stmt=stmt.format(10 ** i, 10 ** i), number=100) for i in range(1000)]
>>> sum(times) * 1.0 / len(times)
3.0851364135742186e-06
>>> times[-1]
3.0994415283203125e-06

对于字符串来说，渐进性能的影响更明显：

>>> stmt = 's[:5] + "a" + s[6:]'
>>> setup = 's = "b" * {0}'
>>> times = [timeit.timeit(stmt=stmt, setup=setup.format(i), number=10) for i in range(100000)]
>>> sum(times) * 1.0 / len(times)
6.2434492111206052e-05
>>> times[-1]
0.0001220703125

最后一个操作的执行时间远低于平均水平，而且趋势相当稳定：

>>> for t in times[0:100000:10000]:
...     print t
... 
5.00679016113e-06
1.31130218506e-05
2.90870666504e-05
3.88622283936e-05
5.10215759277e-05
6.19888305664e-05
7.41481781006e-05
8.48770141602e-05
9.60826873779e-05
0.000108957290649

不过，对于小字符串来说，这些操作的成本还是比较低的。

---

关于你其他的问题，列表和字符串的索引访问都是O(1)。

>>> stmt = 'x = s[{0}] + s[{1}] + s[{2}]'
>>> setup = 's = "a" * {0}'
>>> times = [timeit.timeit(stmt=stmt.format(i / 2, i / 3, i / 4), setup=setup.format(i + 1), number=10) for i in range(1000000)]
>>> sum(times) * 1.0 / len(times)
3.6441037654876707e-06
>>> times[-1]
3.0994415283203125e-06

列表也是一样：

>>> stmt = 'x = s[{0}] + s[{1}] + s[{2}]'
>>> setup = 's = ["a"] * {0}'
>>> times = [timeit.timeit(stmt=stmt.format(i / 2, i / 3, i / 4), setup=setup.format(i + 1), number=10) for i in range(100000)]
>>> sum(times) * 1.0 / len(times)
2.8617620468139648e-06
>>> times[-1]
1.9073486328125e-06

切片操作会复制字符串和列表，因此时间复杂度是O(n)，其中n == len(slice)。没有“好”的方法来替换字符串中的一个字母，虽然我想强调的是，“坏”的方法在大多数情况下已经足够好了。如果你想要“好”的方法，可以使用不同的数据类型；操作一个列表，然后在需要字符串时再连接；或者使用StringIO对象。这个页面提供了一些关于连接不同内置Python数据类型的有用信息。

最后，因为你对内部机制很感兴趣，我查找了PyStringObject的struct声明，来自stringobject.h（版本2.7；3+可能看起来不同）。这大概是你所期待的——一个C字符串，带有一些额外的功能：

typedef struct {
    PyObject_VAR_HEAD

(PyObject_VAR_HEAD是一个C预处理器宏，根据这里解释的规则展开成下面的内容。)

    Py_ssize_t ob_refcnt;
    PyTypeObject *ob_type;
    Py_ssize_t ob_size;

继续...

    long ob_shash;
    int ob_sstate;
    char ob_sval[1];

    /* Invariants:
     *     ob_sval contains space for 'ob_size+1' elements.
     *     ob_sval[ob_size] == 0.
     *     ob_shash is the hash of the string or -1 if not computed yet.
     *     ob_sstate != 0 iff the string object is in stringobject.c's
     *       'interned' dictionary; in this case the two references
     *       from 'interned' to this object are *not counted* in ob_refcnt.
     */
} PyStringObject;

列表有一个类似的结构——C数组加上一些额外的功能——但不是以空字符结尾，通常还会有额外的预分配存储空间。

不必说... 这些内容大多只适用于CPython——PyPy、IronPython和Jython可能看起来完全不同！