데이터 구조용 리소스 풀

Question

stack, queues, linked list 등과 같은 기본 데이터 구조를 구현할 때. 동적으로 메모리를 할당하여 자원 풀 (노드)을 만들어야합니까? 아니면 노드가 필요할 때마다 메모리를 별도로 할당해야합니까?

Answer 1

이것은 전적으로 귀하의 목표에 따라 다릅니다. 기본적으로 (달리 달리해야 할 필요가 없다면) 다음 노드마다 정상적인 할당을 수행하면됩니다. 단지 할당 노드에 비해

메모리 풀은 :

• 빠른 할당을 확인합니다. 기본 할당 메커니즘에 따라 때로는 이 빠릅니다.

• 일반적으로 메모리 조각화는 적지 만 일부 할당 자에게는 문제가되지 않을 수 있습니다.

• 주요 단점 : 예약되었지만 사용되지 않은 노드에 메모리를 낭비합니다. 두 개의 인스턴스 만있는 것과 달리 데이터 구조를 무차별 적으로 (예 : 인스턴스 1000 개) 사용하는 경우 매우 중요합니다. 때문에 단점의

는 메모리 풀 은 일반적인 상황에 적합하지 않습니다.

C++의 모든 표준 컨테이너에는 allocator 템플릿 매개 변수가 있습니다.

Answer 2

기본 시간 대 공간 트레이드 오프입니다. 더 중요한 것을 기반으로 선택하십시오.

풀을 미리 할당하면 런타임 요소 삽입이 평균 속도 - 즉 일정 시간, 즉 O (1)에 최적화됩니다. "평균적으로"는 이 대부분 삽입이 일정 시간 () 인 것을 의미합니다.은 최대 값을 초과하고 풀을 확장해야하며 이는 선형 시간 O (n)입니다. 또한 전체 풀을 사용하지 않으면 결국 메모리를 낭비 할 위험이 있습니다. 당신이 실시간으로 할 경우

모든 새로운 노드의 할당, 당신은 항상 일정 시간의 삽입을해야하지만이 경우, 일정 시간이 조금 더 위의 일정 시간보다 당신 때문에하지 값을 메모리 위치에 저장하면되지만 메모리 위치를 먼저 할당해야합니다. 또한이 방법은 미리 메모리 위치를 예약하여 메모리를 낭비하지 않습니다.

는 대부분의 상황에서, 내가 실시간으로 할당 시간 현명한 당신은 풀링 된 접근 방법을 사용하십시오 내가 왜보고하지 않는 것이 충분히 효율적이라고 생각, 는하지 않는 한 응용 프로그램은 거대한 할 극단적 인 평균 속도 을 필요로하거나 삽입 횟수.