알고리즘 )1장 문풀

#7

 

#11~풀기 [ ]

---

 

 

 

더블버퍼링, 2pmm 

 

 

 

 

 

 

 

 

 

디스크 성능이 너무 낮아 안정성을 위해 Triple Buffering을 사용하기로 했다. 각 런당 3개의 입력 버퍼와 3개의 출력 버퍼를 사용할 때, 한 번의 병합으로 정렬 가능한 F의 최대 크기는?

 

읽기 작업은 느리지만 쓰기 작업은 충분히 빨라서, 입력에만 Double Buffering을 적용하고 출력은 1개의 버퍼만 사용한다. 이때 F

의 최대 크기는?

 

 

입력 버퍼 (Input Buffer)의 역할: "재료 가져오기"
여러 개의 정렬된 파일(런, Run)들에서 데이터를 읽어와 CPU가 비교할 수 있도록 대기시키는 공간입니다.

출력 버퍼 (Output Buffer)의 역할: "결과물 포장하기"
CPU가 비교해서 찾아낸 작은 값들을 순서대로 모았다가 디스크에 한꺼번에 저장하기 위한 공간입니다.

 

 

3pmm일때 

r=k**2까지 커져도됨

(k=r**2이면 이건 어차피 한번안에 끝남 (k>r이니깐 ) 

 

 

 

 

Huffman Tree

 

병합의 전체 비용은 모든 내부 노드(병합 단계에서 발생한 중간 합계)의 합입니다.

• 1단계 비용: 7
• 2단계 비용: 11
• 3단계 비용: 17
• 4단계 비용: 26
• 5단계 비용: 43

전체 비용 = 7+11+17+26+43=1047+11+17+26+43=104 (다 더해야한다 , 젤 큰 43이 답이 아니라 )

 

원래 있던, 노드(3,5는 안더하고,

 합해졋는 결과만 더하나 

 

외부 경로 길이==모두 더하기 

 

 

 

m-원 균형합병(m-way balanced sort-merge)

 

 

 

아 나 이거 기호가 되게 햇갈렷는데, 원래 r=F/M, k=M/B인데, 여기서 F=X, M=n이라서 대입하면 되는건가, ㅇㅇㅇ

 

 

런생성

 

외부 정렬에서 만드는 '런'은 단순히 데이터를 묶는 것이 아니라, 그 자체로 이미 오름차순 정렬이 되어 있는 덩어리여야 합니다. 그래야 나중에 이 덩어리들을 합쳐서(Merge) 최종 정렬을 할 수 있기 때문입니다.

 

1. 메모리 5칸을 채웁니다: [109, 49, 34, 68, 45]
2. 가장 작은 34를 선택해서 밖으로 내보냅니다. (런의 시작: 34)
3. 대체(Replacement): 34가 나간 빈자리에 입력 파일의 다음 숫자인 2를 가져와서 채웁니다.
4. 이제 메모리는 다시 5개가 되었습니다: [109, 49, 2, 68, 45]
5. 선택(Selection): 또 이 5개 중에 하나를 골라 내보냅니다. (단, 정렬을 위해 방금 나간 34보다 큰 놈 중에서만!)

이 과정을 "새로 들어온 놈들이 전부 방금 나간 놈보다 작아서, 더 이상 내보낼 놈이 없을 때까지" 무한 반복합니다. 그래서 메모리는 5칸이지만 런은 8개, 10개, 혹은 그 이상도 될 수 있는 것입니다.

 

 

 

메모리 크기'**와 **'런의 길이'

 

 

• 메모리 (Memory, 5칸): 이건 **'작업대'**입니다. 한 번에 책상 위에 올려둘 수 있는 숫자가 딱 5개뿐이라는 뜻입니다. 책상이 꽉 차면, 하나를 치워야(출력해야) 새 숫자를 책상에 올릴 수 있습니다.
• 런 (Run): 이건 책상에서 치워진 숫자들이 **'복도에 정렬되어 줄 서 있는 결과물'**입니다.

 

 

 

근데 f/m<=m/b-1에 f에 2**40, b=2**12햇는데 이러면, m을 한쪽에 두면 

이차 부등식되는데 인수분해 해 를 못찾겟는데 

 

 

 

2pmm  vs  k-sort병합 

 

나는 그냥 log2 5000인줄, 이거 메모리 적재 가능 레코드 수==M인가, 전체 레코드 수==F이고, 

즉 logk r을 구해야하는데, k=2(binary),r=f/m이니깐, 10인가, 

근데 이게 2pmm문젤ㅇ 헷갈리는게 그떄는 k=M/b엿는데 

물론 여기서는 블록에 대한건 엇긴햇지만

 

 

 

2pmm이엇으면 k==r==10이어야하는건가 그래서 logr k==1인거?ㅇㅇㅇ

 

 

 

 

성능개선방법 

 

k-way Sort/Merge에서의 Parallel I/O (기본 개념)

외부 정렬의 가장 큰 문제점은 **"CPU가 계산하는 동안 디스크는 놀고, 디스크가 읽는 동안 CPU는 노는 것"**입니다. 이를 해결하려고 '병렬성'을 도입합니다.

•  
• Fixed vs Dynamic Allocation:
  • Fixed: 각 런(Run)마다 버퍼 2개를 딱 고정해서 주는 방식입니다. 간단하지만, 특정 런의 데이터가 빨리 소모되면 다른 버퍼가 놀고 있어도 기다려야 하는 단점이 있습니다.
  • Dynamic: 어떤 런이 데이터를 더 빨리 소모할지 예측(Selection Tree 이용)하여 버퍼를 유연하게 할당하는 더 똑똑한 방식입니다.

 

 

 

• Clustering (클러스터링): 관련 있는 블록들을 디스크 상에 연속적으로 배치하여, 헤드가 움직이는 '탐색 시간(Seek Time)'을 줄이고 한 번에 많이 읽어오게 합니다.
•  
• Data Replication with Multiple Disks: 똑같은 데이터를 여러 디스크에 복제해두거나 분산 저장(Striping)합니다.
  • 효과: 여러 디스크 헤드가 동시에 데이터를 읽어오므로 전송 속도가 비약적으로 빨라집니다. 질문자님이 앞서 말씀하신 "디스크 여러 곳에 보관하기"가 바로 이 전략입니다.