錬金術師＠溜まり場の感想

変愚蛮怒 Web

中身についてはとりあえず後回しに、基本的な方針の確認をしておく。

新クラスを作るなら。

まず、そのクラスの特色を明確にする必要がある。特色としては

  • どのような立ち回りができるのか。

という部分を重視するべきだ(と私は思う)。

特色について。

私はクラスの特色を大まかに

  • ダメージソース
    • 近接打撃
    • 遠距離攻撃
  • 搦め手
    • 緊急回避（*破壊*、レベルテレポ）
    • ドーピング
    • スレイング
    • 状態異常
    • ペット

というように分けて考えている。
近接打撃職では戦士を単純形として、＋緊急回避（生命プリ、カオス混沌）、＋ドーピング（匠盗賊、超能力者）、＋スレイング（鍛冶）、＋状態異常（修行僧）、＋ペット（魔獣使い、騎兵）。同様に遠距離攻撃職ではアーチャーを単純形として、＋緊急回避（カオスハイ、破邪ハイ）、＋ドーピング（錬気）、＋スレイング（青魔）、＋状態異常（詩人）。十分な固有ダメージソースを持たない魔道具、仙術ハイ、トランプハイなどはその分搦め手が充実している。
どのような搦め手が使えるか、は立ち回りに大きな影響を与える。むしろダメージソースよりも重要なのではないだろうか。
例えば、スナイパーは遠距離攻撃＋溜め撃ちで、錬気術師よりもリスクとリターンが大きいという点が立ち回りの違いを作り出している。例えば、呪術ハイは近接打撃＋ドーピングだけではなく、カウンター、魔法妨害という搦め手を備えている。

〆。

その辺りを考えると、今回の錬金術師は特色が弱いかな。システム面で無茶するのが大好きな人が言うことなので話半分に受け取ってほしいけれども。

おまけ。

どちらかというと「戦力が消耗品に大きく依存する」というクラスにするのはどうだろうか。
現在は「薬を生成する」という特色になっているが、これを「薬の効力を強める」という方向に変える。具体的には

  • 薬を消費する攻撃魔法を使う。（DCの蒸散のパクり）
    • 油壷で火炎のボール
    • 毒・睡眠などの薬で状態異常のボール
    • 突然変異の薬でカオスのボール
  • 薬を消費する補助魔法を使う。
    • 能力アップの薬でパラメータをドーピング
    • ネオつよしスペシャルの薬で最大HPをドーピング！
  • 最大HPを越えて体力を回復できる。（剣術家の気合い溜めと同様、超過分は時間の経過とともに失われる）

などなど。上位魔法は複数の薬を消費しても良さそう。

再開発≠再実装

言語 雑記

http://d.hatena.ne.jp/tt_clown/20091228/1261996214、http://d.hatena.ne.jp/monjudoh/20091228/1262023451、http://d.hatena.ne.jp/Isoparametric/20091230/1262134418の話。

態度表明。

先に明言しておくと、私は「再開発はするな。再実装は考えてからしろ」という意見だ。これだけだと是々非々＝単なる日和見ともとれる無意味な意見になってしまうので、以下では再実装するべき条件について書く。

STLコンテナの現状を。

STLコンテナ共通の仕様では主要インターフェースが定義されている。STLではこのインターフェースを用いて検索やソートなどの基本アルゴリズムを利用する。この仕組みはC++ templateの基本思想に沿って作られており、オーバーヘッドを最小(大抵の場合は文字通り0)にすることができる。
STLコンテナ個別の仕様ではコンテナ全体のメモリ効率や主要インターフェースの速度効率まで定義されている。大抵の場合は用途にあったスペックのコンテナを選ぶ、要求水準が高ければ複数のコンテナ・複数のSTL実装を実ベンチマークで比較して選ぶ、というように開発を効率化することができる。
このような過程を経たC++コードは大抵の手書きCコードと同程度の性能を持つ。メモリアロケータのチューニングを行えばCコードを上回る性能に至ることもしばしばある。

目的と対応を考える。

学習目的
これは実装したコードが目的ではなく実装する行為が目的なので、再実装するのも再開発するのも自由だろう。
コードサイズ削減
大抵のSTLやtemplateはコードサイズの最小化を目的としていないため、単純にSTLを使うのでは失敗する。
追加機能
この場合に再開発するのは無駄だろう。Boostなどを参考にしつつ、STLコンテナを拡張したコンテナを開発するべきだ。
性能目的
STL範囲内でのチューニングで要求性能を満たせない場合もある。この場合の再実装のみが議論の対象になっていると思う。

