質問
最も古いエントリがいっぱいになったときに上書きする循環リストを実装するにはどうすればよいですか?
少しの背景として、GWT内で循環リストを使用します。サードパーティのライブラリを使用することは、私が望むものではありませんではありません。
解決
Cで表される非常に単純な実装。循環バッファスタイルのFIFOキューを実装します。キューサイズ、キューデータ、およびキューインデックス(インとアウト)を含む構造を作成することにより、より汎用的にすることができます。これらは、キューに追加または削除するデータと共に渡されます。これらの同じルーチンは、複数のキューを処理できます。また、これにより任意のサイズのキューが許可されますが、2のべき乗を使用してコードをさらにカスタマイズする場合は高速化を使用できます。
/* Very simple queue
* These are FIFO queues which discard the new data when full.
*
* Queue is empty when in == out.
* If in != out, then
* - items are placed into in before incrementing in
* - items are removed from out before incrementing out
* Queue is full when in == (out-1 + QUEUE_SIZE) % QUEUE_SIZE;
*
* The queue will hold QUEUE_ELEMENTS number of items before the
* calls to QueuePut fail.
*/
/* Queue structure */
#define QUEUE_ELEMENTS 100
#define QUEUE_SIZE (QUEUE_ELEMENTS + 1)
int Queue[QUEUE_SIZE];
int QueueIn, QueueOut;
void QueueInit(void)
{
QueueIn = QueueOut = 0;
}
int QueuePut(int new)
{
if(QueueIn == (( QueueOut - 1 + QUEUE_SIZE) % QUEUE_SIZE))
{
return -1; /* Queue Full*/
}
Queue[QueueIn] = new;
QueueIn = (QueueIn + 1) % QUEUE_SIZE;
return 0; // No errors
}
int QueueGet(int *old)
{
if(QueueIn == QueueOut)
{
return -1; /* Queue Empty - nothing to get*/
}
*old = Queue[QueueOut];
QueueOut = (QueueOut + 1) % QUEUE_SIZE;
return 0; // No errors
}
他のヒント
リンクリストを使用します。頭と尾の別々のポインターを維持します。リストの先頭からポップし、末尾にプッシュします。円形にしたい場合は、新しい尾が常に頭を指すようにしてください。
リンクリストを使用してFIFOを実装する理由を理解できますが、なぜ循環リストにするのですか?
固定長の循環リストが必要な場合。 (動的)配列を使用できます。ハウスキーピングには2つの変数を使用します。 1つは次の要素の位置用、もう1つは要素の数をカウントするためのものです。
Put:自由な場所に要素を置きます。位置(モジュロ長)を移動します。カウントがリストの長さに等しくない限り、カウントに1を追加します。 取得:count> 0の場合のみ。位置を左に移動します(モジュロ長)。カウントを減らします。
配列を使用して、変数Pを最初に使用可能な位置に保持します。
新しい要素を追加するたびにPを増やします。
配列内のPの同等のインデックスを知るには、(P%n)を実行します。nは配列のサイズです。
これをマイクロコントローラーに使用しています。 コードを簡単にするために、1バイトは埋められません。 別名サイズ-1は実際には全容量です。
fifo_t* createFifoToHeap(size_t size)
{
byte_t* buffer = (byte_t*)malloc(size);
if (buffer == NULL)
return NULL;
fifo_t* fifo = (fifo_t*)malloc(sizeof(fifo_t));
if (fifo == NULL)
{
free(buffer);
return NULL;
}
fifo->buffer = buffer;
fifo->head = 0;
fifo->tail = 0;
fifo->size = size;
return fifo;
}
#define CHECK_FIFO_NULL(fifo) MAC_FUNC(if (fifo == NULL) return 0;)
size_t fifoPushByte(fifo_t* fifo, byte_t byte)
{
CHECK_FIFO_NULL(fifo);
if (fifoIsFull(fifo) == true)
return 0;
fifo->buffer[fifo->head] = byte;
fifo->head++;
if (fifo->head == fifo->size)
fifo->head = 0;
return 1;
}
size_t fifoPushBytes(fifo_t* fifo, byte_t* bytes, size_t count)
{
CHECK_FIFO_NULL(fifo);
for (uint32_t i = 0; i < count; i++)
{
if (fifoPushByte(fifo, bytes[i]) == 0)
return i;
}
return count;
}
size_t fifoPopByte(fifo_t* fifo, byte_t* byte)
{
CHECK_FIFO_NULL(fifo);
if (fifoIsEmpty(fifo) == true)
return 0;
*byte = fifo->buffer[fifo->tail];
fifo->tail++;
if (fifo->tail == fifo->size)
fifo->tail = 0;
return 1;
}
size_t fifoPopBytes(fifo_t* fifo, byte_t* bytes, size_t count)
{
CHECK_FIFO_NULL(fifo);
for (uint32_t i = 0; i < count; i++)
{
if (fifoPopByte(fifo, bytes + i) == 0)
return i;
}
return count;
}
bool fifoIsFull(fifo_t* fifo)
{
if ((fifo->head == (fifo->size - 1) && fifo->tail == 0) || (fifo->head == (fifo->tail - 1)))
return true;
else
return false;
}
bool fifoIsEmpty(fifo_t* fifo)
{
if (fifo->head == fifo->tail)
return true;
else
return false;
}
size_t fifoBytesFilled(fifo_t* fifo)
{
if (fifo->head == fifo->tail)
return 0;
else if ((fifo->head == (fifo->size - 1) && fifo->tail == 0) || (fifo->head == (fifo->tail - 1)))
return fifo->size;
else if (fifo->head < fifo->tail)
return (fifo->head) + (fifo->size - fifo->tail);
else
return fifo->head - fifo->tail;
}
キューはキャッシュを作成する最良の方法ではないと思います。あなたは本当に速くなるためにあなたのキャッシュになりたいです!そして、キャッシュを本当に小さくしたい場合やメモリが本当に限られている場合を除き、キューの線形スキャンを実行する方法はありません。
非常に小さいキャッシュや遅いキャッシュが必要ない場合、リンクリスト内のノードへのハッシュマップ値を持つリンクリストを使用するのが良い方法です。いつでもヘッドを削除でき、要素にアクセスするたびに、それを削除してリストのヘッドに入れることができます。アクセスするには、直接取得するか、O(1)のキャッシュにあるかどうかを確認します。要素の削除もO(1)であり、リストの更新も同様です。
例については、JavaのLinkedHashMapをご覧ください。
http://docs.oracle.com/ javase / 6 / docs / api / java / util / LinkedHashMap.html
java を使用して、動的に増加/減少する循環キューを作成するエレガントな方法です。
コードの大部分を簡単にコメントできるように&amp;迅速な理解。役に立てば幸いです:)
public class CircularQueueDemo {
public static void main(String[] args) throws Exception {
CircularQueue queue = new CircularQueue(2);
/* dynamically increasing/decreasing circular queue */
System.out.println("--dynamic circular queue--");
queue.enQueue(1);
queue.display();
queue.enQueue(2);
queue.display();
queue.enQueue(3);
queue.display();
queue.enQueue(4);
queue.display();
queue.deQueue();
queue.deQueue();
queue.enQueue(5);
queue.deQueue();
queue.display();
}
}
class CircularQueue {
private int[] queue;
public int front;
public int rear;
private int capacity;
public CircularQueue(int cap) {
front = -1;
rear = -1;
capacity = cap;
queue = new int[capacity];
}
public boolean isEmpty() {
return (rear == -1);
}
public boolean isFull() {
if ((front == 0 && rear == capacity - 1) || (front == rear + 1))
return true;
else
return false;
}
public void enQueue(int data) {
if (isFull()) { //if queue is full then expand it dynamically
reSize();
enQueue(data);
} else { //else add the data to the queue
if (rear == -1) //if queue is empty
rear = front = 0;
else if (rear == capacity) //else if rear reached the end of array then place rear to start (circular array)
rear = 0;
else
rear++; //else just incement the rear
queue[rear] = data; //add the data to rear position
}
}
public void reSize() {
int new_capacity = 2 * capacity; //create new array of double the prev size
int[] new_array = new int[new_capacity];
int prev_size = getSize(); //get prev no of elements present
int i = 0; //place index to starting of new array
while (prev_size >= 0) { //while elements are present in prev queue
if (i == 0) { //if i==0 place the first element to the array
new_array[i] = queue[front++];
} else if (front == capacity) { //else if front reached the end of array then place rear to start (circular array)
front = 0;
new_array[i] = queue[front++];
} else //else just increment the array
new_array[i] = queue[front++];
prev_size--; //keep decreasing no of element as you add the elements to the new array
i++; //increase the index of new array
}
front = 0; //assign front to 0
rear = i-1; //assign rear to the last index of added element
capacity=new_capacity; //assign the new capacity
queue=new_array; //now queue will point to new array (bigger circular array)
}
public int getSize() {
return (capacity - front + rear) % capacity; //formula to get no of elements present in circular queue
}
public int deQueue() throws Exception {
if (isEmpty()) //if queue is empty
throw new Exception("Queue is empty");
else {
int item = queue[front]; //get item from front
if (front == rear) //if only one element
front = rear = -1;
else if (front == capacity) //front reached the end of array then place rear to start (circular array)
front = 0;
else
front++; //increment front by one
decreaseSize(); //check if size of the queue can be reduced to half
return item; //return item from front
}
}
public void decreaseSize(){ //function to decrement size of circular array dynamically
int prev_size = getSize();
if(prev_size<capacity/2){ //if size is less than half of the capacity
int[] new_array=new int[capacity/2]; //create new array of half of its size
int index=front; //get front index
int i=0; //place an index to starting of new array (half the size)
while(prev_size>=0){ //while no of elements are present in the queue
if(i==0) //if index==0 place the first element
new_array[i]=queue[front++];
else if(front==capacity){ //front reached the end of array then place rear to start (circular array)
front=0;
new_array[i]=queue[front++];
}
else
new_array[i]=queue[front++]; //else just add the element present in index of front
prev_size--; //decrease the no of elements after putting to new array
i++; //increase the index of i
}
front=0; //assign front to 0
rear=i-1; //assign rear to index of last element present in new array(queue)
capacity=capacity/2; //assign new capacity (half the size of prev)
queue=new_array; //now queue will point to new array (or new queue)
}
}
public void display() { //function to display queue
int size = getSize();
int index = front;
while (size >= 0) {
if (isEmpty())
System.out.println("Empty queue");
else if (index == capacity)
index = 0;
System.out.print(queue[index++] + "=>");
size--;
}
System.out.println(" Capacity: "+capacity);
}
}
出力:
-動的循環キュー-
1 =&gt;容量:2
1 =&gt; 2 =&gt;容量:2
1 =&gt; 2 =&gt; 3 =&gt;容量:4
1 =&gt; 2 =&gt; 3 =&gt; 4 =&gt;容量:4
4 =&gt; 5 =&gt;容量:2