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中的循环缓冲区？

回答

相关问题