要求性能を満たせないなら。

STLコンテナを適切に使っても要求性能を満たせない場合、次のような可能性を疑っておく必要がある。これらが原因ならば用途に特化したコンテナを用意してオーバーヘッドを削った程度では解決できないと思われる。遡って軌道修正するべきだろう。

  • そもそも要求水準が高すぎる。
  • 不適切なアルゴリズムを利用している。
  • 排他・同期に時間をとられている。

こういった問題がないことが明らかであってコンテナの性能を高めなければならない場合に初めて再実装を行う意味があると思う。その場合にもSTLコンテナの延長として開発するべきではないだろうか。STLコンテナのテストケースの大半を流用して品質を担保できるという点も魅力である。
例えば、stl::vectorのような擬似配列であれば、要素の追加・挿入の速度を犠牲にしても平均メモリ効率を向上したいことがある。このような要望は十分考えられるものだが、insert()時などに適宜reserve()を呼ぶようにstl::vectorを拡張すれば済むはずだ。また、STLコンテナのサブセットとして開発するのもよい。要素数を増減する必要は一切ないという条件ならばstl::vectorよりも高速な擬似配列を作るのも容易だろう。ただし、そういったコンテナは大抵Boostに存在していることを忘れてはならない。

〆。

STLなど、標準ライブラリ相当のものを再実装するのは確実に無駄だと思う。それとは逆に、"社内標準"など、ローカルライブラリは大抵ゴミなので標準ライブラリで置き換えることを考えるべきだと思う。

エラー握りつぶし

言語 ダメなコード

ありがちダメなコードのダメな理由を書くコーナー。

#include <stdlib.h>
#include <math.h>
#include <stdio.h>

int mysqrt(int x) {
  if (x < 0) {
    return 0;
  } else {
    return (int)sqrt(x);
  }
}

int main() {
  printf("%d\n", mysqrt(4));
  printf("%d\n", mysqrt(1));
  printf("%d\n", mysqrt(0));
  printf("%d\n", mysqrt(-1));
  
  printf("%f\n", sqrt(4));
  printf("%f\n", sqrt(1));
  printf("%f\n", sqrt(0));
  printf("%f\n", sqrt(-1));
  
  return 0;
}

をコンパイルして実行すると、

$ gcc -std=c99 -pedantic -O0 -lm -g tmp.c
$ ./a.out
2
1
0
0
2.000000
1.000000
0.000000
nan

と出力された。

"nan"って何？

"nan"とは"Not a Number"の略で、和訳時には非数と称されるもの*1。文字通り、数値では表せない値を表現するのに用いられる。次のような条件の場合、CPU例外として扱われるか、または計算結果としてNaNを返す。

  • 数学関数に定義域外の引数を与えた。
  • 0で割り算を行った。

何がダメなのか。

大抵のNaNは途中の計算にエラーがあったことを示す。そのNaNをintにキャストした結果はただの0なので(intにNaNはない)、mysqrt(0) == mysqrt(-1)というように、エラーが通常出力に紛れて判別不能になっている。
この類の間違いは正常処理に影響を与えない／与えにくいために放置されることが多い。しかし、例外処理／異常処理として扱われるべきものが正常処理に紛れ込んでいると、大量の処理結果を並べるとどこか歪なものになるだろう。
例えば、上の例では入力に負数を含む分だけ出力の0点にスパイクが立つことになる。これを「この関数はこういう特性だから〜」と後処理で切り捨てるといった手法はカーゴカルトプログラミング*2そのものだ。

〆。

基本は次の分岐表にしたがってください。

  • 呼び出し先はエラーを返すか？
    • エラーを返さない→値をそのまま返して良い
    • エラーを返すかもしれない→エラーチェックした結果は？
      • 正常→値をそのまま返して良い。
      • 異常→リカバリは可能か？
        • 可能→リカバリ結果は？
          • 成功→リカバリ結果を返す。
          • 失敗→自分もエラーを返す。
        • 不可能→自分もエラーを返す。

追記

こういった「失敗を検出できない仕組み」はフェイル・セーフの観点からもダメなコード。NaNを返すことができない環境でも最低限ログを出力すること。

int mysqrt(int x) {
  if (x < 0) {
    LOG_PRINTF("[%s:%d] Invalid argument! x < 0\n", __FILE__, __LINE__);
    return 0;
  } else {
    return (int)sqrt(x);
  }
}

*1:http://ja.wikipedia.org/wiki/NaN

*2:http://en.wikipedia.org/wiki/Cargo_cult_programming

