[주옥 같은 프로 그래 밍 - 독서 노트] 비트 맵 으로 정렬 문 제 를 해결 합 니 다. - 문제 의 중요성 을 자세히 분석 합 니 다.

'프로 그래 밍 주옥' 을 읽 기 시 작 했 는데, 막 시작 을 보 자마자 매우 기 뻤 다.
저 자 는 'A Friendly Conversation' 에서 말 하면 아마 이 럴 것 이다.
한 프로그래머 가 작성 자 에 게 물 었 다. "디스크 파일 을 어떻게 정렬 합 니까?"
그래서 저 자 는 디스크 에서 Merge Sort 를 어떻게 실현 하 는 지 간략하게 소개 하고 알고리즘 교과 서 를 먼저 연구 하 라 고 제안 했다.그러나 프로그래머 들 은 더 공부 하 는 것 이 아니 라 문 제 를 어떻게 해결 하 느 냐 에 주목한다.유행 하 는 디스크 정렬 프로그램 은 약 10 여 개의 함수, 200 줄 의 프로그램 코드 로 이 부분 코드 를 실현 하고 테스트 하 는 것 은 1 주일 을 넘 지 않 을 것 으로 예상 된다.
더 나 은 대화 에서 작 가 는 정렬 된 파일 은 최대 10000000 개의 기록 을 포함 하고 모든 기록 은 7 개의 정수 이 며 숫자 는 중복 되 지 않 는 다 는 것 을 알 게 되 었 다.그리고 기껏해야 1MB 의 사용 가능 한 메 인 메모리 만 있다.
그래서 문제 가 뚜렷 해 지기 시작 했다. 정수 정렬 이기 때문에 필요 한 코드 의 양 이 상응 하 게 줄 어 들 고 실행 속도 도 많이 빨 라 졌 지만 디 버 깅 은 아직도 시간 이 필요 하 다.
두 번 째 방안 은 40 개의 채널 로 차례대로 정 수 를 메 인 저장 소 에 읽 고 정렬 출력 (32 비트 정수 로 각 번 호 를 표시 하고 1MB 공간 은 250000 개의 번 호 를 저장 할 수 있다.) 메 인 저장 소 에 서 는 빠 른 배열 효율 이 높 고 코드 가 간단 하 다.
상기 두 가지 방안 에 비해 첫 번 째 는 입력 에서 파일 을 한꺼번에 읽 은 다음 작업 파일 의 보조 하에 정렬 (작업 파일 은 여러 번 읽 고 쓰기 작업) 한 다음 에 파일 을 한꺼번에 출력 합 니 다.
두 번 째 는 입력 파일 을 여러 번 읽 어야 하 며 중간 파일 을 사용 하지 않 습 니 다.출력 파일 작업 을 한 번 만 합 니 다.
세 번 째 방법 이 있 습 니까? 상기 두 가지 장점 을 결합 할 수 있 습 니까? - > 한꺼번에 읽 고 중간 파일 을 사용 하지 않 습 니까?
입력 파일 의 모든 정 수 를 저장 할 수 있 을 때 (또는 표시) 사용 가능 한 메 인 저장 공간 에 저장 할 수 있 을 때 만 세 번 째 를 실현 할 수 있 습 니 다.
그래서 문 제 는 최대 천만 개의 서로 다른 정 수 를 약 800 만 개의 사용 가능 한 비트 에 표시 하 는 방법 으로 바 뀌 었 다.
비트 맵
쉽게 말 하면 우 리 는 20 자리 이하 의 비 마이너스 정수 집합 을 20 자리 문자열 로 표시 할 수 있다. 예 를 들 어 집합 {1, 2, 3, 5, 8, 13} 은 다음 과 같다.
0 1 1 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0
7 비트 10 진수 가 천만 보다 작은 숫자 를 표시 하기 때문에 우 리 는 천만 비트 가 있 는 문자열 로 이 파일 을 표시 할 수 있 습 니 다. 정수 i 가 이 파일 에 있 을 때 만 i 위 를 1 로 설정 할 수 있 습 니 다.
알고리즘:

for i = [0,n)
    bit[i] = 0
for each i in the input file
    bit[i] = 1
for i = [0,n)
    if bit[i] == 1
        write i on the output file

비트 맵 한계 성:
입력 범 위 는 상대 적 으로 작 아서 중복 데 이 터 를 포함 할 수 없고 데이터 가 정수 기록 과 관련 이 없습니다.
감언이설
최초의 디스크 를 병합 하여 정렬 하고 메 인 메모리 의 빠 른 정렬 에 이 르 기 까지 비트 맵 을 사용 한 다 는 점 이 눈 에 띈 다.앞의 두 가지 방법 은 일반적으로 생각 하기 쉽 지만 그 간결 정 도 는 비트 맵 의 해결 방법 보다 훨씬 못 하 다.이 사례 에서 도 문제 에 대한 묘사 와 정의 가 이렇게 중요 하 다 는 것 을 알 수 있다.작가 가 말 한 것 처럼 "문 제 를 정의 하 는 것 은 이 전투 의 약 90% 였 습 니 다!"
만약 뒤의 대화 가 없다 면, 문 제 는 단지 "How do I sort a disk file?" 일 뿐이다. 이것 은 의심 할 여지없이 많은 시행 착 오 를 돌 았 다.
비트 맵 데이터 구 조 는 한계 가 있 고 기묘 한 점도 있 습 니 다. 우리 가 해 야 할 일 은 적당 한 문제 에서 적당 한 데이터 구 조 를 선택 하여 유연 하 게 대응 하 는 것 입 니 다 ~