アルゴリズムとデータ構造編【その他のアルゴリズム】 第1章 交換のアルゴリズム

先頭へ戻る

この章の概要

この章の概要です。


値の交換

この章では、アルゴリズムというものを考えるに当たって、ごく簡単な事例として、2つの変数に格納された値を交換する方法を取り上げます。

実際のプログラミングでは、値の交換は至るところで行われます。

例えば、配列(【データ構造】第1章参照)に格納された複数の整数を昇順に並び替えようとするとき、多くの整列アルゴリズム(【整列】参照)では、2つの値の交換を繰り返すことで実現しようとします。

また、文字列を逆順になるように反転させる操作も、先頭と末尾、先頭+1 と末尾-1 … といったように文字を交換していく操作に他なりません。

このようによく使われる操作ですから、効率的な形で部品化しておくことも考えるべきでしょう。その点に関しても取り上げます。

一時変数を使う

まず、初心者にありがちなミスを取り上げておきます。

#include <stdio.h>

int main(void)
{
    int a = 10;
    int b = 20;

    /* 変数a と b の値を交換している? */
    a = b;
    b = a;

    printf( "%d %d\n", a, b );

    return 0;
}

実行結果:

20 20

変数a と b の初期値はそれぞれ、10 と 20 ですから、正しく交換できていれば出力結果は「20 10」となるはずですが、そうなっていません。したがって、この実装には間違いがあるということです。

a = b;
b = a;

という実装は、ぱっと見では確かに交換しているように見えるかもしれませんが、それは、この2つの文が「同時に」実行されるように考えてしまっているからです。実際には「1つずつ」実行されるのですから、最初の a = b; が実行された後の時点で、変数a と b は両方とも 20 になってしまいます。

何が起こっているか詳しく書くと、次の表のようになります。上から順番に時系列になっていると考えてください。

過程 変数a の値 変数b の値
初期状態 10 20
a = b; 実行後 20 20
b = a; 実行後 20 20

結局、問題なのは「a = b;」の実行後には、変数a の元の値である 10 が失われてしまう点にあります。この 10 がないと、変数b を 10 にできないのは当然といえば当然です。

そこで、変数a の 10 をいったん、どこかに退避させてしまおうという考えが浮かびます。そのように書き換えると、次のようになります。

#include <stdio.h>

int main(void)
{
    int a = 10;
    int b = 20;
    int tmp;

    /* 変数a と b の値を交換している */
    tmp = a;
    a = b;
    b = tmp;

    printf( "%d %d\n", a, b );

    return 0;
}

実行結果:

20 10

実行結果を見る限り、今度は正しく交換できているようです。今度は何が起きているのか、先ほどのように表にまとめてみます。

過程 変数a の値 変数b の値 変数tmp の値
初期状態 10 20 不定
tmp = a; 実行後 10 20 10
a = b; 実行後 20 20 10
b = tmp; 実行後 20 10 10

今度は「a = b;」の実行後の時点で、変数a の元の値 10 が、変数tmp に保存されていますから、これを使えば、変数b を 10 にできます。

このように、別の変数にいったん、値を退避させておけば、値の交換が実現できます。このとき、変数tmp のような作業用に使われる変数を、一般に一時変数とか作業用変数などと呼びます。

1文で書ける言語の場合

C言語では不可能ですが、プログラミング言語の種類によっては、3文も使わなくても交換の処理を記述できることがあります。

最初に間違った方法を見たとき、その説明文の中に次のようなものがありました。
"この2つの文が「同時に」実行されるように考えてしまっているから"
であるのならば、「同時に」実行できるのなら問題はない訳です。例えば、Perl という言語の場合、次のように書けます。

my $x = 10;
my $y = 20;

# 変数x と y の値を交換している
($y, $x) = ($x, $y);

実行結果:

20 10

これは、1文だけで、2つの変数の値を2つの変数へ代入しています。こういう方法が使える言語なら、このように書いてしまった方が簡単だし、大抵は効率的です。

突然、変数名が a, b でなくなったのは、Perl では $a と $b は特定の用途に予約されているためです。

XOR演算を使う

