Pythonのリスト長調整方法（コード付き）

この記事はPythonのリストの長さ調整方法(コード付き)についての内容であり、ある程度の参考値はありますので、困っている方は参考にしていただければ幸いです。

Python の list (リスト) は非常に柔軟な配列であり、長さを自由に調整できます。この利便性があるからこそ、必要に応じて配列を変更せずにはいられないのですが、insert や Pop などに比べて、append の使用が一般的です。

こんな風に使われることもあります:

>>> test = []
>>> test.append(1)
>>> test.append({2})
>>> test.append([3])
>>> print test

# 输出 
[1, set([2]), [3]]

こんな風に使われることもあります:

test = []

for i in range(4):
    test.append(i)
print test

# 输出 
[0, 1, 2, 3]

このように使えてとても嬉しいです。

しかし実際には、データ長が動的に変更される可能性があるシナリオ、つまりメモリ管理の問題に遭遇した場合には、すぐに対応する必要があります。

業務効率化と利便性が同時に実現できれば、それは素晴らしいことです。

しかし、神はあなたのために窓を開けるとき、必ずドアも閉めているはずです。

ペニーピンチ初期化

私たちは事前割り当ての知識に深く影響されており、初期化中にリストには一定の長さが割り当てられると感じています。毎回記憶を申請します。

実際、リストは非常に「少ない」です:

import sys

test = []
test_1 = [1]
print sys.getsizeof(test)
print sys.getsizeof(test_1) - sys.getsizeof(test)

# 输出 
72     # 空列表内存大小，也是 list 对象的总大小
8       # 代表增加一个成员，list 增加的大小

私たちの推測では、リストが定義された後、データを埋めるために特定のサイズのプールが事前に割り当てられるのではないかと考えられます。 . 毎回メモリを申請することは避けてください。

しかし、上記の実験は、メンバー リストの長さが空のリストよりも 8 バイト大きいだけであることを示しています。そのような事前割り当てプールが実際に存在する場合、メンバーを追加するときに事前割り当てされたプールの数は、両方のメモリ サイズは変更されないはずです。

したがって、このリストにはそのような事前割り当てメモリ プールが存在すべきではないと推測できます。ここでは実際のハンマーが必要です。

PyObject *
PyList_New(Py_ssize_t size)
{
    PyListObject *op;
    size_t nbytes;

    if (size < 0) {
        PyErr_BadInternalCall();
        return NULL;
    }
    /* Check for overflow without an actual overflow,
     *  which can cause compiler to optimise out */
    if ((size_t)size > PY_SIZE_MAX / sizeof(PyObject *))
        return PyErr_NoMemory();
        
    // list对象指针的缓存
    if (numfree) {
        numfree--;
        op = free_list[numfree];
        _Py_NewReference((PyObject *)op);
    } else {
        op = PyObject_GC_New(PyListObject, &PyList_Type);
        if (op == NULL)
            return NULL;
    }
    
    // list 成员的内存申请
    nbytes = size * sizeof(PyObject *);
    if (size <= 0)
        op->ob_item = NULL;
    else {
        op->ob_item = (PyObject **) PyMem_MALLOC(nbytes);
        if (op->ob_item == NULL) {
            Py_DECREF(op);
            return PyErr_NoMemory();
        }
        memset(op->ob_item, 0, nbytes);
    }
    Py_SIZE(op) = size;
    op->allocated = size;
    _PyObject_GC_TRACK(op);
    return (PyObject *) op;
}

test = [1] を実行するとき、実際に行うことは次の 2 つだけです:

メンバーの数に基づいて、対応する長さの空のリストを構築します ;(上のコード)

これらのメンバーを 1 つずつ入れてください;

メンバーを詰めるステップで、何かのメカニズムがトリガーされて大きくなるのではないかと考える子供もいるかもしれません。

残念ですが、初期化メソッドは PyList_SET_ITEM なので、ここにはトリガー メカニズムはなく、配列メンバーの単純な割り当てだけです。

#define PyList_SET_ITEM(op, i, v) (((PyListObject *)(op))->ob_item[i] = (v))

したがって、リスト全体の初期化は次のようになります。本当に唯一のことは、事前に割り当てられたメモリ プールがないということです。オンデマンドで直接適用できます。すべてのニンジンは穴であり、これは本当に残酷です。

可変長の鍵

#初期化処理はこれは理解できますが、運用中にこのままだとちょっと無理があります。

想像してみてください。記事の冒頭の append の例で、要素が追加されるたびにメモリが適用されると、リストは生命を疑うほど批判される可能性があります。記憶を求めるとき、神にはまだ独自のルーチンがあるということです。

リストでは、挿入、ポップ、追加のいずれであっても、list_resize が使用されます。名前が示すように、この関数はリスト オブジェクトのメモリ使用量を調整するために使用されます。

