Common Lispでループ処理に使われるloopマクロの使い方です。網羅的にまとめた資料が少ないので、備忘録的にまとめておこうと思います。 loopマクロには多くの機能があります。なので、最初から全てを抑える必要はないと思います。 この記事の内容 loopマク…

Common Lispでインクリメントやデクリメントを行う方法です。紹介するマクロはインクリメント・デクリメントだけでなく色々できます。 incf, decf incfは第２引数に指定した分だけ、第１引数の変数の値を大きくします。 (incf 変数 数字) decfは第２引数に指…

データ構造の一つであるDisjoint Setsと、それを管理するUnion-Findアルゴリズムについて勉強した内容のまとめです。 この記事の内容 Disjoint Sets とは何か Disjoint Sets の実装のアイディア 例題を解く Disjoint Sets とは？ 複数の集合を考えたとき、そ…

C++にはインライン関数を使う機能があります。その使い方のまとめです。 目標 インライン関数が何者か理解する C++でインライン関数を使えるようになる インライン関数とは？ 通常の関数は、呼び出すたびにメモリのどこかに存在するその関数を（関数へのポイ…

C++のクラスの基本的な使いかたについてまとめました。 対象 クラスについての基本的な知識を持っているけど、C++ではどうやって使えばいいの？という人。 やること スタックの実装を通して、C++におけるクラスの実際の使い方を学ぶ。クラスの定義から、コン…

C++でのメモリの動的確保の方法です。Cではmallocとfreeを使うことが多かったのですが、C++ではnewとdeleteを使います。 それらの使い方を書いていきます。 メモリの確保 メモリの確保はnew演算子で行います。newを使うと、ヒープ領域と呼ばれる空きメモリ領…

最近lispを勉強しているのですが、やっぱり数学的な背景についてもちょっと勉強しておきたいなぁ、、と思いました。 ということで、ラムダ計算についてまとめました。今回は入門編で、厳密な定義は置いておいてとりあえず具体例を用いて初歩的な用語・概念を…

最短経路問題をやります。最短経路を求めるアルゴリズムとして、ダイクストラ法を取り上げます。最後に問題を解きます。 最短経路問題 重み付きグラフが与えられているとします。最短経路問題とは、ある２点間をつなぐパスを構成する辺の重みの総和が最小と…

最小全域木の基本と、それに関連する知識を簡単にまとめておきます。最後に最小全域木に関する問題を解きます。 最小全域木 全域木 グラフGがあるとします。そして、その部分グラフG'を考えます。G' が G の全ての頂点を含み、かつ辺をできるだけ多く含む木…

連結グラフと連結成分について簡単にまとめてから、問題を解いていきます。 連結グラフ グラフに含まれる全ての頂点が他のいずれかの頂点とリンクしているようなグラフを連結グラフと言います。こんな感じ。 連結成分 あるグラフの部分グラフのうち、極大で…

幅優先探索の勉強メモです。アルゴリズムの解説と、問題を解くことまでをやっていきたいと思います。 幅優先探索 幅優先探索（Breadth First Search, BFS）はグラフを用いた基本的な探索アルゴリズム。近いものから順にアクセスしていく感じ。例えば次のよう…

深さ優先探索を勉強したのでメモしておきます。 深さ優先探索 深さ優先探索（Depth First Search, DFS）はグラフを用いた代表的な探索アルゴリズムです。大まかにスタックを使ったものと再帰を利用したものという２つの実装方法があります。基本的なアイディ…

グラフの基本的な内容です。グラフが隣接リストの形で与えられたとき、隣接行列に直します。 隣接リストと隣接行列 隣接リスト 配列Aを用意します。頂点uに対して、A[u]はuと隣接する全ての頂点を格納します。 隣接行列 ２次元配列Aを用意します。頂点iから…

動的計画法の例題です。連鎖行列積をやります。アルゴリズムの勉強と実装をします。 連鎖行列積 厳しい名前がついていますが、やることは行列の積の計算順序の決定です。 与えられたn個の行列の連鎖の積を計算しますが、計算結果には興味がありません。見つ…

defmethodを使って関数を定義する方法です。 目標 defmethodコマンドを使ってジェネリック関数を定義する。 defmethodの利点 データ型によらないジェネリックな関数を定義する際に便利なのが defmethod です。 例えば、引数を２つとる関数を考え、整数が渡さ…