もう1つ、別の手法を紹介しておきましょう。今度は、ビット単位の XOR演算を利用します(C言語編第49章参照

XOR演算は、ビット同士を比較したとき、いずれか一方だけが 1 のときに結果が 1 になるビット演算です。この演算は、2回繰り返すと、元のビット列に戻るという特性があります。この特性をうまく利用すると、値を交換できます。

#include <stdio.h>

int main(void)
{
    int a = 10;
    int b = 20;

    /* 変数a と b の値を交換している */
    a ^= b;
    b ^= a;
    a ^= b;

    printf( "%d %d\n", a, b );

    return 0;
}

実行結果:

20 10

変数の値の変化を確認してみましょう。( ) の中の数値は 2進数に変換したものです。

過程 変数a の値 変数b の値
初期状態 10 (00001010) 20 (00010100)
a ^= b; 実行後 30 (00011110) 20 (00010100)
b ^= a; 実行後 30 (00011110) 10 (00001010)
a ^= b; 実行後 20 (00010100) 10 (00001010)

これだけだと原理がよく分からないと思います。次のように、各過程での結果ではなく、各過程で適用されている式を書き出してみると原理が見えてきます。

過程 変数a に適用されている式 変数b に適用されている式
初期状態 a b
a ^= b; 実行後 a ^ b b
b ^= a; 実行後 a ^ b b ^ (a ^ b)
a ^= b; 実行後 (a ^ b) ^ (b ^ (a ^ b)) b ^ (a ^ b)

XOR演算を2回適用すると元の値に戻るということは、「(a ^ b) ^ b == a」だということです。従って、「b ^= a; 実行後」という行の変数b の式「b ^ (a ^ b)」は結局のところ、「a」に置き換えられるということです。

同様に、一番下の行の変数a の式「(a ^ b) ^ (b ^ (a ^ b))」は、「(a ^ b) ^ a」となります。これはさらに進めて「b」にまで置き換えられます。

このように式を縮めた状態で表記すれば、次のようになります。

過程 変数a に適用されている式 変数b に適用されている式
初期状態 a b
a ^= b; 実行後 a ^ b b
b ^= a; 実行後 a ^ b a
a ^= b; 実行後 b a

ということで、一番下の行の結果を見ると、確かに変数a と b の値は入れ替わっています。

この手法は、ビット演算を利用しているため、素直に適用できるのは整数の場合だけです。また、a と b が同じ変数の場合には、結果がともに 0 になってしまうため、使い方に注意が必要です。

この手法は、一時変数を必要としないため、メモリアクセスの回数を減らす効果があり、効率的である可能性があります。現実的には、他にもさまざまな要因が絡むため、一時変数を使った方法とどちらが高速になるかは、実測してみるしかありません。


部品化

ここでは、一時変数を使う方法で部品化してみます。

C言語で関数化すると次のようになります。

#include <stdio.h>

static void swap(int* a, int* b);

int main(void)
{
    int a = 10;
    int b = 20;

    swap( &a, &b );

    printf( "%d %d\n", a, b );

    return 0;
}

void swap(int* a, int* b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

実行結果:

20 10

引数a と b はポインタ変数(C言語編第31章参照)でなければなりません。

ポインタ変数である以上、NULL が渡される可能性がありますから、厳密にはそのチェックが必要です。しかし、呼び出し回数が非常に多くなることが想像される関数ですし、使い方を考えると誤って NULL を渡す可能性はかなり低いでしょう。そういう意味で、あまり NULLチェックしているものは見かけません。

関数を使うと、関数呼び出しに伴う時間的なコストが掛かります。また、(これはC言語の事情ですが)int型などの特定の型に依存してしまうため、「double型の値を交換したい」という要望があれば、別の関数が必要です。

インライン関数の利用

プログラミング言語の種類によっては、インライン関数を用いることで時間的なコストは無くせます。 例えば、C++ では次のように書けます。

inline void swap(int* a, int* b)  // ※ヘッダ側に記述する
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

インライン関数は、コンパイルの時点で、関数の中身を呼び出し側に展開します。従って、コード上は関数呼び出しのように見えますが、実際には関数呼び出しが起こらなくなります。

インライン関数は、C言語であっても、C99規格に対応しているコンパイラであれば利用できます(C言語編第28章)。

ジェネリクスの利用

プログラミング言語の種類によっては、特定の型に依存してしまう問題を、ジェネリクスの利用によって解決できます。例えば、C++ では次のように書けます。

template <typename T>
void swap(T* a, T* b)
{
    T tmp = *a;
    *a = *b;
    *b = tmp;
}

int型などの特定の型の代わりに、T という総称型を用いると、T の部分に任意の型を当てはめることが可能になります。

int a, b;
double c, d;

swap( &a, &b );  // 自動的に T は int型と判断
swap( &c, &d );  // 自動的に T は double型と判断
swap<int>( &a, &b );    // 明示的に T に int型を指定
swap<double>( &c, &d ); // 明示的に T に int型を指定


C言語では、マクロ(C言語編第28章参照)を使うことも考えられます。

#define SWAP(type,a,b) { type work = a; a = b; b = work; }

マクロの場合、関数呼び出しのコストが無くなるので、時間的な効率は向上します。 一方で、コードが呼び出し位置にコピーされた状態になるので、プログラムサイズが増加します。また、マクロは潜在的に危険が伴うことを理解していなければなりません。

この SWAPマクロの実装について、C言語編で詳説しています。

まとめ

値を交換する方法について、代表的な2つのアルゴリズムを取り上げました。効率面でどちらが優れているかは、プログラムを実行する環境によって変わってきますから、効率を求めるのなら実測に基づいて判断する必要があります。

ただし、プログラミング言語によっては、値の交換の処理は標準機能として用意していることもあるので、そちらを使うことを考えた方がいいかもしれません。

また、プログラミング言語の種類によっては、その言語特有の機能が利用できることにも触れました。アルゴリズムは考え方であり、特定の言語に依存しない抽象的なものです。それを実際のコードに落とし込むに当たっては、プログラミング言語の特性を理解し、より良い実装を探る必要があるのです。これは、交換のアルゴリズムだけに限ったものではなく、いかなるアルゴリズムで共通しています。


練習問題

問題① XOR演算による方法を関数化してください。

問題② 部品化した交換アルゴリズムを使って、文字列を反転させるプログラムを作成してください。


解答ページはこちら


参考リンク



更新履歴

'2015/2/21 サンプルプログラムで、ファイルスコープでよい関数に static を付加。

'2012/11/11 「ジェネリクスの利用」の項のサンプルプログラム内で、変数名が間違っていたのを修正。

'2011/10/10 新規作成。



次の章へ (第2章 ランダムシャッフル)

アルゴリズムとデータ構造編のトップページへ

Programming Place Plus のトップページへ


はてなブックマーク Pocket に保存 Twitter でツイート Twitter をフォロー
Facebook でシェア Google+ で共有 LINE で送る rss1.0 取得ボタン RSS
管理者情報 プライバシーポリシー