Come avvolgere in modo efficiente l'indice di un buffer circolare a dimensione fissa

Question

Ho un buffer circolare di dimensioni fisse (implementato come array): al momento dell'inizializzazione, il buffer viene riempito con il numero massimo specificato di elementi che consente l'uso di un indice di posizione singola per tenere traccia della nostra posizione attuale nel cerchio.

Che cos'è un modo efficace per accedere a un elemento nel buffer circolare? Ecco la mia soluzione attuale:

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]; 
} 

Alcune definizioni:
end_index è l'indice dell'elemento immediatamente dopo l'ultimo elemento nel cerchio (che sarebbe anche essere considerato uguale al START_INDEX, o il primo elemento di il cerchio).
buffer_size è la dimensione massima del buffer.

Answer 1

Assicurarsi che il buffer sia sempre una potenza di due lunghi e mascherare i bit superiori.

Answer 2

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

Vedere modulo operation per maggiori informazioni sul modulus operator (%).

Answer 3

Sarà dipende un po 'sul processore, ma è probabilmente almeno la pena di provare qualcosa di simile return (end_index + index) % buffer_size;

Answer 4

FWIW, si può sempre fare un allineamento parallelo: i = next[i];

Ma, in realtà, ho sempre appena fatto questo: i++; if (i >= n) i = 0; O i = (i+1) % n;

Indipendentemente da ciò, sarei davvero sorpreso se questo è mai un problema significativo delle prestazioni.

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); 
} 

I risultati di performance (zecche):

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

Così sembra che il modulo è la scelta migliore, in quanto non richiede alcuna restrizione alla dimensione della buffer.

Answer 6

migliore che è venuta in mente è:

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

(Se c'è bisogno di lavorare con i numeri negativi)