Сценарий интервью" последние 100 байт"

Я получил этот вопрос в интервью на днях и хотел бы знать некоторые наилучшие возможные ответы(я не очень хорошо ответил Ха-ха):

сценарий: существует веб-страница, которая отслеживает байты, отправленные по некоторой сети. Каждый раз, когда байт отправляется функция recordByte () вызывается передача этого байта, это может произойти сотни тысяч раз в день. На этой странице есть кнопка, которая при нажатии отображает последние 100 байт, переданные в recordByte () on экран (он делает это, вызывая метод печати ниже).

следующий код-это то, что мне дали и попросили заполнить:

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

каков наилучший способ хранения 100 байт? Список? Любопытно, как лучше всего это сделать.

7 78
javascript algorithm

7 ответов:

что-то вроде этого (кольцевой буфер):

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, streaming,..)это часто делается потому, что вам не нужно хранить все данные передачи, а только окно, содержащее новые байты для обработки.
  2. это быстро: может быть реализован с массивом с чтения и записи стоимости O (1).
148

Я не знаю 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
  }
}
34

Кольцевой Буфер используя массив:

  1. массив из 100 байт
  2. следите за тем, где находится индекс головы i
  3. на recordByte() поместите текущий байт в A[i] и i = i+1% 100;
  4. на print(), return subarray(i+1, 100) конкатенация с subarray (0, i)

очереди использование связанного списка (или очереди java):

  1. на recordByte() добавить новый байт в конец
  2. если чтобы новая длина была больше 100, удалите первый элемент
  3. на print() просто распечатайте список
26

вот мой код. Это может показаться немного неясным, но я уверен, что это самый быстрый способ сделать это (по крайней мере, это будет в 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 раз, когда достигается первая запись. Возможно, в этом нет необходимости, компилятор мог бы позаботиться об этом.
  • если было менее 100 вызовов recordByte (), остальное-нули.
9

проще всего засунуть его в массив. Максимальный размер, который может вместить массив, составляет 100 байт. Продолжайте добавлять байты по мере их потоковой передачи из интернета. После того, как первые 100 байт находятся в массиве, когда приходит 101-й байт, удалите байт в голове (т. е. 0-й). Продолжай делать это. Это в основном очередь. Концепция ФИФО. После завершения загрузки, у вас остаются последние 100 байт.

не только после загрузки, но в любой момент времени, этот массив будет иметь последние 100 байт.

@Yottagray не получает, где проблема? Кажется, существует ряд общих подходов (массив, круговой массив и т. д.) и ряд языковых подходов (byteArray и т. д.). Я что-то упустил?

4

многопоточное решение с неблокирующим вводом / выводом:

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

просто для галочки. Как насчет использования 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");
        //  }
        // }
    }
}
0