"最后100个字节"采访场景

Question

我前几天在接受采访时得到了这个问题,想知道一些最好的答案(我没有很好地回答哈哈):

场景:有一个网页正在监视通过某个网络发送的字节.每次发送一个字节时,都会调用recordByte()函数传递该字节,这可能每天发生数十万次.此页面上有一个按钮,按下时会显示传递给屏幕上的recordByte()的最后100个字节(它通过调用下面的print方法来完成).

以下代码是我给出的并要求填写的代码:

public class networkTraffic {
    public void recordByte(Byte b){
    }
    public String print() {
    }
}

存储100个字节的最佳方法是什么？一个列表？好奇如何做到最好.

Answer 1

像这样的东西(循环缓冲区):

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

使用循环缓冲区的好处:

1. 您可以静态保留空间.在实时网络应用程序(VoIP,流媒体......)中,这通常是因为您不需要存储传输的所有数据,而只需要存储包含要处理的新字节的窗口.
2. 速度很快:可以使用读写成本为O(1)的阵列实现.

Answer 2

我不知道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
  }
}  

Answer 3

循环缓冲区使用数组:

1. 100字节的数组
2. 跟踪头部索引的位置
3. 用于recordByte()把当前字节在A [i]和I = I + 1%100;
4. 对于print(),返回子阵列(i + 1,100)与子阵列(0,i)连接

队列使用链表(或java队列):

1. 用于recordByte()添加新字节到最后
2. 如果新长度大于100,则删除第一个元素
3. 对于 print()简单的打印列表

Answer 4

这是我的代码.它可能看起来有点模糊,但我很确定这是最快的方法(至少它是在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--没有临时变量更快.
• 我倒数到0,因为那时我不必_ary.length每次都在通话中,而是在第一次进入时每100次.也许这不是必需的,编译器可以处理它.
• 如果对recordByte()的调用少于100次,则其余为零.