0
데이터 길이보다 작은 버퍼를 사용하여 직렬 입력에서 데이터를 정렬하는 알고리즘이 있습니까?버퍼로 시리얼 데이터 정렬
예를 들어, 한 번만 읽을 수있는 100 바이트의 직렬 데이터와 40 바이트의 버퍼가 있습니다. 그리고 정렬 된 바이트를 출력해야합니다.
자바 스크립트에서 필요하지만, 일반적인 아이디어는 인정됩니다.
A
답변
3
이러한 종류의 정렬은 한 번에 수행 할 수 없습니다.
예제를 사용하여 : 40 바이트 버퍼를 채웠다 고 가정합니다. 따라서 다음 바이트 공간을 확보하기 위해 바이트 인쇄를 시작해야합니다. 정렬 된 데이터를 인쇄하려면 가장 작은 바이트를 먼저 인쇄해야합니다. 그러나, 가장 작은 바이트가 읽히지 않으면, 당신은 아직 그것을 인쇄 할 수 없습니다!
질문에 가장 잘 어울리는 것은 external sorting 알고리즘 일 수 있습니다. 알고리즘은 메모리에 맞지 않는 데이터를 정렬하기 위해 여러 번 통과합니다. 즉, 처리 패스의 출력을 저장할 수있는 주변 장치가있는 경우 O (로그 (N/M)) 패스에서 메모리보다 큰 데이터를 정렬 할 수 있습니다. 여기서 N은 문제의 크기이고 M은 당신의 기억의 크기.
외부 정렬을위한 고전적인 저장 장치는 테이프 드라이브입니다. 그러나 디스크 드라이브 (모든 종류의)에 대해 동일한 알고리즘이 작동합니다. 또한 캐시 계층 구조가 깊어짐에 따라 메모리 정렬의 경우에도 외부 정렬 원칙이 더욱 관련이 있습니다. cache-oblivious 알고리즘을 살펴보십시오.
데이터가 적어도 어느 정도 사전 주문되지 않은 한 가능하지 않습니다. 수신 한 마지막 바이트가 출력에서 첫 번째 바이트가되어야하고, 그 앞에 바이트를 출력 할 수는 없지만, 그 바이트가 먼저 나올 수는 있지만 모든 중간 데이터를 그보다 작은 버퍼에 저장할 수는 없습니다 데이터가 차지하고있다. 데이터를 압축하는 것과 같은 것을 시도 할 수는 있지만 역효과를 일으킬 수 있습니다. –