“最后100字节”访谈情景
我有一天在面试中得到了这个问题，想知道一些最好的答案（我没有很好回答哈哈）：
场景：有一个网页正在监视通过某个networking发送的字节。 每次发送一个字节时，recordByte（）函数被称为传递该字节，这可能每天发生数十万次。 这个页面上有一个button，当按下时显示传递给屏幕上的recordByte（）的最后100个字节（通过调用下面的print方法来实现）。
下面的代码是我给的，并要求填写：
public class networkTraffic { public void recordByte(Byte b){ } public String print() { } } 什么是最好的方法来存储100个字节？ 一个列表？ 好奇如何最好地做到这一点。
像这样的东西（ 循环缓冲区 ）：
byte[] buffer = new byte[100]; int index = 0; public void recordByte(Byte b) { index = (index + 1) % 100; buffer[index] = b; } public void print() { for(int i = index; i < index + 100; i++) { System.out.print(buffer[i % 100]); } }
使用循环缓冲区的好处：
- 您可以静态保留空间。 在实时networking应用程序（VoIP，stream媒体…）中，通常这样做是因为您不需要存储传输的所有数据，而只需要包含要处理的新字节的窗口。
- 速度快：可以用读写成本为O（1）的数组来实现。
我不知道java，但是必须有一个队列的概念，在这个概念中，队列中的条目数量达到100个，然后排队一个字节，然后排队。
public void recordByte(Byte b) { if (queue.ItemCount >= 100) { queue.dequeue(); } queue.enqueue(b); }
你可以通过偷看的项目打印：
public String print() { foreach (Byte b in queue) { print("X", b); // some hexadecimal print function } }
使用数组的循环缓冲区
- 100字节的数组
- 跟踪头指数在哪里
- 对于
recordByte()把当前字节放在A [i]和i = i + 1％100中; - 对于
print()，返回子数组（i + 1，100）与子数组（0，i）连接
队列使用链表（或Java队列）：
- 对于
recordByte()添加新的字节结束 - 如果新的长度超过100，则删除第一个元素
- 对于
print()只需打印列表
这是我的代码。 它可能看起来有点模糊，但我很确定这是最快的方法（至less它会在C ++中，不太确定Java）：
public class networkTraffic { public networkTraffic() { _ary = new byte[100]; _idx = _ary.length; } public void recordByte(Byte b){ _ary[--_idx] = b; if (_idx == 0) { _idx = _ary.length; } } private int _idx; private byte[] _ary; }
有些要注意的地方：
- 调用recordByte（）时没有分配/释放数据。
- 我没有使用％，因为它比直接比较慢，使用if（分支预测也可能在这里帮助）
-
--_idx比_idx--更快，因为不涉及临时variables。 - 我向后计数到0，因为那样我不必每次在调用中都得到
_ary.length，但是在第一次进入时只有100次。 也许这不是必要的，编译器可以照顾它。 - 如果有less于100个调用recordByte（），其余的是零。
最简单的就是把它推到一个数组中。 数组可容纳的最大大小是100个字节。 不断添加字节，因为它们正在stream出networking。 在前100个字节在数组中后，当第101个字节到来时，删除头部的字节（即0）。 继续这样做。 这基本上是一个队列。 FIFO的概念。 在下载完成之后，您剩下最后的100个字节。
不仅在下载之后，而且在任何给定的时间点，这个数组将有最后的100个字节。
@Yottagray没有得到问题的地方？ 似乎有一些通用的方法（数组，循环数组等）和一些特定于语言的方法（byteArray等）。 我错过了什么吗？
具有非阻塞I / O的multithreading解决scheme：
private static final int N = 100; private volatile byte[] buffer1 = new byte[N]; private volatile byte[] buffer2 = new byte[N]; private volatile int index = -1; private volatile int tag; synchronized public void recordByte(byte b) { index++; if (index == N * 2) { //both buffers are full buffer1 = buffer2; buffer2 = new byte[N]; index = N; } if (index < N) { buffer1[index] = b; } else { buffer2[index - N] = b; } } public void print() { byte[] localBuffer1, localBuffer2; int localIndex, localTag; synchronized (this) { localBuffer1 = buffer1; localBuffer2 = buffer2; localIndex = index; localTag = tag++; } int buffer1Start = localIndex - N >= 0 ? localIndex - N + 1 : 0; int buffer1End = localIndex < N ? localIndex : N - 1; printSlice(localBuffer1, buffer1Start, buffer1End, localTag); if (localIndex >= N) { printSlice(localBuffer2, 0, localIndex - N, localTag); } } private void printSlice(byte[] buffer, int start, int end, int tag) { for(int i = start; i <= end; i++) { System.out.println(tag + ": "+ buffer[i]); } }
只是为了它。 如何使用ArrayList<Byte> ？ 说为什么不呢？
public class networkTraffic { static ArrayList<Byte> networkMonitor; // ArrayList<Byte> reference static { networkMonitor = new ArrayList<Byte>(100); } // Static Initialization Block public void recordByte(Byte b){ networkMonitor.add(b); while(networkMonitor.size() > 100){ networkMonitor.remove(0); } } public void print() { for (int i = 0; i < networkMonitor.size(); i++) { System.out.println(networkMonitor.get(i)); } // if(networkMonitor.size() < 100){ // for(int i = networkMonitor.size(); i < 100; i++){ // System.out.println("Emtpy byte"); // } // } } }
