関数型言語

関数型言語

関数型言語とは、関数型プログラミングを基本スタイルとして推奨する機能を持つプログラミング言語、関数型プログラミング言語の略称である。何をもって関数型プログラミングとするか、関数型プログラミングを行っているコミュニティ内でも正確な定義や合意というものは存在しないが、ここでは、再代入できない永続データを駆使して問題を解く永続データプログラミングを奨励し支援している言語を関数型言語と定義する。

関数型言語との対比で言えば，命令プログラミングとは「短命データプログラミング」ということになる。短命データとは再代入により破壊できるデータのことである。for文のカウンタ変数iが典型的な短命データである。

たとえば、手続き型プログラミングでは 1 から 10 までの整数を足し合わせるプログラムは、以下のように一時変数に数値を足していくコマンドの繰返し実行という形を取る:

total = 0;
for i = 0 to 10 do
  total = total + i;
done;

一方、関数型プログラミングでは、同じプログラムを一時変数を使わずに関数の再帰呼出しを使い、全体として一つの式として書くことができる:

let    
    sum x = if x == 0 then  0
            else  x + sum (x - 1)
in
sum 10

関数型言語の具体例

静的型付き：Clean，F#，Haskell，OCaml，Scala，SML
動的型付き：Clojure，Erlang

型の検査を（コンパイル時など）実行の前に実施するのが静的型付き，実行時に実施するのが動的型付きである。

memcachedの分散アルゴリズム

memcashedの分散

memcachedは「分散」キャッシュサーバと言われていますが，サーバ側には「分散」の機能は備わっていない。サーバ側には当連載の第2回，第3回で前坂が紹介したメモリストレージの機能のみが組み込まれており，非常にシンプルな実装となっている。では，memcachedの分散はどのように実現しているのかと言うと，すべてクライアントライブラリによって実現される。この分散方法はmemcachedの大きな特徴である。

memcachedの分散とは

memcachedのサーバが，node1〜node3まであり，アプリケーションから「tokyo」「⁠kanagawa」「⁠chiba」「⁠saitama」「⁠gunma」というキー（名前）のデータを保存する場合を想定する。

まず「tokyo」をmemcachedにaddする。クライアントライブラリに「tokyo」を渡すと，ライブラリに実装されたアルゴリズムよって「キー」から保存するmemcachedサーバを決定する。サーバが決定したら，そのサーバに対して「tokyo」とその値を保存する命令する。

同じように，「⁠kanagawa」「⁠china」「⁠saitama」「⁠gunma」もサーバを決定して保存する。

次は保存したデータの取得です。取得の場合も，ライブラリに対して，取得したいキー「tokyo」を渡す。ライブラリは保存時と同じアルゴリズムを使い，「⁠キー」からサーバを決定する。同じアルゴリズムを利用しており保存したときと同じサーバが決定されるので，サーバに対してgetの命令を送るとなんらかの理由でデータが削除されていない限り，保存した値が取得できる。



このようにキーごとに異なるサーバへ保存することでmemcachedの分散は実現される。memcachedのサーバが多くなればキーも分散され，もしmemcachedのサーバが1台障害がおきて接続できない状態になったとしても，ほかのキャッシュに影響はせずにシステム全体は動き続けることができる。

剰余による分散方法の弱点

Cache::Memcachedの分散方法について簡単に書くと，「⁠サーバの台数の剰余による分散」になる。キーの整数のハッシュ値を求め，その数値をサーバの台数で割った余りでサーバを決定する。この剰余による分散はシンプルでデータの散らばり具合も優れているが、memcachedサーバの追加や削除を行ったときのキャッシュの組み替えのコストが非常に大きい。サーバを追加すると剰余の結果が大きく変わってしまい，その結果データを保存したときと同じサーバへ取得しにいかなくなり，キャッシュのヒット率に影響が出る。

Consiste Hashing

Consistent Hasingでは，まずmemcachedのサーバ（ノード）のハッシュ値を求め，0から232までの円（continuum）の中に配置する。そして格納するデータのキーも同じようにハッシュ値を求め，円の上にマッピングする。データはマッピングされた地点から時計回りで最初に見つかるサーバに保存される。サーバが見つからず232を超えた場合は最初のmemcachedのサーバに保存する。

この状態からmemcachedのサーバを1台追加をします。剰余による分散ではキーが保存されるサーバが大きく変化しキャッシュ率に影響がでていたが，Consistent-Hashingではcontinuum上でサーバが追加された地点から時計回りとは逆方向で最初に見つかるサーバまでにあるキーのみが影響を受ける。

