Idi SudaIdi Sudahttps://teletype.in/atom/bvrch2026-05-13T20:37:56.629Zbvrch:Hy5wvP-gIПредставление в памяти2020-01-07T02:05:21.969Z2020-01-07T11:34:28.133ZПеремещая элементы в структурах данных общего назначения, мы копируем адрес. Т.е. всегда существует одна копия объекта, независимо от того, сколько раз он появляется в tuple/list/dict
<p>Перемещая элементы в структурах данных общего назначения, мы копируем адрес. Т.е. всегда существует одна копия объекта, независимо от того, сколько раз он появляется в tuple/list/dict</p>
<p></p>
<h3>Int</h3>
<pre>x = 123</pre>
<ul>
<ul>
<li>refcount</li>
<li>address of type <code>-> type <int></code></li>
<li>123</li>
</ul>
</ul>
<hr />
<h3>String</h3>
<pre>s = 'Hello!'</pre>
<ul>
<ul>
<li>refcount</li>
<li>address of type <code>-> type <str></code></li>
<li>length</li>
<li>hash</li>
<li>flags</li>
<li>address = 0</li>
<li>'Hello!'</li>
</ul>
</ul>
<hr />
<h3>Tuple</h3>
<pre>t = (1, 2.0, 'Hello!')</pre>
<ul>
<ul>
<li>refcount</li>
<li>address of type <code>-> type <tuple></code></li>
<li>length</li>
<li>address <code>-> int <1></code></li>
<li>address <code>-> float <2.0></code></li>
<li>address <code>-> str <'Hello!'></code></li>
</ul>
</ul>
<blockquote><em><u>Для последних трех адресов эта техника называется <code>indirection</code>, т.е. хранятся просто адреса, а не объекты.</u></em></blockquote>
<p></p>
<p>Вот как <code>tuple(10, 20)</code> описан на C:</p>
<pre>typedef struct {
Py_ssize_t ob_refcnt;
struct _typeobject *ob_type;
Py_ssize_t ob_size;
PyObject *ob_item[2]; /* store a pointer to 10 and a pointer to 20 */
} PyTupleObject;</pre>
<p>Заметьте, что <code>tuple</code> включает в себя непосредственно два указателя на данные.</p>
<hr />
<h3>Dict</h3>
<p>За каждым dict - массив, в котором ключи хранятся на индексах согласно их hash value. Каждый слот должен хранить ключ и хэш.</p>
<p>Словарь обычно растёт увеличиваясь в 2 или в 4 раза. Расширение происходит, когда он заполнен на 2/3.</p>
<hr />
<h3>List</h3>
<pre>my_list = [1, 2, 3]</pre>
<p>Чтобы расти, списку необходимо переместиться, но объекты в Python не могут менять адрес. Спасает двойной <code>indirection</code>.</p>
<ul>
<ul>
<li>refcount</li>
<li>address of type <code>-> type <list></code></li>
<li>length = 3</li>
<li>array address <code>-> указывает на список из 4 элементов, один из которых пустой, о нём ниже</code></li>
<ul>
<li>array len = 4</li>
</ul>
</ul>
</ul>
<p>Почему есть пустой элемент во "внутреннем" списке? Если бы не резервировалось для него место, то для каждого <code>append()</code> надо было заноыо выделять место. Это дорого - каждый адрес эл-та копируется в новое место. </p>
<p>Релокация на каждом следующем append() суммируется:<br /> - Чтобы добавить 2 эл-т в список нужно скопировать адрес 1 эл-та<br /> - Чтобы добавить 3 эл-т в список нужно скопировать адрес 1 и 2 эл-тов<br />И т.д.<br /><code>append()</code> на полный список запрашивает доп слоты для элементов. Списки в среднем используют 94% своих слотов, потребляя на 6% больше места, чем они используют. </p>
<p>Вот описание на C:</p>
<pre> PyObject arr[2]; /* store a pointer to 10 and a pointer to 20 */
typedef struct {
Py_ssize_t ob_refcnt;
struct _typeobject *ob_type;
Py_ssize_t ob_size;
PyObject **ob_item = arr; /* store a pointer to the two-pointer array */
Py_ssize_t allocated;
} PyListObject;</pre>
<p>Заметьте, что список включает в себя указатель ещё один уровень indirect, храня указатель на внешний массив с указателями.</p>