O(n) 시간 내에 파일의 처음 n바이트 삭제

O(n) 시간 내에 파일의 처음 n바이트 삭제

개인 프로젝트(읽기: 코딩 실험)를 위한 솔루션을 찾아봤지만 적합한 것이 없는 것 같습니다. 솔직히 말해서 이것이 가능한지조차 모르겠습니다.

이제 전체 파일을 기반으로 이 작업을 수행할 수 있는 방법은 없습니다. 처음 n 바이트 없이 새 파일을 작성하는 작업은 이미 존재하더라도 작동하지 않습니다. 내가 생각할 수 있는 유일한 것은 어떻게든 파일의 시작 부분이 이제 더 멀리 떨어져 있음을 파일 시스템에 알리고 시작 부분을 지우는 것입니다.

하지만 내가 말했듯이, 나는 그것이 가능한지조차 확신하지 못합니다.

답변1

파일에서 바이트를 삭제하면 다시 작성해야 합니다. 이는 O(L) 시간이 됩니다. 여기서 L은 파일 길이입니다. 일반 파일 시스템에서는 O(n)을 달성할 수 없습니다.

n을 파일 시스템 블록 크기로 나눌 수 있는 경우 이러한 상황이 발생할 수 있습니다. < O(n)이 작업은 디렉토리 항목에서 일부 예약된 inode만 제거하기 때문입니다. (이상적인 세계에서는 프로그램이 정확히 그렇게 할 것입니다!)

관련 정보