SHELL排序测试

　2007-05-02 09:30:48　来源：WEB开发网　　　

核心提示：一、比较表：第一章第一节中所提及的排序程式测试结果如下： ┌──────┬─────────┬────────┐ │ 项目│ Ｃ │组合语言 │ ├──────┼─────────┼────────┤ │源程式长度 │ 1,363 Bytes│ 3,581 Bytes│ │执行程式长度│ 69,345 Byt

一、比较表：

第一章第一节中所提及的排序程式测试结果如下：
┌──────┬─────────┬────────┐
│ 项目│ Ｃ │组合语言 │
├──────┼─────────┼────────┤
│源程式长度 │ 1,363 Bytes│ 3,581 Bytes│
│执行程式长度│ 69,345 Bytes│ 803 Bytes│
│编程时间 │ 20 小时 │ 80 小时 │
│8,000 笔需时│ 30 秒 │ 8 秒 │
│48,000笔需时│ 640KB中, 无法执行│ 70 秒 │
└──────┴─────────┴────────┘

组合语言在大量资料处理时，应用灵活，而Ｃ语言因受到空间限制，以目前之系统空间，无法执行。
测试时间: 1989年 9月12至18日。
参加人员: 张达权，段旭光，李朝辉。
使用机种: IBM PS/2-50，80286 CPU，8MHZ。
使用语言: Ｃ及组合语言。
因其他语言皆无法胜任，故仅选用此二者。
处理对象: 48,000个中文词组，分别取自12个资料档中。
每档有 4,000个词组。
每个词组有一至五个中文字。
每个中文字占两个字元内码。
全部资料占 316,421字元。
排序方式: 按仓颉字母顺位排列。
为了效率，采用SHELL 排序法。

二、组合语言之制作:

