代码之家 › 专栏 › 技术社区 › paxdiablo

这种排序功能是如何工作的?

readability sorting c

6

paxdiablo · 技术社区 · 14 年前

作为我工作的一部分,我偶尔会被要求对编程职位的候选人进行评估。最近我的办公桌上传来了一段代码片段,我最初的想法是我不确定这样的代码编译再。但是编译它就可以了,它也可以工作。

有人能解释为什么会这样做吗?任务是提供一个函数来排序五个整数值。

void order5(arr) int *arr; {
    int i,*a,*b,*c,*d,*e;
    a=arr,b=arr+1,c=arr+2,d=arr+3,e=arr+4;
    L1: if(*a >*b){*a^=*b;*b^=*a;*a^=*b;}
    L2: if(*b >*c){*b^=*c;*c^=*b;*b^=*c;goto L1;}
    L3: if(*c >*d){*c^=*d;*d^=*c;*c^=*d;goto L2;}
        if(*d >*e){*d^=*e;*e^=*d;*d^=*e;goto L3;}
}

现在我可以看到缺点对于这种方法(对于1970年之后出生的人来说缺乏可读性和可维护性),但是有人能想到任何优势吗?我犹豫着不去想,但是,在我们决定是否把这个人带回来参加第二轮之前,我想知道,对于作者来说,它是否有任何除了工作安全以外的补救功能。

5 回复 | 直到 14 年前

1

6

Ben Jackson 14 年前

这是一个完全展开的泡沫排序,用内联表示的XOR交换技巧。我用几个不同的选项来编译它,希望它能产生一些很棒的紧凑代码,但实际上并没有那么令人印象深刻。我投掷了一些 __restrict__ 关键字,以便编译器知道 *a 可以互相化名,这有很大帮助。总的来说,我认为尝试的聪明已经远远超出了标准,以至于编译器根本没有很好地优化代码。

我认为这里唯一的优势是新颖性。它的确引起了你的注意!我会对滥用更多 现代的 技术,比如使用mmx/sse或gpu进行排序,或者使用5个线程,这些线程都在努力将元素插入正确的位置。或者可能是外部合并排序,以防5元素数组不能容纳在核心中。

2

5

Armen Tsirunyan 14 年前

XOR技巧只是交换两个整数。Goto是循环的仿制品。优势?一点也没有,除了展示如何模糊你可以写的代码。函数()后的参数是不推荐使用的功能。手头有一个数组,有5个不同的指针指向数组的每一个元素,这是很可怕的。总而言之:糟糕!:)

3

1

Nietzche-jou 14 年前

这是对 Gnome sort 五项。

这里是如何花园侏儒整理一行花壶。基本上,他看他旁边的花盆和前一个;如果它们在右边命令他向前走一步, 否则他会交换它们,然后第一步向后倒。边界条件:如果没有以前的锅,他走了向前;如果旁边没有罐子他,他完了。

“向前走一步”是通过跳到下一步来完成的。 if . 这个 goto 在每次XOR交换之后,立即执行“后退一个pot”。

4

1

Martin Broadhurst 14 年前

你不能因为这样的回答而失去控制地解雇某人。它可能是装在嘴边的。

这个问题是高度人为的,促使人为的回答。

你需要了解候选人如何解决更多的现实问题。

5

1

JeremyP 14 年前

1970年以后出生的人缺乏可读性和可维护性

1970年以前出生的人在维护不可读的代码方面是否更好?如果是这样的话,那很好,因为我是,而且它只能是一个卖点。

在我们决定是否把这个人带回来参加第二轮之前,我想知道它是否有除了工作安全以外的任何补偿功能。

代码有不一个补救功能 S . 它奇怪地使用了XOR交换技术,其唯一可能的补救功能是节省ONER整数的堆栈空间。但是,即使这被定义的五个指针和未使用的int所否定,它也有一个逗号运算符的免费使用。

通常情况下,我也会说“goto,yuck”,但在本例中,一旦您了解了所使用的排序算法,它就以相当优雅的方式使用了。事实上,你可以说它比使用一个索引变量(除非它不能泛化为n个元素)使gnome排序算法更清晰。所以你有一个补偿功能,它使goto看起来很好:)

至于“你带候选人回来参加第二次面试吗?”如果代码片段附带一个详细的注释,解释算法的工作原理和作者使用它的动机,我肯定会说是的。如果没有,我可能会给他打电话问那些问题。

注意,代码片段使用K&R样式的参数声明。这意味着作者可能已经10到15年没有用C语言编写程序了,或者他从互联网上复制了它。