Interview-Szenario "Letzte 100 Bytes"

Ich habe diese Frage neulich in einem Interview bekommen und möchte einige bestmögliche Antworten wissen (ich habe nicht sehr gut geantwortet, haha):

Szenario: Es gibt eine Webseite, die die über ein bestimmtes Netzwerk gesendeten Bytes überwacht. Jedes Mal, wenn ein Byte gesendet wird, wird die Funktion recordByte () aufgerufen, die dieses Byte übergibt. Dies kann hunderttausend Mal pro Tag passieren. Auf dieser Seite befindet sich eine Schaltfläche, die beim Drücken die letzten 100 Bytes an recordByte () auf dem Bildschirm anzeigt (dies erfolgt durch Aufrufen der folgenden Druckmethode).

Der folgende Code wurde mir gegeben und zum Ausfüllen aufgefordert:

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

Was ist der beste Weg, um die 100 Bytes zu speichern? Eine Liste? Neugierig, wie das am besten geht.

So etwas wie ( kreisförmiger Puffer ):

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

Die Vorteile der Verwendung eines Ringpuffers:

1. Sie können den Platz statisch reservieren. In einer Echtzeit-Netzwerkanwendung (VoIP, Streaming, ..) geschieht dies häufig, weil Sie nicht alle Daten einer Übertragung speichern müssen, sondern nur ein Fenster, das die neuen zu verarbeitenden Bytes enthält.
2. Es ist schnell: Kann mit einem Array mit Lese- und Schreibkosten von O (1) implementiert werden.

Ich kenne Java nicht, aber es muss ein Warteschlangenkonzept geben, bei dem Sie Bytes in die Warteschlange stellen, bis die Anzahl der Elemente in der Warteschlange 100 erreicht hat. An diesem Punkt würden Sie ein Byte aus der Warteschlange entfernen und dann ein anderes in die Warteschlange stellen.

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

Sie können drucken, indem Sie einen Blick auf die Artikel werfen:

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

Kreispuffer mit Array:

1. Array von 100 Bytes
2. Verfolgen Sie, wo der Kopfindex i ist
3. Zum recordByte()Setzen des aktuellen Bytes in A [i] und i = i + 1% 100;
4. Für print()Subarray (i + 1, 100) zurückgeben mit Subarray (0, i) verketten

Warteschlange mit verknüpfter Liste (oder der Java-Warteschlange):

1. Zum recordByte()Hinzufügen eines neuen Bytes am Ende
2. Wenn die neue Länge mehr als 100 beträgt, entfernen Sie das erste Element
3. Zum print()einfachen Drucken der Liste

Hier ist mein Code. Es mag etwas dunkel aussehen, aber ich bin mir ziemlich sicher, dass dies der schnellste Weg ist (zumindest in C ++, nicht so sicher in Bezug auf 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;
}

Einige Punkte zu beachten:

• Beim Aufruf von recordByte () werden keine Daten zugewiesen / freigegeben.
• Ich habe% nicht verwendet, da es langsamer ist als ein direkter Vergleich und die Verwendung des if (Verzweigungsvorhersage könnte auch hier hilfreich sein).
• --_idxist schneller als _idx--weil keine temporäre Variable beteiligt ist.
• Ich zähle rückwärts bis 0, weil ich dann nicht _ary.lengthjedes Mal in den Anruf kommen muss, sondern nur alle 100 Male, wenn der erste Eintrag erreicht ist. Vielleicht ist das nicht nötig, der Compiler könnte sich darum kümmern.
• Wenn es weniger als 100 Aufrufe von recordByte () gab, ist der Rest Null.

Am einfachsten ist es, es in ein Array zu schieben. Die maximale Größe, die das Array aufnehmen kann, beträgt 100 Byte. Fügen Sie weitere Bytes hinzu, während diese aus dem Web gestreamt werden. Nachdem sich die ersten 100 Bytes im Array befinden und das 101. Byte kommt, entfernen Sie das Byte am Kopf (dh das 0.). Mach das weiter. Dies ist im Grunde eine Warteschlange. FIFO-Konzept. Nach dem Download verbleiben die letzten 100 Bytes.

Nicht nur nach dem Download, sondern zu jedem Zeitpunkt hat dieses Array die letzten 100 Bytes.

@ Yottagray Nicht bekommen, wo das Problem ist? Es scheint eine Reihe generischer Ansätze (Array, kreisförmiges Array usw.) und eine Reihe sprachspezifischer Ansätze (byteArray usw.) zu geben. Vermisse ich etwas

Multithread-Lösung mit nicht blockierenden E / A:

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

Nur zum Teufel. Wie wäre es mit einem ArrayList<Byte>? Sag warum nicht?

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