このようにしてConsistent Hashingでは，キーの組み替えを最小限にしている。また，Consistent Hasingの実装によっては仮想ノードという考え方が取り入れられている。通常のhash関数を通す方法ではサーバがマッピングされる場所のばらつきが非常に大きくなる。そこで仮想ノードでは1つのノード（サーバ）に対して100〜200個の点をcontinuum上に作成してそれを利用する。これによりばらつきを押さえ，サーバの増減時のキャッシュの組み替えを最小限にしている。

後述するConsistent Hashingに対応したmemcachedのクライアントライブラリを利用した実験の結果からは，現在のサーバの台数（n）と増やすサーバの台数（m）から，増設後のヒット率を以下の計算で求めることがわかっている。

(1 - n/(n + m))*100

memcashed,Slab Allocator

memcashed

多くのWebアプリケーションは，RDBMSにデータを格納し，アプリケーションサーバでそのデータを引き出してブラウザ等に表示させている。しかしデータが大量になったり，アクセスが集中すると，RDBMSの負荷があがり，データベースのレスポンスが悪化し，Webサイトの表示が遅延するなど大きな影響がでてしまう。

memcachedは高性能な分散メモリキャッシュサーバである。通常，データベースへの問い合わせ結果を一時的にキャッシュすることで，データベースへのアクセス回数を減らし，動的なウェブアプリケーションの高速化やスケーラビリティの向上のために利用されている。

キャッシュサーバ

キャッシュ サーバとは、インターネット上のWebサイト等で提供されているコンテンツの複製を保存し、ユーザからの要求があった場合に、本来コンテンツを提供すべきサーバ（コンテンツ サーバ）に代わってコンテンツを配信するサーバのことである。

memcachedの特徴

memcachedは非常に高速に動作する分散キャッシュサーバで，特徴としては以下のような点が上げられる。

1.シンプルなプロトコル
2.libeventによるイベントハンドリング
3.内蔵のオンメモリストレージ
4.memcached同士での通信は行わない分散方式

シンプルなプロトコル

memcachedのサーバとクライアントの通信は，XMLなどの複雑なフォーマットは利用せず，シンプルな行ベースのプロトコルによって行われる。行ベースのプロトコルなのでtelnetでmemcachedにデータを保存して，保存したデータを取得することもできる。

$ telnet localhost 11211
Trying 127.0.0.1...
Connected to localhost.localdomain (127.0.0.1).
Escape character is '^]'.
set foo 0 0 3     （保存コマンド）
bar               （データ）
STORED            （結果）
get foo           （取得コマンド）
VALUE foo 0 3     （データ）
bar               （データ）

libeventによるイベントハンドリング

libeventとは，Linuxではepoll，BSD系のOSではkqueueなどのイベントハンドリング機能(特定のイベントに反応して特定の処理を行う機能)をラップして，サーバに対するコネクション数の増加に対してもO(1)のパフォーマンスを発揮する共通仕様で利用できるようにしたライブラリである。memcachedはこのlibevetのライブラリを利用しているので、高いパフォーマンスをLinux，BSD，SolarisなどのOS上で発揮することができる。

内蔵のオンメモリストレージ

memcachedに保存したデータは，パフォーマンスを向上させるように設計されたmemcached内蔵のメモリストレージに貯められる。データはすべてメモリ上にのみ存在するので，memcachedを再起動したり，OSを再起動するとすべてのデータが消えることになる。またメモリが指定された容量に達すると，LRU（Least Recently Used）に基づいて利用されないキャッシュから自動的に削除されていく。memcached自体キャッシュのためのサーバとして設計されているので，データの永続化についてはあまり考慮されていない。

memcached同士での通信は行わない分散方式

memcachedは「分散」キャッシュサーバだが，分散に関しての機能はサーバ側には備わっていない。memcached同士で通信を行って情報をシェアすることはない。どのようにして分散を行うかというと，すべてクライアント側の実装に依存するようになっている。

メモリを整理して再利用するSlab Allocationメカニズム

昨今のmemcachedはデフォルトでSlab Allocatorというメカニズムを使ってメモリの確保・管理を行っている。このメカニズムが登場する以前のメモリ確保の戦略は，単純にすべてのレコードに対してmallocとfreeを行うといったものだった。しがしながら，このアプローチではメモリにフラグメンテーション（断片化）を発生させてしまい，OSのメモリマネージャに負荷をかけ，最悪の場合だとmemcachedのプロセスよりも重くなってしまうという問題が発覚した。この問題を克服するために生まれたのがSlab Allocatorである。

