2009-12-19

期待されない答え

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()は現実に起こり得る間違いなので注意。

2009-12-19

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

雑記開発

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

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

具体例は。

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

〆。

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