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

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

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

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

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

Ответ 2

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

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

Начальное смещение позволяет O (1) удалить данные с начала строки.