원형 배열을 옮기기

Question

나는 원형 배열을 메모리에 옮겨야한다는 숙제가있다.

나는 다음과 같은 C++ 구문을 사용하여 작업을 수행 한 : 사람이 -n 단위로 원형 배열을 변화의 더 나은, 더 효율적인 방법이 있는지 궁금 해서요

while (r < 0) // rotate negatively. 
{ 
    if (i == top+1) 
    { 
     current->n = items[top+1].n; 
     items[top+1].n = items[back-1].n; 
    } 
    midPtr->n = items[++i].n; 
    items[i].n = current->n; 

    if (i == back-1) 
    { 
      items[back-1].n = current->n; 
      i = 0; 
      r++; continue; 
    } 
    else 
    { 
      current->n = items[++i].n; 
      items[i].n = midPtr->n; 
      if (i == back-1) 
      { 
        i = 0; 
        r++; continue; 
      } 
    } 
} 

.

ptr 변수 사이에 불필요한 전송 을 수행하고있는 것처럼 보였기 때문에.

Answer 1

코드를주지 않고도 (이 모든 숙제가 끝난 후)이 점을 고려하십시오 ... 원형 배열은 메모리의 n 단위와 배열의 "시작"에 대한 포인터의 할당입니다. 배열의 첫 번째 항목은 할당 된 메모리의 가장 낮은 주소 일 필요는 없지만 논리적 인 첫 번째 요소를 나타내는 배열의 항목에 대한 포인터/색인 일뿐입니다. 배열을 옮기는 것은 단순히 첫 번째 요소의 인덱스를 이동하는 것입니다. 루프없이 수행 할 수 있습니다. 단순히 데이터 구조의 순환 특성을 고려하여 인덱스가 얼마나 멀리 이동해야하는지 계산하십시오.

Answer 2

Finnicky,하지만 필자는 OK 일 것입니다. (단 하나의 오류가있을 수있는 곳이 너무 많아서 단위 테스트가 많이 이루어 졌는지 확인하십시오 .--). 개인적으로, 그러한 문제에 직면 할 때마다 (숙제의 시간은 과거 나에게 훨씬 멀었다 ;-) 나는 오래 전 그리리스 (Gries)에서 배운 것에 중점을 두는 경향이있다. 배열의 내부에있는 "스왑 두 블록"작업은 단일 기본 요소 인 "블록 반전"을 사용하여 매우 효과적으로 (선형 시간, 추가 메모리 0 개) 수행 할 수 있습니다.

start 
    . 
    . 
beg1 
    . 
    . 
end1 
    . 
    . 
beg2 
    . 
    . 
end2 
    . 
    . 
finis 

을 당신의 작업은 블록과 블록 (beg1..end1)를 교환하는 것입니다 (beg2..end2) : 메모리의 일반 컴팩트 한 조각과 배열을 떠올리 ... 당신은 말한다. 하세요 Gries 액 (극한 포함하여 각각의 경우 블록의 소정 (begin..end)에서)이다

1. invert (beg1..end2) 
2. invert (end2..beg2) 
3. invert (end2+1..end1-1) 
4. invert (end1..beg1) 

... 그 전부 -) 반전 (X..Y 이후)는 (Y-X 소요 +1) 기본 동작 인 경우 Gries 솔루션은 이러한 동작을 2 * (end2-beg1 + 1) 가지게됩니다. "최소 가능 기본 동작"솔루션과 비교 한 상대적 오버 헤드는 일부 특수한 경우에 높을 수 있습니다 예를 들어 정확히 같은 길이의 두 블록).하지만 개괄적이지 않은 문제에 대한 보편성과 부족함에 대한 걱정은 나에게 가치있는 것입니다.

"회전"은 "스왑 2 블록"의 특별한 경우입니다. 그래서 내 본능은 내가 "반전"원시적 (어쨌든 프로그램하기가 훨씬 쉽다 ;-)을 보장하고 그것을 사용하는 것이다.

하지만 그렇다면 TA가 분명히 평가할 방법이 아니라 명확하고 정확하며 빠르다는 사실에 대해서만 염려해야합니다.