線形探索と番兵アルゴリズム

  • 番兵アルゴリズムはただの書き方の問題だと思ってたけど,高速化のテクニックだった,という話.
  • forでvectorの要素を回す時に,毎回比較演算が行われるけど,それが勿体無いという場合に,絶対に止まるよに番兵を置いておいて無限ループで回すというのが番兵テクニックみたいだ.
  • アルゴリズム本体が軽い時,かなり性能がシビアに要求される時には必要なのかな?

forで書く場合(比較は2回)

for (int i=0; i<n; ++i) {         // ここで1回
  if (vec[j] == key) return true; // ここで1回(計2回)
}
return false;

番兵で書く場合(比較は1回)

vector<int> vec(n+1);       // +1個分確保
vec[n] = key;               // 末尾に番兵を置く
int j = 0;
while (1) {                 // 無限ループが絶対に止まることが保証される
  if (vec[j] == key) break; // ここの比較だけで良い
  ++j;
}
if (j==n) return false;// 末尾まで行っていたら失敗
else return true;

プロコンと標準入出力

プロコンをかじってみたら,標準入出力で躓いた...ということで,使い方を整理しておく.

scanf

  • 空白文字または改行文字を区切りとして,フォーマットに従って変換して変数に取り込む.2つ以上フォーマット指定子を指定すれば一度にその分だけ読み進む.注意として,最後の空白や改行自体は変換後にバッファに残っている.よって,連続して読み込む場合に前回の改行や空白文字が残ることになるので,2回目以降使う場合はfflush(stdin)する.
  • 整数はd, 浮動小数点数はlf, 文字はc, 文字列はsで受け取る.但し,sは空白は含まないので注意.
  • 戻り値は,成功のときは変換した変数の数,ミスの場合はEOF.
// 0 * 入力で終了.
#include <stdio.h>
int main()
{
  int a, b;
  scanf("%d %d", &a, &b);
  while (a != 0) {
    printf("a:%d, b:%d\n", a, b);
    fflush(stdin);
    scanf("%d %d", &a, &b);
  }
}

fgets/sscanf

  • バッファサイズが指定できないことや,フォーマットを無視した入力の取扱が面倒なので,普通はscanfは使わずにfgetとsscanfを組合せて使う.これも合わせて覚えておく.
  • sscanfの戻り値は,フォーマットに従って入力された変数の数.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
main()
{
    FILE    *fp;
    char    buf[256]; // バッファサイズを指定する
    double  d1, d2;

    if( (fp = fopen( "hoge.dat", "r" )) == NULL ) {
        printf( "ERROR: file can't be opened." );
        exit(1);
    }
    while( fgets( buf, sizeof(buf), fp ) ) {
        if( strncmp(buf,"//",2) == 0 || strcmp(buf,"\n") == 0 ) // skip comment line
            continue;
        if( sscanf( buf, "%lf %lf", &d1, &d2 ) != 2 ) {
            printf( "WARNING: format does not match.\n" );
            break;
        }
        printf( "d1=%.1f, d2=%.1f\n", d1, d2);
    }
    fclose( fp );
}

cin

  • 空白区切りで文字列をパースしていく,改行文字は取り込まれないなどscanfとほぼおなじ動きをする.
  • 関数じゃなくて(オーバーロードされた)演算子
#include <iostream>
int main() {
  int a, b;
  cin >> a >> b; // "1 2" のようなラインを読み取る書き方
}

n個の数列を入力する例

// n
// 1 2 3 4 5
int n;
cin >> n;
vector<int> v(n); // (当然)コンストラクタは変数でも良い
for(int i = 0; i < v.size(); ++i) cin >> v[i];

文字列として連続して受け取る

  • cin >> がEOFを読み込んだ時にfalseとなることを利用する.
string str;
while (cin >> str) { // EOF(Ctrl-D)入力時に抜ける
 ...
}
//同じことの別の書き方
while (1) {
  cin >> str;
  if (cin.eof()) break;
  ...
}

C++ファイル分割

またまた久しぶりにC++を書こうとすると,ヘッダファイル,ファイル分割を忘れてしまっていたので,整理.

