コンピューターサイエンス 学び直し オブジェクトとリスト編
今月からコンピューターサイエンスを学び直しているので、そのアウトプットをしようと思います。
そもそも、コンピュータサイエンスとは、「コンピュータを利用して様々な課題を解決する方法を研究する学問」と言えます。
コンピュータサイエンスが扱う分野は、プログラミング言語やフレームワークだけでなく、ハードウェアや設計パターン、アルゴリズムなど多岐にわたります。
これらを組み合わせ、最適な選択をし、社会的学術的な課題を解決していくことが、コンピュータサイエンスの本質です。
今回は、プログラムの基本的なデータ構造となる「オブジェクトとリスト」について解説していきます。
オブジェクト
前の記事では、プリミティブ型について解説しました。
プリミティブ型とは、原則として他のデータ型から構成されず、それ以上分解できないデータ型のことを指しました。
ブーリアン型や整数型、文字型がこれに相当します。
しかしプリミティブ型でデータを表す場合、限界があります。
例えば、車のようなものをデータとして表すとき、プリミティブ型では表すことができません。
そしてその場合に使われるのが、オブジェクトです。
プリミティブ型ではないものは、全てオブジェクトと呼ばれます。
実世界のものには、状態と振る舞いという2つの特徴があります。
例えば、マリオカートで使用されるマシンについて考えてみましょう。
マシンは、カート、タイヤ、グライダーのような状態を持ち、アイテムを使う、クラクションを鳴らす、ブレーキをかけるなどの振る舞いを示すことができます。
そして、オブジェクトも同じ特徴を持ちます。
状態は変数に格納され、振る舞いはメソッド（関数）によって定義されます。
クラス
次に、オブジェクトと深い関わりのあるクラスについて解説していきます。
簡単に言うと、クラスはオブジェクトを作成するために必要な情報をまとめたものです。
オブジェクト指向プログラミングの用語では、クラスから作成されたオブジェクトをインスタンスと呼ばれます。
つまりクラスは、オブジェクトの設計図のようなもので、異なるインスタンスを作成するために必要な共通情報を提供します。
クラスを定義することで、同じ性質のものを簡単に作成することができます。
例えば、先ほどのマリオカートの例で話します。
マシンクラスというものを作成し、その状態としてカート、タイヤ、グライダーの変数を持たせます。
このようにすることで、設計図さえ定義すれば、変数を変更するだけで、さまざまなインスタンスを表現することができます。
コンストラクタ
オブジェクト指向プログラミングでは、コンストラクタ関数はオブジェクトを初期化するために使用される特別な種類の関数です。
この関数は、オブジェクトの新しいインスタンスが作成されたときに自動的に呼び出され、通常、オブジェクトのプロパティの初期値を設定したり、オブジェクトを使用するための準備として必要なその他の操作を実行するために使用されます。
コンストラクタ関数の重要な特徴のひとつは、戻り値の型がないことです。
これは、関数が呼び出されたときに値を返さないことを意味し、通常オブジェクトを初期化するためだけに使用されます。
また、this または self キーワードは、現在のオブジェクトを参照するためにコンストラクタ関数の内部でよく使用されます。
これらのキーワードは、コンストラクタ関数が呼び出されているインスタンスを参照するために使用されます。
状態
クラス内の変数の中でも、クラス内の全てのオブジェクトに対して共通する値を持つ変数はクラス変数と呼ばれます。
例えば、マリオカートで言えば、全ての車体に共通するものとしてエンジンが挙げられます。
エンジンの種類が異なれば、車体のスピードが変わってしまうので、クラス変数として扱うことになります。
一方、タイヤやグライダーのように、各オブジェクトのインスタンスごとに値が変わる変数をインスタンス変数と呼びます。
ちなみにクラス変数は静的メモリに保存されるため、値の変更によって、クラスの全てのインスタンスに影響を及ぼします。
振る舞い
振る舞いとはオブジェクトの状態の読み取り、変更、更新を行う処理のことを指します。
オブジェクトの振る舞いは、オブジェクトのクラスのメソッド内で定義されます。
振る舞いは、オブジェクトができることを記述する「動詞」であり、状態は、オブジェクトの状態を記述する「名詞」のような役割を持ちます。
アクセス修飾子
プログラミング言語によっては、アクセス修飾子というものを使ってクラス内で制御をかけることができます。
アクセス修飾子とは、変数やメソッドへのアクセスを制限したり、許可したりするキーワードのことを指します。
例えば private キーワードを用いると、クラス内部でのみその変数の読み書きができ、public キーワードを用いると、どのスコープでもオブジェクトの変数の読み書きができるようになります。
オブジェクトとメモリ
オブジェクトは、多くのプログラミング言語で、ヒープ上に確保されます。
オブジェクトは通常、そのサイズがコンパイル時には決まらない、または実行時に変更される可能性があるため、動的にメモリが管理されるヒープ上に確保されます。
たとえばJavaScriptのオブジェクトを作成するとき、以下のような手順が踏まれます。
- オブジェクトが作成されると、そのプロパティとメソッドを格納するためのメモリがヒープ上に割り当てられます。
- そのオブジェクトへの参照（アドレス）が、オブジェクト変数に格納されます。この変数はスタック上に確保されます。
- オブジェクトが不要になる（すなわち、そのオブジェクトへの参照を持つ変数がスコープから外れる）と、ガベージコレクションがそのメモリを解放します。
このように、オブジェクトは動的にサイズが変わることが可能で、またそのライフサイクルはスコープに依存しないため、ヒープ領域が適しています。
リスト
プログラムを書いていると、たくさんの場面で複数のデータを扱う必要が出てきます。
そのときに、データを順序通りにまとめて保管できるのがリストという構造です。
リストは、データを順番に並べて保管するための仕組みで、その中に入っている値には番号（インデックス）が割り当てられています。
たとえば名前のリストがある場合、インデックスを使用してリストから特定の名前を取得したり、スライシングを使用して名前の範囲を取得したりすることができます。
リストのデータ構造には、以下の2つがあります。
- 配列
- 連結リスト
リストを扱うときは、メモリ効率が良いという理由から配列を選択するのが一般的ですが、連結リストを用いた方が効率が良いケースもあります。
今回は配列について解説していきます。
配列
配列は、連続したメモリにそれぞれの要素を格納するデータ構造です。
要素は通常、連続した形で保存され、各要素はメモリ内の特定の場所を占めます。
要素のサイズとアクセスしたい要素のインデックスから、簡単な計算式でそのメモリアドレスを算出すれば、配列内のどの要素にもアクセスできます。
たとえば、32 ビット整数の配列がある場合、最初の要素のメモリアドレスを 10 × 4 バイトだけシフトすれば、配列の 10 番目の要素にアクセスできるようになります。
このように、どの要素のメモリアドレスも簡単な式で計算できるため、配列内のどの要素にも素早く効率的にアクセスすることができます。
動的配列
格納されている要素数に応じて、必要に応じて自動的に大きくしたり小さくしたりできるデータ構造として動的配列が挙げられます。
逆に、サイズが固定されている配列を固定長配列と呼びます。
動的配列では、配列に新しい要素を追加したときに、それを格納するための十分なスペースがない場合、配列は自動的に大きなメモリブロックを確保し、すべての要素を新しい場所にコピーします。
同様に、配列から要素を削除して配列のサイズがある閾値より小さくなると、配列は自動的にメモリの一部を割り当ててスペースを確保します。
この動的配列の主な利点のひとつは、配列のサイズや占有するメモリの量を気にすることなく、要素の保存やアクセスを効率的に行うことができる点です。
また、配列のデータを操作するためのさまざまなメソッドや演算子が用意されており、要素の挿入や削除、検索などを行うことができます。
動的配列の仕組み
それでは動的配列の仕組みについて詳しく見てみましょう。
動的配列では、配列の論理サイズと容量というものが常にメモリ内で把握されています。
論理サイズとは、現在配列に格納されている要素数を表し、容量はサイズを変更する前に配列が保持できる最大要素数を表します。
動的配列に要素を追加し、要素数が容量を超えると、新しい要素を収容するために配列は自動的に大きなサイズにリサイズされます。
このとき動的配列では以下のようなステップで、自動的でさらに大きな容量の配列を作成し、拡張します。
まず、新しい容量 = 論理サイズ × d となるように、より大きな容量の新しい配列を作成します。
この d は成長係数と呼ばれ、1.5 や 2 がよく使われます。
なので最悪の場合、O(n) 分のメモリが無駄になることもあります。
動的配列の挿入と削除
動的配列の先頭に要素を挿入するには、通常、既存のすべての要素を 1 つずつずらして、新しい要素のためのスペースを確保する必要があります。
これは特に配列が大きい場合には、時間のかかる操作となります。
n 個の要素の動的配列の真ん中へ要素の挿入を行う場合は、0.5n 個の要素を移動させる必要があり、結果として O(n) の計算コストが必要になります。
このように、コンピュータは複数の要素を一気に追加することができず、ステップバイステップでしか処理を行うことができないため、時間計算量や空間計算量を常に意識する必要がある点に注意しましょう。
二次元配列
データの「列」を扱うには、int 型、double 型、str 型、オブジェクトのリストなどを格納する配列を利用しました。
では、データの「表」の扱い方について見ていきましょう。
これは配列の中に配列を入れることで表現することができます。
そして、これを二次元配列と呼びます。
二次元配列を使うと、チェスやオセロのようなボードゲームでも、データとして表すことができるようになります。
多次元配列
配列の配列が可能であるように、配列の配列のまた更なる配列といった多次元にわたる配列も表現することができます。
現実世界で入れ子構造になっているものはなんでも多次元配列を適用することができます。
例えば、動物の分類の場合は、目 > 科 > 属 > 種の４次元の配列を使用すると、表現することができます。
連想配列
インデックス以外に文字列を使って、データを効率的に取得することを考えます。
例えば、ある本のタイトルを知りたいときは myBook["title"]、あらすじを知りたいときは myBook["description"] といったようにデータを取得できると便利です。
このようにコンピュータが文字列などのキーをインデックスとして使用する場合、これは連想配列と呼ばれます。
連想配列は、従来の配列のような数値インデックスではなく、文字列やその他のキーをインデックスとして使用するデータ構造です。
この方法だと人間もデータを理解し利用することが容易になります。
ちなみにプログラミング言語では、連想配列はしばしば辞書やマップと呼ばれることもあります。
連想配列の仕組み
連想配列内の値を効率的に検索するために、キーは通常ハッシュ関数でハッシュ化されています。
ハッシュ関数とは、キーを取り込んで、ハッシュ値またはハッシュコードと呼ばれる固定サイズの出力を生成する関数です。
ハッシュ値は通常数字で、キーに含まれる文字のコードポイントに基づいて計算されます。
そして、連想配列を実装する方法のひとつにハッシュマップがあります。
ハッシュマップは、ハッシュ関数を用いてキーと値を対応付けるデータ構造です。
ハッシュ関数では、キーをハッシュ値と呼ばれる数値に変換しました。
ハッシュ値は、ハッシュマップ内のどこに値を格納すべきかを決定するために使われ、また値が必要になったときにその値を調べるために使われます。
例えば、hogeというkeyに"bar"という文字列が対応されている連想配列で考えてみます。
この場合、hogeのコードポイントの数値を元に、ハッシュ関数を用いてハッシュ値が生成されます。
そして、ハッシュマップを使ってそのハッシュ値のindexにbarのコードポイントを格納します。
もし、hogeをkeyにその値を取得したい時は、再度hogeをハッシュ関数に渡してハッシュ値を取得します。
そして配列と同じように、そのハッシュ値のindexのデータ取得するわけです。
ハッシュマップを使うと、インデックスを使う時と同様に、時間計算量 O(1) で要素にアクセスすることができます。これはハッシュマップを使う大きなメリットになります。
まとめ
今回はプログラムの基本となる「オブジェクトとリスト」について解説しました。
今回学んだ知識を使うことで、プログラムをよりわかりやすく、効率的に記述することができます。
引き続き学んだ内容をアウトプットしていこうと思うので、参考にしてください。
宣伝
0からエンジニアになるためのノウハウをブログで発信しています。
また、YouTubeでの動画解説も始めました。
インスタの発信も細々とやっています。
興味がある方は、ぜひリンクをクリックして確認してみてください！
Discussion