1: CG SEGMENT
2: ASSUME CS:CG,DS:CG,ES:CG
3: ORG 100H
4: START:
5: MOV AX,CS
6: MOV DS,AX
7: MOV SI,130 ; 指向输入缓冲区
8: MOV BL,[SI-2]
9: DEC BX
10: SUB BH,BH
11: MOV [BX][SI],BH
12: CLD
13: MOV DX,SI
14: MOV AX,3D00H
15: INT 21H ; 打开源档
16: JNC ZSTART
17: MOV DX,OFFSET ZSTR1 ; 若无此档则退出
18: MOV AH,9
19: INT 21H
20: INT 20H
21: ZSTART:
22: MOV BX,AX
23: SUB DX,DX
24: MOV CX,8000H
25: MOV BP,4D00H
26: MOV DS,BP
27: ZREAD:
28: MOV AH,3FH ; 读档
29: INT 21H
30: OR AX,AX
31: JZ ZREND
32: MOV AX,DS ; 未完，换段再读
33: ADD AX,800H
34: MOV DS,AX
35: JMP ZREAD
36: ZREND:
37: MOV AH,3EH ; 关档
38: INT 21H
39: MOV AX,2400H
40: MOV ES,AX
41: SUB DI,DI
42: SUB SI,SI
43: MOV DS,BP
44: SUB BP,BP
45: ZC1:
46: CALL ZCHGSEG
47: MOV CX,5 ; 将不等长换为等长
48: ZC3:
49: LODSW
50: CMP AL,0DH
51: JZ ZC4
52: STOSW
53: LOOP ZC3
54: INC SI
55: INC SI
56: JMP SHORT ZC5
57: ZC4:
58: MOV AX,2020H
59: REP STOSW
60: ZC5:
61: INC BP
62: LODSB
63: DEC SI
64: CMP AL,1AH
65: JNZ ZC1
66: STOSB
67: MOV CS:ZBW2,BP ; BP为资料计数
68: CALL ZSORT ; 排序
69: CALL ZDEL ; 删除相同者
70: CALL ZTR ; 换为不等长方式
71: MOV SI,DX
72: SUB CX,CX
73: PUSH CS
74: POP DS
75: MOV DX,OFFSET ZFCB ; 将结果存档
76: MOV AH,3CH
77: INT 21H
78: MOV BX,AX
79: MOV AX,2400H
80: MOV DS,AX
81: SUB DX,DX
82: OR SI,SI
83: JZ ZC7
84: MOV CX,8000H
85: ZC6:
86: MOV AH,40H
87: INT 21H
88: MOV AX,DS
89: ADD AX,800H
90: MOV DS,AX
91: DEC SI
92: JNZ ZC6
93: ZC7:
94: MOV CX,DI
95: MOV AH,40H
96: INT 21H
97: MOV AH,3EH
98: INT 21H
99: INT 20H
100: ZSORT: ; 排序子程式
101: SHR BP,1
102: ZS0:
103: PUSH BP
104: MOV CS:ZBW1,BP
105: MOV AX,CS:ZBW2
106: SUB AX,BP
107: MOV DX,BP
108: MOV BP,AX
109: MOV DI,2400H
110: MOV DS,DI
111: SUB SI,SI
112: CALL ZFINDES
113: ADD BX,DI
114: MOV ES,BX
115: MOV DI,AX
116: SUB DX,DX
117: ZS1:
118: CALL ZCOMPS
119: JBE ZS4
120: CALL ZXCHG
121: PUSH DS
122: PUSH ES
123: PUSH SI
124: PUSH DI
125: PUSH DX
126: ZS2:
127: MOV DI,SI
128: MOV AX,DS
129: MOV ES,AX
130: SUB DX,CS:ZBW1
131: JC ZS3
132: CALL ZFINDES
133: MOV SI,AX
134: ADD BX,2400H
135: MOV DS,BX
136: CALL ZCOMPS
137: JBE ZS3
138: CALL ZXCHG
139: JMP ZS2
140: ZS3:
141: POP DX
142: POP DI
143: POP SI
144: POP ES
145: POP DS
146: ZS4:
147: ADD SI,10
148: JS ZS7
149: ZS5:
150: ADD DI,10
151: JS ZS8
152: ZS6:
153: INC DX
154: CMP DX,BP
155: JNZ ZS1
156: POP BP
157: SHR BP,1
158: JNZ ZS0
159: RET
160: ZS7:
161: SUB SI,8000H
162: MOV AX,DS
163: ADD AX,800H
164: MOV DS,AX
165: JMP ZS5
166: ZS8:
167: SUB DI,8000H
168: MOV AX,ES
169: ADD AX,800H
170: MOV ES,AX
171: JMP ZS6
172: ZFINDES:
173: SUB BX,BX
174: MOV AX,DX
175: SHL AX,1
176: RCL BX,1
177: SHL AX,1
178: RCL BX,1
179: ADD AX,DX
180: ADC BX,0
181: SHL AX,1
182: RCL BX,1
183: PUSH AX
184: MOV CL,4
185: SHR AX,CL
186: MOV CL,12
187: SHL BX,CL
188: ADD BX,AX
189: POP AX
190: AND AX,15
191: RET
192: ZXCHG:
193: MOV CL,5
194: ZXCHG1:
195: LODSW
196: MOV BX,ES:[DI]
197: STOSW
198: MOV [SI-2],BX
199: LOOP ZXCHG1
200: SUB SI,10
201: SUB DI,10
202: RET
203: ZCOMPS:
204: MOV CL,5
205: MOV AX,DI
206: MOV BX,SI
207: REPZ CMPSB
208: MOV SI,BX
209: MOV DI,AX
210: RET
211: ZTR: ; 将等长串换为不等长串
212: MOV AX,2400H
213: MOV DS,AX
214: MOV ES,AX
215: SUB SI,SI
216: MOV DI,SI
217: MOV BP,CS:ZBW2
218: MOV DX,SI
219: ZTR1:
220: MOV CL,5
221: LODSW
222: CMP AX,2020H
223: JNZ ZTR21
224: ADD SI,8
225: DEC BP
226: JMP ZTR1
227: ZTR2:
228: LODSW
229: CMP AX,2020H
230: JZ ZTR3
231: ZTR21:
232: STOSW
233: ZTR3:
234: LOOP ZTR2
235: MOV AX,0A0DH
236: STOSW
237: DEC BP
238: JZ ZTR4
239: CALL ZCHGSEG
240: JMP ZTR1
241: ZTR4:
242: MOV AL,1AH
243: STOSB
244: RET
245: ZCHGSEG: ; 换段子程式
246: OR SI,SI
247: JNS ZCH1
248: SUB SI,BX
249: MOV AX,DS
250: ADD AX,800H
251: MOV DS,AX
252: ZCH1:
253: OR DI,DI
254: JNS ZCH2
255: SUB DI,BX
256: MOV AX,ES
257: ADD AX,800H
258: MOV ES,AX
259: INC DX
260: ZCH2:
261: RET
262: ZDEL: ; 删除相同字串
263: MOV AX,2400H
264: MOV DS,AX
265: MOV ES,AX
266: SUB SI,SI
267: MOV DI,10
268: MOV BP,CS:ZBW2
269: MOV BX,8000H
270: ZDEL1:
271: DEC BP
272: JZ ZCH2
273: MOV AX,SI
274: PUSH DI
275: MOV CL,10
276: REPZ CMPSB
277: POP DI
278: MOV SI,AX
279: JNZ ZDEL2
280: MOV AX,2020H
281: MOV [SI],AX
282: ZDEL2:
283: ADD SI,10
284: ADD DI,10
285: CALL ZCHGSEG
286: JMP ZDEL1
287: ZBW1 DW 0
288: ZBW2 DW 0
289: ZFCB DB 'YRRR',0
290: ZSTR1 DB 'FILE NOT FOUND !$'
291: CG ENDS
292: END START

