동적으로 할당 된 어레이의 이상적인 성장률은 얼마입니까?

동적으로 할당 된 어레이의 이상적인 성장률은 얼마입니까?

---

C ++에는 std :: vector가 있고 Java에는 ArrayList가 있으며 다른 많은 언어에는 고유 한 형태의 동적 할당 배열이 있습니다. 동적 배열에 공간이 부족하면 더 큰 영역에 재 할당되고 이전 값이 새 배열에 복사됩니다. 이러한 어레이의 성능에 대한 핵심적인 질문은 어레이의 크기가 얼마나 빨리 증가하는지입니다. 항상 현재 푸시에 맞을만큼만 커지면 매번 재 할당하게됩니다. 따라서 배열 크기를 두 배로 늘리거나 1.5x를 곱하는 것이 좋습니다.

이상적인 성장 인자가 있습니까? 2 배? 1.5 배? 이상적으로는 수학적으로 정당화되고 최상의 균형 성능과 낭비되는 메모리를 의미합니다. 이론적으로는 응용 프로그램에 잠재적 인 푸시 분포가있을 수 있다는 점을 감안할 때 이것이 다소 응용 프로그램에 따라 다릅니다. 하지만 "보통"최고인지 아니면 엄격한 제약 내에서 최고로 간주되는 가치가 있는지 궁금합니다.

어딘가에 이것에 대한 논문이 있다고 들었지만 찾을 수 없었습니다.

---

전적으로 사용 사례에 따라 다릅니다. 데이터 복사 (및 어레이 재 할당)에 낭비되는 시간이나 추가 메모리에 대해 더 신경 쓰십니까? 어레이는 얼마나 오래 지속됩니까? 오래 지속되지 않을 경우 더 큰 버퍼를 사용하는 것이 좋습니다. 페널티는 짧습니다. (예를 들어 Java에서, 이전 세대와 이전 세대로 이동하는 경우) 그것은 분명히 더 많은 벌칙입니다.

"이상적인 성장 인자"와 같은 것은 없습니다. 이론적으로 응용 프로그램에 의존하는 것이 아니라 확실히 응용 프로그램에 따라 다릅니다.

이 꽤 일반적인 성장 인자이다 - 나는 확신이 무엇이야 ArrayList와 List<T>의 .NET의 용도. ArrayList<T>Java에서는 1.5를 사용합니다.

편집 : Erich가 지적했듯이 Dictionary<,>.NET에서는 해시 값이 버킷간에 합리적으로 분산 될 수 있도록 "크기를 두 배로 늘리고 다음 소수로 증가"를 사용합니다. (최근에 프라임이 실제로 해시 버킷을 배포하는 데 그다지 좋지 않다는 문서를 보았을 것입니다.하지만 그것은 또 다른 대답에 대한 논쟁입니다.)

---

몇 년 전에 적어도 C ++에 적용된 것처럼 1.5가 2보다 선호되는 이유를 읽은 적이 있습니다 (이는 런타임 시스템이 원하는대로 개체를 재배치 할 수있는 관리 언어에는 적용되지 않을 것입니다).

그 이유는 다음과 같습니다.

1. 16 바이트 할당으로 시작한다고 가정 해 보겠습니다.
2. 더 필요하면 32 바이트를 할당 한 다음 16 바이트를 확보합니다. 이로 인해 메모리에 16 바이트 구멍이 남습니다.
3. 더 필요하면 64 바이트를 할당하여 32 바이트를 확보합니다. 이렇게하면 48 바이트 구멍이 남습니다 (16과 32가 인접 해있는 경우).
4. 더 필요하면 128 바이트를 할당하여 64 바이트를 확보합니다. 이로 인해 112 바이트 구멍이 남습니다 (이전 할당이 모두 인접 해 있다고 가정).
5. 기타 등등.

아이디어는 2 배 확장을 사용하면 결과 구멍이 다음 할당에 재사용 할 수있을만큼 충분히 커질 시점이 없다는 것입니다. 1.5x 할당을 사용하면 대신 다음과 같이됩니다.