ソートの速度を決める要因についてメモ

雑記 開発

思いつく限りの要因をあげてみる。

  • データ内容
    • 個別比較が必要かどうか
    • 比較にかかる時間
    • 比較の分割性
    • 比較の並列度
  • データ
    • 要素数
    • 読み込みにかかる時間
    • 読み込みの並列度
    • 交換にかかる時間
    • 交換の並列度
  • ワーキングメモリ
    • 要素数
    • 再帰段数
    • 読み込みにかかる時間
    • 読み込みの並列度
    • 書き込みにかかる時間
    • 書き込みの並列度
  • 初期状態
    • どの程度ソートされているか
    • 事前にソートの程度を知っているか

具体例は。

スパゲティソート
個別に比較する必要がない。比較にかかる時間は定数。並列度は要素数と同じ。
辞書順ソート、多倍長数値のソート
個別に比較する必要がない。比較にかかる時間が各データ長Nに比例する。比較をN段階に分割できる。並列度は要素数と同じ。
データベース上のソート
通常、要素数は非常に大きい。読み込みにかかる時間も大きい。交換にかかる時間も大きいが、読み込みより小さい。並列度は実装に大きく依存し、それなりに高いものが多い。

〆。

通常はソートの計算量の指標として個別比較の回数を用いる。もちろんこれは大抵の場合に適切だが、交換よりも読み書きで律速される条件も多い。読み書きは特にハードウェアへの依存が大きく、同一アルゴリズムでも実装によって効率が大きく変わってくる。身近な例としてキャッシュヒット率があるだろう。

期待されない答え

Web 言語

http://d.hatena.ne.jp/skelton_boy/20091217/1261053652の話、というよりhttp://d.hatena.ne.jp/Isoparametric/20091219/1261201890の話。ポータブルに仕様の穴を突く方向で考えてみた。

/* MyTypeの定義 */
typedef int MyType[1];

void set(MyType m, int val);
void inc(MyType m);
void print(MyType m);

int main(void)
{
  MyType m;
  set(m, 0); /* mを0にセット */
  inc(m); /* mをインクリメント */
  print(m); /* 1と表示される */
  return 0;
}
/* 各関数の実装 */
static int m;/* mがローカルなんてどこにも書いていないよね！ */
void set(MyType m, int val) {
  do {
    extern int m;
    m = val;/* mを0にセット */
  } while (0);
}
void inc(MyType m) {
  do {
    extern int m;
    ++m;/* mをインクリメント */
  } while (0);
}
void print(MyType m) {
  puts("1");/* 1と表示される */
}

〆。

set(), inc()は冗談だけれど、print()は現実に起こり得る間違いなので注意。

毒魔を育てる

Web 雑記 Dungeon Crawl

＠の溜まり場IIで「毒→妖→地はどう？」と話を振ったのだけど、「ありかもしれないが微妙」というところで終わってしまった。向こうは今更なので続きをここに書く。

毒の特徴は。

  • 利点
    • 毒針は序盤の攻撃魔法では最強だろう。
    • 悪臭の雲は序盤から中盤まで搦め手として使える。
    • 蜘蛛の躯は毒液と俊足を同時に得られる。
    • 毒の耐性を魔法で得られる。
    • サソリの召喚は複数現れて攻撃力も期待できる。
    • 毒素の矢は総ダメージが大きい。
    • (NEW!)乗り換え時の成長阻害がない。
    • (NEW!)シフ信仰時の魔法書打ち止めが早い。
  • 欠点
    • アンデッドやデーモンに対処しづらい。
    • 最上位魔法の毒素の矢・猛毒の雲がLv6しかない。
    • 以前、耐性バグ(修正済)で毒素の矢が弱くなっていた。
    • 経験値と呪文スロットが無駄になる。

というようなところだろうか。終盤はどうしようもないとしても、序盤〜中盤は十分に役立つものが多いと思う。しかし、

  • 代替手段
    • 毒針は手投げ毒吹き矢で済む。
    • 悪臭の雲より蒸散の方が強い。
    • 蜘蛛の躯より俊足の方が安い。浮遊と組み合わせればさらに良い。
    • 毒耐性も属性変異で得られる。
    • 毒素の矢より水晶槍で素早く殺したい。

というように微妙感が満載だ。これをもうちょっと何とかできないものか。

水晶槍ルート

闇エルフ、刺客、ヴェフメット信仰で進める。毒スキルを抑制し、妖術スキルを伸ばす。手詰まりに陥る前に鉄塊の矢を使えるようになればOK。