本段程式，计用了80小时，源程式为 3,581字元，执行程式则为 803 字元。执行48,000词组排序，需时70秒。
及后，因为Ｃ语言所写的程式，无法处理48,000个词组，一直试到8,000 条，Ｃ才能胜任。再用组合语言程式测试，仅需时８秒。

三、C 语言之制作过程:

我们用相同的方法，利用Ｃ写作如下程式:
1: # include <fcntl.h>
2: # include <sys\stat.h>
3:
4: extern unsigned char yr[];
5:
6: main(argc, argv)
7: int argc;
8: char *argv[];
9: {
10: int i, n, fd, result;
11: long rsum;
12: unsigned char *yrp[8000], *yrptr, eof[1];
13:
14: fd = open(argv[1], O_RDWR);
15: rsum = 0;
16: while ((result = read(fd, &yr[rsum], 16384)) > 0)
17: {
18: rsum += result;
19: printf("%d %ld\n", result, rsum);
20: }
21: close(fd);
22: printf("after reading file\n");
23: fd = creat(argv[1], S_IREAD | S_IWRITE);
24: printf("after creat file\n");
25: yrp[0] = yrptr = yr;
26: n = 1;
27: while (*yrptr && n < 8000)
28: {
29: while (*yrptr++ != '\n');
30: yrp[n++] = yrptr;
31: }
32: sort(yrp, n);
33: for (i = 0; i < n; i++)
34: {
35: yrptr = yrp[i];
36: do
37: {
38: write(fd, yrptr, 1);
39: } while (*yrptr++ != '\n');
40: }
41: eof[0] = 0x1a;
42: write(fd, eof, 1);
43: close(fd);
44: }
45:
46:
47: sort(v, n)
48: unsigned char *v[];
49: int n;
50: {
51: int gap, i, j;
52: unsigned char *temp;
53:
54: printf("enter sorting\n");
55: for (gap = n / 2; gap > 0; gap /= 2)
56: for (i = gap; i < n; i++)
57: for (j = i - gap; j >= 0; j -= gap)
58: {
59: if (strcmp(v[j], v[j + gap]) <= 0)
60: break;
61: /* printf("swapping\n");*/
62: temp = v[j];
63: v[j] = v[j + gap];
64: v[j + gap] = temp;
65: }
66: }
67:
68: strcmp(v1, v2)
69: unsigned char *v1, *v2;
70: {
71: /* printf("enter strcmp\n");*/
72: for (; *v1 == *v2; v1++, v2++)
73: if (*v1 == '\n')
74: return(0);
75: return(*v1 - *v2);
76: }