我最近一直想知道我在字符串和整数等基本类型上执行的各种操作如何在性能方面起作用,我想如果我知道这些基本类型是如何实现的话我可以更好地理解这一点(即我已经听说字符串和整数在Python中是不可变的.这是否意味着修改字符串中一个字符的任何操作都是O(n),因为必须创建一个全新的字符串？如何添加数字？)
我对Python和Perl都很好奇,并且觉得两次基本相同的问题很傻,所以我只是把它包装成一个.
如果您可以在答案中包含一些示例操作成本,那么这将使其更有帮助.
在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数据类型的一些有用信息.
最后,因为你真的对内部感兴趣,我挖出了in 的struct声明(从版本2.7; 3+可能看起来不同).这是关于你期望的 - 带有一些额外花里胡哨的ac字符串:PyStringObjectstringobject.h
typedef struct {
PyObject_VAR_HEAD
(PyObject_VAR_HEAD是ac预处理器宏,根据此处说明的规则扩展为类似下面的内容.)
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可能看起来完全不同!
Perl字符串肯定不是不可变的.每个字符串都有一个缓冲区,缓冲区中字符串的初始偏移量,缓冲区的长度以及使用的缓冲区数量.此外,对于utf8字符串,在需要计算字符长度时会缓存字符长度.有一点,也有一些额外的字符偏移缓存到字节偏移信息,但我不确定它是否仍然存在.
如果需要增加缓冲区,则重新分配它.许多平台上的Perl都知道系统malloc的粒度,所以它可以为一个11字节的字符串分配一个14字节的缓冲区,知道它实际上不会占用任何额外的内存.
初始偏移允许O(1)从字符串的开头删除数据.