Slab Allocatorは、確保したメモリをあらかじめ決められたクラスサイズに応じた固定長の固まりに分けて，フラグメンテーション問題を完全に克服する。Slab Allocationの仕組みは簡素で，確保したメモリをさまざまなサイズの固まり（chunk）に分けて，同じサイズの固まりをクラス（chunkの集合，またはchunkのサイズを定めるクラス）に整理する。

また，slab allocatorには「確保したメモリは再利用する」という目標もある。したがって，memcachedは一度確保したメモリは解放せず，常にchunkを再利用する。

Slab Allocatorの主な用語

・Page
デフォルトで1MB確保され，Slabに割り当てられるメモリ領域。Slabに割り当てられた後に，slabのサイズに応じたchunkに切り分けられる。

・Chunk
レコードをキャッシュするためのメモリ領域。

・Slab Class
特定のサイズのchunkをまとめるクラス。

Slabにレコードをキャッシュする仕組み

memcachedは受けとったデータのサイズを参照し，データサイズにもっとも適したslabを選ぶ。memcachedはslab内の使用可能なchunkのフリーリストを保持しているので，このリストを基にchunkを選び，そこにキャッシュする。

Slab Allocatorの弱点

Slab Allocatorの開発により，当初の課題であったフラグメンテーション問題は解消されたが，新たなメカニズムにより新しい課題がmemcachedに生まれた。その問題は，固定長なメモリ確保のアプローチにより，確保したメモリを有効活用できないということである。例えば100バイトのデータを128バイトのchunkにキャッシュすると，余りの28バイトが無駄になる。

クライアントが送ってくるデータの共通サイズがあらかじめ解っている，もしくは同じサイズのデータしかキャッシュしないユースケースであれば，そのサイズに適したクラスのリストを使い，無駄を抑えることが可能である。ただし残念なことに，現状ではこのチューニングを行うことはできず，将来の課題として残っている。しかしながら，slab classたちのサイズ差をチューニングすることは可能である。

Growth Factorを使ったチューニング

memcachedはスタートアップ時にGrowth Factorという因子を指定して（-f オプション）⁠，slab間のサイズをある程度制御することが可能である。デフォルト値は1.25だが，このオプションが開発される以前は“⁠powers of 2⁠”戦略といって，2が固定だった。

Lazy Expiration

memcachedは内部的にレコードがexpireしたかの監視を行わない。替わりにgetする際にレコードのtimestampを見ることで，そのレコードがexpireしたかをチェックする。このテクニックをlazy（なまけた）expirationと呼ぶ。したがって，memcachedはexpireの監視にCPUタイムを消費しない。

LRU: 有効的にキャッシュからデータが消える仕組み

memcached はtimeoutしたレコードの領域を優先的に再利用するが，それでも新しいレコードを追加する領域がなかった場合はLeast Recently Used（LRU）という仕組みを使って，領域を確保する。LRUはその名の通り，「⁠最近もっとも使っていない」レコードを削除対象にする仕組みである。したがってmemcachedがメモリ不足になった場合（slab classから領域を取れなかった場合）⁠，最近参照されていないレコードを検索して，その領域を新しいレコードに割り当てる。

参考:memcachedを知り尽くす：特集｜gihyo.jp … 技術評論社

連結リスト

連結リスト

連結リストは、配列のように各要素を連続的に並べることをしない。各要素は、メモリ上に飛び飛びの位置に置かれており、それぞれを何らかの方法で「連結（リンク）」する。
要素が、Ａ→Ｂ→Ｃ→Ｄ　のように、先へ先へと連結されていくものを線形リストと呼ぶ。一方、Ａ→Ｂ→Ｃ→Ｄ→Ａ　のように、最後の要素の先が最初の要素に戻ってくるようなものは、循環リストと呼ばれる。さらに、Ａ⇔Ｂ⇔Ｃ⇔Ｄ のように、先へも前へも連結されているものを、双方向リストと呼び、そうでなく、一方向だけに連結されているものを、単方向リストと呼ぶ。

ポインタ

ポインタとは変数の格納場所（アドレス）を指し示す変数」のことである。変数にせよ関数にせよ、実体のあるものは必ずメモリ上にあり、メモリ上に実体を作る行為が「定義」である。変数だけでなく、関数の実体、つまり関数の中身のプログラム（をコンパイルして生成されたコード）についても、メモリ上にある。