1. 16 바이트로 시작합니다.
2. 더 많이 필요하면 24 바이트를 할당 한 다음 16 바이트를 확보하여 16 바이트 구멍을 남깁니다.
3. 더 많이 필요하면 36 바이트를 할당 한 다음 24 바이트를 확보하고 40 바이트 구멍을 남깁니다.
4. 더 많이 필요하면 54 바이트를 할당 한 다음 36 바이트를 확보하여 76 바이트 구멍을 남깁니다.
5. 더 필요하면 81 바이트를 할당 한 다음 54 바이트를 확보하여 130 바이트의 구멍을 남깁니다.
6. 더 필요하면 130 바이트 구멍에서 122 바이트 (반올림)를 사용합니다.

---

이상적 (같은 한계에 N → ∞), 그것의 황금 비율 : φ = 1.618은 ...

실제로 1.5와 같이 가까운 것을 원합니다.

그 이유는 캐싱을 활용하고 OS가 더 많은 메모리 페이지를 제공하지 않도록 이전 메모리 블록을 재사용 할 수 있기를 원하기 때문입니다. 이가 감소되도록 해결하려는 식 X ^{N - 1} - 1 = X ^{N + 1} - X ^N , 그 용액 접근 X = φ 위해 큰 N .

---

이와 같은 질문에 답할 때 한 가지 접근 방식은 널리 사용되는 라이브러리가 최소한 끔찍한 일을하지 않는다는 가정하에 인기있는 라이브러리가 무엇을하는지 "속임수"로 살펴 보는 것입니다.

따라서 매우 빠르게 확인하면 Ruby (1.9.1-p129)는 배열에 추가 할 때 1.5x를 사용하는 것으로 보이며 Python (2.6.2)은 1.125x와 상수 (in Objects/listobject.c)를 사용합니다.

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

newsize위는 배열의 요소 수입니다. 에 newsize추가 new_allocated되므로 비트 시프트 및 삼항 연산자를 사용하는 표현식은 실제로 초과 할당을 계산하는 것입니다.

---

배열 크기를 x. 따라서 size로 시작한다고 가정합니다 T. 다음에 배열을 확장하면 크기는 T*x. 그럼 그렇게 될 것 T*x^2입니다.

목표가 이전에 생성 된 메모리를 재사용하는 것이라면 할당 한 새 메모리가 할당 해제 한 이전 메모리의 합계보다 작은 지 확인해야합니다. 따라서 다음과 같은 불평등이 있습니다.

T*x^n <= T + T*x + T*x^2 + ... + T*x^(n-2)

양쪽에서 T를 제거 할 수 있습니다. 그래서 우리는 이것을 얻습니다 :

x^n <= 1 + x + x^2 + ... + x^(n-2)

비공식적으로 우리가 말하는 것은 nth할당시 이전에 할당 해제 된 메모리를 재사용 할 수 있도록 이전에 할당 해제 된 모든 메모리가 n 번째 할당에서 필요한 메모리보다 크거나 같아야한다는 것입니다.

예를 들어, 우리는 3 단계 (즉,에서이 작업을 수행 할 수 있도록하려면 n=3), 다음 우리가

x^3 <= 1 + x 

이 방정식은 0 < x <= 1.3(대략)

아래에서 다른 n에 대해 우리가 얻는 x를 참조하십시오.

n  maximum-x (roughly)

3  1.3

4  1.4

5  1.53

6  1.57

7  1.59

22 1.61

성장 요인은 2이후 보다 작아야 x^n > x^(n-2) + ... + x^2 + x + 1 for all x>=2합니다.

---

It really depends. Some people analyze common usage cases to find the optimal number.

I've seen 1.5x 2.0x phi x, and power of 2 used before.

---

If you have a distribution over array lengths, and you have a utility function that says how much you like wasting space vs. wasting time, then you can definitely choose an optimal resizing (and initial sizing) strategy.

The reason the simple constant multiple is used, is obviously so that each append has amortized constant time. But that doesn't mean you can't use a different (larger) ratio for small sizes.

In Scala, you can override loadFactor for the standard library hash tables with a function that looks at the current size. Oddly, the resizable arrays just double, which is what most people do in practice.

I don't know of any doubling (or 1.5*ing) arrays that actually catch out of memory errors and grow less in that case. It seems that if you had a huge single array, you'd want to do that.

I'd further add that if you're keeping the resizable arrays around long enough, and you favor space over time, it might make sense to dramatically overallocate (for most cases) initially and then reallocate to exactly the right size when you're done.

---

I agree with Jon Skeet, even my theorycrafter friend insists that this can be proven to be O(1) when setting the factor to 2x.

