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

https://stackoverflow.com/questions/1100311

11-09-2019
|

문제

C ++에는 std :: 벡터가 있으며 Java에는 Arraylist가 있으며 다른 많은 언어에는 자체 형태의 동적으로 할당 된 배열이 있습니다. 동적 배열이 공간이 부족하면 더 큰 영역으로 재 할당되고 이전 값이 새 배열로 복사됩니다. 이러한 배열의 성능의 중심에있는 질문은 배열의 크기가 빠르게 증가하는 것입니다. 당신이 항상 현재 푸시에 맞게 충분히 크게 자라면, 매번 재 할당됩니다. 따라서 배열 크기를 두 배로 늘리거나 1.5x로 곱하는 것이 합리적입니다.

이상적인 성장 요인이 있습니까? 2x? 1.5 배? 이상적으로 나는 수학적으로 정당화되고 최고의 균형을 유지하고 기억을 낭비한다는 의미입니다. 응용 프로그램이 푸시의 잠재적 분포를 가질 수 있다는 점을 감안할 때 이론적으로는이를 알고 있습니다. 그러나 나는 "일반적으로"가장 좋은 가치가 있는지, 또는 엄격한 제약 내에서 가장 잘 간주되는지 궁금합니다.

나는 이것에 대한 논문이 있다고 들었지만 그것을 찾을 수 없었습니다.

해결책

전적으로 사용 사례에 따라 다릅니다. 시간을 낭비하는 시간 (및 재 할당 배열) 또는 추가 메모리를 낭비하는 시간에 더 관심이 있습니까? 배열은 얼마나 오래 지속됩니까? 오랫동안 주변에 있지 않으면 더 큰 버퍼를 사용하는 것이 좋은 생각 일 수 있습니다. 페널티는 수명이 짧습니다. 그것이 주위에 매달려 있다면 (예 : Java에서, 나이가 많은 세대에 들어가는 것) 그것은 분명히 더 많은 형벌입니다.

"이상적인 성장 인자"와 같은 것은 없습니다. 그것은 단지 아닙니다 이론적으로 응용 프로그램 의존적입니다 분명히 응용 프로그램 종속.

2는 꽤 일반적인 성장 요인입니다 - 나는 그것이 무엇이라고 확신합니다. ArrayList 그리고 List<T> .NET에서 사용합니다. ArrayList<T> Java에서는 1.5를 사용합니다.

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

다른 팁

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

추론은 이것입니다.

16 바이트 할당으로 시작한다고 가정 해보십시오.
더 필요한 경우 32 바이트를 할당 한 다음 16 바이트를 제거하십시오. 이것은 기억에 16 바이트 구멍을 남깁니다.
더 필요한 경우 64 바이트를 할당하여 32 바이트를 제거합니다. 이것은 48 바이트 구멍을 남깁니다 (16과 32가 인접한 경우).
더 필요한 경우 128 바이트를 할당하여 64 바이트를 제거합니다. 이것은 112 바이트 구멍을 남깁니다 (이전의 모든 할당이 인접 해 있다고 가정).
그리고 그리고 그렇게.

아이디어는 2 배 확장으로 결과 구멍이 다음 할당을 재사용 할 수있을 정도로 커질 정도로 크다는 점이 없다는 것입니다. 1.5 배의 할당을 사용하여 대신 다음과 같습니다.

16 바이트로 시작하십시오.
더 필요한 경우 24 바이트를 할당 한 다음 16 바이트 구멍을 남기십시오.
더 필요한 경우 36 바이트를 할당 한 다음 24를 풀어 40 바이트 구멍을 남깁니다.
더 필요한 경우 54 바이트를 할당 한 다음 36을 풀어 76 바이트 구멍을 남깁니다.
더 필요한 경우 81 바이트를 할당 한 다음 54를 풀어 130 바이트 구멍을 남깁니다.
더 필요한 경우 130 바이트 구멍에서 122 바이트 (반올림)를 사용하십시오.

이상적으로 (한계에 N → ∞), 이것의 황금 비율: ϕ = 1.618...

실제로, 당신은 1.5와 같은 가까운 것을 원합니다.

그 이유는 오래된 메모리 블록을 재사용하고 캐싱을 활용하고 지속적으로 OS가 더 많은 메모리 페이지를 제공하지 않기를 원하기 때문입니다. 당신이 해결해야 할 방정식은 이것이 줄어 듭니다 엑스^{N − 1} − 1 = 엑스^{N + 1} − 엑스^N, 그 솔루션이 접근합니다 엑스 = 큰 경우 ϕ N.

이와 같은 질문에 대답 할 때의 한 가지 접근법은 널리 사용되는 도서관이 최소한 끔찍한 일을하지 않는다는 가정하에 "속임수"와 인기 도서관이하는 일을 살펴 보는 것입니다.