このようにメモリ上に置かれている変数や関数は、メモリアドレス（あるいは単にアドレス）という整数値を使って、その置き場所を表現できる。ポインタはメモリアドレスを保存し、その位置にあるものを指し示す（ポイントする）機能である。

構造体

C言語での構造体とは、ひとつの名前でまとめられた、いくつかの異なった型の変数の集まりである。異なった型を格納できる点が配列と異なっている。構造体の中で命名された変数はメンバと呼ばれる。そして、このメンバは通常互いに関連のあるものになる。

単方向線形リスト

この図において、１つの塊は次のような構造体で表現できる。

struct LinkedList_tag {
    int                         value;
    struct LinkedList_tag*      next;
};

ここでは、連結リストの要素は int型であると想定して、int型のメンバ value を持たせている。もちろん、この部分は何でも問題ない。連結リストの鍵となるのは、もう１つのメンバ next である。これは、この構造体と同じ型を指すポインタ変数である。このポインタ変数を使って、次の要素への連結を行う。今後、このメンバnext のことを、「nextポインタ」と呼ぶ。構造体メンバが、自分の属する構造体と同じ型の構造体変数を参照する形は、自己参照構造体と呼ばれる。

事前に固定的にメモリを確保する必要がなく、必要に応じた伸縮が可能である点、要素の追加や削除が効率的である点が長所であり、要素の探索は、原則的に先頭からすべての要素をたどるしか手段がない点、配列と比べると、nextポインタを保持するために、１要素ごとに余分にメモリを消費することになり、メモリ空間の利用効率はやや劣る点が短所である。

単方向循環リスト

単方向で線形なリスト」との違いは、末尾の要素の nextポインタが NULL ではなく、先頭の要素を指すようになったという点だけである。末尾の次が先頭に戻ってくるため、リスト全体の要素に対して何らかの処理を行うとき、最後の要素の nextポインタが NULL かどうかという判定方法が使えなくなる。代わりに、開始位置を覚えておき、nextポインタが開始位置と一致しているかどうかで、最後の要素を判定する。

しかし、前章の単方向線形リストの例のように、先頭にダミーの要素があるのなら、最後の要素の nextポインタはダミーの要素を指すようにしておけば、ダミーの要素に戻ってきたときが、先頭に戻ってきたときであると判定できる。


循環しない場合との違いは、以下の部分である。

1. ダミーの先頭要素の nextポインタは、自分自身を指すように初期化されている
2. リスト全体をたどるとき、終端判定は、ポインタがダミーの先頭要素のメモリアドレスと一致するかどうかになる
3. 新しい要素を末尾に追加するとき、その要素の nextポインタは、ダミーの先頭要素になる

これらの変化はいずれも、最後の要素の次の要素の扱い方が変わったことに起因したものである。循環リストは、循環しない連結リストと比べて何が良くなっているのか。次の２点が、循環しないリストと比べて、有利になり得る場面である。

1. リストの途中の要素からたどり始めたとしても、リスト全体を一周することが容易である
2. 最後の要素のポインタを保存しておけば、先頭も末尾も高速にアクセスできる


途中からでも全体をたどれるという性質は、前回使った要素から処理を再開させるような場合に有利に働く。この場合、一周したかどうかという終了判定が必要ですが、これは開始要素のメモリアドレスを覚えておけば可能である。
最後の要素を記憶しておけば、先頭の要素は nextポインタを見るだけで参照できるので、先頭も末尾も同時に高速参照できるという訳である。先頭と末尾が、いずれも参照頻度が高いような場合、これは大きな利点になり得る。

双方向線形リスト

単方向な連結リストが、後続の要素へのポインタ(nextポインタ) だけを持つのに対し、双方向な連結リストは、手前の要素へのポインタも持つ。これによって、前後どちらの方向へでも連結をたどることが可能になる。なお、双方向の連結リストは、単に双方向リストと呼んだり、重連結リストと呼ばれることもある。

１つ前の要素へのポインタであるprevポインタが追加される。

struct LinkedList_tag {
    int                         value;
    struct LinkedList_tag*      next;
    struct LinkedList_tag*      prev;
};