全般

  • 共通にするものをヘッダに書く(当たり前だけど).
  • 宣言と定義の違いを持つこと.宣言は名前だけ.定義は実態を生成する文.
  • 定義は(普通)は一つ.ということで関数の定義や,変数の定義は書かない.
  • 逆に変数の宣言(extern)はヘッダに書く.共通したいから.
  • グローバル変数は実態を(何処か1つの)ソースファイルに書いて,そのヘッダにexternで宣言する.他のソースをはそのヘッダをインクルードする.
  • static変数は(普通は)ヘッダに書かない.ヘッダに書くってことはそのヘッダをインクルードしたソース(Cのインクルードは基本的にコピー)全てに,ソース固有のstatic変数が生成される.
  • ヘッダの中で不要にヘッダファイルをインクルードしない.相互依存が発生してしまうし,そのヘッダをインクルードしているソース全部が再コンパイルされてしまう.ラベルが欲しいだけなら前方宣言を利用する.

前方宣言

  • クラス定義をしていると,他のクラスを変数として持ちたいことが(当然だけど)ある.その場合にそのクラスのヘッダファイルをインクルードしないといけなくなって,すぐにヘッダの依存関係が混雑してしまう.
  • そんな時に利用するのが,その変数をポインタとして持つ方法.ポインタであればメソッドやメンバ変数などの情報(というかコンパイル時のメモリ割当)が不要(ポインタ64ビットか32ビットあれば良い)だから,ラベルさえあれば良い.
// シンプルVer.
class Hoge; // <- 前方宣言

class Foo {
private
  Hoge *hoge; // <- ポインタで持つ
};

// 名前空間の下にいるVer.
namespace BAR {
  class Hoge;
}

class Foo {
private
  BAR::Hoge *hoge;
};

extern C {...}

  • Cの関数をC++でも使えるようにするための宣言.
  • 関数名はコンパイル時にリネームされる.しかし,その方法がCとC++で異なるため,普通にコンパイルするとリンクエラー(そんな名前の関数無いよ)になる.
  • それを避けるために,extern C {...}で囲っておく.特に,g++とかだと_cplusplusマクロが定義されているから,それでifdefする.
#ifdef _cpuluspulus
extern C {
#endif
... // Cの宣言文

#ifdef _cpuluspulus
}
#endif

実行中プロセスのREPLに接続

メモ

長いシミュレーションなどをサーバ上でプロセスを実行させたまま帰って,あとでミスに気づいて関数を変更したい,などという状況. swankというのがSlimeの機能なのかEmacsの機能なのかSBCL(CL)の機能なのかが良く分からないけど,イメージとしては,SBCL側でSWANKサーバを立ち上げておいて,SlimeからそのSwankサーバにソケット接続してS式で通信,というイメージなのかな.

やり方

  • sbcl側でやっておくこと.
(ql:quickload :swank)
(swank:create-server :port 4005) ; swankサーバ立上げ
  • Emacs側からの接続/切断
M-x slime-connect RET 127.0.01 RET 4005 RET ; 接続
M-x slime-disconnect RET                    ; 切断

Ltkのメモ

  • 書きかけ

    雑記

  • with-ltkはwishの起動やmainloopの呼び出しとか全部やってくれるマクロ.基本的にltkのプログラミングではこれで全体を囲む.マニュアルでやりたいなら,(start-wish), (mainloop)を実行する.
  • ウィジットのmasterオプションは親ウィジットの指定.nilはトップが親の場合.

イベントハンドリング

  • 単純なイベント(ボタンのプレスとか)はウィジット生成時に:commandで定義できるけど,一般的にはbindを使う.(bind widget event function)形式で指定する.functionは1変数関数で,その変数にはイベントが格納される.マニュアルの下記例が分かりやすい.
