Как базовые типы данных (строки и целые числа) реализованы в Python и Perl

Question

В последнее время меня интересует, как различные операции, которые я выполняю над базовыми типами, такими как строки и целые числа, работают с точки зрения производительности, и я полагаю, что мог бы получить гораздо лучшее представление об этом, если бы знал, как реализованы эти базовые типы (т.е.Я слышал, что строки и целые числа неизменны в Python. Означает ли это, что любая операция, которая изменяет один символ в строке, является O (n), потому что должна быть создана совершенно новая строка? Как насчет добавления чисел?)

Мне интересно об этом как в Python, так и в Perl, и я чувствовал себя глупо, задавая в основном один и тот же вопрос дважды, поэтому я просто сворачиваю его в один.

Если вы можете включить в свой ответ некоторые примерные операционные расходы, это сделало бы это еще более полезным.

Answer 1

Perl-строки определенно не являются неизменяемыми.Каждая строка имеет буфер, начальное смещение строки в буфере, длину буфера и объем используемого буфера.Кроме того, для строк utf8 длина символа кэшируется, когда ее необходимо вычислить.В какой-то момент было некоторое кэширование дополнительного символьного смещения в байтовой информации о смещении, но я не уверен, что это все еще на месте.

Если необходимо увеличить буфер, он перераспределяет его.Perl на многих платформах знает гранулярность системы malloc, поэтому он может выделить, скажем, 14-байтовый буфер для 11-байтовой строки, зная, что на самом деле это не займет никакой дополнительной памяти.

Начальное смещениепозволяет 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.

Наконец, поскольку вы действительно интересуетесь внутренними компонентами, я откопал объявление struct PyStringObject в stringobject.h (с версии 2.7; 3+, вероятно, выглядит иначе).Это примерно то, что вы ожидаете - строка ac с некоторыми дополнительными функциями:

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 вероятно, все выглядят совершенно по-разному!