std :: vector 삽입의 상각 분석

Question

std :: vector에서 뒤에서 삽입 분석 (push_back)은 어떻게합니까? 상각 된 시간은 삽입 당 O (1)입니다. 특히 video in channel9 by Stephan T Lavavej과 in this (17:42 onwards)에서 그는 최적의 성능을 위해 Microsoft의이 방법 구현으로 벡터의 용량이 약 1.5로 증가한다고 말합니다.

이 상수는 어떻게 결정됩니까?

Answer 1

push_back을 삽입하고 삽입하지 않는다고 가정하면 중요한 부분은 상수 (매번 N 개 더 많은 요소를 가져 오는 것과 반대되는)에 의해 곱해진다는 것과 당신이 상수로 상환 한 일정 시간을 얻을 수 있다고 생각합니다. 계수를 변경하면 평균 사례 및 최악의 경우의 성능이 변경됩니다.

구체적으로 : 상수 요소가 너무 큰 경우 좋은 평균 성능을 보일 수 있지만 배열이 커질수록 최악의 성능이 좋지 않습니다. 예를 들어 10001 번째 요소를 푸시했기 때문에 10000 크기 벡터를 두 배로 늘린 (2x) 것으로 상상해보십시오. 편집 : 마이클 버가 간접적으로 지적한 것처럼 여기 실제 비용은 아마 당신이 필요로하는 것보다 훨씬 더 큰 메모리를 키울 것입니다. 귀하의 요인이 너무 큰 경우 속도에 영향을 미치는 캐시 문제가 있다는 것을 추가 할 것입니다. 필요한 것보다 훨씬 커질 경우 실제 비용 (메모리 및 계산)이 있다고 말하는 것으로 충분합니다.

그러나 상수 요소가 너무 작 으면 (1.1x) 좋은 성능을 보일 것입니다. 그러나 평균 성능이 좋지 않을 것입니다. 너무 많은 재 할당 비용이 필요하기 때문입니다 타임스.

Also, see Jon Skeet's answer to a similar question previously. (감사 @Bo 페르손) 분석에 대한

좀 더 : 당신이 n 다시 밀고 항목과 M의 배율을 말한다. 그러면 재 할당 횟수는 로그베이스 M (n)이됩니다 (log_M(n)). 그리고 i 번째 재 할당은 M^i (M에서 i의 힘까지)에 비례합니다. 그러면 모든 푸시 백 시간은 M^1 + M^2 + ... M^(log_M(n))이됩니다. 푸시 백수는 n이므로이 계열 (기하학적 계열이며 제한적으로 (nM)/(M-1)으로 축소)을 n으로 나눈 값입니다. 이것은 대략 상수 인 M/(M-1)입니다.

큰 값인 M의 경우 너는 많이 오버 슈팅하고 합리적으로 자주 필요한 것보다 많이 할당합니다 (위에서 언급 한 것). M의 작은 값 (1에 가깝습니다)의 경우이 상수 M/(M-1)이 커집니다. 이 요소는 평균 시간에 직접적인 영향을줍니다.

Answer 2

음, 보통의 소수점 숫자 시스템과 같은 숫자 시스템에 익숙하다면 분석이 정말 간단합니다.

간단히하기 위해 현재 용량에 도달 할 때마다 새로운 10 배의 큰 버퍼가 할당된다고 가정하십시오.

원래 버퍼의 크기가 1이면 첫 번째 재 할당은 1 요소를 복사하고 두 번째 재 할당은 10 요소를 복사하는 등의 작업을 수행합니다. 따라서 5 가지 재 할당을 사용하면 1 + 10 + 100 + 1000 + 10000 = 11111 요소 복사가 수행됩니다. 9를 곱하면 99999가됩니다. 이제 1을 추가하면 100000 = 10^5가됩니다. 또는 다시 말하면, 그 5 개의 재 할당을 지원하기 위해 수행 된 요소 사본의 수는 (10^5-1)/9입니다.

5 회의 재 할당 후 버퍼 크기가 10 배로 증가하면 10^5가됩니다. 이는 대략 요소 복사 작업의 수보다 9 배 큰 요소입니다. 즉, 복사에 소비 된 시간은 최종 버퍼 크기에서 대략 선형입니다.

10 대신 2를 사용하면 (2^5-1)/1 = 2^5-1이됩니다.

기타 염기 (또는 버퍼 크기를 늘리는 요인)에 대해서도 마찬가지입니다.

건배 &hth.

Answer 3

당신은 이런 종류의 일이 어떻게 작동하는지 파악하려고 수학을 할 수 있습니다.

점근 분석과 관련하여 널리 사용되는 방법은 뱅커스 방법입니다. 당신이하는 일은 추가 비용으로 모든 작업을 마크 업하고 나중에 비싼 작업을 지불하기 위해 "절약"하는 것입니다.

---

는의 일부 덤프 가정이 수학을 단순화하기 위해 만들어 보자 :

• 배열 비용 1에 쓰기. (배열 간 삽입 및 이동과 동일)
• 큰 배열을 할당하는 것은 무료입니다. 우리는 새로운 배열 요소를 이동해야 할 때 분명히

  function insert(x){ 
      if n_elements >= maximum array size: 
       move all elements to a new array that 
       is K times larger than the current size 
      add x to array 
      n_elements += 1 
  

  에서, "최악의 경우"가 발생합니다 같은

그리고 우리의 알고리즘은 보인다. 삽입 비용에 일정한 마크 업을 d으로 추가하여이 값을 상환하려고합니다. 작업 당 총 합계는 (1 + d)입니다.

배열의 크기를 조정 한 직후에 (1/K)가 채워지고 비용이 절약됩니다. 배열을 채울 때까지 적어도 d * (1 - 1/K) * N을 저장해야합니다. 이 돈이 이동하는 모든 N 요소에 대한 비용을 지불 할 수 있어야하기 때문에, 우리는 K와 d 사이의 관계를 알아낼 수 :

d*(1 - 1/K)*N = N 
d*(K-1)/K = 1 
d = K/(K-1) 

도움 테이블이에서 그래서

k d  1+d(total insertion cost) 
1.0 inf inf 
1.1 11.0 12.0 
1.5 3.0 4.0 
2.0 2.0 3.0 
3.0 1.5 2.5 
4.0 1.3 2.3 
inf 1.0 2.0 

---

이 문제에 대해 시간/메모리 트레이드 오프가 어떻게 작동하는지에 대한 거친 수학자의 아이디어를 얻을 수 있습니다. 물론 몇 가지주의 사항이 있습니다. 요소가 적어지면 배열을 축소하지 않고 요소가 제거되지 않고 추가 메모리를 할당하는 데 드는 시간 비용이 고려되지 않은 최악의 경우 만 나타냅니다.

그들은 대부분 내가 관련성이없는 것을 작성하면서 결국 이것을 알아 내기 위해 일련의 실험적 테스트를 실행했을 가능성이 큽니다.