The ratio between cpu time and memory is different on each machine, and so the factor will vary just as much. If you have a machine with gigabytes of ram, and a slow CPU, copying the elements to a new array is a lot more expensive than on a fast machine, which might in turn have less memory. It's a question that can be answered in theory, for a uniform computer, which in real scenarios doesnt help you at all.

---

I know it is an old question, but there are several things that everyone seems to be missing.

First, this is multiplication by 2: size << 1. This is multiplication by anything between 1 and 2: int(float(size) * x), where x is the number, the * is floating point math, and the processor has to run additional instructions for casting between float and int. In other words, at the machine level, doubling takes a single, very fast instruction to find the new size. Multiplying by something between 1 and 2 requires at least one instruction to cast size to a float, one instruction to multiply (which is float multiplication, so it probably takes at least twice as many cycles, if not 4 or even 8 times as many), and one instruction to cast back to int, and that assumes that your platform can perform float math on the general purpose registers, instead of requiring the use of special registers. In short, you should expect the math for each allocation to take at least 10 times as long as a simple left shift. If you are copying a lot of data during the reallocation though, this might not make much of a difference.

Second, and probably the big kicker: Everyone seems to assume that the memory that is being freed is both contiguous with itself, as well as contiguous with the newly allocated memory. Unless you are pre-allocating all of the memory yourself and then using it as a pool, this is almost certainly not the case. The OS might occasionally end up doing this, but most of the time, there is going to be enough free space fragmentation that any half decent memory management system will be able to find a small hole where your memory will just fit. Once you get to really bit chunks, you are more likely to end up with contiguous pieces, but by then, your allocations are big enough that you are not doing them frequently enough for it to matter anymore. In short, it is fun to imagine that using some ideal number will allow the most efficient use of free memory space, but in reality, it is not going to happen unless your program is running on bare metal (as in, there is no OS underneath it making all of the decisions).

My answer to the question? Nope, there is no ideal number. It is so application specific that no one really even tries. If your goal is ideal memory usage, you are pretty much out of luck. For performance, less frequent allocations are better, but if we went just with that, we could multiply by 4 or even 8! Of course, when Firefox jumps from using 1GB to 8GB in one shot, people are going to complain, so that does not even make sense. Here are some rules of thumb I would go by though:

If you cannot optimize memory usage, at least don't waste processor cycles. Multiplying by 2 is at least an order of magnitude faster than doing floating point math. It might not make a huge difference, but it will make some difference at least (especially early on, during the more frequent and smaller allocations).

Don't overthink it. If you just spent 4 hours trying to figure out how to do something that has already been done, you just wasted your time. Totally honestly, if there was a better option than *2, it would have been done in the C++ vector class (and many other places) decades ago.

Lastly, if you really want to optimize, don't sweat the small stuff. Now days, no one cares about 4KB of memory being wasted, unless they are working on embedded systems. When you get to 1GB of objects that are between 1MB and 10MB each, doubling is probably way too much (I mean, that is between 100 and 1,000 objects). If you can estimate expected expansion rate, you can level it out to a linear growth rate at a certain point. If you expect around 10 objects per minute, then growing at 5 to 10 object sizes per step (once every 30 seconds to a minute) is probably fine.

What it all comes down to is, don't over think it, optimize what you can, and customize to your application (and platform) if you must.

---

Another two cents

• Most computers have virtual memory! In the physical memory you can have random pages everywhere which are displayed as a single contiguous space in your program's virtual memory. The resolving of the indirection is done by the hardware. Virtual memory exhaustion was a problem on 32 bit systems, but it is really not a problem anymore. So filling the hole is not a concern anymore (except special environments). Since Windows 7 even Microsoft supports 64 bit without extra effort. @ 2011
• O(1) is reached with any r > 1 factor. Same mathematical proof works not only for 2 as parameter.
• r = 1.5 can be calculated with old*3/2 so there is no need for floating point operations. (I say /2 because compilers will replace it with bit shifting in the generated assembly code if they see fit.)
• MSVC went for r = 1.5, so there is at least one major compiler that does not use 2 as ratio.

As mentioned by someone 2 feels better than 8. And also 2 feels better than 1.1.

My feeling is that 1.5 is a good default. Other than that it depends on the specific case.

참고URL : https://stackoverflow.com/questions/1100311/what-is-the-ideal-growth-rate-for-a-dynamically-allocated-array