次の要素がないとき nextポインタを NULL にするのと同様に、前の要素がないときには prevポインタを NULL にする。先頭にダミーの要素を置いているのなら、ダミー要素の prevポインタが常に NULL になる。単方向の連結リストと、双方向の連結リストとでは、ポインタのつなぎ変えが起こる場面での実装が変わる。prevポインタの方も書き換える必要があるため、前後両方の要素に影響を与えることになるので、複雑さが増している。

双方向の連結リストの利点は、リスト内のどの要素を参照しても、前後両方の要素を辿れることにある。単方向のリストでは、要素の削除を行うときに常に手前の要素を保存しながら走査する必要があったが、そういう厄介事から解放される。一方で、prevポインタが増えたことにより、１要素ごとにポインタ変数１個分のメモリを多く消費するようになることが欠点である。

双方向循環リスト

nextポインタと prevポインタを両方持っており、かつ、最後の要素の次に最初の要素が来るように循環しているものを指す。循環の場合の特徴、双方向の場合の特徴はいずれも、これまでに見てきた通りであり、それが組み合わさっただけである。メモリ消費量の増加と、ポインタの付け替えの作業量の増加という双方向リストの欠点を受け入れられるのであれば、通常、単方向リストよりも双方向リストの方が便利に使える。循環リストは、リスト内の途中の要素から走査を開始するようなことが多いのであれば有利に働く。

二分木/二分探索木

上記概念図において、○の部分を節（ノード）、線の部分を枝と呼ぶ。この概念図で上下を逆さまにしてみれば、木のような形をしていることが分かる。これが木構造と呼ばれる由来である。ここで、ある節から見て、その１つ下にある節のことを子と呼び、逆に１つ上の節を親と呼びます。一番上にある節のことを根（ルート）と呼び、一番下にある節のことを葉と呼ぶ。なお、葉のことを外部ノード、葉以外の節を内部ノードと呼ぶことがある。

二分木（バイナリツリー）

１つの節が、２つ以下の子を持つような木構造を二分木（バイナリツリー）と呼ぶ。もし、必ず２つの子を持つようならば、全二分木と呼ばれる。さらに、どの葉も同じ深さにある場合は、完全二分木と呼ばれる。最初の概念図では、根の下に子が３つあるので、これは二分木ではない。１つの節が、３つ以上の子を持つ木構造も考えられる。これは、多分木と呼ばれている。

１つの節が、１つしか子を持たない場合、これはもはや木構造とは呼べないような形になる。なぜなら、そのような構造は連結リストそのものであるからだ。木構造に要素を追加していくとき、節を置く位置を誤ると、このような状態になってしまうことがある。大抵の場合、これは性能を悪化させる結果になる。

再帰的な性質

囲まれた部分だけを単独で観察してみても、その部分もやはり二分木になっていることが分かる。このように、木構造はその一部分だけを取り出してみても、やはり木構造の形をしているという特徴がある。これを部分木と呼ぶ。この概念図の場合、全体としての根の右側にある部分木を囲っているが、この場合、根に対して右部分木、左側にあれば左部分木と呼ぶ。

もっと大きな木構造であれば、部分木の中にさらに部分木が、その中にさらに部分木があるという構造になる。このように、自分自身の一部が、自分自身と同じ形状をしているような構造は、再帰的な構造と呼ばれる。データ構造が再帰的になっているのであれば、プログラムも再帰処理を活用しやすくなる。

走査

二分木に含まれるすべての節を調べたいとする。このような処理を、走査（トラバース）と呼ぶ。ここで重要な点は、「すべてをもらさず」「同じものを重複せず」に調べつくすことである。二分木に対する走査の方法には、大きく分けると、深さ優先探索と幅優先探索の２つがある。前者はさらに、行きがけ順探索、通りがけ順探索、帰りがけ順探索に分類できる。これらは、調べる節の順序が異なる。

深さ優先探索では、根から始めて、葉に行き着くまで子を辿っていく。葉まで行き着いたら、その親に戻り、別の子の方を調べに行き、やはり葉まで辿る。これを繰り返せば、いずれすべての節を調べられる。

ここで、行きがけ順探索、通りがけ順探索、帰りがけ順探索の違いは、根とその２つの子をどんな順序で調べるかである。行きがけ順探索では、根→左の部分木→右の部分木の順で調べる。通りがけ順探索では、左の部分木→根→右の部分木の順で調べる。帰りがけ順探索では、左の部分木→右の部分木→根の順で調べる。幅優先探索の方は、まず根を調べ、次に１つ深い階層の左部分木、右部分木を調べる。１つの階層の節をすべて網羅してから、次の階層へ降りることを繰り返す。

