【Java】クラスの基本メモ
Javaのクラスの基本的な内容を備忘録としてまとめておきます。
見やすさのために、具体例なしで各概念の簡単な説明と書き方を羅列します。
クラス
クラスの定義
クラスを次のように定義する。
class クラス名 { // フィールドやメソッドを定義 }
ファイル名はクラス名.javaのようにする。なお、クラス名は大文字から始める。
実体化
次のようにしてインスタンスを作成する。
型名(クラス名) インスタンス名 = new クラス名(引数1, ... );
このとき与えた引数はコンストラクタに渡される。
インスタンス instanceof クラス名;
フィールドとメソッド
クラスはフィールド（変数）とメソッドを持つ。
インスタンスフィールドとクラスフィールド
クラスフィールドには宣言時にstaticをつける。
クラスフィールドはクラスで共通する値を、インスタンスフィールドは個別のインスタンスごとの値を保持する。
クラス外では次のようにアクセスする。
// クラスフィールド クラス名.クラスフィールド名; // インスタンスフィールド インスタンス名.インスタンスフィールド名;
クラス内ではインスタンスフィールドに次のようにアクセスできる。
this.インスタンスフィールド名;
インスタンスメソッドとクラスメソッド
クラスメソッドには宣言時にstaticをつける。
クラス外では次のようにアクセスする。
// インスタンスメソッド インスタンス名.インスタンスメソッド名(); // クラスメソッド クラス名.クラスメソッド名();
クラス内では、インスタンスメソッドに次のようにアクセスできる。
this.インスタンスメソッド名();
コンストラクタ
インスタンス作成時に呼ばれるメソッド。クラスと同じ名前を持つ。修飾子をつけず、次のように定義する。
クラス名(引数) {
...
}
オーバーライド
- オーバーライド：同じ名前のメソッドを異なる型や個数の引数に対して定義する
引数の個数や型に依らず同様な処理を行いたいとき、異なる引数を同じ名前のメソッドで受け取れると便利だが、これはメソッドのオーバーライドによって実現できる。
引数に応じて適切なものが呼び出される。
コンストラクタをオーバーロードすることもできる。
this()を使うと、異なる定義のコンストラクタを呼び出すことができる。
クラス名(引数) {
this(引数); // 与えた引数に対応するコンストラクタが呼び出される
...
}
アクセス制限
メソッドやフィールドがどこからアクセスできるかを指定するため、次のようなアクセス修飾子がある。
public：どこからでもアクセスできるprivate：クラス内からのみアクセスできるprotected：クラス内・サブクラス内からのみアクセスできる
クラスの継承
スーパークラス（親クラス）を継承して子クラス（サブクラス）を作るには次のようにする。
class サブクラス名 extends スーパークラス { ... }
コンストラクタのオーバーライド
super()を用いるとスーパークラスのコンストラクタを呼び出せる。
サブクラス名() {
super(); // スーパークラスのコンストラクタを呼び出す
// 新たな処理
}
メソッドのオーバーライド
スーパークラスのメソッドと同名のメソッドをサブクラスで定義すると、そのメソッドが上書きされる。
super.メソッド名()によってスーパークラスのインスタンスメソッドを呼び出せる。
抽象クラス・抽象メソッド
- 抽象メソッド：スーパークラスで宣言され、具体的な処理はサブクラスで定義される。
- 抽象クラス ：抽象メソッドを持つクラス。実体化できない。
抽象メソッド、抽象クラス共にabstractキーワードをつける。
abstract class クラス名() { ... abstract アクセス修飾子 返り値の型 メソッド名(); ... }
サブクラス
アクセス修飾子 返り値の型 メソッド名() {
// 具体的な処理
};
まとめ
抽象クラスのありがたみがまだよくわかりません。
【JavaScript】クラスの基本
JavaScriptのクラスについてまとめておきます。
具体例を交えず構文だけ書いていきます。忘れたときに見返す用です。
クラス
次のようにクラスを定義する。
class クラス名 { ... }
インスタンス
インスタンスの生成は次のように行う。
const インスタンス名 = new クラス名();
メソッド
メソッドを次のように定義する。
class クラス名 { ... メソッド名(引数) { 処理 } ... }
クラス内でプロパティにアクセスしたりメソッドを呼び出すときはthisを使う。
this.プロパティ名 this.メソッド名()
コンストラクタ
インスタンス生成時に実行されるメソッド。次のように定義する。
class クラス名 { constructor(引数) { 処理 } ... }
クラスの継承
次のようにクラスを継承できる。
class 子クラス名 extends 親クラス名{ ... }
クラスを継承することで子クラスで親クラスのメソッドやプロパティを利用でき、それらに加えて新しく定義したものを使えるようになる。
メソッド・コンストラクタのオーバーライド
親クラスで定義されていたメソッドを子クラスで再定義することができる。この結果そのメソッドが子クラスで上書きされることになり、これをオーバーライドという。
コンストラクタのオーバーライドでsuper()を使って親クラスのコンストラクタを呼びすことができる。
class クラス名 extends 親クラス名 { constructor(引数1, 引数2, ...) { super(引数); // ここで親クラスのコンストラクタが呼び出される 新しく追加する処理 } }
CSSで余白を指定する方法メモ
CSSで余白を指定する方法をすぐに忘れてしまうので、メモしておきます。
ボックスモデル
要素を取り囲む領域にはmargin, border, paddingがある。余白の確保にはmargin, paddingを使う。
余白の指定方法
margin, paddingはそれぞれCSSでmargin, paddingプロパティを用いて指定する。
まとめて指定する方法
margin: 上 右 下 左; margin: 上下 左右; margin: 上 左右 下;
padding: 上 右 下 左; padding: 上下 左右; padding 上 左右 下;
個別に指定する方法
margin-top, margin-left, margin-right, margin-bottomプロパティを指定する。paddingも同様。
Common Lisp で乱数を生成する
乱数を生成するには、random関数を使います。
random
引数より小さい非負の整数の乱数を返してくれます。
例：０から９の整数乱数を生成します。
CL-USER> (random 10) 6 CL-USER> (random 10) 8 CL-USER> (random 10) 3
参考
コンラッド・バルスキ（2013）「Land of Lisp」 川合史郎訳 オライリー・ジャパン
「プログラミング言語の基礎概念」のためのEmacsメジャーモードを書いた
「プログラミング言語の基礎概念」の演習システムのためのメジャーモードを作ってみました。 ソースコードと、実際に利用するまでの流れを書いておきます。
環境
GNU Emacs 26.1
動機
「プログラミング言語の基礎概念」（五十嵐淳著）という、とても良い本があります。何が良いかというと、計算理論の初学者にとってわかりやすく書かれている（まだ最初の方しか読んでないが）ことと、この本に対応するオンライン演習システムが利用できることです。
演習システムに回答する際に導出木を書く必要があるのですが、当然そのまま入力することができません。そこで、導出木を適切な形式（補助資料によればASCII表記）に直してあげる必要があります。
Emacsで書こうにも、対応するメジャーモードが見つかりません。しかし、ペアノ自然数は人間が入力するには厳しいものがあります。
じゃあ、自分でメジャーモード作ろう。
メジャーモードを作成
generic mode を使ってメジャーモードを作ることができます。init.elなどに
(require 'generic-x)
と書き、続いてメジャーモードを定義していくという流れになります。
generic mode の使い方はこちらに書かれています。
これを利用してメジャーモードascii-expression-modeを定義しました。init.elなどに次のコードを追加します。
(require 'generic-x) ;; define major mode (define-generic-mode 'ascii-expression-mode ;; comments '("//") ;; keywords '("plus" "times" "is" "by" "evalto" "--->" "-*->" "-d->" "|-" "->" "==>" "=>" ">>") ;; faces nil ;; files for which to activate this mode '("\\.as$") ;; other function to call '(define-as-keymap) ;; description for this mode "Major mode for ASCII expression, which is used in COPL." ) (global-set-key (kbd "s-z") nil) (defun define-as-keymap () "This function define local keymap for ascii-expression-mode." ;; doc string ;; insert "S()" (local-set-key (kbd "s-s") '(lambda () (interactive) (insert "S()") (backward-char))) ;; insert "Z" (local-set-key (kbd "s-z") '(lambda () (interactive) (insert "Z"))))
ascii-expression-mode の説明
asという拡張子をつけたファイルを開くと今回定義したascii-expression-modeが起動します。次のようなコマンドが使えます。
- Super + s：
S()を挿入し、かっこ内にカーソルを移動します。 - Super + z：'Z'を挿入します。
- Super + s：
S()の次のZを入力するときに、右手をSuperキーからShiftキーに移すのがストレスだったのでこのようなコマンドを作りました。
有効化とテスト
通常、どのファイルを開いたときにメジャーモードを有効化するかを指定するには(add-to-list 'auto-mode-alist '(""\\.hoge\\'" . hoge-mode))とする必要があるのですが、上のように generic mode で拡張子を指定した場合、このような記述が必要ありません。つまり、ascii-expression-modeはhoge.asと言ったファイルを開くと既に起動するようになっているはずです。
それではきちんと動くかどうかテストしてみます。
Emacsで.asファイルを開き、モードラインにAscii-Expressionと表示されていたら成功です。
まとめ
簡易的なメジャーモードを作ったので、そのメモです。インデントは難しくてまだ着手していませんが、作ると捗りそうなのでやってみたいと思います。
ていうか、証明すべき命題を与えたら導出木を出力するプログラムを書いた方が早そうですね。
参考
数列の転倒数をマージソート で求める
転倒数を求める問題を解きました。バブルソートの交換回数を数えることによっても求めることができますが、より高速なマージソート を用いた解法を実装します。
問題
次の問題を解きます。
反転数 | アルゴリズムとデータ構造 | Aizu Online Judge
考え方
マージソートを知っているものとします。
基本的なアイディアは、２つの部分列をマージするときに、順序が逆になっている数の組み合わせの数を数え、足し上げていくというものです。
左右の部分列の要素を先頭から順に比較し、小さいものをソート先の配列に格納するのがマージの手順です。右の部分列の要素の方が左の部分列の要素よりも小さいとき、左の部分列の要素のうち残されているものの数をカウントします。
解答例
#include<iostream> using namespace std; typedef long long ll; const int N = 200000; const int INFTY = 1000000001; ll merge(int left, int mid, int right, int A[]) { ll cnt = 0; int i, j, k, n1, n2, *L, *R; n1 = mid - left; n2 = right - mid; L = new int[n1+1]; R = new int[n2+1]; for (i = 0; i < n1; i++) L[i] = A[left+i]; for (i = 0; i < n2; i++) R[i] = A[mid+i]; L[n1] = R[n2] = INFTY; j = k = 0; for (i = left; i < right; i++) { if (L[j] <= R[k]) { A[i] = L[j++]; } else { A[i] = R[k++]; cnt += n1 - j; } } delete [] L; delete [] R; return cnt; } ll merge_sort(int left, int right, int A[]) { if (left + 1 < right) { ll cnt1, cnt2, cnt3; int mid = (left + right) / 2; cnt1 = merge_sort(left, mid, A); cnt2 = merge_sort(mid, right, A); cnt3 = merge(left, mid, right, A); return cnt1 + cnt2 + cnt3; } else { return 0; } } int main() { int n; int A[N]; cin >> n; for (int i = 0; i < n; i++) cin >> A[i]; ll cnt = merge_sort(0, n, A); cout << cnt << endl; return 0; }
参考
渡部有隆（2015）「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」 Ozy・秋葉拓哉協力 株式会社マイナビ
Emacsで右かっこの自動挿入
C++の標準ライブラリでソート
C++のソートを、標準ライブラリを使って行う方法のメモです。 主要なソートをだいたい勉強し終えたので、そろそろ車輪の再発明のフェーズを脱しようという意図です。
安定でないソート
sortを使います。ヘッダファイル
ソートしたいものの先頭のイテレータと末尾のイテレータを指定してあげます。ただし、末尾はソート対象に含まれていないことに注意。
sort(先頭のイテレータ, 末尾のイテレータ)
配列の場合は先頭と末尾へのポインタを指定します。
安定なソート
安定なソートであることが必要な時はstable_sortを用います。ヘッダファイル
使い方はsortと同じ。
例
トランプを数字の順にソートする例です。
ソートの基準とするメンバをrank（数字を表す）とするために、演算子<をオーバーロードしています。
#include<iostream> #include<algorithm> using namespace std; class Card { public: int rank; char suit; // < をオーバーロード bool operator< (const Card c) const { return rank < c.rank; } }; void print(Card A[], int n) { for (int i = 0; i < n; i++) { if (i > 0) cout << " "; cout << A[i].suit << A[i].rank; } cout << endl; } int main() { int i, n = 6; int ranks[] = {3, 2, 1, 3, 2, 1}; char suits[] = "DHDSDC"; Card *c1, *c2; c1 = new Card[n]; c2 = new Card[n]; // トランプの並び方を設定 for (i = 0; i < n; i++) { c1[i].suit = suits[i]; c1[i].rank = ranks[i]; c2[i] = c1[i]; } print(c1, n); // ソート sort(c1, c1+n); stable_sort(c2, c2+n); print(c1, n); print(c2, n); return 0; }
結果
D3 H2 D1 S3 D2 C1 D1 C1 H2 D2 D3 S3 D1 C1 H2 D2 D3 S3
この例ではいずれのソート結果も安定となっています。安定でなくなる例を思いつかなかったのですが、とりあえず使い方の確認はできたということで、これでよしとしておきます。
まとめ
STLで用意されているソートの使い方の基本的なところはわかったと思います。演算子のオーバーロードも機会を見つけてきっちりとやっておきたいところです。
参考
渡部有隆（2015）「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」 Ozy・秋葉拓哉協力 株式会社マイナビ
【OCaml】Graphicsモジュールが読み込めなかった時の解決策のメモ
先日OCamlをインストールして、チュートリアルをやっていたんですが、Graphicsが読み込めない...という事態に陥りました。解決策を記録しておきます。
環境
Mac OS Mojave バージョン 10.14.4
問題
open Graphics;;と書いたファイルをコンパイルしようとすると、
$ ocamlc graphics.cma grtest1.ml -o grtest1
Error: Unbound module Graphics
というエラーが吐かれる。標準ライブラリなのに...。
そもそもライブラリがインストールされてないようです。
解決法
公式リファレンスのインストールのページを読んだところ、opamというパッケージマネジャーを利用することがオススメだとのことです。
僕がOCamlをインストールするときにはbrew install ocamlとしただけだったので、opamをインストールすることにしました。
opamをインストール
$ brew install gpatch
$ brew install opam
$ opam --version
2.0.4
opamのセットアップ
$ opam init $ eval $(opam env)
指定したバージョンのコンパイラを入れる
$ opam switch create 4.06.1 $ eval $(opam env)
以上でomapのインストールとセットアップは終了。
これでコンパイルしたら成功しました。
まとめ
インストールする時は公式を読みましょう。
参考
【C++】コンストラクタのオーバーロード
プロコンの本を読んでいたら、１つのクラスの中にいきなり２つのコンストラクタの定義が出てきたので、なんぞこれと思って調べてみました。勉強した内容をまとめておきます。
コンストラクタのオーバーロード
一般的にオーバーロードとは同じものに対して複数の定義を行うことを指しますが、C++ではコンストラクタもオーバーロードすることができます。やり方としては、単に複数のコンストラクタを定義してやるだけです。
何ができるのか
例えば、異なる型の引数を同じ形で渡すことが可能になります。異なる数の引数を渡すなどもできます。コンストラクタの方で色々な引数に対する初期化を定義してやることで、使う方はそれらにいちいち気を使わずに済むという利点があります。
ジェネリックプログラミングと関わりが深いみたいですねー。
使ってみる
タイマーです。初期化の際に引数に時間を与え、スタートしてからその時間が経過したらそれを知らせるプログラムです。 引数の時間は、整数の秒数、文字列の秒数、整数の分・秒で与えることができるようにしてあります。
#include<iostream> #include<cstdlib> #include<ctime> using namespace std; class Timer { int seconds; public: // 秒数を文字列で渡す Timer(const char *t) { seconds = atoi(t); } // 秒数を整数で渡す Timer (int t) { seconds = t; } // 時刻を分と秒で与える Timer (int min, int sec) { seconds = min * 60 + sec; } void run(); }; void Timer::run() { clock_t t1, t2; t1 = t2 = clock(); while (seconds) { if (t1 / CLOCKS_PER_SEC + 1 <= (t2 = clock()) / CLOCKS_PER_SEC) { // 1秒ごとに以下の処理を行う seconds--; t1 = t2; } } cout << "PPPPPPP" << endl; } int main() { Timer a(10), b("20"), c(1, 10); a.run(); b.run(); c.run(); return 0; }
まとめ
単に複数の定義を並べるだけで勝手に適当なコンストラクタを適用してくれるんですね。簡単。
参考
ハーバート・シルト（2009）「標準講座C++」柏原正三訳・監修 株式会社トップスタジオ
【C++】フレンド関数
フレンド関数の勉強メモです。基本的な使い方についてです。
フレンド関数
C++ではクラスの外部で定義した関数をクラスのprivateメンバにアクセスできるようにすることができます。
そのような関数をフレンド関数と呼びます。friend修飾子を使ってフレンド関数を作ることができます。フレンド関数はクラスのメンバ関数になる訳ではないことに注意。
こんな感じです。
#include<iostream> using namespace std; class myclass { int a, b; // private member public: // コンストラクタ myclass(int i, int j) { a = i; b = j; } // フレンドにする friend int sum(myclass x); }; int sum(myclass x) { return x.a + x.b; } int main() { myclass n(3, 4); cout << sum(n) << endl; return 0; }
実行結果
7
この例ではありがたさがわかりにくいですが、複数のクラスで同様の処理を行う場合などでフレンド関数は効力を発揮します。
次の例ではidle関数が２つのクラスC1、C2のフレンド関数となっています。
#include<iostream> using namespace std; const int IDLE = 0; const int INUSE = 1; class C2; class C1 { int status; public: void set_status(int state); friend int idle(C1 a, C2 b); }; class C2 { int status; public: void set_status(int state); friend int idle(C1 a, C2 b); }; void C1::set_status(int state) { status = state; } void C2::set_status(int state) { status = state; } int idle(C1 a, C2 b) { if (a.status || b.status) return 0; else return 1; } int main() { C1 x; C2 y; x.set_status(IDLE); y.set_status(IDLE); if (idle(x, y)) cout << "Screen Can Be Used.\n"; else cout << "Pop-up In Use.\n"; x.set_status(INUSE); if (idle(x, y)) cout << "Screen Can Be Used.\n"; else cout << "Pop-up In Use.\n"; return 0; }
まとめ
まだfriend関数の恩恵を受けるには至っていないですが、とりあえず使い方はわかったかな、という感じです。 演算子のオーバーロードで役に立つみたいですね。
参考
ハーバート・シルト（2009）「標準講座C++」柏原正三訳・監修 株式会社トップスタジオ
APSchedulerの使い方（初心者向け）
APSchedulerの使い方のメモです。
APSchedulerはPythonのライブラリで、ジョブの自動実行のスケジュール管理を行なってくれるものです。この記事ではインストールから、基本的な使い方までを見てみます。
動機
- 日本語で使い方を体系的に説明した資料が少ないので、なるべくわかりやすくまとめておく
- 備忘録
環境
Mac OS Mojave バージョン 10.14.3
APSchedulerで何ができる？
指定したタイミングで指定した処理（ジョブ）を自動的に行ってくれます。実行するタイミングは日時、インターバルなど好きなように設定できます。
インストール
pipでインストールできます。
pip install apscheduler
使い方
仕組み
APSchedulerは次のようなコンポーネントを備えており、それぞれが別々の役割を担っています。
- trigger：ジョブを実行するタイミングを指定
- job store：ジョブを保管しておく
- executor：ジョブを実行する
- scheduler：上の３つを統括する
ジョブの実行に直接関わるのはtrigger, job store, executorですが、ユーザはschedulerを通してこれらを操作することになります。
各コンポーネントはそれぞれ複数の種類が用意されていて、実行したい処理に応じて適切に選択することが求められますが、この記事ではそれらのうちほんの一部しか扱いません。具体的には、明示的に指定するのはスケジューラとトリガーにとどめ、他はデフォルトとします。また、スケジューラは最も基本的なBlockingSchedulerを使います。
詳しい機能は公式リファレンスで。
基本的な流れ
- スケジューラのインスタンスを作成
- 実行すべきジョブのリストにジョブを加える
- スケジューラをスタートさせる
例を見てみましょう。３秒ごとに現在時刻を表示するプログラムです。公式からほとんどそのまま引っ張ってきました。
from apscheduler.schedulers.blocking import BlockingScheduler from datetime import datetime import os def tick(): print("Tick! The time is : %s'" % datetime.now()) if __name__ == '__main__': scheduler = BlockingScheduler() # スケジューラを作る scheduler.add_job(tick, 'interval', seconds=3) # ジョブを追加 print( "Press Ctrl+{0} to exit.".format('Break' if os.name == 'nt' else 'C')) try: scheduler.start() # スタート except (KeyboardInterrupt, SystemExit): pass
実行結果：
$ python scheduler_blocking.py Press Ctrl+C to exit. Tick! The time is : 2019-03-31 20:33:30.974106' Tick! The time is : 2019-03-31 20:33:33.973824' Tick! The time is : 2019-03-31 20:33:36.973688' Tick! The time is : 2019-03-31 20:33:39.976681' Tick! The time is : 2019-03-31 20:33:42.973628' Tick! The time is : 2019-03-31 20:33:45.976807' Tick! The time is : 2019-03-31 20:33:48.972867' ^C
ジョブの追加にはadd_job()メソッドを使います。ここでジョブや、実行するタイミングを指定します。通常、ジョブの処理内容は上の例のように関数を利用して指定するようです。また、２番目の引数が'interval'となっていますが、これはトリガーの種類を表しています。トリガーのパラメータを指定しますが、ここでは３番目の引数secondで実行間隔を指定していますね。これによって一定のインターバルでジョブを実行することができます。
スケジューラをスタートさせるにはstart()メソッドを使います。
トリガーを指定する
様々な方法でジョブが発火するタイミングを指定できます。トリガーを使います。
一定間隔でジョブを実行する
add_job()メソッドの引数で、トリガーに'interval'を指定します。seconds, minutes, hours, daysなどのパラメータがあります。start_time, end_timeで開始や終了のタイミングを指定することもできます。
詳しくはこちら。
時刻を指定してジョブを実行する
トリガーに'date'を指定します。実行タイミングはrun_dateで指定します。
from apscheduler.schedulers.blocking import BlockingScheduler from datetime import datetime scheduler = BlockingScheduler() def my_job(text): print("The time is: %s" % datetime.now()) print(text) scheduler.add_job( my_job, 'date', run_date="2019-03-31 21:45:00", args=['Hello']) scheduler.start()
実行結果：
The time is: 2019-03-31 21:45:00.001948 Hello
詳しくは こちら。
cronライクにトリガーを指定する
トリガーを'cron'にします。Unix系OSで使われるcronのような形式で実行タイミングを指定します。
cronは詳しく説明すると大変なので興味のある方はこちらから。決して僕が説明できないと言うわけでは...。
まとめ
APSchedulerの基本的な使い方をまとめました。あまり深掘りはできませんでしたが、初心者の方には十分かな、ということで。詳しい使い方は適宜公式を参照してもらえればと思います。Twitterのbotやなんかを作るのに役立ちそう。あとcronも勉強しておきたいです。
参考
【Common Lisp】loopマクロの使い方まとめ
Common Lispでループ処理に使われるloopマクロの使い方です。網羅的にまとめた資料が少ないので、備忘録的にまとめておこうと思います。
loopマクロには多くの機能があります。なので、最初から全てを抑える必要はないと思います。
この記事の内容
loopマクロの機能の簡単な使い方の説明と使用例をひたすら列挙します。
紹介する機能一覧
loopマクロでは様々な節を使って、色々な機能を実現します。たくさんあってごちゃごちゃするので、とりあえずどんなものがあるのかだけ最初に書いておきます。
基本
loopコマンドを使ってループする際の基本的な機能を提供する節
- do
- for
- while
- until
- repeat
- return
- initially, finally
範囲指定
ループする範囲を指定する節
- for, as
- in
- on
- across
- by
- from, to
- upfrom, downfrom
- upto, downto
条件分岐
ループ内の処理を条件によって分岐する節
- if, when
- unless
- and
- else
- end
計算結果の集積
結果を集めてリストなどの形で返す節
- collect
- count
- sum
- minimize
- maximize
- append, nconc
- into
その他
- with
- named
- return-from
各節の説明と例
では、上の節の機能と具体例を書いていきます。
基本
for, as
forループ。ループ変数を指定する。
CL-USER> (loop for i below 5 collect i) (0 1 2 3 4)
CL-USER> (loop as i below 5 collect i) (0 1 2 3 4)
複数のループ変数を指定する場合：
CL-USER> (loop for i below 10 for j below 20 collect (+ i j)) (0 2 4 6 8 10 12 14 16 18)
このように、どちらかのループ範囲が尽きるまでループを行う。
ループをネストさせる：
CL-USER> (loop for i below 10 collect (loop for j below 10 collect (cons i j))) (((0 . 0) (0 . 1) (0 . 2) (0 . 3) (0 . 4) (0 . 5) (0 . 6) (0 . 7) (0 . 8) (0 . 9)) ((1 . 0) (1 . 1) (1 . 2) (1 . 3) (1 . 4) (1 . 5) (1 . 6) (1 . 7) (1 . 8) (1 . 9)) ((2 . 0) (2 . 1) (2 . 2) (2 . 3) (2 . 4) (2 . 5) (2 . 6) (2 . 7) (2 . 8) (2 . 9)) ((3 . 0) (3 . 1) (3 . 2) (3 . 3) (3 . 4) (3 . 5) (3 . 6) (3 . 7) (3 . 8) (3 . 9)) ((4 . 0) (4 . 1) (4 . 2) (4 . 3) (4 . 4) (4 . 5) (4 . 6) (4 . 7) (4 . 8) (4 . 9)) ((5 . 0) (5 . 1) (5 . 2) (5 . 3) (5 . 4) (5 . 5) (5 . 6) (5 . 7) (5 . 8) (5 . 9)) ((6 . 0) (6 . 1) (6 . 2) (6 . 3) (6 . 4) (6 . 5) (6 . 6) (6 . 7) (6 . 8) (6 . 9)) ((7 . 0) (7 . 1) (7 . 2) (7 . 3) (7 . 4) (7 . 5) (7 . 6) (7 . 7) (7 . 8) (7 . 9)) ((8 . 0) (8 . 1) (8 . 2) (8 . 3) (8 . 4) (8 . 5) (8 . 6) (8 . 7) (8 . 8) (8 . 9)) ((9 . 0) (9 . 1) (9 . 2) (9 . 3) (9 . 4) (9 . 5) (9 . 6) (9 . 7) (9 . 8) (9 . 9)))
上の例はi, jによる２重ループとなっている。
while
whileループ。条件が偽になるまで繰り返す。
CL-USER> (loop for i from 0 while (< i 3) do (print i)) 0 1 2 NIL
until
条件が真になるまで繰り返す。
CL-USER> (loop for i from 0 until (> i 3) do (print i)) 0 1 2 3 NIL
repeat
繰り返し回数を指定する。
CL-USER> (loop repeat 5 do (print "five times")) "five times" "five times" "five times" "five times" "five times" NIL
do
do以下に記述する任意の式を実行する。なお、暗黙のprognにより、複数の式を続けて記述できる。
CL-USER> (loop for i below 3 do (fresh-line) (princ "number is ") (print i)) number is 0 number is 1 number is 2 NIL
return
値を返し、ループを抜ける。
CL-USER> (loop for i below 10 when (= i 5) return 'return do (print i)) 0 1 2 3 4 RETURN
initially, finally
それぞれ、ループ直前・直後の処理を記述する。複数の処理を続けて書ける。
CL-USER> (loop initially (print 'init-process) (print 'loop-begin) for i below 3 do (print i) finally (print 'loop-end) (print 'final-process)) INIT-PROCESS LOOP-BEGIN 0 1 2 LOOP-END FINAL-PROCESS NIL
範囲指定
in
ループする範囲をリストで指定できる。
CL-USER> (loop for i in '(1 3 5 7 9) collect i) (1 3 5 7 9)
on
inと似ているが、リストを頭から一つづつ削りながらループする。
CL-USER> (loop as i on '(1 3 5) do (print i)) (1 3 5) (3 5) (5) NIL
across
inと似ているが、リストではなく配列で範囲を指定する。
CL-USER> (loop for i
across #(1 3 5)
do (print i))
1
3
5
NIL
by
ループ変数を指定した間隔で増やしながらループできる。
CL-USER> (loop for i from 1 to 10 by 2 collect i) (1 3 5 7 9)
from, to
from m to n の形で、ループ変数がnからmまでループする。
CL-USER> (loop for i from 1 to 10 collect i) (1 2 3 4 5 6 7 8 9 10)
upfrom, downfrom
upfromはfromと同じ？downfromはループ関数をループごとに減らす時に使う。
CL-USER> (loop for i upfrom 1 to 10 collect i) (1 2 3 4 5 6 7 8 9 10)
CL-USER> (loop for i downfrom 5 to 1 collect i) (5 4 3 2 1)
upto, downto
uptoはtoと同じ？downtoはループ変数を減らしながらループする時に使う
CL-USER> (loop for i from 1 upto 5 collect i) (1 2 3 4 5)
CL-USER> (loop for i from 10 downto 1 collect i) (10 9 8 7 6 5 4 3 2 1)
条件分岐
if, when
条件が真となる場合のみ、when直下の処理を実行する。
CL-USER> (loop for i from 1 to 10 when (oddp i) collect i) (1 3 5 7 9)
unless
条件が偽となる場合のみ、unless直下の処理を実行する。
CL-USER> (loop for i below 4 unless (oddp i) do (print i)) 0 2 NIL
else
ifやwhenで条件が偽の処理を記述する。
CL-USER> (loop for i below 5 if (oddp i) do (print i) else do (print "even")) "even" 1 "even" 3 "even" NIL
and
whenやunlessで実行する処理を複数書きたい時に使う。
CL-USER> (loop for i below 5 when (oddp i) do (fresh-line) and do (princ "number is ") and do (princ i)) number is 1 number is 3 NIL
end
複数の節の終わりを表現する。
CL-USER> (loop for i below 4 when (oddp i) do (print i) end do (print "yup")) "yup" 1 "yup" "yup" 3 "yup" NIL
計算結果の集積
collect
ループごとに指定した値を要素とするリストを作る。
CL-USER> (loop for i below 5 collect i) (0 1 2 3 4)
count
ループ変数の個数を数える。
CL-USER> (loop for i below 5 when (oddp i) count i) 2
sum
総和を計算する。
CL-USER> (loop for i below 5 sum (+ i 1)) 15
minimize
最小の値を見つける。
CL-USER> (loop for i in '(3 2 1 2 3) minimize i) 1
maximize
最大の値を見つける。
CL-USER> (loop for i in '(3 2 1 2 3) maximize i) 3
append, nconc
リストを繋げてリストにする。
CL-USER> (loop for i below 5 append (list 'z i)) (Z 0 Z 1 Z 2 Z 3 Z 4) CL-USER> (loop for i below 5 nconc (list 'z i)) (Z 0 Z 1 Z 2 Z 3 Z 4)
into
ローカル変数を作り、集計した値を格納する。
CL-USER> (loop for i in '(3 8 73 4 -5) minimize i into lowest maximize i into biggest finally (return (cons lowest biggest))) (-5 . 73)
その他
with
ローカル変数を作成する。
CL-USER> (loop with x = (+ 1 2) repeat 5 do (print x)) 3 3 3 3 3 NIL
named, return-from
namedはループに名前をつける。return-fromは指定した名前のループから抜ける。
CL-USER> (loop named outer for i below 10 do (progn (print "outer") (loop named inner for x below i do (print "**inner") when (= x 2) do (return-from outer 'kicked-out-all-the-way)))) "outer" "outer" "**inner" "outer" "**inner" "**inner" "outer" "**inner" "**inner" "**inner" KICKED-OUT-ALL-THE-WAY
まとめ
ひたすらloopの機能を羅列してきました。これでも多すぎ...と感じるのですが、まだ他にもコマンドがあります。ただ、実際に使うのはこれくらいなんじゃないかな？と思ってます。また書きたくなったら随時付け足していきます。
参考
コンラッド・バルスキ（2013）「Land of Lisp」 川合史郎訳 オライリー・ジャパン
Common Lisp のインクリメント・デクリメント
Common Lispでインクリメントやデクリメントを行う方法です。紹介するマクロはインクリメント・デクリメントだけでなく色々できます。
incf, decf
incfは第２引数に指定した分だけ、第１引数の変数の値を大きくします。
(incf 変数 数字)
decfは第２引数に指定した分だけ、第１引数の変数の値を減らします。
(decf 変数 数字)
いずれも第２引数のデフォルトは１です。
例
CL-USER> (setq x 5) 5 CL-USER> (incf x) 6 CL-USER> (decf x) 5 CL-USER> (incf x 2) 7 CL-USER> (decf x 2) 5
参考
コンラッド・バルスキ（2013）「Land of Lisp」 川合史郎訳 オライリー・ジャパン
Disjoint SetsとUnion Find
データ構造の一つであるDisjoint Setsと、それを管理するUnion-Findアルゴリズムについて勉強した内容のまとめです。
この記事の内容
- Disjoint Sets とは何か
- Disjoint Sets の実装のアイディア
- 例題を解く
Disjoint Sets とは？
複数の集合を考えたとき、それらの要素の重複がない（どの２つをとっても、共通部分が空集合）とき、これらの集合は「互いの素である」と言います。このような互いに素な集合たちを管理するデータ構造にDisjoint Setsがあります。そのまんまのネーミング。
Disjoint Setsに対する操作は次。
- makeSet(x)： xをただ１つの要素とする集合を作る
- find(x)：xが属する集合の代表の要素を見つける
- unite(x, y)：xが属する集合とyが属する集合の和集合を取る
Union-Findアルゴリズム
Disjoint Setsに対して、「ある２つの要素が同じ集合に属するか」を調べるアルゴリズムをUnion Findと呼びます。上の操作を組み合わせて実装できます。
実装のアイディア
具体的なDisjoint Setsの構造と実装の考え方を見てみます。まず、各集合は木構造として実装されます。一般に木の集合を森いい、木として実装された互いに素な集合をまとめたものをDisjoint Sets Forestと呼びます。つまり、Disjoint Setsは森（Disjoint Sets Forest）として実装されます。
find
各集合を区別するために、それぞれの木の根を代表とします。そして、それぞれの要素から根まで到達できるように、各ノードがそれぞれの親へのポインタを持ちます。
ところが、この方法だと、一つ一つ根まで親をたどって行かなければならず、計算量が多くなります。直接ポインタを根に繋げてしまえば少ない計算ですみます。そこで、ある要素から根までたどっていくとき、途中にあるノードのポインタが根をさすようにつなぎ変えることを考えます。これを経路圧縮と言います。
例えば、これを、次のように経路圧縮します。
unite
２つの集合を合併するには、木をくっつけるだけでOKです。具体的には、２つの木のどちらか一方の根を選んで、新しい集合の代表とし、他方の根のポインタを新しい代表へのポインタとします。 このとき、計算量を考えて、合併後の木の高さがなるべく小さくなるように、低い木を高い木にくっつけるようにします。
例えば、上の木に対して unite(2, 4) を施すと、
要素xを表すノードの高さをrank[x]とし、木の高さを管理します。初期値は全てのxについてrank[x] = 0、同じ高さの木を合併するときに新しく代表となったノードの高さを１増やせば良いでしょう。
問題を解いてみる
次の問題を解きます。
互いに素な集合 Union Find| データ構造ライブラリ | Aizu Online Judge
解答例：
#include<iostream> using namespace std; const int N = 10000; class DisjointSet { int parent[N], rank[N]; public: // コンストラクタ DisjointSet(int n) { for (int i = 0; i < n; i++) make_set(i); }; void make_set(int x) { rank[x] = 0; parent[x] = x; } int find(int x) { if (x != parent[x]) parent[x] = find(parent[x]); return parent[x]; } void unite(int x, int y) { int root_x, root_y; root_x = find(x); root_y = find(y); if (rank[root_x] > rank[root_y]) { parent[root_y] = root_x; } else if (rank[root_x] < rank[root_y]) { parent[root_x] = root_y; } else { parent[root_y] = root_x; root_x++; } } bool same(int x, int y) { return find(x) == find(y); } }; int main() { int i, n, q, com, x, y; cin >> n >> q; DisjointSet ds(n); // 初期化 for (i = 0; i < q; i++) { cin >> com >> x >> y; // same if (com) cout << ds.same(x, y) << endl; // unite else ds.unite(x, y); } return 0; }
メンバ関数findを再帰関数を用いて実装していることに注意。根の親が根なので、根まで行き着くと次々と根となっている要素が返され、経路上にある全てのノードの親が根となることがわかります。
まとめ
Disjoint Setsの考え方を勉強しました。問題を解くことを通してUnion Findの実装を行いました。
参考
渡部有隆（2015）「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」 Ozy・秋葉拓哉協力 株式会社マイナビ