(defun scribble ()
  (with-ltk ()
   (let ((canvas (make-instance 'canvas))
     (down nil))
     (pack canvas)
     (bind canvas "<ButtonPress-1>"
           (lambda (evt)
             (setf down t)                                    
             (create-oval canvas
                      (- (event-x evt) 10) (- (event-y evt) 10)
                      (+ (event-x evt) 10) (+ (event-y evt) 10))))
     (bind canvas "<ButtonRelease-1>" (lambda (evt) 
                                        (declare (ignore evt))
                                        (setf down nil)))
     (bind canvas "<Motion>"
           (lambda (evt)
             (when down
               (create-oval canvas
                    (- (event-x evt) 10) (- (event-y evt) 10)
                    (+ (event-x evt) 10) (+ (event-y evt) 10))))))))

sbclでスクリプト

実行方法

  1. RubyとかPerlみたいにファイルの先頭に#!/usr/bin/sbcl --scriptを付けて,実行権限を与えてシェルから実行.#!xxxはシェバンっていうらしい.sbcl 1.0.22から使えるようになった..ただし,~/.sbclrcを読み込まないので注意.
  2. scriptオプションを与えて実行する.
$ sbcl --script hoge.lisp

コマンドライン引数

$ sbcl hoge foo bar
* *posix-argv* #=> ("sbcl" "hoge" "foo" "bar")

エントリポイント

  • ファイルの上から順に実行されるようだ.
  • mainという名前の関数が実行される,みたいなことは”無い”

tcl/tk

GUIは使わないのですぐ忘れる.tkを使う最低限のメモをまとめておく.

tclメモ

  • データは全て文字列として扱われる.数値の場合は読み込まれてから数値に自動で変換される.
  • 行単位のプログラミング言語で,先頭の文字列がコマンド(butonとか)
  • 変数はsetで値を代入,値を取り出すときは$を付ける.
  • 四則演算はexpr(expression式って意味かな?)の後に数式.Bashみたいだ.
  • コマンドで置換する場合は[]で囲む.
  • ウィジットの名前は"."で始める.これは"."メインウィジットを指すから.Tcl/tkのウィジット名はパス付きの名前みたいなイメージ.
set x [expr 2 + 3]        # 変数とコマンド置換の例
set y "hoge [expr 2 + 3]" # 文字列内でもコマンド置換される
button .b -text "hoge"    # オプションは'-'で指定するUnix形式

各ウィジットのメモ

全体

  • イベントとコマンドを結びつけるにはbindコマンド.
bind .widget-name event-name command

パッケージ

  • 基本的にpackerを使う.グリッドの場合のみgridderを使う.placerは使わない.
  • ウィンドウに対して余白を埋めるには-fillオプション.x,yで縦横を指定する.

ボタン

  • 重要なのはcommandオプション.おした時のコマンドを指定できる.
  • ボタンおした時,離した時でコマンド指定したい場合はbindで各イベントとコマンドを結ぶ.

ラベル(label)

  • 文字列の表示
  • textavailableオプションが重要.ここに変数を指定しておくと,変数の値に変わると自動でアップデートしてくれる.
# buton/labelの例
#! /usr/bin/wish

# label widget
set buffer "hello world!"
label .l -textvariable buffer
pack .l

# procedure for below button command
proc push_button {n} {
    global buffer
    set buffer "I push $n button."
}

# button widget
foreach i {0 1 2 3} {
    button .b$i -text "button $i" -command "push_button $i"
    pack .b$i
}
# bind example
bind .b0 <ButtonPress> {puts "hello tcl/tk"}

# exec command
button .b4 -text "pwd" -command "exec pwd &"
pack .b4

Canvas

  • 図形を描画できるウィジット.
  • create object-type coordinate [option]形式
    • line : 直線,2点(多点でも可)を指定する.
    • rectangle: 長方形,左上と右下の2点を指定.
    • oval : 円,外接する長方形の左上と右下の2点を指定.
    • text : 文字列
    • image : 図
  • 共有オプション
    • fillで塗りつぶし,outlineで枠の色,widthで枠の太さ
  • 図形へのコマンド  - move :図形を動かせる
    • bind :図形へのイベントとコマンドをバインド
    • coords :図形の座標を取得
  • バインドでは図形のIDだけでなくタグで指定できる.
# create canvas widget
canvas .c0 -width 200 -height 150
pack .c0

# create a rectangle, and name it as r0.
set r0 [.c0 create rectangle 10 10 20 20 -fill cyan]

# move r0 (above rectangle) by mouse
# B1-Motion: left click, and its coordinates can be access by %x and %y.
# 
.c0 bind $r0 <B1-Motion> {
    set x1 [expr %x-5]
    set x2 [expr %x+5]
    set y1 [expr %y-5]
    set y2 [expr %y+5]
    .c0 coords current $x1 $y1 $x2 $y2
}

.c0 bind hoge <B1-Motion> {
    set x1 [expr %x-5]
    set x2 [expr %x+5]
    set y1 [expr %y-5]
    set y2 [expr %y+5]
    # current means currently pointed object
    .c0 coords current $x1 $y1 $x2 $y2
}


# create rectangle with tag
.c0 create rectangle 20 10 30 20 -fill red -tags hoge
.c0 create rectangle 30 10 40 20 -fill blue -tags hoge
.c0 create rectangle 40 10 50 20 -fill green -tags hoge