主题：【原创】继续关于swap的讨论 -- 不锈钢破锣
- 共: 💬 22 🌺 5
都知道程序设计里的swap()吧。一般是这么写的：
temp=a;
a=b;
b=temp.
如果不用临时变量，只用a,b这两个变量和算术运算该怎么办呢？再推广到逻辑门运算又该怎么办呢？
答案不是唯一的，楼下的朋友给的回答可以算其中之一，但还可以简化到三步：
a = a+b; (a:a+b, b:b)
b = a-b; (a:a+b, b:a)
a = a-b; (a:b, b:a)
推而广之，如果用一个实数域上的可交换运算符，比如*，来替换+，再用它的逆运算符，比如/，替代-， 结果同样成立。
但是，当应用于计算机时，答案中给出的交换方式有两个问题，一个问题是临时结果可能溢出(如果用*和/，会发生除0)，另一个问题是精度可能降低。所以这样的方法不适用于传统计算机结构。
如果把一个变量看成一个二进制数组A(1)，A(2)，...，A(i)，...，A(n), 现在再来看逻辑运算符XOR：
A(i) = A(i) XOR B(i);
B(i) = A(i) XOR B(i);
A(i) = A(i) XOR B(i);
这个表达方式很有意思，同样可以起到交换的作用，而且解决了上面的溢出和精度问题。
那为什么现在比较常用的方法还是使用临时变量呢？两个原因，一个是赋值运算比逻辑运算的速度更快；另一个是在编程方面，使用临时变量可读性更高。
从题目一开始就可以知道，新的运算方式节省了一个临时变量。这在传统计算机结构下是无足轻重的，但是，如果应用到新的计算机机构，比如量子机或者神经网络机，就需要重新衡量不同方法的效率。
从上面的例子可以看出，哪怕最简单的计算机问题，都未必是单一最优解的，原因主要在於问题的解决域不是单一的，从而导致最优解的衡量方式不同。也就是说，计算机科学所研究的往往不是地球围绕太阳转这一类普适性问题，而是条件约束问题。这也是计算机科学与物理之类自然科学在方法论上的主要区别。很可惜的是，当自然科学的方法论已经系统化时，计算机科学的方法论研究还不太成熟。关于这个问题，以后慢慢再谈。
本帖一共被 1 帖 引用 (帖内工具实现)
上回答应的关于方法论的文章，兄弟我还没忘。前阵子做的报告，因为是oral, 用powerpoint写的，而且是英文版，贴成文本可读性很差，所以准备用中文重新码。有些例子和描述也需要更新过以便于阅读。
上面这篇算是开个头，以后有空陆续写点。以我的散漫个性，写到哪里算哪里，只是表达一些观点跟网友们探讨一下。因为上网时间无法保证，文笔又生疏，比不得那些牛牛的出产频率，请谅解。
的存储程序计算机，又叫冯?诺依曼机
如果这个结构有所改变, 很多算法和结论恐怕都会要改变.
老兄谈到量子计算机中算法的问题。我想由于量子计算机是靠概率，而且量子计算机一个位可以同时表示两个变量，是不是对于两个变量交换的问题，只需要筛选变量的时候用不同的“筛子”就可以了？量子算法和现在的所有计算机算法差别太大，现在已由数学家研究处量子算法，有谁明白的，能否给简单解释一下。
似乎不是只有不锈钢兄提的这几条思路。很多很有趣的，匪夷所思，可惜我愚笨，都想不起来了。另外一个有趣的话题就是，“一行”程序，程序只有一行，也能干很复杂的事。
(1)
temp=a;
a=b;
b=temp;
固然要用一个临时变量,但是
(2)
a=a+b;
b=a-b;
a=a-b;
是不是只是在表面上不用临时变量?
拿 "a=a+b;"打个比方:变量 a 在assignment的两边都出现,那么一个compiler是
如何编译这个a=a+b的? 除了暗中用一个临时变量,还有其它办法吗?
即这样:
temp=a+b; a=temp;
也就是说 a 不能同时被用来做加法,而在这个过程中又改变它的值.
更有甚者,(2)中的三行,每行都有一个变量同时出现在assignment的两边,那是不是
compiler要在暗中使用三个临时变量? 如果是这样,岂不是比在程序中明着使用
一个临时变量更糟糕吗?
都需要一个与临时变量相同大小的内存啊。
所以，不用临时变量的意义又在何处呢？
他只是举个例子。。。就如你没钱，一分钱你都要珍惜。。。如果你有一百万，随便请我几次客，可能你都会同意。。。搁浪财除外。。。
一个有optimzation功能的compiler，
对于
temp =a;
a = b;
b = temp;
这样的简单指令，也可以把temp的值放到register里（放一次），
而并不真正使用一个临时变量。
而对
a=a+b;
b=a-b;
a=a-b;
要放三次。
所以我还是不明白， 不使用临时变量有什么更好处呢？
他只是假设其他不变，也不作什么OPTIMAZATION(那个功能有没有都是疑问，放正我不知道)，如此这般，就可以省点内存（其实现在内存这便宜，没人干这事，当年贵时都没人干）。。。
他只是用这个做例子，讲其他东西。。。你别老钻在这里出不来。。。
btw,一个没有optimization的compiler对于
a=a+b这样一个指令的处理，一般就是把它
编译成temp=a+b; a=temp; 就是暗中用临时变量。
类似这种问题在写一些C++的operators时常常遇到。
也有人写文章，教人怎么尽量避免这种暗中
临时变量。倒不是为了省内存，主要是速度问题。
扯远了，呵呵。谢谢讨论。