Escenario de entrevista "Últimos 100 bytes"

Recibí esta pregunta en una entrevista el otro día y me gustaría saber algunas de las mejores respuestas posibles (no respondí muy bien jaja):

Escenario: hay una página web que supervisa los bytes enviados a través de una red. Cada vez que se envía un byte, se llama a la función recordByte () pasando ese byte, esto podría suceder cientos de miles de veces al día. Hay un botón en esta página que, cuando se presiona, muestra los últimos 100 bytes pasados ​​a recordByte () en la pantalla (lo hace llamando al método de impresión a continuación).

El siguiente código es lo que me dieron y me pidieron que completara:

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

¿Cuál es la mejor forma de almacenar los 100 bytes? ¿Una lista? Curioso cuál es la mejor manera de hacer esto.

Algo como esto ( búfer circular ):

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

Los beneficios de usar un búfer circular:

1. Puedes reservar el espacio estáticamente. En una aplicación de red en tiempo real (VoIP, streaming, ..) esto se hace a menudo porque no es necesario almacenar todos los datos de una transmisión, sino solo una ventana que contiene los nuevos bytes que se van a procesar.
2. Es rápido: se puede implementar con una matriz con un costo de lectura y escritura de O (1).

No sé Java, pero debe haber un concepto de cola mediante el cual pondría en cola bytes hasta que el número de elementos en la cola llegara a 100, momento en el que sacaría de la cola un byte y luego pondría en cola otro.

public void recordByte(Byte b)
{ 
  if (queue.ItemCount >= 100)
  {
    queue.dequeue();    
  }
  queue.enqueue(b);
}

Puede imprimir mirando los elementos:

public String print() 
{ 
  foreach (Byte b in queue)
  {
    print("X", b);  // some hexadecimal print function
  }
}  

Búfer circular usando matriz:

1. Matriz de 100 bytes
2. Mantenga un registro de dónde está el índice de cabeza i
3. Para recordByte()poner el byte actual en A [i] e i = i + 1% 100;
4. Para print(), return subarreglo (i + 1, 100) concatenar con subarreglo (0, i)

Cola usando la lista vinculada (o la cola de Java):

1. Para recordByte()agregar un nuevo byte al final
2. Si la nueva longitud es superior a 100, elimine el primer elemento
3. Para print()simplemente imprimir la lista

Aquí está mi código. Puede parecer un poco oscuro, pero estoy bastante seguro de que esta es la forma más rápida de hacerlo (al menos estaría en C ++, no estoy tan seguro de 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;
}

Algunos puntos a tener en cuenta:

• No se asignan / desasignan datos al llamar a recordByte ().
• No usé%, porque es más lento que una comparación directa y usando el if (la predicción de rama también podría ayudar aquí)
• --_idxes más rápido que _idx--porque no interviene ninguna variable temporal.
• Cuento hacia atrás hasta 0, porque entonces no tengo que entrar _ary.lengthcada vez en la llamada, sino solo cada 100 veces cuando se alcanza la primera entrada. Quizás esto no sea necesario, el compilador podría encargarse de ello.
• si hubo menos de 100 llamadas a recordByte (), el resto son ceros.

Lo más fácil es meterlo en una matriz. El tamaño máximo que puede acomodar la matriz es de 100 bytes. Siga agregando bytes a medida que se transmiten desde la web. Después de que los primeros 100 bytes estén en la matriz, cuando llegue el byte 101, elimine el byte de la cabecera (es decir, el 0). Sigue haciendo esto. Esto es básicamente una cola. Concepto FIFO. Una vez realizada la descarga, le quedan los últimos 100 bytes.

No solo después de la descarga, sino en cualquier momento dado, esta matriz tendrá los últimos 100 bytes.

@Yottagray ¿No llegas a donde está el problema? Parece haber una serie de enfoques genéricos (matriz, matriz circular, etc.) y una serie de enfoques específicos del lenguaje (byteArray, etc.). ¿Me estoy perdiendo de algo?

Solución multiproceso con E / S sin bloqueo:

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

Sólo por el gusto de hacerlo. ¿Qué tal usar un ArrayList<Byte>? Di por qué no

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");
        //  }
        // }
    }
}