二分探索木

二分探索木とは、「左の子の値＜親の値＜右の子の値」という条件を持たせるというルールを適用することによって、データの探索効率を向上させたデータ構造である。これだと同じ値を持てないが、２つの不等号のうち片方だけなら＝を付け加えれば対応できる。このルールを満たした木は、次のようになる。

このようなルールを満たしていれば、特定のデータを探すには、次のように行える。

１.根を調べる。一致していれば探索完了
２.根の値と探したい値を比較して、探したい値の方が小さければ左の子を、大きければ右の子を調べる
３.葉に行き着くまで上記を繰り返す。葉に行き着いても一致しなければ、探したい値は木の中にない

先ほどのイメージ図を見ながら考えると、例えば、最初に根を調べたとき、探したい値の方が小さかったとしたら、根の右部分木は調べる必要がない。これは、１回比較を行うたびに、探索する対象が半分になることを意味している。

この作業を繰り返すので、探索する対象はどんどん半分に減っていきます。これはつまり、二分探索と同じことが起きている訳である。したがって、二分探索木の探索の計算量は、二分探索と同じく O(log n) となる。

二分探索木の効率が落ちる例

二分探索木の効率を維持するためには、どの葉も同じような高さにあることが重要である。完全二分木という状態は、どの葉も同じ高さにある二分木のことであるが、これが理想的な状態と言える。なぜなら、どの節の値を探索しようとしても、必ず O(log n) 以内の計算量で済むからだ。要するに、二分探索並みの性能が保証される訳である。

しかし、要素の追加が、左部分木や右部分木の一方に偏ると、木構造ではなくリスト構造のような状態になってしまう。これは、次のような状態である。

この状態でも、二分探索木のルールは満たしているが、探索の性能は、二分探索レベルではなく、線形探索レベルになっている。つまり、計算量も O(log n) から O(n) に落ち込むということである。このような状態は、要素を昇順や降順に追加していけば容易に起こることなので、場合によっては重大な問題である。

対策として、常に木を整理して、葉の高さをできるだけ揃えるようにする方法がある。これは一般に、平衡木（バランス木）と呼ばれており、二分探索木であれば、平衡二分探索木と呼ぶ。平衡二分探索木には、いくつかの実装方法があります。例えば、AVL木、赤黒木、AA木などがある。

あるいは、可能であれば、昇順や降順に追加しないように、ランダム性を持たせるようにすれば、性能の低下を防げる。悪い状態を防げると仮定すると、二分探索木は、配列を二分探索することと比べて、要素の追加や削除が少ないコストで行えるという利点がある。配列の二分探索の場合は、常に配列全体をソート済みな状態にしなければならないから、要素の挿入や削除のたびに既存の要素をずらす操作が必要な配列では、効率が落ちる。つまり、配列を二分探索することは、探索自体は速くても、追加や削除が弱い。

データ構造

データ構造

データ構造（data structure）は、計算機科学において、データの集まりをコンピュータの中で効果的に扱うため、一定の形式に系統立てて格納するときの形式のことである。多くのプログラムの設計において、データ構造の選択は主要な問題である。これは大規模システムの構築において、実装の困難さや質、最終的なパフォーマンスはベストのデータ構造を選択したかどうかに大きく依存してきたという経験の結果である。

多くの場合、データ構造が決まれば、利用するアルゴリズムは比較的自明に決まる。しかし場合によっては、順番が逆になる。つまり、与えられた仕事をこなす最適なアルゴリズムを使うために、そのアルゴリズムが前提としている特定のデータ構造が選択される。いずれにしても適切なデータ構造の選択は極めて重要である。

この洞察は、多くの定式化された設計手法やプログラミング言語において、データ構造がアルゴリズムよりもキーとなる構成要素となっていることに現れている。大半の言語は異なるアプリケーションにおいてデータ構造を安全に再利用できるよう、実装の詳細をインターフェイスの背後に隠蔽するような、モジュール化のしくみを備えている。C++やJavaといったオブジェクト指向プログラミング言語はクラスをこの目的に用いている。

データ構造の3つの概念

データ構造は、プログラムの中でデータの集合を系統立てて管理するための形式で、一般的に単にデータの集合を表すだけでなく、以下の3つの概念から成り立つ。

データの集合

対象となるデータの本体で、例えば、配列や構造体などの基本データ構造でデータの集合を保持する。

規則

