見出し画像
Photo by daisaw33

データ構造その2(抽象データ型)

string name; cin >> name;

乳児がいるとなかなか時間が取れないですね。
非技術側のブログで不確実な話で誹謗中傷する人達に辟易して記事書いたり。ホント、ネットリンチとかする奴らに成功体験を与えてはいけないんですよ。世論はそんなところにはないし、あってはならないので。それはカスによるカスハラ至上主義の世界。会社で憶測で文句や悪口ばかり言ってる社員の意見を貴重な意見として考慮するか、というと、まぁ、毒社員として扱われますよね。なんでネットの意見だけ攻撃的でも世論とするのか。駅でだけ毎日発生する体当たりしても気にしない人達とか。彼らによるとタックルの体勢で広がって歩いて、避けずにぶつかるのは故意じゃないらしい。彼らは釣銭泥棒を悪いと思わないんだろうね。考えてみると駅や電車ほど暴力行為が横行してるとこないですよね。Fラン不良高校より暴行の発生数多いのでは。

前回はデータ構造の前段として計算量の話を取り上げました。

今回はデータ構造第2回ですが、あまり技術ネタは需要ないですかね。
まぁ、本買って読めばいい話ではあるのですが。そうなるとあれですかな、ちょっとネタ盛り込んで読みやすくした方が良いのかも知れないです。

今回は抽象データの話です。

あと前回の補足ですが、計算量には時間計算量と空間計算量と二つに分かれ、前回取り上げたのは時間計算量です。空間計算量というのはメモリをどれくらい使うか、という話で、特に組み込みなどのリソースの少ない環境では重要になったりします。この辺もアルゴリズムの話で掘り下げるかも知れません。まぁ、木構造とかMapの辺りでは実装方法でメモリどうなるか、の話は出てくるとは思います。

空間計算量とかこだわる人はこだわりますね。
確かに機械学習とかになってくると、あれ、メモリ51GB使用とかなってんぞ？とか言う話あるけど、計算量知らない人が触る領域では基本ない気もする。マシンスペック上がってて、そこまで気にならないことは多いですが、マイコンとか携帯向けのプログラム書いてた人は気にするかもですね。昔のガラケーゲームとか、裏技みたいな実装してる人もいたようで。

抽象データ型とは

抽象データ型に関して、そこまで重要な話ではないのですが、初級者の人達は概念として知っておいた方がいいです。コンピュータサイエンスの世界では言語やライブラリの中で共通の仕様を標準化して使うことで言語間での差異をなるべく減らして、可読性を高め理解しやすくしています。特に通信仕様のように送信側と受信側でルールが一致しないとまともに通信が成り立たなかったりします。

で、抽象データ型ですが、データ構造と操作に関して定義されたデータ抽象の方法です。英語ではAbstruct Data Type(ADT)と言います。通常データ型は数値型のように値の解釈の仕方の定義ですが、抽象データ型では操作も含むのが特徴です。

抽象データ構造

抽象データ型と抽象データ構造と別で書かれたりしますが、これ、違いがよくわからない。計算量の定義等と考えるとある程度しっくりきますが。つまり、このデータ構造のこの操作はO(n log n)以下であると保証される、という感じで。

何が嬉しいの？

こういう標準化というので何が嬉しいか、というとまず違う言語でも同じ名前(たまに少し違う)の関数で同じ処理ができることです。ライブラリのimportの仕方やインスタンス化は言語で変わりますが、基本的に操作は同じ名前でできます。同様に、最悪ケースの時間計算量が保証されることです。なので、どの言語を使っていてもこのデータ構造でこの処理をする限り処理時間は問題にならない、と安心して使えます。

3段階の抽象化

  • ADT(言語に依存しない)

    • どんなデータ型か定義される

  • インターフェース(コンテナのライブラリ)

    • どうやって使うか定義される

    • コンテナの振る舞いがわかる

  • 実装(ライブラリ)

    • どう動作するか

ADTはプログラミング言語に依存しません。言語ごとに関数名は違ったとしても基本的なふるまいは同じものが提供されます。つまり、ADTの中小レベルでデータ型を理解すれば、基本的に全ての言語で提供されるそのデータ型を把握できる＝すぐに使えるということです。

例

スタックは後入れ先出し(Last In First Out=LIFO)でデータのコレクションと定義されます。また、ADTは比喩で説明されることもあります。例えばスタックは皿を積むようなデータ構造と説明されます。

古典的なADT

  • Bag, Ordered bag
    単純なデータのコレクションです

  • Stack, Queue, Deque
    入れた順に並びます

  • Priority Queue
    優先度で並びます

  • List
    データの連続に依存性がある(前後を知っている)コレクション

  • Tree, Graph
    複雑なデータの依存性を持たせられる

  • Set
    要素がユニークな(重複のない)コレクション

  • Map
    Key/Valueで結びついているコレクション

Bag ADT

定義

順不同なデータの集合(重複は許容する=>許容しないのはSet)

操作

  • bagの初期化

  • 要素の追加/削除

  • bagに要素が含まれてるかのチェック

  • bagのサイズの取得

振る舞い

時間計算量の要求

Bagのインターフェース

下記のシグネチャで利用できると定義することで実装が隠蔽されます。
要は違う言語でも同じ振る舞いを期待できるということです。

initBag (); 
addBag (value);
containsBag (value);
removeBag(value);
sizeBag();

課題

自分の好きな言語でデータの配列とサイズを持った構造体で上記を実装してバッグの動きを作ってみましょう。
その際にcontainsとかデータ構造の関数を使うと意味がないので、基本的にはindex(添え字)でアクセスしましょう。
削除の時にどうするかがポイントでしょう。

次回

次は動的配列を取り扱います。

この記事が気に入ったらサポートをしてみませんか？