DevQuiz スライドパズルの反省点　「1stepでも処理を削る」

久々にC言語のプログラミングを行ったのですが、いろいろと忘れていることが多くあせりました。
自己反省をこめて備忘録として残しておきます。
C言語以外の言語でも同じことだと思います。
ひじょーーに初歩的なことです。

無駄な処理はなるべく削る

アルゴリズムがどうとか言う前に、コストのかかる無駄な処理を削る。

固定値はテーブル化してしまえ

以下のような、決まりきったパターンは毎回計算するのではなくテーブル化しましょう。

現在地から目標値までのManhattanDistanceの計算
現在地から上下左右に移動した場所の計算
その他の有限なパターンの計算
ごくごくわずかなforループ

現在地Aから目標値BまでのManhattanDistanceの値は以下の式で求めます。

md = abs( Aの横位置 - Bの横位置) + abs( Aの縦位置 - Bの縦位置 );

ですが、最高で6x6=36点しかないので、予めすべてのManhattanDistanceを計算しておいて、
2次元配列：ManhattanDistanceに格納しておく。

int ManhattanDistance[36][36];

md = ManhattanDistance[現在地A][目標値B];

現在地から上下左右に移動した場所も、毎回以下のようにしてしまうと計算コストが増大します

/* 左に移動 */
pos = 現在地 - 1;
/* 右に移動 */
pos = 現在地 + 1;
/* 上に移動 */
pos = 現在地 + 横幅;
/* 下に移動 */
pos = 現在地 - 横幅;

これもManhattanDistanceと同様に、各位置から上下左右の移動場所を予め計算しておいた方がいいでしょう。
ついでに壁の場合は、その印(=値)も入れておけばOK。

#define MOVE_L 0
#define MOVE_R 1
#define MOVE_U 2
#define MOVE_D 3

int MovePosition[][];

/* 左に移動 */
pos = MovePosition[ 現在地] [ MOVE_L ];
/* 右に移動 */
pos = MovePosition[ 現在地] [ MOVE_R ];
/* 上に移動 */
pos = MovePosition[ 現在地] [ MOVE_U ];
/* 下に移動 */
pos = MovePosition[ 現在地] [ MOVE_D ];

ごくごくわずかなforループ。

for(i = 0; i< 4; i++){

}

「i++」と「i< 4」がもったいないので、これならforループを使わずに処理をべた書きした方が速いかもしれません。

再帰呼び出しで数10億回の同処理を行うときは、上記のテーブル化だけでスピードアップが可能です。
その他にも、不必要な初期化：「int hoge = 0;」　やmemset()を削るとスピードアップ可能。
1stepでも処理を削ることが重要です。

「あの人と同じアルゴリズムなのにどうして解けないのだろう？」って思っている人は、
今一度、自分のソースコードが最適化されているかどうかチェックしてみるといいかもしれませんね。