データの集合を一定のルールに従って正しく操作・管理・保持するための決まり事である。どういった順番でデータを取り出すかなどの取り決めである。

操作

「要素を挿入する」や「要素を取り出す」などの、データの集合に対する操作である。「データの要素数を調べる」や「データの集合が空かどうか調べる」といった問い合わせも含まれる。

基本的なデータ構造は、その操作や規則はいたってシンプルなものであるが、プログラミングやアルゴリズム設計の様々な場面で活用される。プログラムの中でどのようなデータ構造を用いて、それをどのように実装したかによって、アルゴリズムの効率も変わってくる。

配列

配列とは

配列とは、複数の要素（値）の集合を格納・管理するのに用いられるデータ構造が配列である。数学のベクトルおよび行列に近い概念であり、実際にベクトルおよび行列をプログラム上で表現する場合に配列が使われることが多い。同様に複数要素の集合を管理するデータ構造（コレクションあるいはコンテナ）には連結リストやハッシュテーブルなどがあるが、通常はメモリアドレス上での連続性の違いなどから配列とは区別される。1次元の配列は特に線形配列 (linear array) とも呼ばれる。

配列の長所は、簡単に使用できる、メモリ使用量に無駄がなく、空間的な効率が良い、添字（インデックス）による直接アクセスが可能という点で、短所は、要素の追加や削除が非効率、探索の効率が高くない(ただしソート済みであることが保証できるのなら、二分探索法を使う等して効率を高められる。)という点である。

実用的には、配列の要素数が宣言時（あるいはコンパイル時）に静的に決まってしまうよりも、実行時に要素数を動的に指定して配列を確保できたほうが便利なことがある。例えば、縦横任意サイズの画像ファイルから全画素情報を読み出す場合や、コンピュータで利用可能な空きメモリ量に合わせて扱うデータ個数上限を変化させたい場合などである。

配列の動的確保

多くのプログラミング言語では、配列のサイズをプログラム実行時に指定して配列を生成する（動的に確保する）手段が用意されている。例えばC言語ではmalloc関数やcalloc関数を利用する。確保に成功するとメモリブロック（配列先頭要素）へのポインタが返却され、このポインタ経由で配列を操作する。

計算オーダー

「配列」という語は、抽象データ型というよりも、添え字をオフセットとしてメモリのアドレスにマップすることで、Ο(1) でアクセスできる具象あるいは実装を特に指す場合がある（その意味では、次節の連想配列などは「配列」ではない、ということになる）。

要素に「隙間」が無いようにするには、線形リストと異なり、挿入・削除にO(n)時間かかる。探索は一般的には線型探索になるためΟ(n)だが、データがソート済みであれば二分探索を使うことでΟ(log n)に軽減することもできる（抽象データ型としては、sorted array などの名前で別のデータ構造と考える場合もある。

様々な配列

連想配列

添え字は一般に通例0か1始まりの (非負) 整数である。一方、文字列など他のデータ型を添え字のように使用できる配列を連想配列という。一般に動的配列のように、任意に拡大されるものが多いが、固定サイズのものもありえなくはない。また、完全ハッシュ（ハッシュ関数#完全ハッシュ関数）の利用も考えられる。

動的配列

要素数によって自動的にサイズが拡張する配列を、動的配列 (dynamic array) あるいは可変長配列 (variable-length array) と呼ぶ。メモリが許す限り、要素の末尾追加や途中挿入がいくらでもできる。ライブラリで提供されるものと、言語に組み込まれているもの（PerlやDなど）がある。またPerlなど、言語によっては、最初に配列を生成する際に指定されたサイズからはみ出してアクセス（範囲外アクセス）しても、自動的に拡大されるような配列を持っているものもある。逆に決まった要素数しか格納できない配列を、静的配列 (static array) あるいは固定長配列 (fixed length array) と呼ぶ。

動的配列の拡大などの場合には、最悪の場合、メモリ上の別の場所が確保されて、そこに全体をコピーする、というような時間のかかる操作が起きる可能性があるものもある（そのシステムの設計次第で、配列の内部にあるものが他からポインタで指されていて、それを更新できないなど、そういうことができない場合もある）。最悪ではなく償却計算量でNにならなければ良い、という考え方もある。

時間計算量

時間計算量は、あるアルゴリズムを使ったときに問題のインスタンスを解くのに要するステップ数を意味し、入力データの長さ（ビット数などで表現できる）の関数として表される。ランダウの記号を使ってO(n2)やO(nlogn)という形で表記することが多い。償却計算量とは、同じ処理をN回行った時に、1回あたりどれくらいの計算量になるかというものである。