Common Lisp の型述語の勉強メモです。 型述語 真偽値を返す関数を述語と言います。特にデータ型の判定をするものを型述語と呼びます。 numberp arrayp characterp consp functionp hash-table-p listp stringp symbolp 型の名前に述語（predicate）を表すp…

動的計画法の例題です。最長共通部分列を実装します。 目標 最長共通部分列を実装する 最長共通部分列 ２つの列X、Yがあるとします。XとYの共通部分列のうち、最長のものを最長共通部分列（Longest Common Subsequence, LCS）と言います。列は数列など色々な…

動的計画法の例題としておなじみのフィボナッチ数列を実装します。 目標 動的計画法の基本的なアイディアを理解する。 フィボナッチ数列 次のように定義されます。 いかにも再帰関数で書けそうです。 素朴な再帰関数による実装 nを入力として与えると、フィ…

ジェネリックプログラミングの一環として、シーケンス関数について勉強したので、そのメモです。 目標 ジェネリックとは何かざっくりと理解する 基本的なシーケンス関数を使えるようにする ジェネリックである、とは？ 簡単に言えば、異なるものを同じ方法で…

lispの構造体の勉強をしたのでメモを残しておきます。基本的な使い方です。 構造体とは データ型の１つ。複数の属性を持つオブジェクトをうまく表現することができます。 属性のことをスロットと呼びます。 構造体を作る defstructコマンドで宣言します。 CL…

lispのハッシュテーブルの勉強メモです。 ハッシュテーブル ハッシュテーブルはlispの持つ複合的なデータ型の一つで、キーと値をセットにして管理します。連想リストと似ていますが、より高速に定数時間で要素にアクセスできます。 ハッシュテーブルを作る m…

Common Lisp における配列の勉強メモです。 配列 lispのデータ型の１つです。リストと似ていますが、配列の方が特定の要素に高速にアクセスできます。 配列を作る make-array関数で配列を生成できます。 CL-USER> (make-array 3) #(NIL NIL NIL) 頭に # をつ…

優先度付きキューをヒープを使って実装します。標準ライブラリに入っていますが、勉強するために自分でやってみました。 最後に標準ライブラリの優先度付きキューの使い方も見てみます。 目標 実装を通して優先度付きキューを理解する。 標準ライブラリを使…

世のEmacs使いの皆さんは、日々slimeでlispのコードを書いていることでしょう。僕は先日slimeを入れたばかりの初心者ですが、slimeを初めて起動して、初めてのlispのコードを書いて、初めて実行したとき、こう思いました。すなわち、「返り値がめっちゃ見に…

リストはLispの基本ですが、単なるリストではなく色々なリストがあります。ドットリスト、循環リスト、連想リストについてまとめます。 ドットリスト 以下に２つの例を挙げます。普通のリスト： CL-USER> (cons 1 (cons 2 (cons 3 nil))) (1 2 3) 終端がnil…

Common Lispの条件分岐についてのメモです。条件分岐のためのコマンドと、それらを使うのに必要な基本的な演算子や関数をまとめておきます。 真偽値 common lispでは、空リストが唯一の偽値です。それ以外は全て真となります。 なお、'(), (), nil, 'nilは空…

graphviz-dot-mode.elの導入メモです。グラフ描画ツールgraphvizを使ってEmacsでグラフを描くelispです。 graphvizはDOT言語で書かれたファイルを画像に起こします。ネットワークや木構造を描くのに重宝します。 graphviz-dot-mode.elを使うと、コンパイルか…

リストはLispにおいて非常に大事です。ということで、Common Lispのリストの基本的なアイデアをまとめました。 フォーム Lispのコードはリストで構成されています。このリストは、フォームでなければなりません。フォームとは、先頭の要素がコマンドであるよ…

ビットシフトのためのash関数についてのメモです。 ash関数 ash関数はビットシフトを行うLispの組み込み関数。 第１引数に数値を渡し、これをビットシフトの対象とする。 第２引数で左右どちらにシフトするかを指定する。第２引数が１のとき、左にシフト。-…

Common Lispでの変数と関数の種類、定義についてのメモです。 変数を定義する グローバル変数 グローバル変数のことをトップレベル定義と呼ぶ。defparameterまたはdefvarで定義する。defvarで定義した場合、値を上書きすることができない。 変数名をアスタリ…