「値のswapとか今更」って思ってました - 活きのいいコード目指すお

はじめに

色んなアルゴリズム、勉強しちゃおうぜ。
ということで、「奥村晴彦著　C言語による最新アルゴリズム事典」を入手してきました。 (ホントは同氏著のJavaによるアルゴリズム事典が欲しかったんですが、こっちは絶版になっていたのでこちらを購入しました)

まずは「値swap」のお話から。

今更swapとかはスルーしてもいいんじゃないかなって思ったんですが、ためになることも書かれていました。
こいつぁいい本ですね！！

C言語による最新アルゴリズム事典 (ソフトウェアテクノロジー)

作者: 奥村晴彦
出版社/メーカー: 技術評論社
発売日: 1991/03
メディア: 単行本
購入: 20人クリック: 396回
この商品を含むブログ (96件) を見る

let's swap

有名なswap(すわっぷ: exchange of values)さん。
2つの変数(a,bとする)の値を入れ替えることを言いますが、なんとなくまず思いつく方法としては、第3の変数(temp)とするを使って、

#!/usr/bin/env python
# -*- coding: utf-8 -*-
def swap(x, y):
    temp = x
    x = y
    y = temp
    return (x, y)

a, b = 3, 7
(a, b) = swap(a, b)
print(a, b)

というように、一旦片方の値を退避してから着実に交換する方法かと思います。

tempとかいらなかった

「一旦値を避けるとかそれこそ逃げだよね」
できたらいいなとは思っていたんですが、やっぱりtempなんてなくてもできたんですねー。
何となく方法ググってなかったんですが、なんだかんだで積年となってしまっていた思いが解消されました。
方法としては、

排他的論理和
加算減算
乗算除算

のどれかを使うことで実現できます。

排他的論理和

まずは実装から

#!/usr/bin/env python
# -*- coding: utf-8 -*-
def swap(x, y):
    y ^= x
    x ^= y
    y ^= x
    return (x, y)

a, b = 3, 7
(a, b) = swap(a, b)
print(a, b)

これは排他的論理和の性質( $a \oplus a = 0, (a \oplus b) \oplus c = a \oplus (b \oplus c)$ )を利用すると証明できます。$ \eqref{eq: oplus} $

$$ \begin{align} \begin{split} y' &= x \oplus y \\ x' &= x \oplus y' = x \oplus (x \oplus y) = (x \oplus x) \oplus y = y \\ y'' &= y' \oplus x' = (x \oplus y) \oplus y = x \oplus (y \oplus y) = x \end{split} \label{eq: oplus} \end{align} $$ 上で言う $ x' $と$ y'' $がそれぞれswap後の$ x $と$ y $を表します。(「'」:ダッシュは各変数の更新回数を表しており、新しい変数を定義しているわけではありません)

加算減算

排他的論理和を使わなくても、加算減算でも同じ結果を得ることができるとのこと。

#!/usr/bin/env python
# -*- coding: utf-8 -*-
def swap(x, y):
    y = x - y
    x -= y
    y += x
    return (x, y)

a, b = 3, 7
(a, b) = swap(a, b)
print(a, b)

こちらもサラッと証明風のことをしておきます。(ただの変数遊び) $ \eqref{eq: plus_minus} $

$$ \begin{align} \begin{split} y' &= x - y \\ x' &= x - y' = x - (x - y) = y \\ y'' &= x' + y' = y + (x - y) = x \end{split} \label{eq: plus_minus} \end{align} $$

乗算除算

条件付きではありますが、乗算除算を利用してもいけるそうです。

#!/usr/bin/env python
# -*- coding: utf-8 -*-
def swap(x, y):
    y = x / y
    x /= y
    y *= x
    return (x, y)

a, b = 3, 7
(a, b) = swap(a, b)
print(a, b)

これにかんしてもサr・・・(ry $ \eqref{eq: multi_devide} $ $$ \begin{align} \begin{split} y' &= \frac{x}{y} \\ x' &= \frac{x}{y'} = \frac{x}{\frac{x}{y}} = y \\ y'' &= x' * y' = y * \frac{x}{y} = x \end{split} \label{eq: multi_devide} \end{align} $$ 条件付き、と言いましたが、上を見てもお分かりいただけるように、ちょいちょいyが分母に来ます。
ということで、yが0でないこと($ y \neq 0 $)となります。

条件判定が余分に必要になってしまうことを考えると、こちらは実用的ではなさそうですね。使うとすればシンプルに「加算減算」verを使うか、よりよい計算効率を求めてビット演算を行うかのどちらかになるかと思います。