Java中的循環緩衝區？

我需要一個類似deque的數據結構，我認爲它被稱爲循環緩衝區。Java中的循環緩衝區？

這就是我所做的。

public class MyStack { 


    byte[][] orders = { {0, 1, 2, 3}, {1, 2, 3, 0}, {2, 3, 0, 1}, {3, 0, 1, 2} }; 

    byte state  = 0; 

    int[] data  = {1, 2, 3, 4}; 


    void swap(int value){   
     data[state] = value; 

     if(state == 3){ 
      state = 0; 

     }else{ 
      state ++; 

     }  
    } 

    int[] dump(){ 

     int[] output = { 
          data[ orders[state][0] ], 
          data[ orders[state][1] ], 
          data[ orders[state][2] ], 
          data[ orders[state][3] ], 
         }; 

     return output; 
    } 

}

這裏的輸出正是我需要的功能類型。它基本上是一個長度爲四的窗口，通過一個無限的離散空間或沿着一條數字線移動。

我的問題是：這個解決方案是否高效？是否有爲此功能而設計的內置庫？如果是這樣，是否值得使用？

來源

2016-02-28 bigcodeszzer

沒有'push'或'pop'操作 - 這是如何實現堆棧ADT？如果你的數據結構不打算像堆棧那樣工作，那麼你就會把它弄糊塗，否則你會迷惑人。 – Joni

我不確定一個堆棧的手動實現如何與內置的實現（經過深入審查）相比較。我確實認爲真正的問題是你遇到了哪些性能/使用問題？如果實現一個堆棧不是你的目標 - 我相信這是不值得的不使用現有的庫的開銷。 –

@Joni推送和彈出都在交換中同時完成。 – bigcodeszzer

circular buffer的典型實現使用兩個索引來標記隊列的第一個和最後一個元素。沒有必要明確存儲狀態，因爲enqueue和dequeue可以通過索引計算完成。 swap方法的更好名稱是rotate。

您可以刪除orders陣列和改變dump實施：

int[] output = { 
         data[ (state+0)%4 ], 
         data[ (state+1)%4 ], 
         data[ (state+2)%4 ], 
         data[ (state+3)%4 ], 
        };

來源

2016-02-28 08:22:08 Joni

我要測試這個。但我想知道，你認爲存儲狀態比每次迭代運行四次模數計算要快嗎？ – bigcodeszzer

這些功能可能有多達10個或20個同時運行。 – bigcodeszzer

如果性能對您很重要，您應該對其進行測試。訪問外部陣列會導致高速緩存未命中的危險。 4的模數可以優化爲按位AND＆＆3。我的直覺是計算將比使用數組更快。 – Joni

一個改進這個就可以了，刪除訂單大小爲n的二維數組。

byte[][] orders = { {0, 1, 2, 3}, {1, 2, 3, 0}, {2, 3, 0, 1}, {3, 0, 1, 2} };

因爲如果知道的狀態下，則該訂單陣列也可以是動態的由式

for(int i =0; i<data.length; i++){ 
    output[i] = data[(state+i)%data.length]; 
}

確定這可以被用來返回輸出。

來源

2016-02-28 08:36:40 PyThon

雖然它給你一種改進的感覺，但我更加好奇地知道你需要這種類型的ADT的情況，我很感謝你能否提供你的問題需求的一些描述。 – PyThon

Java中的循環緩衝區？

回答

相關問題