您的位置:寻梦网首页文学书苑现代文学朱邦复作品集组合语言之艺术>附录一 SHELL 排序测试

组合语言之艺术

作者: 朱邦复

目录
附录一 SHELL 排序测试


一、比较表:

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

    汇编语言在大量数据处理时,应用灵活,而C语言因受到空间限制,以目前之系统
空间,无法执行。
    测试时间: 1989年 9月12至18日。
    参加人员: 张达权,段旭光,李朝辉。
    使用机种: IBM PS/2-50,80286 CPU,8MHZ。
    使用语言: C及汇编语言。
         因其它语言皆无法胜任,故仅选用此二者。
    处理对象: 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
 :     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 字符。执行4
8,000词组排序,需时70秒。
    及后,因为C语言所写的程序,无法处理48,000个词组,一直试到8,000 条,C才
能胜任。再用汇编程序测试,仅需时8秒。

三、C 语言之制作过程:

    我们用相同的方法,利用C写作如下程序:
   1: # include
   2: # include
   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: }

    本段程序由设计到制作完成,仅用了20小时。但在测试时,花了不少时间,费尽心
机,始终无法令本程序运行,原因是数据太大系统空间不够。
    最后不得已将数据删至8,000 条,才运行成功,需时30秒。



上一页  目录  下一页

文学书苑首页