Hena Hena Nikki

* [book] 工学のための確率・統計 / 北村, 尾崎, 東野, 中北, 堀

メモ。 工学系出身者はこういう基礎知識を持ってるから羨ましい。

* [computer][bookmark] Perl-5.8 覚え書き

土屋さんの文書。メモ。

このページは，Perl-5.8.2 を使う上で困ったことなどの覚え書きです．

* [computer] PowerPC G4 1GHz vs. Intel Core Duo 2GHz

新人研修でやらせた N クイーンの回答に 「ああ、なるほど」と思うものがあったので、 その実装を一部利用して適当に書いてみた。 要 C99 環境。

/**
 * @file    main.c
 * @brief   N クイーン問題の解の個数を求めるコマンド
 */

/* ヘッダ・ファイルの読み込み */
#include <stddef.h>     /* NULL, size_t */
#include <stdio.h>      /* printf, fprintf, putchar */
#include <stdlib.h>     /* atoi */
#include <string.h>     /* strcmp, memset */
#include <ctype.h>      /* isdigit */
#include <assert.h>     /* assert */
#if defined(__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L)
#include <stdbool.h>    /* bool (C99) */
#else   /* C99 */
#error  このコマンドのコンパイルには C99 対応コンパイラが必要です。
#endif  /* C99 */

/*
 * ** 盤の表現について **
 * - 盤は 1 次元配列を 2 次元配列と見たもので表現している。
 * - 値が負であれば、それは効き筋となっている。
 * - 値が 0 であれば、それは効き筋ではなく、クイーンもまだ置いてない。
 * - 値が正であれば、クイーンが既に置いてある。
 */

/**
 * @brief   盤の状態を出力
 * @param   file [out] 出力先
 * @param   board [in] 盤の情報
 * @param   width [in] 盤の幅
 * @param   count [in] 盤の表示の前に付ける正の数
 * @note    引数 count が負の数の場合、数字のつかない盤の表示になる。
 * @note    不適切な引数を適用した場合の動作は不定。
 */
void
Print(FILE* const file,
      const int* board,
      const size_t width,
      const int count)
{
    assert(file);
    assert(board);
    if (count < 0) {
        fprintf(file, ">>>>\n");
    }
    else {
        fprintf(file, ">>%d\n", count);
    }
    for (size_t l = width; l > 0; --l) {
        for (size_t c = width; c > 0; --c) {
            if (*board < 0) {
                fputc('X', file);
            }
            else if (*board == 0) {
                fputc('-', file);
            }
            else {
                fputc('Q', file);
            }
            ++board;
        }
        fputc('\n', file);
    }
}

/**
 * @brief   クイーンを置ける可能性を確認
 * @param   board [in] 盤の情報
 * @param   width [in] 盤の幅
 * @param   line [in] 行
 * @param   column [in] 列
 * @retval  true: 置ける
 * @retval  false: 置けない
 * @note    不適切な引数を適用した場合の動作は不定。
 */
inline bool
PutQueenOk(const int* const board,
           const size_t width,
           const size_t line,
           const size_t column)
{
    assert(board);
    assert(line < width);
    assert(column < width);
    return board[line*width+column] == 0;
}

/**
 * @brief   クイーンを置く
 * @param   board [in/out] 盤の情報
 * @param   width [in] 盤の幅
 * @param   line [in] 行
 * @param   column [in] 列
 * @note    不適切な引数を適用した場合の動作は不定。
 */
void
PutQueen(int* const board,
         const size_t width,
         size_t line,
         const size_t column)
{
    size_t left = column;
    size_t right = column;
    size_t line_width = line*width;
    assert(board);
    assert(line < width);
    assert(column < width);
    assert(board[line_width+column] == 0);
    board[line_width+column] = 1;
    while (++line < width) {
#if     defined(__i386__) || defined(__x86_64__)
        line_width += width;
#else   /* x86, x86_64 */
        line_width = line*width;
#endif  /* x86, x86_64 */
        if (left > 0) {
            --left;
            --board[line_width+left];
        }
        --board[line_width+column];
        if (++right < width) {
            --board[line_width+right];
        }
    }
}

