Окончательно разбираем списки в питоне

[CrazyElf]

Надо же, я почему-то думал, что и в Python и в C# происходит банальное удвоение массива, выделенного под список, до каких-то совсем уж больших размеров списка, а потом идёт переход не на удвоение, а где-то на 1.4 увеличивается. Интересно, почему я так думал, надо покопать матчасть. ) Возможно, в C# именно так и происходит, а в Python всё хитрее.

[masha_proger]

В C# вроде удвоение, и в C++ тоже, а вот в питоне примерно x1.125 получается.

[wataru]

В C++ зависит от компилятора MSVC использует x1.5, остальные вроде бы, да, удваивают.

[wataru]

В таком случае считают амортизированную сложность. И окажется, что амортизированная сложность — О(1).

Это только если каждый раз при переаллокации увеличивать размер массива кратно. Все это знают и я очень удивлюсь, если в питоне не так.

Но судя по графику это не так!

Не могли бы вы провести эксперимент с 1000 элементов и вывести только те строчки, где перед добавлением allocated == ob_size?

[CrazyElf]

Если я вас правильно понял, то вот. Вообще там же есть формула на C++, она хитрая какая-то.
0
4
8
16
24
32
40
52
64
76
92
108
128
148
172
200
232
268
308
352
400
456
520
592
672
760
860
972

[wataru]

Да, рост экспоненциальный, хоть и очень медленный. Так что append будет O(1) в среднем.

[masha_proger]

Размер массива и увеличивается кратно, просто там коэффициент не 2, а поменьше. Что впрочем не влияет на оценку сложности.

[Tencix]

Я в свои 15 лет тоже написал собственный контейнер для POD-типов на C++, где я сделал выделение памяти при помощи malloc и дальнейшим заполнением. Я сделал много полезных функций, например, функцию для сдвига хвоста, чтобы можно было вставлять новые элементы, без создания промежуточных буферов. Рост у меня в коде - экспоненциальный, как и в vector. Главное у этого контейнера достаточно большая эффективность, я заменил тот код, где у меня был конвейер для создания промежуточного буфера с вершинами, а затем его вставка при помощи insert, заменив на новую функцию я получил прирост в скорости в 2,5 раза, так как вершины вставлялись сразу на своё место.

[masha_proger]

В 15 лет такое писать - уважаемо. Уже могли бы свой python реализовать. Даже интересно, куда в итоге вас вывел ваш карьерный путь?