edition - selection sort algorithm java

Escenario de la entrevista "Últimos 100 bytes"

Question

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 está supervisando los bytes enviados a través de una red. Cada vez que se envía un byte, la función recordByte () se llama pasar ese byte, esto podría suceder cientos de miles de veces por 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 el que me dieron y solicité que completara:

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

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

Answer 1

Algo así ( memoria intermedia 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 buffer circular:

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

Answer 2

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 sería en C ++, no tan seguro acerca 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 cuando se llama a recordByte ().
• No usé%, porque es más lento que una comparación directa y usa el if (la predicción de rama también podría ayudar aquí)
• --_idx es más rápido que _idx-- porque no está involucrada ninguna variable temporal.
• _ary.length hacia atrás hasta 0, porque entonces no tengo que obtener _ary.length cada vez en la llamada, sino solo cada 100 veces cuando se alcanza la primera entrada. Tal vez esto no sea necesario, el compilador podría encargarse de eso.
• si hubo menos de 100 llamadas a recordByte (), el resto es ceros.

Answer 3

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

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

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

Answer 4

No conozco Java, pero debe haber un concepto de cola en el que encola los bytes hasta que el número de elementos en la cola llegue a 100, momento en el que debes dequear un byte y luego poner otro en cola.

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

Puede imprimir mirando a los elementos:

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

Answer 5

Sólo por el gusto de hacerlo. ¿Qué le ArrayList<Byte> 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");
        //  }
        // }
    }
}

Answer 6

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

Answer 7

Buffer circular usando matriz:

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

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

1. Para recordByte() agrega un nuevo byte al final
2. Si la nueva longitud es más de 100, elimine el primer elemento
3. Para print() simplemente imprima la lista