/**
 * @brief   クイーンをどかす
 * @param   board [in/out] 盤の情報
 * @param   width [in] 盤の幅
 * @param   line [in] 行
 * @param   column [in] 列
 * @note    不適切な引数を適用した場合の動作は不定。
 */
void
RemoveQueen(int* const board,
            const size_t width,
            size_t line,
            const size_t column)
{
    size_t left = column;
    size_t right = column;
    size_t line_width = line*width;
    assert(board);
    assert(line < width);
    assert(column < width);
    assert(board[line_width+column] == 1);
    board[line_width+column] = 0;
    while (++line < width) {
#if     defined(__i386__) || defined(__x86_64__)
        line_width += width;
#else   /* x86, x86_64 */
        line_width = line*width;
#endif  /* x86, x86_64 */
        if (left > 0) {
            --left;
            ++board[line_width+left];
        }
        ++board[line_width+column];
        if (++right < width) {
            ++board[line_width+right];
        }
    }
}

/**
 * @brief   N クイーンの解を求める (盤の状態の出力あり)
 * @param   file [out] 出力先
 * @param   width [in] 盤の幅
 */
size_t
GetSolutions(FILE* const file,
             const size_t width)
{
    assert(file);
    size_t count = 0;
    if (width > 0) {
        int line = 0;
        int board[width*width];
        size_t columns[width];
        size_t column;
        memset((void*)board, 0, sizeof(int)*width*width);
        memset((void*)columns, 0, sizeof(size_t)*width);
        while (true) {
            column = columns[line];
            if (column < width) {
                if (!PutQueenOk(board, width, line, column)) {
                    ++columns[line];
                }
                else {
                    PutQueen(board, width, line, column);
                    if (++line >= width) {
                        ++count;
                        Print(file, board, width, count);
                        --line;
                        RemoveQueen(board, width, line, column);
                        ++columns[line];
                    }
                }
            }
            else {
                columns[line] = 0;
                if (--line < 0) break;
                RemoveQueen(board, width, line, columns[line]);
                ++columns[line];
            }
        }
    }
    return count;
}

/**
 * @brief   N クイーンの解を求める (表示なし)
 * @param   width [in] 盤の幅
 * @note    まだまだ改良の余地あり。
 */
size_t
GetNumberOfSolutions(const size_t width)
{
    size_t count = 0;
    if (width > 1) {
        const size_t half_width = width / 2;
        size_t line = 0;
        size_t i = 0;
        int board[width*width];
        size_t columns[width];
        size_t column;
        memset((void*)board, 0, sizeof(int)*width*width);
        memset((void*)columns, 0, sizeof(size_t)*width);
        while (i < half_width) {
            PutQueen(board, width, line, i);
            ++line;
            while (true) {
                column = columns[line];
                if (column < width) {
                    if (!PutQueenOk(board, width, line, column)) {
                        ++columns[line];
                    }
                    else {
                        PutQueen(board, width, line, column);
                        if (++line >= width) {
                            count += 2;
                            --line;
                            RemoveQueen(board, width, line, column);
                            ++columns[line];
                        }
                    }
                }
                else {
                    columns[line] = 0;
                    if (--line < 1) break;
                    RemoveQueen(board, width, line, columns[line]);
                    ++columns[line];
                }
            }
            RemoveQueen(board, width, line, i);
            ++i;
        }
        if (width % 2 > 0) {
            PutQueen(board, width, 0, half_width);
            i = 0;
            const size_t loop = half_width - 1;
            while (i < loop) {
                PutQueen(board, width, 1, i);
                line = 2;
                while (true) {
                    column = columns[line];
                    if (column < width) {
                        if (!PutQueenOk(board, width, line, column)) {
                            ++columns[line];
                        }
                        else {
                            PutQueen(board, width, line, column);
                            if (++line >= width) {
                                count += 2;
                                --line;
                                RemoveQueen(board, width, line, column);
                                ++columns[line];
                            }
                        }
                    }
                    else {
                        columns[line] = 0;
                        if (--line < 2) break;
                        RemoveQueen(board, width, line, columns[line]);
                        ++columns[line];
                    }
                }
                RemoveQueen(board, width, 1, i);
                ++i;
            }
            RemoveQueen(board, width, 0, half_width);
        }
    }
    else if (width == 1) {
        ++count;
    }
    return count;
}

