메모리의 목록 크기

메모리의 목록 크기

---

방금 메모리에서 파이썬 데이터 구조의 크기를 실험했습니다. 다음 스 니펫을 작성했습니다.

import sys
lst1=[]
lst1.append(1)
lst2=[1]
print(sys.getsizeof(lst1), sys.getsizeof(lst2))

다음 구성에서 코드를 테스트했습니다.

• Windows 7 64 비트, Python3.1 : 출력은 다음과 같습니다. 52 40따라서 lst1에는 52 바이트가 있고 lst2에는 40 바이트가 있습니다.
• Python3.2가 포함 된 Ubuntu 11.4 32 비트 : 출력은 48 32
• Ubuntu 11.4 32 비트 Python2.7 : 48 36

둘 다 1을 포함하는 목록이지만 두 크기가 다른 이유를 설명 할 수 있습니까?

getsizeof 함수에 대한 파이썬 문서에서 다음을 발견했습니다. ...adds an additional garbage collector overhead if the object is managed by the garbage collector.내 작은 예제에서 이런 경우가 될 수 있습니까?

---

다음은 무슨 일이 일어나고 있는지 설명하는 데 도움이되는보다 완전한 대화 형 세션입니다 (Windows XP 32 비트의 Python 2.6이지만 실제로는 중요하지 않습니다).

>>> import sys
>>> sys.getsizeof([])
36
>>> sys.getsizeof([1])
40
>>> lst = []
>>> lst.append(1)
>>> sys.getsizeof(lst)
52
>>> 

빈 목록은 그 안에있는 목록보다 약간 작 [1]습니다. 그러나 요소가 추가되면 훨씬 더 커집니다.

그 이유 Objects/listobject.c는 CPython의 소스에있는 의 구현 세부 사항 때문입니다 .

빈 목록

빈 목록 []이 생성되면 요소를위한 공간이 할당되지 않습니다 PyList_New. 이는에서 볼 수 있습니다 . 36 바이트는 32 비트 시스템에서 목록 데이터 구조 자체에 필요한 공간입니다.

요소가 하나 인 목록

단일 요소 [1]가 포함 된 목록 이 생성되면 목록 데이터 구조 자체에 필요한 메모리와 함께 한 요소에 대한 공간이 할당됩니다. 다시 말하지만 PyList_New. size인수로 주어지면 다음 을 계산합니다.

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;

따라서를 사용 size = 1하면 포인터 하나에 대한 공간이 할당됩니다. 4 바이트 (내 32 비트 상자).

빈 목록에 추가

append빈 목록을 호출하면 다음 과 같은 결과가 발생합니다.

• PyList_Append 전화 app1
• app1 목록의 크기를 요청합니다 (그리고 응답으로 0을 얻음)
• app1다음 호출 list_resize로 size+1(우리의 경우 1)
• list_resize 흥미로운 할당 전략이 있습니다.

여기있어:

/* 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;
}

수학을 좀 해보자

내 기사의 시작 부분에서 세션에서 인용 한 숫자에 어떻게 도달하는지 봅시다.

따라서 36 바이트는 32 비트에서 목록 데이터 구조 자체에 필요한 크기입니다. 단일 요소를 사용하면 포인터 하나에 공간이 할당되므로 4 바이트가 추가되어 총 40 바이트가됩니다. 지금까지 좋습니다.

When app1 is called on an empty list, it calls list_resize with size=1. According to the over-allocation algorithm of list_resize, the next largest available size after 1 is 4, so place for 4 pointers will be allocated. 4 * 4 = 16 bytes, and 36 + 16 = 52.

Indeed, everything makes sense :-)

---

sorry, previous comment was a bit curt.

what's happening is that you're looking at how lists are allocated (and i think maybe you just wanted to see how big things were - in that case, use sys.getsizeof())

when something is added to a list, one of two things can happen:

1. the extra item fits in spare space

2. extra space is needed, so a new list is made, and the contents copied across, and the extra thing added.

since (2) is expensive (copying things, even pointers, takes time proportional to the number of things to be copied, so grows as lists get large) we want to do it infrequently. so instead of just adding a little more space, we add a whole chunk. typically the size of the amount added is similar to what is already in use - that way the maths works out that the average cost of allocating memory, spread out over many uses, is only proportional to the list size.

so what you are seeing is related to this behaviour. i don't know the exact details, but i wouldn't be surprised if [] or [1] (or both) are special cases, where only enough memory is allocated (to save memory in these common cases), and then appending does the "grab a new chunk" described above that adds more.

but i don't know the exact details - this is just how dynamic arrays work in general. the exact implementation of lists in python will be finely tuned so that it is optimal for typical python programs. so all i am really saying is that you can't trust the size of a list to tell you exactly how much it contains - it may contain extra space, and the amount of extra free space is difficult to judge or predict.

ps a neat alternative to this is to make lists as (value, pointer) pairs, where each pointer points to the next tuple. in this way you can grow lists incrementally, although the total memory used is higher. that is a linked list (what python uses is more like a vector or a dynamic array).

[update] see Eli's excellent answer. s/he explains that both [] and [1] are allocated exactly, but that appending to [] allocates an extra chunk. the comment in the code is what i am saying above (this is called "over-allocation" and the amount is porportional to what we have so that the average ("amortised") cost is proportional to size).

---

Here's a quick demonstration of the list growth pattern. Changing the third argument in range() will change the output so it doesn't look like the comments in listobject.c, but the result when simply appending one element seem to be perfectly accurate.

allocated = 0
for newsize in range(0,100,1):
    if (allocated < newsize):
        new_allocated = (newsize >> 3) + (3 if newsize < 9 else 6)
        allocated = newsize + new_allocated;
    print newsize, allocated

참고URL : https://stackoverflow.com/questions/7247298/size-of-list-in-memory