프로 그래 밍 주옥 Chap 1

제1장 에서 논의 한 문제: 최대 1000 만 개의 중복 되 지 않 은 7 개의 정 수 를 정 하고 1MB (좌우) 의 메모리 공간 (디스크 공간 충분) 을 어떻게 이용 하여 정렬 을 완성 합 니까?
세 가지 해결 방안:
1. 디스크 기반 병합 정렬 을 이용 합 니 다.이런 방법 은 가장 쉽게 생각 할 수 있 고 결함 도 뚜렷 하 다. 병합 정렬 은 보통 원본 텍스트 의 두 배의 메모리 공간 이 필요 하 다. 원본 텍스트 의 크기 는 10000000 * 32bits (int 형 데이터) = 40MB 이 고 메모리 가 부족 할 것 이다. 외부 작업 파일 (디스크) 의 지원 이 필요 하 다.즉, 전체 과정 은 데이터 읽 기 - > 디스크 를 여러 번 읽 고 정렬 - > 디스크 출력 파일 을 읽 는 것 입 니 다. O (nlogn) 의 복잡 도 에 디스크 읽 기 를 반복 하면 정렬 속도 가 느 릴 것 입 니 다.
2. 여러 차례 정렬 알고리즘 을 사용한다.원본 40M 파일 을 40 개의 단락 (큰 것 에서 작은 것 으로) 으로 나 누 어 데 이 터 를 읽 고 40 번 이 라 고 말 하 며 그 중의 한 단락 의 데 이 터 를 정렬 (빠 른 줄 사용) 하고 출력 하 며 마지막 으로 조합 합 니 다.
3. 비트 맵 의 데이터 구 조 를 이용 합 니 다.현재 데이터 1, 7, 3, 8 이 있다 고 가정 하면 10100011 비트 문자열 로 표시 할 수 있 습 니 다. (낮은 비트 에서 읽 으 면 정렬 된 결 과 를 직접 얻 을 수 있 습 니 다) 이 원리 에 따라 1000 만 개의 7 비트 정 수 는 길이 가 1000 만 개의 bit 문자열 이 필요 하고 약 1.2M 의 공간 이 필요 합 니 다.프로 세 스 가 간단 해 졌 습 니 다. 데이터 흐름 을 읽 고 비트 문자열 의 해당 위 치 를 1 로 설정 한 다음 에 낮은 위치 에서 전체 비트 문자열 을 옮 겨 다 니 며 위 치 를 1 에 해당 하 는 정수 로 출력 하여 정렬 결 과 를 얻 을 수 있 습 니 다.정 답 이 제시 한 실현 코드:

/*
 * Organized by jfk, 2012/10/17
 * Ref: Programming Pearls
 */
#include <stdio.h>

#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define N 10000000

int a[1 + N/BITSPERWORD];

/* “i>>SHIFT”    i     int ，  int  32 bits  （    ）；
 * “(i & MASK)” i 32   ，     offset  value。
 *   ，"i<<(i & MASK)"  1   (i & MASK) ！
 */
void set(int i){ a[i>>SHIFT] |= (1<<(i & MASK));}
void clr(int i){ a[i>>SHIFT] &= ~(1<<(i & MASK));}
int test(int i){ return a[i>>SHIFT] & (1<<{i & MASK});}

