两种不同的交换函数有什么区别? [英] What is the difference between two different swapping function?

问题描述

我想知道 2 个代码在性能上的区别.有什么优点和缺点?

I would like to know the difference between 2 codes in performance. What are the advantages and disadvantages?

代码 1:

temp  = a;
a  = b;
b  = temp;

代码 2:

a = a + b;
b = a - b;
a = a - b;

推荐答案

第一种技术的优点是它是一个通用的习语，显而易见且正确.它适用于任何类型的变量.如果可用，它很可能被优化编译器识别并替换为实际的交换"指令.因此，除了更清晰、更正确之外，第一种技术也可能更有效.

The advantages of the first technique are that it is a universal idiom which is obvious and correct. It will work everywhere, on variables of any type. It is quite likely to be recognized by an optimizing compiler and replaced by an actual 'swap' instruction, if available. So besides being more clear and more correct, the first technique is likely to be more efficient, also.

第二种技术的优点是它避免了使用临时变量，并且它是一种美味的晦涩技巧，受到那些不断收集晦涩技巧并提出涉及晦涩技巧的误导性陷阱"面试问题的人的喜爱，以及(据我所知)他们通过使用晦涩的技巧使他们自己的程序更难维护、更不易移植和更不可靠.

The advantages of the second technique are that it avoids the use of a temporary variable, and that it is a deliciously obscure trick which is beloved by those who incessantly collect obscure tricks, and pose misguided "gotcha" interview questions involving obscure tricks, and (for all I know) who make their own programs less maintainable, less portable, and less reliable by cluttering them with obscure tricks.

