동적 확장 배열 C

Question

텍스트 파일에서 단어 어카운트 수를 계산하여 배열에 저장하는 프로그램이 있습니다. 지금까지 고정 배열을 사용하고 모든 것이 잘 작동하지만 지금은 동적 배열로 변경하여 메모리 낭비/필요성을 없앴습니다. malloc과 realloc을 사용하여이 작업을 수행해야한다는 것을 알고 있지만 실제로 작업하는 방법을 이해하지 못합니다.

첫 번째 아이디어는 텍스트 파일의 단어를 계산 한 다음 모든 공간을 malloc할만한 충분한 공간 이었지만 중복 된 단어는 카운터가 증가하지만 배열에 다시 추가되지 않으므로 낭비되는 공간을 남겨 둡니다.

이 방법은 의미있는 것처럼 들리며이를 달성하는 가장 좋은 방법일까요? 내가 먼저 한 단어와 그 카운터를 찾을만큼 작은 배열을 malloc한다면. 그런 다음 배열에 추가 할 필요가있는 새 단어를 찾을 때마다 다른 단어와 카운터를 넣을만큼 충분히 realloc됩니다. 중복이면 realloc이 필요하지 않습니다. 기존 카운터가 증가합니다.

Answer 1

일반적으로 100 % 메모리 사용을 목표로하지 않는 것이 거래 속도와 메모리 사용 측면에서 가장 좋습니다. 특히 프로그램이 제한된 시간 동안 만 실행되고 필요한 것보다 약간 더 많은 메모리를 사용하면 실제로 "비용이 많이 드는"경우입니다.

한 가지 일반적인 접근법은 동적 배열에 초기 크기, 예를 들어 8 또는 128 또는 무엇이든을 작성한 다음 채울 때마다 두 번 배열하는 것입니다.

이렇게하면 채워질 때 크기를 1 씩 증가시키는 것과 비교하면 (비용이 많이 드는) 재 할당 수가 줄어 듭니다. 물론, 그것은 약간의 기억을 낭비한다.