《编程格调》章节试读

《编程格调》的笔记-第155页 - 排序

下述问题部分已解决，见[http://book.douban.com/annotation/37079021/].
我试图把书中第155页的烧脑FORTRAN代码移值为C代码，重复排序的实验，失败。
不能重现出 比较次数少 的效果。程序太乱了，另外fortran下标下界是1，且程
序把下标与0比较。这可能是我的C版本代码的错误所在。
求教过路君子，FORTRAN到C的移植。
1.1 原书155页烧脑版代码如下。
1.2 变量说明
2. 我实现的C版本（有问题的）如下:
void brainbreak_sort (float* x, unsigned int n)
{
int profile_cmp=0;
int profile_swap=0;
int profile_check=0;
int c=0;
int K=n-1; // n-1
int J=0;
int L=0;
int i=0;
double save=0;
int J1=0;
label_6:
J=1; //1
label_19:
L=0;

for(i=J;i<K;i++)
{
profile_cmp++;
if(x[i]-x[i+1]<0) goto label_2;
if(x[i]-x[i+1]==0) goto label_2;
if(x[i]-x[i+1]>0) goto label_3;
label_3:
if(L<0) goto label_20;
if(L==0) goto label_21;
if(L>0) goto label_20;
label_21:
J1=i-1;//i-1
label_20:
save=x[i];
x[i]=x[i+1];
x[i+1]=save;
profile_swap++;
L=i;// i
label_2:;
}

if(L<0) goto label_8;
if(L==0) goto label_9;
if(L>0) goto label_8;
label_8:
K=L;

if(J1<0) goto label_6;
if(J1==0) goto label_6;
if(J1>0) goto label_7;

label_7:
J=J1;
goto label_19;
label_9:
printf("brainbreak n: %d\ncmp: %d\nswap: %d\n", n, profile_cmp, profile_swap);
;
/* for(c=0;c<n+1;c++)
{
printf("%f\t",x[c]);
}*/
}
3. 作为对照，原书的平凡版排版代码如下:
4. 我实现的平凡版的C版本如下:
void plain_sort (float* x, unsigned int n)
{
if (n < 2 ) return;
int i, j;
double save;
int profile_cmp = 0;
int profile_swap = 0;
for (i=2; i<n; i++)
{
for(j=0;j<i;j++)
{
if(x[i] >= x[j]) {profile_cmp++; continue;}
save = x[i];
x[i] = x[j];
x[j] = save;
profile_swap++;
}
}
printf("plain n: %d\ncmp: %d\nswap: %d\n", n, profile_cmp, profile_swap);
/* for(i=0;i<n;i++)
{
printf("%f\t", x[i]);
}*/
}
5. 原书中profile对比
我的对比如下，问题是 我的烧脑版的比较次数比平凡版要高。
6. 我的版本: 完整的程序、随机数生成、脚本。
6.1 完整的程序#include "stdlib.h"
#include "stdio.h"
void plain_sort (float* x, unsigned int n);
void brainbreak_sort (float* x, unsigned int n);
int main()
{
float x[2000];
float y[2000];
int count=0;
while(scanf("%f", &x[count++])!=EOF); //{printf(":%f\n",x[count-1]);}
int i=0;
/* for(i=0;i<count;i++)
{
printf("%f\n", x[i]);
}
printf("\n");
*/
for(i=0;i<count;i++)
{
y[i]=x[i];
}
plain_sort(x, count-1);
brainbreak_sort(y, count-1);
return 0;
}
void brainbreak_sort (float* x, unsigned int n)
{
int profile_cmp=0;
int profile_swap=0;
int profile_check=0;
int c=0;
int K=n-1; // n-1
int J=0;
int L=0;
int i=0;
double save=0;
int J1=0;
label_6:
J=1; //1
label_19:
L=0;

for(i=J;i<K;i++)
{
profile_cmp++;
if(x[i]-x[i+1]<0) goto label_2;
if(x[i]-x[i+1]==0) goto label_2;
if(x[i]-x[i+1]>0) goto label_3;
label_3:
if(L<0) goto label_20;
if(L==0) goto label_21;
if(L>0) goto label_20;
label_21:
J1=i-1;//i-1
label_20:
save=x[i];
x[i]=x[i+1];
x[i+1]=save;
profile_swap++;
L=i;// i
label_2:;
}

if(L<0) goto label_8;
if(L==0) goto label_9;
if(L>0) goto label_8;
label_8:
K=L;

if(J1<0) goto label_6;
if(J1==0) goto label_6;
if(J1>0) goto label_7;

label_7:
J=J1;
goto label_19;
label_9:
printf("brainbreak n: %d\ncmp: %d\nswap: %d\n", n, profile_cmp, profile_swap);
;
/* for(c=0;c<n+1;c++)
{
printf("%f\t",x[c]);
}*/
}
void plain_sort (float* x, unsigned int n)
{
if (n < 2 ) return;
int i, j;
double save;
int profile_cmp = 0;
int profile_swap = 0;
for (i=1; i<n; i++)
{
for(j=0;j<i;j++)
{
if(x[i] >= x[j]) {profile_cmp++; continue;}
save = x[i];
x[i] = x[j];
x[j] = save;
profile_swap++;
}
}
printf("plain n: %d\ncmp: %d\nswap: %d\n", n, profile_cmp, profile_swap);
/* for(i=0;i<n;i++)
{
printf("%f\t", x[i]);
}*/
}6.2 随机数生成
#include <stdlib.h>
#include <stdio.h>
int main(int argc, char* argv[])
{
if(argc!=2)return 1;
int count=0;
int i=0;
const int MAX =100;
const int MIN =0;

srand((int)getpid());
sscanf(argv[1], "%d", &count);

for(i=0;i<count;i++)
{
printf("%d\n", rand()% (MAX + 1 - MIN) + MIN);
}
return 0;
}6.3 脚本
gcc rand.c -o rand; ./rand 10 > rand2000.txt
gcc sort.c -o sort; ./sort < rand2000.txt

《编程格调》的笔记-第155页

原文
DIMENSION X(300)
READ 1,N,(X(I),I=1,N)
1 FORMAT(I3/(F5.1))
K=N-1
6 J=1
19 L=0
DO 2 I=J,K
IF(X(I)-X(I+1)) 2,2,3
3 IF(L) 20,21,20
21 J1=I-1
20 SAVE=X(I)
X(I)=X(I+1)
X(I+1)=SAVE
L=I
2 CONTINUE
IF(L) 8,9,8
8 K=L
IF(J1) 6,6,7
7 J=J1
GO TO 19
9 END
对应的C代码如下。
void f_sort(float*x, unsigned int n)
{
int profile_cmp=0;
int profile_swap=0;
int profile_check_L=0;
int profile_check_J1=0;
int profile_move_K=0;

int i__1;
int i__, j, k, L;
int j1;
float save;
k = n - 1;
L6:
j = 1;
L19:
L = 0;
i__1 = k;
for (i__ = j; i__ <= i__1; ++i__) {
profile_cmp++;
if (x[i__ - 1] - x[i__] <= 0.f ) {
goto L2;
} else {
goto L3;
}
L3:
if (L != 0) {
goto L20;
} else {
goto L21;
}
L21:
j1 = i__ - 1;
L20:
save = x[i__ - 1];
x[i__ - 1] = x[i__];
x[i__] = save;
L = i__;
profile_swap++;
L2:
;
}
profile_check_L++;
if (L != 0) {
goto L8;
} else {
goto L9;
}
L8:
profile_move_K++;
k = L;
profile_check_J1++;
if (j1 <= 0) {
goto L6;
} else {
goto L7;
}
L7:
j = j1;
goto L19;
L9:
printf("\nf n: %d\ncmp: %d\nswap: %d\ncheck_L %d\ncheck_J1 %d\nprofile_move_K %d\nprofile_check_tatal %d\n",
n, profile_cmp, profile_swap, profile_check_L, profile_check_J1, profile_move_K,
profile_check_L + profile_check_J1 + profile_move_K +profile_cmp);
/* int i=0;
for(i=0;i<n;i++)
{
printf("%f\t", x[i]);
}*/
return;
}