Ответ 1
В 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). Конечно, это справедливо только с небольшими ints. Как только вы нажмете какой-то порог (20 цифр на моей машине), внезапно ints займет переменное количество пространства. Я не знаю, как это влияет на асимптотические характеристики.
Однако я обнаружил, что он даже не имеет значительного эффекта даже вблизи 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 = = "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 = = "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 = = ["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.
Наконец, поскольку вы действительно заинтересованы в внутренних компонентах, я выкопал объявление struct PyStringObject в 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, возможно, все выглядит совершенно иначе!