假设我想在python 2.7中获得字符串的特定字符,假设
a = 'abcdefg...' # a long string
print a[5]
想知道何时访问字符串的任何特定字符,例如,访问第5个元素,想知道性能是什么,是恒定时间o(1)还是线性性能o(n)我们要访问的字符)或整个字符串的线性性能o(n)(在此示例中len(a))?
>>> long_string_1M ="".join(random.choice(string.printable) for _ in xrange(1000000))
>>> short_string = "hello"
>>> timeit.timeit(lambda:long_string_1M[50000])
0.1487280547441503
>>> timeit.timeit(lambda:short_string[4])
0.1368805315209798
>>> timeit.timeit(lambda:short_string[random.randint(0,4)])
1.7327393072888242
>>> timeit.timeit(lambda:long_string_1M[random.randint(50000,100000)])
1.779330312345877
对我来说看起来像O(1)
他们将其实现,因为字符串是连续的内存位置,因此将其索引只是一个抵消的问题……如果您知道C/C ,就没有Seek(至少这是我的理解),它的内容类似于*(pointer+offset)
(ITS ITS)自从我完成C以来已经很长时间了,这可能有点错了)
除了乔兰(Joran
/* String slice a[i:j] consists of characters a[i] ... a[j-1] */
static PyObject *
string_slice(register PyStringObject *a, register Py_ssize_t i,
register Py_ssize_t j)
/* j -- may be negative! */
{
if (i < 0)
i = 0;
if (j < 0)
j = 0; /* Avoid signed/unsigned bug in next line */
if (j > Py_SIZE(a))
j = Py_SIZE(a);
if (i == 0 && j == Py_SIZE(a) && PyString_CheckExact(a)) {
/* It's the same as a */
Py_INCREF(a);
return (PyObject *)a;
}
if (j < i)
j = i;
return PyString_FromStringAndSize(a->ob_sval + i, j-i);
}
为什么这应该是您的直觉
python弦是不变的。这种常见的优化允许在理想时假设连续数据之类的技巧。请注意,在引擎盖下,有时我们只需要计算C中的内存位置的偏移(显然是实现)
在几个地方,弦的不变性可以依靠(或烦恼)。用python作者的话;
有几个优势[字符串是不可变的]。一个是性能:知道字符串是不变的,这意味着我们可以分配创建时间的空间
因此,尽管据我所知,我们可能无法保证这种行为跨实施,但可以假设。