void main()
{
	//     0
	for(int i = 0; i < N; i++)
		clr(i);
	
	//      i   1
	while(scanf("%d", &i) != EOF)
		set(i);
	
	//    i  1  ，   i  
	for(int i = 0; i < N; i++)
		if(test(i)) printf("%d
", i);
}

Step further: 1M 메모리 사용 을 엄 격 히 제한 하면 어떻게 합 니까?
1. 문제 의 정수 와 같은 희소 한 위 치 를 찾는다.
2. 두 번 의 정렬 을 사용 하여 2n 의 시간 지출 과 n / 2 의 공간 지출 로 정렬 을 완성 합 니 다.
Step further & further: 상기 비트 맵 정렬 방법 은 매우 교묘 하지만 전 제 를 한정 하여 입력 데 이 터 는 중복 되 지 않 아야 합 니 다.만약 각 정수 에 최대 10 번 이 나타난다 면, 어떻게 코드 를 다시 씁 니까?나의 실현 방법 은 다음 과 같다.

/*
 * Copywrite @ jfk, 2012/10/17
 * Statement when Ref.
 */

#include <stdio.h>

/*
 *         10 ，    4bit  ,
 *   ，  int       8   。
 */
#define WORDS_PER_INT 8
#define SHIFT 3
#define MASK 0x07
#define CHECK_0 0x0F
#define N 10000000

int a[1 + N/WORDS_PER_INT];

/*
 * set()     i    1。
 *     ：
 * 1.  offset。    i  a[]    ， i  8（   3 ，i>>SHIFT）  ；
 * 2.  value。 i  8   "(i & MASK)"，  i    a[]          ，
 *            4 bits，    4      ， ((i & MASK) * 4);
 * 3.         1。 ，a[i]    (1<<((i & MASK) * 4))；   
 */
void set(int i) { a[i>>SHIFT] += (1<<((i & MASK) * 4));}

/*
 * clr()     i      times ，   1 ；
 *   ：  set()     ，CHECK_0      i   
 *     ： a[]           times  ，   0，        
 */
void clr(int i, int times = 1)
{
	int tmp;
	tmp = a[i>>SHIFT] & (CHECK_0<<((i & MASK) * 4));
	tmp>>((i & MASK) * 4);
	if(tmp < times)
		 a[i>>SHIFT] -= (tmp<<((i & MASK) * 4));
	else
		 a[i>>SHIFT] -= (times<<((i & MASK) * 4));
}

/*
 * test()      i   a[]   i     
 */
void test(int i)
{
	int tmp;
	tmp = a[i>>SHIFT] & (CHECK_0<<((i & MASK) * 4));
	tmp = tmp>>((i & MASK) * 4);

	if(tmp != 0)
		printf("Integer: %d, Times: %d
", i, tmp);
}

void main()
{
	// User Define
}

Back now: 문제 로 돌아 가서 [0, n - 1] 사이 의 k 개의 서로 다른 무 작위 순서의 무 작위 정수 (중복 없 음) 를 어떻게 생 성 합 니까?코드:

void random(int *arr, int k, int n)
{
	for(int i = 0; i < k; i++)
		swap(arr[i], arr[i + rand() % (n - i)]);
}

연습 문제 9: 더 적은 시간 을 사용 하기 위해 더 많은 공간 을 거래 하 는 문제 중 하 나 는 공간 을 초기 화 하 는 것 자체 가 많은 시간 이 걸 릴 수 있다 는 것 입 니 다. 벡터 의 항목 을 초기 화 하 는 기술 을 설계 하여 이 문 제 를 우회 하 는 방법 을 보 여 줍 니 다. 초기 화 및 각 벡터 액세스 에 대해 일정 시간 을 사용 해 야 합 니 다. and use extra space proportional to the size of the vector. Because this method reduces initialization time by using even more space, it should be considered only when space is cheap, time is dear and the vector is sparse.
제목 이해: 이 단 계 는 매우 관건 적 이다. 몇 번 을 반복 해서 읽 고 나 서 야 작가 가 표현 하고 자 하 는 뜻 을 대체적으로 알 게 되 었 고 나중에 다른 사람의 분석 (여 기 를 클릭) 을 참고 했다.
희소 한 배열 을 지정 합 니 다. 모든 요 소 를 초기 화 하 는 데 많은 정력 을 들 여야 합 니 다. 어떻게 디자인 하 는 지 하 는 방식 입 니 다. 시작 할 때 전역 초기 화 를 하지 않 고 특정한 요 소 를 방문 할 때 이 요소 가 초기 화 되 지 않 았 다 고 판단 하면 이 요 소 를 0 으로 초기 화 합 니 다 (이 때 읽 기 작업 을 금지 합 니 다).이 요소 가 초기 화 되 었 다 면 정상 적 인 읽 기 작업 을 할 수 있 습 니 다. 여러 번 초기 화 되 어 데 이 터 를 덮어 쓰 는 것 을 방지 할 수 있 습 니까?문제 의 뜻 을 알 면 답 도 알 수 있 습 니 다. 두 개의 추가 n 원 벡터 from, to 와 하나의 정수 top 을 통 해 from [i] < top 과 to [from [i] = i 를 빌 리 면 요소 data [i] 가 초기 화 되 었 습 니 다.그렇지 않 으 면 데이터 [i] 가 초기 화 되 지 않 고 다음 작업 을 수행 합 니 다.

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

주: top 초기 값 은 0 입 니 다.
"프로그래머 의 주 된 문 제 는 기술적 인 문제 라 기보 다 는 심리 적 인 문제 이다. 그 가 문 제 를 해결 하지 못 하 는 것 은 잘못된 문 제 를 해결 하려 고 했 기 때문이다. 문제 의 최종 해결 은 개념 적 장벽 을 깨 고 간단 한 문 제 를 해결 함으로써 이 루어 진 것 이다. Conceptual Blockbusting." (번역 수준 이 너무 떨어진다)