따라서 매우 빨리 확인하면 Ruby (1.9.1-P129)는 배열에 추가 할 때 1.5 배를 사용하는 것으로 보이며 Python (2.6.2)은 1.125x와 상수를 사용합니다 ( 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. 따라서 크기로 시작한다고 가정하십시오 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 할당, 우리는 이전에 거래 된 메모리가 Nth 할당에서 메모리 요구보다 크거나 동일하여 이전에 거래 된 메모리를 재사용 할 수 있기를 원합니다.

예를 들어, 세 번째 단계 에서이 작업을 수행하려면 (즉, n=3), 우리는 가지고 있습니다

x^3 <= 1 + x

이 방정식은 모든 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.

그것은 정말로 달려 있습니다. 어떤 사람들은 일반적인 사용 사례를 분석하여 최적의 숫자를 찾습니다.

나는 1.5x 2.0x phi x를 보았고 이전에 사용 된 2의 힘을 보았습니다.

배열 길이에 분포가 있고 공간 낭비와 시간 낭비가 얼마나 좋아하는지 말하는 유틸리티 기능이 있다면 최적의 크기 조정 (및 초기 사이징) 전략을 선택할 수 있습니다.

단순한 상수 배수가 사용되는 이유는 분명히 각 부속기가 상각 된 일정한 시간을 갖도록하기 때문입니다. 그렇다고해서 작은 크기에 대해 다른 (더 큰) 비율을 사용할 수 없다는 것을 의미하지는 않습니다.

Scala에서는 현재 크기를 보는 기능으로 표준 라이브러리 해시 테이블의 Loadfactor를 무시할 수 있습니다. 이상하게도, 우리는 대부분의 사람들이 실제로하는 일입니다.

실제로 메모리 오류에서 벗어나이 경우 더 적게 자라는 배열 (또는 1.5*ing) 어레이를 모릅니다. 거대한 단일 배열이 있다면 그렇게하고 싶을 것 같습니다.

더 덧붙여서 Resizedable Array를 충분히 오래 유지하고 시간이 지남에 따라 공간을 선호한다면 처음에는 전체적으로 전체적으로 (대부분의 경우) 극적으로 전체적으로 (대부분) 올바른 크기로 재 할당하는 것이 합리적 일 수 있습니다. 완료.

나는 Jon Skeet에 동의합니다. 심지어 내 이론 속도 친구조차도 이것이 요인을 2x로 설정할 때 O (1)로 입증 될 수 있다고 주장합니다.

CPU 시간과 메모리의 비율은 각 기계마다 다르므로 요인은 마찬가지로 다릅니다. RAM 기가 바이트가있는 기계와 느린 CPU가있는 경우 요소를 새 배열로 복사하는 것은 빠른 기계보다 훨씬 비싸므로 메모리가 적을 수 있습니다. 이론적으로는 균일 한 컴퓨터에 대해 이론적으로 대답 할 수있는 질문입니다. 실제 시나리오에서는 전혀 도움이되지 않습니다.

나는 그것이 오래된 질문이라는 것을 알고 있지만 모두가 빠진 것 같습니다.

첫째, 이것은 2 : size << 1의 곱셈입니다. 이것은 곱셈입니다. 아무것 1과 2 : int (float (size) * x), 여기서 x는 숫자, *는 부동 소수점 수학이며 프로세서는 플로트와 int 사이의 캐스팅에 대한 추가 지침을 실행해야합니다. 다시 말해, 기계 수준에서 배가는 새로운 크기를 찾기 위해 매우 빠른 지침이 필요합니다. 1에서 2 사이의 무언가를 곱하면 요구가 필요합니다 적어도 크기를 플로트로 캐스트하는 하나의 지시, 하나의 지시가 곱하기 (플로트 곱셈 일 것이므로 4 번 또는 8 배나 많은 사이클보다 2 배 이상이 걸릴 것입니다), 하나의 명령어는 Int로 다시 캐스트합니다. 또한 플랫폼이 특수 레지스터를 사용하는 대신 범용 레지스터에서 플로트 수학을 수행 할 수 있다고 가정합니다. 요컨대, 각 할당에 대한 수학이 단순한 좌회전시기보다 10 배 이상 걸릴 것으로 예상해야합니다. 재 할당 중에 많은 데이터를 복사하는 경우 큰 차이가 발생하지 않을 수 있습니다.

둘째, 아마도 큰 키커 : 모든 사람들은 해방되는 기억이 그 자체와 인접하고 새로 할당 된 기억과 인접하다고 가정하는 것 같습니다. 당신이 모든 기억을 직접 할당하고 수영장으로 사용하지 않는 한, 이것은 거의 확실하지 않습니다. OS 때때로 결국이 작업을 수행하지만 대부분의 시간에는 절반의 괜찮은 메모리 관리 시스템이 메모리에 맞는 작은 구멍을 찾을 수있는 충분한 여유 공간 조각화가있을 것입니다. 일단 당신이 정말로 조금 덩어리를 얻으면, 당신은 인접한 조각으로 끝날 가능성이 높지만, 그때까지 배분은 더 이상 문제가 될 정도로 자주 할당하지 않을 정도로 충분히 커집니다. 요컨대, 이상적인 숫자를 사용하면 무료 메모리 공간을 가장 효율적으로 사용할 수 있다고 상상하는 것은 재미 있지만 실제로는 프로그램이 베어 메탈에서 실행되지 않으면 (OS가없고, OS가 없습니다. 그 아래에서 모든 결정을 내린다).

질문에 대한 나의 대답? 아니, 이상적인 숫자는 없습니다. 아무도 실제로 시도하지 않을 정도로 응용 프로그램에 따라 다릅니다. 목표가 이상적인 메모리 사용이라면 운이 좋지 않습니다. 성능의 경우 덜 빈번한 할당이 더 좋습니다. 그러나 우리가 그와 함께 가면 4 또는 8을 곱할 수 있습니다! 물론, Firefox가 한 번의 샷에서 1GB에서 8GB를 사용하는 것에서 점프하면 사람들은 불평을 할 것이므로 말이되지 않습니다. 그래도 내가 가야 할 경험 규칙은 다음과 같습니다.

메모리 사용량을 최적화 할 수없는 경우 적어도 프로세서주기를 낭비하지 마십시오. 2를 곱하는 것은 플로팅 포인트 수학을하는 것보다 적어도 몇 배 더 빠릅니다. 그것은 큰 차이를 만들지 않을 수도 있지만, 적어도 (특히 더 빈번하고 작은 할당 중 초기에) 약간의 차이를 만들 것입니다.

그것을 지나치게 생각하지 마십시오. 이미 한 일을하는 방법을 알아 내려고 4 시간을 보냈다면 시간을 낭비했습니다. 정직하게도, *2보다 더 나은 옵션이 있다면, 수십 년 전에 C ++ 벡터 클래스 (및 다른 많은 장소)에서 이루어 졌을 것입니다.

마지막으로, 당신이 있다면 진짜 최적화하고, 작은 물건을 땀을 흘리지 마십시오. 이제 며칠 동안 내장 시스템에서 작업하지 않는 한 아무도 4KB의 메모리가 낭비되는 것을 신경 쓰지 않습니다. 각각 1MB에서 10MB 사이의 1GB의 물체에 도달하면 두 배가 너무 많을 것입니다 (즉, 100에서 1,000 객체 사이). 예상 확장 속도를 추정 할 수 있다면 특정 시점에서 선형 성장 속도로 평준화 할 수 있습니다. 분당 약 10 개의 물체를 예상하면 단계 당 5 ~ 10 개 객체 크기 (30 초에서 1 분마다)로 성장하는 것이 좋습니다.

모든 것이 내려 오는 것은 과도하게 생각하지 말고, 할 수있는 것을 최적화하고, 애플리케이션 (및 플랫폼)에 사용자 정의 해야하는 것입니다.

또 다른 2 센트

대부분의 컴퓨터에는 가상 메모리가 있습니다! 물리적 메모리에서는 프로그램의 가상 메모리에 단일 연속 공간으로 표시되는 모든 곳에서 임의의 페이지를 가질 수 있습니다. 간접의 해결은 하드웨어에 의해 수행됩니다. 가상 메모리 피로는 32 비트 시스템에서 문제가되었지만 더 이상 문제가되지 않습니다. 그래서 채우기 구멍 더 이상 걱정이 아닙니다 (특별 환경 제외). Windows 7이므로 Microsoft조차도 추가 노력없이 64 비트를 지원합니다. @ 2011
o (1)은 어떤 것도 도달합니다 아르 자형 > 1 요인. 동일한 수학적 증거는 매개 변수로 2에 대해서만 작동합니다.
아르 자형 = 1.5는 계산할 수 있습니다 old*3/2 따라서 부동 소수점 작업이 필요하지 않습니다. (내가 말하다 /2 컴파일러가 적합하다면 생성 된 어셈블리 코드의 비트 이동으로 컴파일러를 교체하기 때문입니다.)
MSVC가 갔다 아르 자형 = 1.5이므로 2를 비율로 사용하지 않는 주요 컴파일러가 하나 이상 있습니다.

누군가 2 명이 언급했듯이 2는 8보다 기분이 좋습니다. 또한 2는 1.1보다 기분이 좋습니다.

내 느낌은 1.5가 좋은 기본이라는 것입니다. 그 외에는 특정 사례에 따라 다릅니다.

라이센스 : CC-BY-SA ~와 함께 속성

제휴하지 않습니다 StackOverflow