アルゴリズムは使用するプログラミング言語に引きづられる

Written by じび on 10月 9th, 2018

某所で5分以内にプログラムを考えるという課題がありました。

最初にプログラミング言語を選択するのですが、最近は swift ばかりなので swift を選択しました。

その後に出たお題は「文字列を逆順にする。ただし、プログラミング言語にある逆順にする命令などは使わないこと」というものです。

そこで私の思考は、以下のようになりました。

  1. 文字列は文字の配列
  2. 配列を処理するならイテレータ
  3. 先頭から文字をとっていき、新しい配列の先頭にインサートしていけばいける

IDEなしだったので、仮想コードですが、以下のような感じに書きました。

let src = "hogemoge"
var dest = ""

for char in src {
    dest.insert(0, char)
}

しかし、帰りの電車で、C言語ならもっと効率良くできることに気づきました。

  1. 最初と最後の文字をスワップ
  2. 最初+1と最後-1の文字をスワップ
  3. 上記の処理を「文字数 / 2」回繰り返す
unsinged char *src = "hogemoge";
unsigned char swap;

for (int i = 0, int last = strlen(src) - 1; i < strlen(src) / 2; i++, last--, ) {
    swap = src[i]
    src[i] = src[last]
    src[last] = swap
}

なぜ、思いつかなかったのだろうと考えたのですが、最初に言語を選択していたため、そこでよく使う手法に囚われていたのです。swift だと文字列を文字単位で扱うことはあまりないため、配列として処理しようと考えてしまったのです。それに対してC言語はビット単位やバイト単位で扱うことが多いので、すんなりと効率が良いアルゴリズムに導かれたのでした。

「オブジェクト指向プログラミング入門 第二版 (ティモシイ・A. バッド)」の「1.2 言語と思考」にも、APLのプログラマが行列のソートで解決した話が載っていましたが、まさにその通りのことを身を以て体験したのでした。

 

Leave a Comment