[java] “마지막 100 바이트”인터뷰 시나리오

Program / 글쓴이

저번에 인터뷰에서이 질문을 받았는데 가능한 최선의 답변을 알고 싶습니다 (아주 잘 대답하지 않았습니다).

시나리오 : 일부 네트워크를 통해 전송 된 바이트를 모니터링하는 웹 페이지가 있습니다. 바이트가 전송 될 때마다 해당 바이트를 전달하는 recordByte () 함수가 호출되며 이는 하루에 수십만 번 발생할 수 있습니다. 이 페이지에는 버튼을 누르면 화면에 recordByte ()에 전달 된 마지막 100 바이트가 표시됩니다 (아래의 print 메서드를 호출하여이 작업을 수행합니다).

다음 코드는 내가 제공하고 작성하도록 요청한 것입니다.

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

100 바이트를 저장하는 가장 좋은 방법은 무엇입니까? 목록? 이를 수행하는 가장 좋은 방법이 궁금합니다.

답변

다음과 같은 것 ( 순환 버퍼 ) :

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) 인 배열로 구현할 수 있습니다.

답변

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
  }
}

답변

배열을 사용하는 원형 버퍼 :

  1. 100 바이트 배열
  2. 헤드 인덱스가 어디에 있는지 추적하십시오.
  3. 들면 recordByte()A [I]에서 현재의 바이트 넣고 난 + 1 % = 100;
  4. 의 경우 print()subarray (i + 1, 100)를 반환하고 subarray (0, i)와 연결합니다.

연결 목록을 사용하는 대기열 (또는 Java 대기열) :

  1. recordByte()끝에 새 바이트 를 추가하려면
  2. 새 길이가 100보다 크면 첫 번째 요소를 제거하십시오.
  3. 내용은 print()단순히 목록을 인쇄

답변

다음은 내 코드입니다. 약간 모호해 보일 수 있지만 이것이 가장 빠른 방법이라고 확신합니다 (적어도 Java에 대해서는 확실하지 않지만 C ++에서는 가능합니다).

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 개 미만인 경우 나머지는 0입니다.

답변

가장 쉬운 것은 그것을 배열로 밀어 넣는 것입니다. 배열이 수용 할 수있는 최대 크기는 100 바이트입니다. 웹에서 스트리밍 할 때 바이트를 계속 추가하십시오. 처음 100 바이트가 배열에있는 후 101 번째 바이트가 오면 헤드 (즉, 0 번째)에서 바이트를 제거합니다. 계속하세요. 이것은 기본적으로 대기열입니다. FIFO 개념. 다운로드가 완료되면 마지막 100 바이트가 남습니다.

다운로드 후뿐만 아니라 특정 시점에서이 배열은 마지막 100 바이트를 갖게됩니다.

@Yottagray 문제가 어디 있는지 알지 못합니까? 일반적인 접근 방식 (배열, 원형 배열 등)과 언어 별 접근 방식 (byteArray 등)이 많이있는 것 같습니다. 내가 뭔가를 놓치고 있습니까?

답변

비 차단 I / O가있는 멀티 스레드 솔루션 :

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

답변

그냥 도대체. 사용하는 것은 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");
        //  }
        // }
    }
}