고정 크기 순환 버퍼의 인덱스를 효율적으로 줄이는 방법

Question

고정 크기 순환 버퍼 (배열로 구현 됨)가 있습니다. 초기화시 버퍼가 지정된 최대 수의 요소로 채워 지므로 서클의 현재 위치를 추적하기 위해 단일 위치 인덱스.

순환 버퍼의 요소에 액세스하는 효율적인 방법은 무엇입니까?

int GetElement(int index) 
{ 
    if (index >= buffer_size || index < 0) 
    { 
     // some code to handle the case 
    } 
    else 
    { 
     // wrap the index 
     index = end_index + index >= buffer_size ? (index + end_index) - buffer_size : end_index + index; 
    } 

    return buffer[index]; 
} 

일부 정의 :
end_index 즉시 원의 마지막 요소 (그것은 또한 START_INDEX, 또는 첫 번째 요소의 같은 간주됩니다 후 요소의 인덱스입니다 여기에 내 현재의 솔루션입니다 동호회).
buffer_size은 버퍼의 최대 크기입니다.

Answer 1

버퍼가 항상 2의 제곱수인지 확인하고 맨 위 비트를 마스크 아웃하십시오.

Answer 2

int GetElement(int index) 
{ 
    return buffer[(end_index + index) % buffer_size]; 
} 

는 modulus operator (%)에 대한 자세한 내용은 modulo operation 참조하십시오.

Answer 3

가 프로세서에 다소 의존 하겠지만, 그것은 return (end_index + index) % buffer_size;

Answer 4

FWIW 같은 적어도 가치가 시도하는 것을 아마, 당신은 병렬 배열 할 항상 수 : 정말, 난 항상했습니다, i = next[i];

하지만를 이 이제까지 상당한 성능 문제가되는 경우 i++; if (i >= n) i = 0; 또는

i = (i+1) % n;에 관계없이, 내가 정말 놀랄 것 : 그냥이 완료.

Answer 5

I tested all 3 versions :

// plain wrap 
public static int WrapIndex(int index, int endIndex, int maxSize) 
{ 
    return (endIndex + index) > maxSize ? (endIndex + index) - maxSize : endIndex + index; 
} 

// wrap using mod 
public static int WrapIndexMod(int index, int endIndex, int maxSize) 
{ 
    return (endIndex + index) % maxSize; 
} 

// wrap by masking out the top bits 
public static int WrapIndexMask(int index, int endIndex, int maxSize) 
{ 
    return (endIndex + index) & (maxSize - 1); 
} 

의 실적은 (틱) :

Plain: 25 Mod: 16 Mask: 16 (maxSize = 512) 
Plain: 25 Mod: 17 Mask: 17 (maxSize = 1024) 
Plain: 25 Mod: 17 Mask: 17 (maxSize = 4096) 

를 그것의 크기에 어떤 제한을 필요로하지 않기 때문에 그래서, 계수가 더 나은 선택 인 것 같다 완충기. 내가 함께 왔어요 최저

Answer 6

은 다음과 같습니다

는

public static int Wrap(int index, int n) 
{ 
    return ((index % n) + n) % n; 
}