메모리 할당의 시간 복잡도
https://stackoverflow.com/questions/282926
-
08-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
new, malloc 등을 사용한 동적 메모리 할당의 시간 복잡도는 얼마입니까?나는 메모리 할당자가 어떻게 구현되는지에 대해 거의 알지 못하지만 대답은 구현에 따라 다르다고 가정합니다.따라서 보다 일반적인 사례/구현에 대해 답변해 주시기 바랍니다.
편집하다:최악의 경우 힙 할당이 무제한이라는 말을 들었던 기억이 어렴풋이 나지만, 평균/전형적인 경우에는 정말 관심이 갑니다.
해결책
O 표기법을 다룰 때 알아야 할 사항 중 하나는 무엇을 이해하는 것이 종종 매우 중요하다는 것입니다. N 이다. 만약 N 제어 할 수있는 것과 관련된 것입니다 (예 : 정렬하려는 목록의 요소 수) 그러면 열심히 보는 것이 합리적입니다.
대부분의 힙 구현에서 귀하의 N 관리자가 처리하는 메모리 덩어리의 수입니다. 이것은 결정적으로입니다 ~ 아니다 일반적으로 고객 통제하에있는 것. 유일한 N 클라이언트는 실제로 제어 할 수있는 메모리 덩어리의 크기입니다. 종종 이것은 할당자가 취하는 시간과 관련이 없습니다. 큰 N 작은 것만 큼 빠르게 할당 될 수 있습니다 N, 또는 훨씬 더 오래 걸릴 수도 있고, 보증 할 수 없을 수도 있습니다. 이 모든 것이 동일하게 변할 수 있습니다 N 다른 고객의 이전 할당 및 거래가 어떻게 들어 왔는지에 따라. 따라서 실제로 힙을 구현하지 않는 한 적절한 대답은 그것이 비 결정적이라는 것입니다.
이것이 하드 실시간 프로그래머가 동적 할당을 피하려고하는 이유입니다 (시작 후).
다른 팁
힙 할당 자의 시간 복잡성은 최적화 할 수있는 내용에 따라 다른 시스템에서 다를 수 있습니다.
데스크탑 시스템에서 힙 할당자는 아마도 최근 할당 캐싱, 일반적인 할당 크기에 대한 룩타이드 목록, 특정 크기 특성을 가진 메모리 덩어리의 빈 등을 포함한 다양한 전략의 혼합물을 사용하여 할당 시간을 낮추지 않고 단편화를 유지할 수 있습니다. 사용되는 다양한 기술에 대한 개요는 Doug Lea의 Malloc 구현에 대한 메모를 참조하십시오. http://g.oswego.edu/dl/html/malloc.html
더 간단한 시스템의 경우, First Fit 또는 Best Fit의 전략이 사용될 수 있으며, 무료 블록은 링크 된 목록에 저장됩니다 (N)가 무료 블록의 수를 가진 O (n) 시간을 제공합니다). 그러나 AVL 트리와 같은보다 정교한 스토리지 시스템은 O (log n)에서 무료 블록을 찾을 수 있습니다 (http://www.oocities.org/wkaras/heapmm/heapmm.html).
실시간 시스템은 O (1) 할당 비용이있는 TLSF (2 레벨 분리 적합성)와 같은 힙 할당자를 사용할 수 있습니다. http://www.gii.upv.es/tlsf/
나는 일반적으로 O(n)이라고 생각합니다. 여기서 n은 사용 가능한 메모리 블록의 수입니다(적절한 메모리 블록을 찾으려면 사용 가능한 메모리 블록을 스캔해야 하기 때문입니다).
그렇긴 하지만, 특히 크기 범위에 따라 사용 가능한 블록의 여러 목록을 유지 관리하는 등 속도를 높일 수 있는 최적화를 보았습니다(따라서 1k 미만의 블록은 하나의 목록에 있고 1k에서 10k까지의 블록은 다른 목록에 있는 등). ).
그러나 이것은 여전히 O(n)이지만 n이 더 작습니다.
무한한 힙 할당이 있다는 소스를 확인하고 싶습니다(만약 영원히 걸릴 수 있다는 의미라면).
일반적인 할당자가 어떻게 작동하는지 확인하십시오.
범프-포인터 할당자가 작동합니다 o (1), 그리고 그것은 작은 것입니다. '1'그것에.
분리 된 스토리지 할당 자의 경우, K Bytes의 할당은 "목록에서 첫 번째 블록을 반환합니다 (N) "Where List (N)은 N 바이트 블록 목록입니다. n> = k. 그것 ~할 것 같다 그 목록 찾기 (N)이 비어 있으므로 다음 목록에서 블록 (목록)2n))는 두 개의 결과 블록으로 분할되어야합니다. N 목록에 바이트를 넣는 바이트 (N), 그리고이 효과 ~할 것 같다 모든 availlable 크기를 통해 파급되어 복잡성을 만듭니다. O (NS) 여기서 NS는 다양한 크기의 수입니다. ns = log (n) 어디 N 가장 큰 블록 크기의 크기는 availlable이므로 작습니다. 대부분의 경우, 특히 많은 블록이 할당되고 거래 된 후 복잡성은 o (1).
두 가지 말 :
TLSF 단일 루프가없는 의미에서 O (1)입니다. 최대 2GB를 관리합니다. 정말로 믿기 어렵지만 코드를 확인하십시오.
"가장 적합한"정책 (타이트 블록 찾기)이 작은 조각화를 달성하기에 가장 적합한 것은 사실이 아닙니다. 이 주장을 입증하는 것은 사소한 일이 아닙니다. 실제로 공식적으로 입증되지는 않았지만 그 방향으로가는 많은 증거가 있습니다. (좋은 연구 주제).
