char buffer[1000] = {0};
이렇게하면 1000 개의 요소가 모두 0으로 초기화됩니다.이 일정 시간입니까? 그렇지 않다면, 왜?일정 시간에 C++ 배열 초기화
이 O이 최적화 할 수있는 컴파일러 보인다 (1) 다음과 같은 사실에 기초하여 :
답변은 모든 컴파일러에서 일반적 일 수 있지만 Windows의 MSVC 컴파일러 (모든 버전)에서 테스트 한 답변에 특히 관심이 있습니다.
보너스 포인트 : 자세한 내용은 기사, 백서 등의 링크를 참조하십시오.
글로벌 시간대가 아닌 일정 시간이 될 수 없습니다. 사실 컴파일러가 그것을 초기화하지만, 운영 체제는 모든 파일을 메모리에로드해야합니다. 메모리는 O(n) 시간이 걸립니다.
왜 파일에 대해 이야기하고 있습니까? –
@RobertDailey : 실행 파일 (프로그램)을 메모리에로드해야하기 때문에. 데이터 세그먼트에 실행 파일에 1000 개의 0이 할당되어 있어도 해당 실행 파일을 선형 시간 작업 인 메모리에 매핑해야했습니다. –
Dani가 맞습니다. 배열은 메모리의 0으로 초기화되거나 디스크에서 읽혀집니다. 그러나 디스크에서 N 개의 0을 읽는 것은 O (N)입니다. –
전역 변수로만 O (1)가 될 수 있습니다. 로컬 변수 (스택)이면 O (n)입니다. 여기서 n은 배열의 크기입니다.
스택은 공유 메모리이기 때문에 항상 0을 항상 0으로 만들고 싶습니다. 정의한 배열은 데이터 세그먼트에 대한 포인터로 구현되지 않으며 스택에 1000 개의 변수가 있으므로 O (1000)로 초기화해야합니다.
EDIT : Dani가 맞습니다. 내 진술을 수정해야합니다. 전역 배열 인 경우 프로그램이 시작될 때 초기화됩니다. 그리고 그것도 O (n)입니다.
프레이밍이 포함 된 일반적인 관용구는 공간을 만들기 위해 스택 포인터를 이동 한 다음 뒤에 와서 로컬 변수에 값을 적용하는 것입니다. – user7116
글로벌, 운영 체제에서도 여전히로드해야하는 경우 내 대답 – Dani
을 참조하십시오. 데이터 세그먼트의 데이터가 각 기능의 스택에 복사되었다고 생각했습니다. 저는 이처럼 낮은 수준의 세부 사항에 대한 전문가는 아니지만 배열에 대해 일괄 복사로 생각했습니다. 즉, 최적화 된 작업으로 스택에 1000 바이트를 '밀어 넣습니다'. 나는 그것이 각 요소에 대해 단일 푸시를하고 있다는 것을 몰랐다. 어떻게 든 최적화 될 수있는 것처럼 보입니다 ... –
전역 정적 인 경우 여기의 "상수"는 0입니다 - 초기화는 COMPILE TIME에서 수행됩니다.
아직 존재하지 않는 컴퓨터에 1000 개의 연속적인 0 블록을 어떻게 할당 할 예정입니까 ?? –
함수 안에 있으면 아니지만 일정 시간이 아닙니다.
번째 가정이 올바르지 않습니다 :
"어레이가 아마도 실행 파일의 청크 (윈도우)에 실행 파일의 데이터 세그먼트 내의 데이터를 포함 할 수 있다는 것을 의미한다 스택에 위치하고 이미 0으로 채워진 데이터입니다. "
스택에 아직 0이 채워지지 않았습니다. 이전 함수 호출의 쓰레기 잔량으로 가득 차 있습니다.
따라서 0이되어야하므로 O(1)에서 수행 할 수 없습니다.
어레이는 스택에 있습니다. 즉, 실행 파일은 실행 파일 (Windows의 경우)의 데이터 세그먼트에이 데이터가 이미 0으로 채워져있을 수 있습니다.
배열을 정의하는 함수로 회신하면 어떻게됩니까? 전역 DATA 세그먼트는 각 함수가 작동하도록 자체 배열을 가질 수 있도록 각 함수 호출에 대해이 배열의 복사본을 가져야합니다. 컴파일러는 최대 재귀가 발생할지 결정하기 위해 코드를 실행해야합니다.
또한 프로그램에 여러 개의 스레드가 있고 각각이 foo를 호출하면 어떻게됩니까? 갑자기 잠겨 야하는 데이터를 공유했습니다. 잠금은 초기화를 제거하는 것보다 더 많은 성능 문제점을 야기 할 수 있습니다.
나는 너무 많이 걱정하지 않을 것이다. 대부분의 플랫폼은 매우 효율적인 메모리 채우기 방법을 가지고 있습니다. 당신이 그것을 프로파일하고 문제를 발견하지 않는다면, 그것을 땀을 내지 마라.
다른 사람들이 지적한 것처럼 가정 2가 잘못되었습니다. 스택 변수는 O (1) 시간에 런타임에 할당되지만 디버그 빌드를 실행하지 않는 한 정상적으로 초기화되지 않습니다.
PUSH ebp
MOV ebp, esp
SUB esp, 10
// function body code goes here
여기서 스택 포인터 'esp'는 일부 로컬 함수 변수를위한 공간을 만들기 위해 10 씩 감소합니다. 그것들은 본격적으로되지 않습니다 ... 그것은 반복을 필요로합니다.
This 기사는 충분히 친근 해 보입니다.
어떤 문맥입니까? 공전? – user7116
한 문단에서 O 표기법과 "컴파일 시간"에 대해 이야기하는 것은 의미가 없습니다. –
@ n.m. 나는 컴파일 시간이나 퍼포먼스에서와 같이 "컴파일 시간"을 언급하지 않고 컴파일 시점, 즉 컴파일 단계에서 어떤 정보가 있는지를 나타 내기 위해 "컴파일 시간"을 언급합니다. –