Delphi에서 배열 초기화의 빠른 방법

Question

저는 Delphi 애플리케이션에서 모든 성능 비트를 집어 넣으려고하고 있습니다. 이제 동적 배열과 함께 작동하는 절차를 밟았습니다. 가장 느린 라인은

입니다. SetLength (Result, Len);

동적 배열을 초기화하는 데 사용됩니다. SetLength 프로 시저의 코드를 살펴보면 최적은 아니라는 것을 알 수 있습니다. 다음과 같이 호출 시퀀스는 다음

_DynArraySetLength -> DynArraySetLength

DynArraySetLength는 (초기화 제로 임) 다음과 같은시 초기화 불필요하다는 ReallocMem 사용 배열 길이를 얻는다.

나는 동적 배열을 항상 초기화하기 위해 SetLength를하고 있었다. 어쩌면 내가 뭔가를 놓친거야? 이 작업을 수행하는 더 빠른 방법이 있습니까?

편집 : 주요 알고리즘을 설명하는 것은 많은 공간이 필요하며 실제로는 그 중 일부를 최적화하려고하기 때문에 불필요합니다. 일반적으로 그것은 Vehicle Routing Problem (http://en.wikipedia.org/wiki/Vehicle_routing_problem)입니다. 모든 데이터를 유지해야하므로 할당량이 필요합니다. Probalby는 내가 여기에 영리한 데이터 구조를 생각할 수 있다면 도움이 될 것이지만, 내가 생각할 수있는 어떤 것이라도 코드의 복잡성을 크게 증가시킬 것이다. 기본적으로 알고리즘 수준에서 할 수있는 모든 작업을 수행 했으므로 이제는 저수준의 모든 것을 얻을 수 있도록 노력하고 있습니다. 그래서 이것은 다소 좁은 질문입니다 :이 특별한 전화를 더할 수있는 가능성이 있습니까? 그리고 나는 이것을하기 위해 SetLength 코드에 기초한 나 자신의 초기화 함수를 작성할 필요가 있다고 생각한다. 그리고 그것을 인라인으로 만드십시오.

Answer 1

는 최대 썼다 :

내가 엄청나게 한 시간 SetLength를 수행하는 기능 (결과, 렌) 호출해야합니다.

함수를 어떻게 사용하는지 확인하십시오.이 할당 함수에 수천 가지 고유 한 호출이 실제로 필요합니까? Francois가 제안한대로 통화 횟수를 줄이기 위해 코드를 재 설계 할 수 있습니까?

실제로 함수에 대한 수천 개의 별개의 호출이 필요하고 속도를 높여야하는 경우 동적 배열을 유지하고 다른 구조를 사용해야합니다.

하지만 그렇게하기 전에 전체 디버깅 지옥을 입력하기 전에 나는 Francois 제안에 강력하게 참여하고 코드를 재 설계하려고합니다.

알고리즘에 대해 좀 더 알려주시겠습니까? 그래픽 3D 구조를 다루는 것입니까?

[편집] 좋아, NP- 완전한 문제를 해결하는 경우, 나는 가능한 한 많이 할당하지 않도록 노력할 것입니다.

대부분의 시간, 당신은 당신의 배열/스택/구조의 크기에 상한을 줄 수

- 예 : #cities, #vehicles + #drivers, #roads * #cities ...

들어 그 부분들, 나는 가능한 한 가장 큰 배열을 한 번 할당하고, 처음 n 개의 행만을 사용한다는 사실을 수동으로 처리 할 것을 제안합니다.

나중에 계산할 수있는 시간을 감안할 때 n^2 또는 n^3으로 구조를 할당 할 수도 있습니다.

SetLength 최적화 : 제안하는 것이 의미가 있습니다.

그러나 동적 배열이 주로 "자동 생성자"의미론 때문에 델파이 코드를 작성하는 데 적합하다면 - IMHO는 고성능 계산에 잘 맞지 않습니다 - 참조 계산은 RTT에 크게 의존합니다 당신은 지금 당장 놀라워 할 것입니다 ...
당신이 제안하는 것은 동적 배열 의미론의 변화입니다. "데이터 유형 변경"솔루션이 실제로는 불가능하다는 것을 확인한 후 & 디버그를 작성하십시오.

Answer 2

댓글에 더 많은 댓글을 달았지만 댓글에 큰 코드 블록을 게시하는 것이 그리 좋지 않기 때문에 대신 여기에 게시합니다. 당신은 당신이 결국 끝낼 얼마나 많은 요소 모르는 경우

때때로, 다음과 같은 코드를 작성하는 유혹이 될 수 있습니다

var 
    Arr: array of cardinal; 

procedure AddElement(const NewElement: cardinal); 
begin 
    SetLength(Arr, length(Arr) + 1); 
    Arr[high(Arr)] := NewElement; 
end; 

이 다음 메모리 요구에 매우 나쁜 새 요소를 추가 할 때마다 다시 할당됩니다. 훨씬 더 나은 접근법 (가능한 경우)은 MAX_ELEMENTS = 100000과 같이 요소 수에 대한 상한을 찾는 것입니다. 다음 초기 길이를 설정 :

이

SetLength(Arr, MAX_ELEMENTS); 

는 그런 다음

var 
    ActualNumberOfElements: cardinal = 0; 

같은 변수를 생성하고이 배열 충전이 완료되면, 간단하게 절단

procedure AddElement(const NewElement: cardinal); 
begin 
    Arr[ActualNumberOfElements] := NewElement; 
    inc(ActualNumberOfElements); 
end; 

쓰기 :

SetLength(Arr, ActualNumberOfElements); 

Answer 3

nly는 그것을 한 번 호출하면 오랜 시간이 걸리고 사용 가능한 RAM보다 더 많은 RAM을 요청하게되므로 OS가 다른 것들을 스왑 아웃하여 사용자를위한 공간을 확보하게됩니다. 수정 : 더 많은 RAM을 추가하고 더 작은 어레이를 사용하십시오.

루프에서 호출하는 경우 "realloc"이 문제입니다. 당신이 그것을 호출 할 때마다, 배열의 길이를 조금씩 늘리면, Delphi는 전체 배열을 다시 할당하고, 이전 배열에서 새로운 배열로 모든 것을 복사합니다. 정확하지는 않습니다.

Answer 4

는 "조기 최적화는 모든 악의 뿌리입니다."
난 당신이 평생 초기화에 한 번 걱정해야 할 것이다 의심 ... 당신은 엄청나게 많은 시간을 필요하지 않은 경우입니다
다음 코드 재 디자인을 제안합니다.

Answer 5

SetLength의 가장 느린 부분은 "unnessesary calls"가 아니며 메모리 관리자가 수행하는 메모리 할당입니다 (원본 포인터가 nil이므로 간단한 GetMem이됩니다).

그래서 어떤 메모리 관리자를 사용합니까? 혹시 FastMM이없는 D7에 있습니까?

FastMM을 설치하고 조금 도움이되는지 확인하십시오.

Answer 6

SetLength이 포함 된 함수를 호출하는 대신 오히려 저장 장치를 미리 할당하고 사전 할당 된 배열을 함수에 전달하십시오.이것은 내부 루프 내부에 SetLength를 호출하는 것보다 크게 빨라집니다

const 
    NUM_ARRAYS = 1000; 
    ARRAY_SIZE = 1000; 
type 
    TMyArray = array [0..ARRAY_SIZE] of Integer; 
var 
    MyStorage: array[0..NUM_ARRAYS] of TMyArray; 

procedure DoWork(var AArray: TMyArray); 
begin 
    Blah; 
end; 

procedure MainLoop; 
var 
    i: Integer; 
begin 
    for i := 0 to High(MyStorage) do 
    begin 
    DoWork(MyStorage[i]); 
    end; 
end; 

: 하나 개는 이러한 방법이 같은 것입니다. 주의 할 점은 하드웨어에 너무 많은 메모리를 사용한다는 것입니다.