독서 노트

《프로그래밍 주옥》 제1장.
문제1: 한 파일에 10000000개의 기록이 포함되어 있으며, 각 기록의 내용은 7자리의 정수이다.기록은 중복되지 않는다.파일 내용을 읽는 프로그램이 필요하고, 이 기록을 정렬한 후 파일을 출력해야 하며, 메모리는 1M 정도 제한된다.
해답: 기록이 중복되지 않기 때문에 모든 기록은bit로 표시하면 기록의 표시와 정렬을 간단하게 완성할 수 있다.이렇게 하려면 약 1.25M의 메모리가 필요하며 시간과 공간이 크지 않다.
 

/* Phase 1: initialize set to empty */
for i = [0, n)
    bit[i] = 0
/* Phase 2: insert present elements into the set */
for each i in the input file
    bit[i] = 1
/* Phase 3: write sorted output */
for i = [0, n)
    if bit[i] = 1
        write i on the output file

문제2: 문제1에서 1M을 넘지 못할 메모리를 엄격히 제한한다면?
해답: 다중 채널로 진행하여 시간으로 공간을 바꾼다.원본 파일을 두 번 스캔하고 처음으로 0x7FFFFF 이하의 수치만 검사하여 표시하고 출력한다.원본 파일을 두 번째로 읽으면 0x80000000 이상의 수치만 기록하고 검사하며 표시하고 출력합니다.이렇게 하려면 약 0.63M의 메모리가 필요합니다.
 
문제3: 문제1에서 만약에 모든 정수가 최대 한 번이 아니라 최대 열 번까지 나타난다면?
해답: 그러면 4개의 비트를 통해 각 기록을 기록해야 한다. 이전의 비트가 아니라.이렇게 하면 메모리 사용량이 4배로 증가해야 한다.만약 여전히 변하지 않는 메모리 제한을 유지한다면, 계속해서 여러 채널을 나누어 처리할 수밖에 없다.
 
문제4: 문제1에서 전체 비트 그룹을 초기화하는 시간을 줄일 수 있다면?
해답:두 가지 방법.
방법1:bit수 그룹을 수동으로 초기화되지 않은 전역 변수로 정의하여bss단에 컴파일합니다.이렇게 하면 프로그램이 메모리에 삽입될 때 운영체제는 자동으로 bss단의 내용을 0으로 설정합니다.시스템이 실행될 때 차지하는 시간을 시스템이 불러올 때로 앞당길 수 있다는 것이다.
방법2: (책의 해법) 전체 세그먼트의 원소 개수는 n이고 세그먼트는 데이터이다.n개의 요소를 포함하는 두 개의 그룹from과 to를 정의하고 전역 변수 t=0을 초기화합니다.
데이터[i]의 수치를 설정하기 전에 다음 코드를 실행합니다.

from[i]  = t;
to[t]    = i;
data[i]  = 0;
t++;

이렇게 하면 설정해야 할 요소 항목만 설정하고from, to와 전역 변수 t를 통해 데이터의 신뢰성을 공동으로 확보하며 일반적인 전체 세그먼트 그룹memset을 대체하는 방법을 대체할 수 있다.
  
우연히 책에서 제공한 방법 두 가지에 대해 의문이 있다. i와 t가 비교적 클 수 있는 상황에서from과 to수 그룹의 요소 유형은 unsigned long으로 설정해야 한다. 이렇게 소모되는 메모리는 너무 크다. 실제로 조작해야 하는 데이터 그룹의 모든 요소는 1개bit에 불과하다.이렇게 하면 얻는 것보다 잃는 것이 많지 않습니까?
전재 대상:https://www.cnblogs.com/Gigabyte/archive/2010/04/14/Reader-Notes-01.html