暗殺術の魔法書(初期)
毒針で経験値を稼ぐ。騒音の投射で強敵を避ける。悪臭の雲はなるべく使わない。
妖術の魔法書(下賜)
石錐の矢があれば訓練用に習得する。
力の魔法書(下賜)
鉄塊の矢に移行する。
殲滅の魔法書(下賜)
レフディブの水晶の槍を常用できるようになれば完成。

注意点は以下の通り。

  • ヴェフメットから二冊の下賜を受けるまでが長い。
  • 鉄塊の矢に移行するまではカモ以外と戦わない。
  • 悪臭の雲なしでは中盤を生き抜けないが、風スキルが地スキルの成長を阻害するので控えめに。
  • 毒素の魔術師で開始して毒液の矢を中盤の主力に据えるのは普通なので省略。

おぞまールート

泥エルフ or 水棲の民、毒素の魔術師、シフ信仰で進める。召喚スキル＞妖術スキルは困難だが必須。

初級毒殺者の手引書(初期)
毒針で経験値を稼ぐ。悪臭の雲で搦め手を補う。妖術スキルを抑制し、毒スキルを伸ばす。
毒害の魔法書(下賜)
サソリの召喚を常用する。毒スキルを抑制し、召喚スキルを伸ばす。
招集の魔法書(下賜)
小動物の召換でサソリを補助する。
召換の魔法書(下賜)
解放の宣誓、招来が便利。おぞましきものを数体連れ歩けるようになれば完成。

注意点は以下の通り。

  • 泥エルフの方が召喚スキル適正が高く、水棲の民の方が白兵戦能力が高い。
  • サソリの召喚を毒スキルのみで使う期間が厳しい。反逆対策も必要。
  • 寺院前に毒害の魔法書を手に入れた場合(獲得など)はヴェフメット信仰も選べる。

刃の手ルート

泥エルフ、毒素の魔術師、シフ信仰で進める。泥エルフ変異術師よりも序盤が楽、というところが利点。

初級毒殺者の手引書(初期)
毒針で経験値を稼ぐ。悪臭の雲で搦め手を補う。妖術スキルを抑制し、毒スキルもそこそこに、徒手格闘スキルを伸ばす。
毒害の魔法書(下賜)
蜘蛛の躯を常用する。毒スキルを抑制し、変異スキルを伸ばす。
小変異の魔法書(下賜)
刃の手を常用する。

注意点は以下の通り。

  • 腕力強化がないので打撃力が不足しがち。
  • 搦め手が少ないので手詰まりに陥りやすい。呪術か召喚を加えると大幅に安定する(はず)。

〆。

実用レベルなのは刃の手ルートだけかも。

RAIIの代用

言語 雑記

C++だとRAIIでリソースの後始末ができる。CだとRAIIが使えないが代案を考えてみた。エラーコードが雑なのは気にしないで。

ありがちなもの。

int func(char const* filename) {
  FILE *fout = fopen(filename, "a+");
  if (fout == NULL) {
    return -1;
  }
  fprintf(fout, "Logging ...\n");
  if (do_something()) {
    fclose(fout);
    return -1;
  }
  fprintf(fout, "Logging ...\n");
  if (do_something()) {
    fclose(fout);
    return -1;
  }
  fprintf(fout, "Logging ...\n");
  fclose(fout);
  return 0;
}

リソースの後始末が面倒だよね。

もう一つのありがちなもの。

int func(char const* filename) {
  int ercd = 0;
  FILE *fout = fopen(filename, "a+");
  if (fout == NULL) {
    ercd = -1;
    goto ON_EXIT;
  }
  fprintf(fout, "Logging ...\n");
  if (do_something()) {
    ercd = -1;
    goto ON_EXIT;
  }
  fprintf(fout, "Logging ...\n");
  if (do_something()) {
    ercd = -1;
    goto ON_EXIT;
  }
  fprintf(fout, "Logging ...\n");
ON_EXIT:
  fclose(fout);
  return ercd;
}

ercdって変数は要らないよね。

思いついたもの。

static int func_impl(FILE *fout) {
  if (fout == NULL) {
    return -1;
  }
  fprintf(fout, "Logging ...\n");
  if (do_something()) {
    return -1;
  }
  fprintf(fout, "Logging ...\n");
  if (do_something()) {
    return -1;
  }
  fprintf(fout, "Logging ...\n");
  return 0;
}
int func(char const* filename) {
  FILE *fout = fopen(filename, "a+");
  int const ercd = func_impl(fout);
  fclose(fout);
  return ercd;
}

まともなコンパイラならfunc_implをインライン化するよね。