解題區/出題解題

[讀檔操作] 有限記憶體排序數組

contents

  1. 1. 背景
  2. 2. 題目描述
  3. 3. 輸入格式
  4. 4. 輸出格式
  5. 5. 範例輸入
  6. 6. 範例輸出
  7. 7. 提示
  8. 8. Solution

背景

現在的系統架構中，內存 (Memory，台灣翻譯：記憶體，大陸翻譯：內存) 的大小仍無法完全像硬碟機一樣。如檔案大小 64GB，內存只有 4GB，處理檔案無法全部 In Memory，當然最近的硬體技術也逐漸朝著 All In Memory 的方式進行加速。回過頭來，在內存不足的情況下，來練習如何處理檔案大小遠大於內存的情況吧。

題目描述

給予一個 binary file 的檔案名稱，裡面用 4 個位元組為一個 signed 32-bit 整數，有數個直到 EOF，請排序後以 binary mode 導入 stdout 輸出。

輸入格式

標準輸入串流只有一行一個字串，表示檔案名稱 $F$。檔案大小最多 16 MB，而你的程序被限制最多使用 4 MB 的內存。

每個整數 $x$，限制條件 $0 \le x \le 10^9$

輸出格式

輸出在標準串流以 binary mode 下，請避開使用 console 輸出，會因為特殊字元 (如 「嗶」一聲) 導致系統嚴重當機。

範例輸入

1
1.dat

範例輸出

1
... binary mode 無法顯示

提示

download p10068-in.dat

1
2
3
4
5
6
7
8
9
morris821028@morris821028-PC MINGW64 ~/Desktop/10068
$ ./sort2.exe >test.out
1.dat
morris821028@morris821028-PC MINGW64 ~/Desktop/10068
$ xxd test.out
00000000: 0000 0000 0100 0000 0100 0000 0100 0000  ................
00000010: 0300 0000 0400 0000 0500 0000 0500 0000  ................
00000020: 0800 0000 0900 0000                      ........

1.dat 以 binary file 儲存 10 個 4 bytes 整數，依序為 5, 9, 3, 5, 0, 1, 1, 8, 4, 1，排序後即為 0, 1, 1, 1, 3, 4, 5, 5, 8, 9。

由於限制內存使用量，無法寫入暫存檔案，可利用多次讀檔完成。

Solution

乍看之下，這一題是最常見的 external sort (外部排序)，外部排序需要額外寫檔案，由於記憶體用量計算，一寫檔案會計算到使用的記憶體中，實際上這一題不寫檔也是能解決的。

  • 給定要排序的數據範圍
  • 二分搜尋可容納的排序範圍，利用平衡樹或者 hash 來完成計算 <某整數, 某整數出現個數>
  • 將可容納到 hash 的所有數字排序，再將其直接寫到輸出檔案。
  • 不斷地遞增二分搜尋的左邊邊界。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#define swap(x, y) {int t; t = x, x = y, y = t;}
int fsize(FILE *fp) {
    int prev = ftell(fp);
    fseek(fp, 0L, SEEK_END);
    int size = ftell(fp);
    fseek(fp, prev, SEEK_SET);
    return size;
}
#define USAGEMEM (2<<20)
#define MAXELE ((2<<20)/8)
int A[MAXELE];
#define HSIZE 100007
#define HNODE 50000
typedef struct HashNode {
    int f, cnt;
    struct HashNode *next;
} HashNode;
HashNode *hhead[HSIZE], hnodes[HNODE];
int nodesize = 0;
int cmp(const void *x, const void *y) {
    return ((HashNode*) x)->f - ((HashNode*) y)->f;
}
unsigned int hash(int f) {
    unsigned int a = 63689, b = 378551;
    unsigned int value = 0;
    value = value * a + f, a = a * b;
    return value;
} 
void initHash() {
    memset(hhead, 0, sizeof(hhead));
    nodesize = 0;
}
int insertHash(int f) {
    unsigned int hidx = hash(f)%HSIZE;
    for (HashNode *p = hhead[hidx]; p != NULL; p = p->next) {
        if (f == p->f) {
        	p->cnt++;
            return 1;
        }
    }
    if (nodesize >= HNODE)	return 0;
    HashNode s = {.f = f, .cnt = 1, .next = NULL};
    hnodes[nodesize] = s;
    hnodes[nodesize].next = hhead[hidx];
    hhead[hidx] = &hnodes[nodesize];
    nodesize++;
    return 1;
}
int merge_int(FILE *fp, int l, int r) {
    initHash();
    int ret = 0, x, n = 0;
    fseek(fp, 0, SEEK_SET);
    while ((n = fread(A, sizeof(int), MAXELE, fp))) {
        for (int i = 0; i < n; i++) {
            if (A[i] >= l && A[i] <= r) {
                if (!insertHash(A[i]))
                    return 0;
            }
        }
    }
    return 1;
}
#ifdef _WIN32
#include <fcntl.h>
#endif
int block_process(FILE *fp) {
    int base = 0;
    int l, r, mid, ret;
    l = base, r = 1000000000, ret = 0;
#ifdef _WIN32
    if (setmode(fileno(stdout), O_BINARY) == -1) {
        perror("Cannot set stdout to binary mode");
        return 2;
    }
#endif
#ifdef __linux__
    FILE *const out = fdopen(dup(fileno(stdout)), "wb");
#endif
    while (l <= r) {
        mid = (l + r)/2;
        int status = merge_int(fp, base, mid);
        if (status == 1) {
            l = mid + 1, r = 1000000000;
            base = mid + 1;
            qsort(hnodes, nodesize, sizeof(HashNode), cmp);
            for (int i = 0; i < nodesize; i++) {
                int x = hnodes[i].f;
                for (int j = hnodes[i].cnt-1; j >= 0; j--) {
#ifdef _WIN32
                    fwrite(&x, sizeof(int), 1, stdout);
#endif
#ifdef __linux__
                    fwrite(&x, sizeof(int), 1, out);
#endif
                }
                ret += hnodes[i].cnt;
            }
        } else {
            r = mid - 1;
        }
    }
    return ret;
}
int main() {
    char fName[128];
    scanf("%s", fName);
    FILE *fin = fopen(fName, "rb");
    
    int n = fsize(fin) / sizeof(int);
    block_process(fin);
    return 0;
}