/**
 * @brief   メイン関数
 * @note    コマンドとして呼ぶ際にオプションとして
 *          -p や -print を与えると解の盤を表示します。
 *          数字を与えると、その幅・高さを持つ盤で探索します。
 *          -h や -help を与えると使用方法を表示します。
 */
int
main(int arg_count,
     char** arg_strings)
{
    int width = 8;
    bool print = false;
    bool help = false;
    bool bad_arg = false;
    const char* arg_string = NULL;
    while (arg_count > 1) {
        arg_string = arg_strings[arg_count - 1];
        if (isdigit(*arg_string)) {
            const int number = atoi(arg_string);
            if (number > 0) {
                width = number;
            }
        }
        else if (*arg_string == '-') {
            ++arg_string;
            if (!strcmp(arg_string,"p")) {
                print = true;
            }
            else if (!strcmp(arg_string,"-print")) {
                print = true;
            }
            else {
                if (!strcmp(arg_string,"h")) {
                    help = true;
                }
                else if (!strcmp(arg_string,"-help")) {
                    help = true;
                }
                else if (!strcmp(arg_string,"hp")) {
                    help = true;
                }
                else if (!strcmp(arg_string,"ph")) {
                    help = true;
                }
                else {
                    --arg_string;
                    bad_arg = true;
                }
                break;
            }
        }
        else {
            bad_arg = true;
            break;
        }
        --arg_count;
    }

    if (!help && !bad_arg) {
        unsigned int number = 0;
        if (print) {
            number = GetSolutions(stdout, width);
            fprintf(stdout, ">>RESULT\n");
        }
        else {
            number = GetNumberOfSolutions(width);
        }
        fprintf(stdout, "解の数 (%d クイーン): %u\n", width, number);
    }
    else {
        if (bad_arg) {
            fprintf(stderr, "\"%s\"は不正なオプションです。\n", arg_string);
        }
        fprintf(stderr,
                "Usage: %s [-ph] [number]\n"
                "\tnumber\t\tボードの幅\n"
                "\t-p, --print\t解のボードをプリント\n"
                "\t-h, --help\tこのヘルプをプリント\n",
                *arg_strings);
    }

    return 0;
}

で、まあ、動くのは別に良いとして、 とりあえず Mac OS X 10.4.7 / iBook G4 1GHz / GCC 4.0.1 の結果。

$ gcc -Wall -O3 -mcpu=7450 -pipe -fno-strict-aliasing -std=c99 -DNDEBUG main.c -o nqueen
$ time ./nqueen 15
解の数 (15 クイーン): 2279184
16.753u 0.068s 0:18.40 91.3%    0+0k 0+2io 0pf+0w

$ gcc -Wall -Os -mcpu=7450 -pipe -fno-strict-aliasing -std=c99 -DNDEBUG main.c -o nqueen
$ time ./nqueen 15
解の数 (15 クイーン): 2279184
26.024u 0.106s 0:29.28 89.2%    0+0k 0+2io 0pf+0w

次に Mac OS X 10.4.7 / MacBook Pro Intel Core Duo 2GHz / GCC 4.0.1 の結果。

$ gcc -Wall -O3 -march=prescott -pipe -fomit-frame-pointer -std=c99 -DNDEBUG *.c -o nqueen
$ time ./nqueen 15
解の数 (15 クイーン): 2279184
20.514u 0.030s 0:20.55 99.9%    0+0k 0+0io 0pf+0w

$ gcc -Wall -Os -march=prescott -pipe -fomit-frame-pointer -std=c99 -DNDEBUG *.c -o nqueen
$ time ./nqueen 15
解の数 (15 クイーン): 2279184
17.249u 0.025s 0:17.28 99.8%    0+0k 0+2io 0pf+0w

うーん、G4 1.25GHz dual とかで試したら、 もしかして完全に (ハッキリと分かる程度に!) 逆転する可能性があるんじゃ…。

その前に本当に速い N クイーンのプログラムを作ってみたいかも。 以前 C++ で作成したのは、これよりは速いけど、けっこう不満点が多いので…。 とりあえずビット演算主体で実装してみたいな。

• この日記には本日 名の方が訪問してくださっているようです。 また、昨日は 名の方が訪問してくださったようです。
• この日記の更新情報の取得には antenna.lirs を利用するのがおすすめです。