Внутреннее устройство Python list

[torkve]

Кажется, всю статью надо просто заменить на фразу «list в python — это на самом деле vector» где-нибудь в стандартной документации.

[ramntry]

«вектор указателей» может быть лучше. Или «динамический массив» вместо «вектор» — последний все-таки больше C++-специфический термин, чем общепринятое в CS понятие.

[torkve]

Про вектор указателей согласен.
Про «C++-специфичный» — нет, это достаточно стандартный термин для обозначения одномерного массива. Хотя в данном случае конечно он устроен именно как вектор в C++.

[Viacheslav01]

«app1:
n = size of list
call list_resize() to resize the list to size n+1 = 0 + 1 = 1
list[n] = list[0] = new element
return 0
»

Это прям так на C и написано?

[medvedGrizli]

Нет, конечно; это что-то вроде псевдокода. Если речь про то, что я указал язык «cpp» в хайлайтере — просто не удалось подобрать что-либо удобоваримое под эти блоки, а оставлять их совсем не расцвеченными не хотелось.

[nickolaym]

А какой смысл в переводе статьи, если так называемый псевдокод остался на английском? Да ещё и раскрашен чёрт знает как.
Был бы он хотя бы на псевдо-питоне или псевдо-си, ещё можно было бы смириться.
А это даже не псевдо-кобол, это тупо английский текст пополам с формулами, только с отбивкой.

[medvedGrizli]

Проявите снисходительность к новичку :) Я не думал, что есть смысл переводить этот псевдокод. Если попытаться представить его в другом формате — не будет ли это нарушением правил перевода? Если вы считаете, что перевод этих блоков улучшит статью — я буду только «за» сделать это.

[nickolaym]

Однозначно улучшит.

[medvedGrizli]

Исправил. Прошу review.

[nickolaym]

Функция app1 — в ней фигурирует не определённая переменная n.
Ну и в других местах — то указывается полное определение — Py_ssize_t i; — то просто по факту инициализации понятно, о чём речь.

А в остальном, неплохо.

[archim]

Спасибо.
А что это за магический PyMem_RESIZE?
Там внутри должно наверное происходить выделение нового места в памяти и копирование данных туда?
Так что сложность O(1) при добавлении элемента будет не всегда.

[ya_boiko]

Спасибо за вашу статью! Спорил на техническом собеседование что такое list в python - массив или связанный список. Думаю, что я оказался прав - list хранится в памяти как массив. Надеюсь в 2к20 list "изнутри" не изменился)