static int
list_resize(PyListObject *self, Py_ssize_t newsize)
{
    PyObject **items;
    size_t new_allocated;
    Py_ssize_t allocated = self->allocated;

    /* Bypass realloc() when a previous overallocation is large enough
       to accommodate the newsize.  If the newsize falls lower than half
       the allocated size, then proceed with the realloc() to shrink the list.
    */
    if (allocated >= newsize && newsize >= (allocated >> 1)) {
        assert(self->ob_item != NULL || newsize == 0);
        Py_SIZE(self) = newsize;
        return 0;
    }

    /* This over-allocates proportional to the list size, making room
     * for additional growth.  The over-allocation is mild, but is
     * enough to give linear-time amortized behavior over a long
     * sequence of appends() in the presence of a poorly-performing
     * system realloc().
     * The growth pattern is:  0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
     */
    # 确定新扩展之后的占坑数
    new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);

    /* check for integer overflow */
    if (new_allocated > PY_SIZE_MAX - newsize) {
        PyErr_NoMemory();
        return -1;
    } else {
        new_allocated += newsize;
    }

    if (newsize == 0)
        new_allocated = 0;

    # 申请内存
    items = self->ob_item;
    if (new_allocated <= (PY_SIZE_MAX / sizeof(PyObject *)))
        PyMem_RESIZE(items, PyObject *, new_allocated);
    else
        items = NULL;
    if (items == NULL) {
        PyErr_NoMemory();
        return -1;
    }
    self->ob_item = items;
    Py_SIZE(self) = newsize;
    self->allocated = new_allocated;
    return 0;
}

上記のコードでは、newize と new_allocated という 2 つの名詞が頻繁に登場しますが、newsize は増減数ではなく、増減後のメンバーの総数であることを説明する必要があります。 。例:

a = [1, 2, 3]
a.append(1)

上記の append が list_resize をトリガーすると、newsize は 1 ではなく 3 1 になります。pop を使用してリストのメンバーを減らすと、減った合計数が渡されるため、これはより重要です。

リストの構造定義には、ob_size (実際のメンバー数) と割り当てられた (メンバーの総数) という 2 つの長さの定義があります。

それらの間の関係は次のとおりです。

 0 <= ob_size <= allocated
 len(list) == ob_size

ということで new_allocated というのがわかりやすいですね、これが新しいピットの総数です。

名詞の意味がほぼ理解できたら、手がかりに従って list_resize? の後にリストのサイズがどのくらいになるかを知ることができます。

メソッドは、実際には上記のコメントとコードから非常に明確です。簡単にまとめます:

最初にベースを決定します: new_allocated = (newsize >> 3) (newsize < ; 9 ? 3 : 6);

new_allocated newsize が PY_SIZE_MAX を超えているかどうかを決定します。超えている場合は、エラーが直接報告されます。

最後に、新しい合計ピット数を決定します: new_allocated newsize、if newsize が 0 の場合、ピットの総数は直接 0 になります;

以下はデモンストレーションです:

#coding: utf8
import sys

test = []
raw_size = sys.getsizeof(test)

test.append(1)
print "1 次 append 减去空列表的内存大小：%s " % (sys.getsizeof(test) - raw_size)

test.append(1)
print "2 次 append 减去空列表的内存大小：%s " % (sys.getsizeof(test) - raw_size)

test.append(1)
print "3 次 append 减去空列表的内存大小：%s " % (sys.getsizeof(test) - raw_size)

test.append(1)
print "4 次 append 减去空列表的内存大小：%s " % (sys.getsizeof(test) - raw_size)

test.append(1)
print "5 次 append 减去空列表的内存大小：%s " % (sys.getsizeof(test) - raw_size)

test.append(1)
print "6 次 append 减去空列表的内存大小：%s " % (sys.getsizeof(test) - raw_size)

# 输出结果
1 次 append 减去空列表的内存大小：32
2 次 append 减去空列表的内存大小：32
3 次 append 减去空列表的内存大小：32
4 次 append 减去空列表的内存大小：32
5 次 append 减去空列表的内存大小：64
6 次 append 减去空列表的内存大小：64

簡単な置換法から始めて段階的に計算します:

そのうち:

new_allocated = (newsize >> 3) (newsize < 9 ? 3 : 6) newsize (次の newsize > 0 のため)

元の割り当て時>= newize と newize >= オリジナル 割り当て / 2 の場合、割り当てられた値は変更されず、メモリは適用されずに直接返されます

第 n 次 append	列表原长度	新增成员数	原 allocated	newsize	new_allocated
1	0	1	0	0 + 1 = 1	3 + 1 = 4
2	1	1	4	1 + 1 = 2	无需改变
3	2	1	4	2 + 1 = 3	无需改变
4	3	1	4	3 + 1 = 4	无需改变
5	4	1	4	4 + 1 = 5	3 + 5 = 8
6	5	1	8	5 + 1 = 6	无需改变

通过上面的表格，应该比较清楚看到什么时候会触发改变 allocated，并且当触发时它们是如何计算的。为什么我们需要这样关注 allocated？理由很简单，因为这个值决定了整个 list 的动态内存的占用大小；

扩容是这样，缩容也是照猫画虎。反正都是算出新的 allocated， 然后由 PyMem_RESIZE 来处理。

总结

综上所述，在一些明确列表成员或者简单处理再塞入列表的情况下，我们不应该再用下面的方式：

test = []

for i in range(4):
    test.append(i)
print test

而是应该用更加 pythonic 和 更加高效的列表推导式：test = [i for i in range(4)]。

以上がPythonのリスト長調整方法（コード付き）の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。