第一种技术的缺点是:无.
(理论上，有人可能会说它使用临时变量有一个缺点，但实际上，这根本没有缺点，因为临时变量是免费的.我认为地球上没有人还在为处理器编码，所以内存和寄存器有限，以这种方式保存"临时变量实际上是需要担心的.)

The disadvantages of the first technique are: None.
(Theoretically, one might say there's a disadvantage in that it uses a temporary variable, but really, that's no disadvantage at all, because temporary variables are free. I don't think there's anyone on the planet who is still coding for a processor so limited in memory and registers that "saving" a temporary variable in this sort of way is something to actually worry about.)

第二种技术的缺点是编写起来更困难，读者更难理解，而且效率可能较低(可能很明显).它仅适用于"算术类型，而不适用于结构或其他类型.如果它应该用于尝试与自身交换数据，它将不起作用(它会悄悄地破坏数据).(稍后会详细介绍这种可能性.)如果这些还不够糟糕，那么即使在普通"情况下，它也可能从根本上有问题，因为它可能会溢出，并且对于浮点类型，它可能会改变一个或两个值稍微由于舍入误差，对于指针类型，如果被交换的指针不指向同一个对象，则未定义.

The disadvantages of the second technique are that it is harder to write, harder for the reader to understand, and likely less efficient (perhaps significantly so). It "works" only on arithmetic types, not structures or other types. It won't work (it will quietly corrupt data) if it should happen be used in an attempt to swap data with itself. (More on this possibility later.) And if those aren't all bad enough, it is likely to be fundamentally buggy even under "ordinary" circumstances, since it could overflow, and with floating-point types it could alter one or both values slightly due to roundoff error, and with pointer types it's undefined if the pointers being swapped do not point within the same object.

您专门询问了性能，所以让我们多说几句.(免责声明:我不是微优化方面的专家；我倾向于用相当抽象、随意的术语来考虑指令级性能.)

You asked specifically about performance, so let's say a few more words about that. (Disclaimer: I am not an expert on microoptimization; I tend to think about instruction-level performance in rather abstract, handwavey terms.)

第一种技术使用三个赋值.第二种技术使用加法和两次减法.在许多机器上，算术运算的周期数与简单赋值的周期数相同，因此在许多情况下，这两种技术的性能是相同的.但是很难想象第二种技术如何更有效，而很容易想象第一种技术如何更有效.特别是，正如我已经提到的，如果目标处理器有 SWP 指令，第一种技术更容易让编译器识别并转化为更高效的 SWP 指令.

The first technique uses three assignments. The second technique uses an addition and two subtractions. On many machines an arithmetic operation takes the same number of cycles as a simple value assignment, so in many cases the performance of the two techniques will be identical. But it's hard to imagine how the second technique could ever be more efficient, while it's easy to imagine how the first technique could be more efficient. In particular, as I mentioned already, the first technique is easier for a compiler to recognize and turn into a more-efficient SWP instruction, if the target processor has one.

现在，有些题外话.这里介绍的第二种技术是传统的、美味的晦涩技巧的一种不太美味的变体，用于在不使用临时变量的情况下交换两个变量.在不使用临时变量的情况下交换两个变量的传统的、非常晦涩的技巧是:

And now, some digressions. The second technique as presented here is a less-delicious variant of the traditional, deliciously obscure trick for swapping two variables without using a temporary. The traditional, deliciously obscure trick for swapping two variables without using a temporary is:

a ^= b;
b ^= a;
a ^= b;

曾几何时，在某些圈子中，以一种更加美味、晦涩的方式呈现这些技术是一种时尚:

Once upon a time it was fashionable in some circles to render these techniques in an even more deliciously obscure way:

a ^= b ^= a ^= b;       /* WRONG */
a += b -= a -= b;       /* WRONG */

但是这些演绎(虽然，是的，如果你喜欢那种东西，绝对精致很好地晦涩难懂)具有额外的崩溃缺点，它们代表未定义的行为，因为他们尝试在同一个表达式中多次修改 a 而没有中间序列点.(另请参阅关于该主题的规范 SO 问题.)

But these renditions (while, yes, being absolutely exquisitely deliciously obscure if you like that sort of thing) have the additional crashing disadvantage that they represent undefined behavior, since they try to modify a multiple times in the same expression without an intervening sequence point. (See also the canonical SO question on that topic.)

公平地说，我不得不提到在一种实际情况下，第一种技术使用临时变量可能是一个明显的缺点，因此第二种技术的缺乏可能是一个实际的优势.一种情况是，如果您尝试编写一个通用的交换"宏，沿着

In fairness, I have to mention that there is one actual circumstance under which the first technique's use of a temporary variable can be a significant disadvantage, and the second technique's lack of one can be therefore be an actual advantage. That one circumstance is if you are trying to write a generic 'swap' macro, along the lines of

#define Swap(a, b) (a = a + b, b = a - b, a = a - b)

这个想法是你可以在任何地方使用这个宏，并且可以在任何类型的变量上使用，并且(因为它是一个宏，因此很神奇)你甚至不必使用 &你调用它的参数，就像它是一个函数一样.但至少在传统 C 中，如果您想编写这样的 Swap 宏，使用技术 1 基本上是不可能的，因为无法声明必要的临时变量.

The idea is that you can use this macro anywhere, and on variables of any type, and (since it's a macro, and therefore magic) you don't even have to use & on the arguments you call it with, as you would if it were a function. But in traditional C, at least, if you wanted to write a Swap macro like this, it was essentially impossible to do so using technique 1, because there was no way to declare the necessary temporary variable.

你不是在问这个子问题，但既然我提出来了，我不得不说解决方案(尽管它永远让那些默默无闻的美味爱好者感到沮丧)就是不要试图首先编写一个通用"宏来交换两个值.你不能用 C 来做(事实上，你可以用 C++ 来做，有了 auto 的新定义，现在我猜 C 有一些写泛型的新方法宏.)

You weren't asking about this sub-problem, but since I brought it up, I have to say that the solution (although it is eternally frustrating to the lovers of delicious obscurity) is to just not attempt to write a "generic" macro to swap two values in the first place. You can't do it in C. (As a matter of fact, you could do it in C++, with the new definition of auto, and these days I guess C has some new way of writing generic macros, too.)

当您尝试以这种方式编写swap"宏时，实际上还有一个额外的崩溃问题，那就是它不起作用——它会将一个或两个变量设置为 0 来代替交换值——如果调用者试图与自己交换一个值.你可能会说这不是问题，因为也许没有人会写 Swap(x, x)，但是在一个不太完美的排序例程中，他们可能很容易写出 Swap(a[i], a[j]) 其中有时 i 碰巧等于 j，或 Swap(*p, *q) 有时指针 p 恰好等于 q.

And there is actually an additional, crashing problem when you try to write a 'swap' macro this way, which is that it will not work — it will set one or both variables to 0 instead of swapping the values — if the caller ever tries to swap a value with itself. You might say that's not a problem, since maybe nobody would ever write Swap(x, x), but in a less-than-perfectly-optimal sorting routine they might very easily write Swap(a[i], a[j]) where sometimes i happened to be equal to j, or Swap(*p, *q) where sometimes the pointer p happened to be equal to q.

另请参阅C 常见问题列表，问题3.3b, 10.3 和 20.15c.

See also the C FAQ List, questions 3.3b, 10.3 and 20.15c.

这篇关于两种不同的交换函数有什么区别?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！