多次元配列

1次元だけではなく2次元・3次元などの多次元配列 (multidimensional array) を備える言語もある。 マトリックスやグリッドのような矩形構造を持ったデータ構造であることから、矩形配列 (rectangular array) と呼ばれることもある。

ジャグ配列

「配列の配列」の場合、内側の配列について、要素数が揃っていることを要求しないデータ構造であることもある。ジャグ配列 (jagged array)、不規則配列などと言う。これに対し、内側の配列の要素数が揃った配列を矩形配列 (rectangular array) などと言う。Javaにおける配列の配列はジャグ配列である。C#には前述の通り、「真の多次元配列」もあるが、それとは別に配列の配列もあり、そちらはJavaと同様のジャグ配列である。

スタックとキュー

スタックとは

スタックは、コンピュータで用いられる基本的なデータ構造の1つで、データを後入れ先出しの構造で保持するものである。抽象データ型としてのそれを指すこともあれば、その具象を指すこともある。特にその具象としては、割込みやサブルーチンを支援するために極めて有用であることから、1970年代以降に新しく設計された、ある規模以上のコンピュータは、スタックポインタによるコールスタックをメモリ上に持っていることが多い。

抽象データ型

抽象データ型（ちゅうしょうデータがた、英: abstract data type、ADT）とは、データ構造とそれを直接操作する手続きをまとめてデータ型の定義とすることでデータ抽象を実現する手法またはそのひとまとまりとして定義されたデータ型を言う。通常のデータ型であれば変数宣言で変数に束縛されるものは値であるが、抽象データ型の世界において値に相当するものはデータ構造とその操作のまとまりである。

抽象データ型を用いない場合、データ構造またはデータの操作手続きのアルゴリズムの変更を行うとソースコード中にその変更部分が散在してしまい規模によっては修正困難となるが、データとその操作がひとまとめに記載されることになる抽象データ型においては、型の定義における実装部分を変更するだけで修正が完了する。

抽象データ型としてのスタックは、ノード（何らかのデータを持ち、別のノードを指し示すことができる構造）のコンテナ（データを集めて格納する抽象データ型の総称）であり、2つの基本操作プッシュ(push)とポップ(pop)を持つ。Pushは指定されたノードをスタックの先頭（トップ）に追加し、既存のノードはその下にそのまま置いておく。Popはスタックの現在のトップのノードを外してそれを返す。

キュー

キュー（queue）、あるいは待ち行列はコンピュータの基本的なデータ構造の一つ。データを先入れ先出しのリスト構造で保持するものである。キューからデータを取り出すときには、先に入れられたデータから順に取り出される。キューにデータを入れることをエンキュー、取り出すことをデキューという。

参考:
データ構造 - Wikipedia

Rails Command

rails new

指定のディレクトリにRailsアプリケーションのスケルトンを作成するコマンド。

rails server / rails s

Railsのサーバーを起動するコマンド。

bundle install (—without 環境名) / bundle 

bundle install とは、bundlerというgemを使って、Gemfileの記載内容に従ってgemをインストールするためのコマンド。 
まずbundlerというgemをインストールするとbundleというコマンドが有効になる。bundlerはbundle installの他にもbundle update等、様々なgem管理コマンドを提供してくれる。without 環境名オプションを使うことで、指定した環境のgemをインストールしなくできる。--withoutオプションは “remembered option” と呼ばれ、このオプションを一度実行すると.bundle/configに設定が保存され、今後bundle installを実行するときに--withoutオプションを追加する必要がなくなる。

bundle update

bundle updateは、gemのバージョンを更新する時に使用する。

rails generate / rails g

指定のジェネレータを実行する。第1引数は実行するジェネレータ名で、残りの引数はジェネレータにそのまま渡される。
参考:http://maeharin.hatenablog.com/entry/20130212/rails_generate

rails destroy

rails generateで生成したファイルをまとめて削除する。

rails db:migrate

マイグレーションを実行するためのコマンド。

rails db:rollback

1つ前の状態に戻すコマンド。

rails db:migrate VERSION=0

最初の状態に戻すコマンド。

rails test / rails t

テストを実行するコマンド。

rails console / rails c

irb(Ruby の式を標準入力から簡単に入力・実行することができる。)を読み込んだ環境でrubyを実行するためのコマンド。全部のモデルを参照することができる。