アルゴリズムとデータ構造

Question

アルゴリズムとデータ構造について、

Progateにて プログラミングの勉強を一通りして、次のレベルへ挑戦したいと思います。

そこで先ずはアルゴリズムとデータ構造について勉強したいと思います。この分野はプログラムにおいて欠かせない分野だと聞きました。

しかし実際に内容を見てみると、自分がprogateで習ったプログラミングと、アルゴリズムデータ構造の 分野がどのように関連付いていくのかイメージしずらいです。

配列？スタック？キュー？など、説明は理解できるのてすが プログラミングとどう繋がるのか教えて下さい。

Comments

[hayataka2049]

progateでどんなことを学んで、どんなことができるようになったのかとか書くとちょっと回答しやすくなるかなと思いました。

[Q71]

データ構造を学ばずにどのようなプログラムを学んだのでしょうか。とても興味深いです。

Answer 1

アルゴリズムをスクラッチで書く機会はそう多くはありません。

基本的には言語やツールが内部で実装しているものを使わせていただく、という位置付けです。自分でアルゴリズムを使いたくなることもありますが、それ用のライブラリや言語機能などがあるでしょうからたいていそれで片付きます。低レイヤ（それこそライブラリとかOSとか）だったり特殊なもので既存のライブラリが役に立たなかったり、きっちり目的とする処理に最適化したい……というときはまれにフルスクラッチで書くかもしれません。

Progateだと実践的（というかアプリケーション寄り）な内容が多いので、ほとんど意識しなかったと思いますが、配列（はともかく）、スタック、キューなんかはすでに使っているでしょう。

スタックは関数のコールスタックがありますし、Java仮想マシンはスタックマシンです。あとはプログラミング言語を構文解析するだけでもスタック使いますね。

キューの方は、身近な話だとCLIの標準入出力はOSによってバッファリングされることが多いですが、これもキューの一種です。もう少し実感の沸く例だと、たとえば、Webサーバがリクエストを受けるときに、短時間に応答できないほどたくさんのリクエストが来たら、とりあえずキューに入れて順次処理するとかする訳です。

まあ、いくらでも使ってます。

偉大な先人たちは、そういうことを実現するためにアルゴリズムとデータ構造の研究をやって、使えるようにしてくれたのですね。我々はそれに乗っかるだけですが、中の仕組みくらいは教養として知っておけ、というのが「プログラムにおいて欠かせない分野」の意味するところの1/2くらい。

で、1/4くらいは、自分でフルスクラッチで実装する機会はなくても、アルゴリズムを活用した処理を書くことはよくあるので、そのときにちゃんと使い分けるために知っておく、ということですね。たとえばソートだけで何百種類とあって、少ないデータ量なら効率がいいけどデータ量が増えると遅いやつとか、メモリ食うけどすごく速いやつとか逆にメモリ食わないけど少し速度で劣るやつとか、ほとんどのデータの並びは高速にソートできるけど特定のデータの並びに対してはてんで駄目なやつとか、それぞれいろいろ特色があります。知らないと使い分けられない。

残り1/4は、知識として知っておくと車輪の再発明を避けられるという事情です。解決したい問題があるときに、「これは○○法というアルゴリズムを使えば一発だな」と気づいてライブラリ探してそれ使って解決して……となるのと、あれこれ考えて悩んで頑張った末に既存アルゴリズムの劣化版を実装しちゃうのと、どちらが理にかなっているか？　ということです。

あと、これはおまけですが、アルゴリズムとデータ構造はプログラミング初心者にちょうどよい問題の規模なので、Cとかで書くとプログラミングの練習になります。

なので、たとえばJavaの書き方とかを覚えるとか、HTMLやCSSやJavaScriptやWebフレームワークの使い方を学ぶとか、そういう「プログラミング」とはちょっと違った位置付けになります。極論すれば、アルゴリズムとデータ構造を知らなくてもプログラミングはできます（場合によっては数桁くらい効率の悪いものを作っちゃうかもしれないけど）。知らないでやっている人もたくさんいます。私も「そらで○○を実装しろ」とか言われたら、たぶんギブアップします。

最優先で勉強すべきものなのかどうかは、もう少し考えても良いでしょう。後回しにしてもなんとかなります。それより、Progateによりかかりっきりでやっていたなら、とりあえず自分で開発環境を作って、学んだ知識を生かして何かしら簡単なものでいいので作ってみた方が良いんじゃないか、とか。

ありがたみがわからないうちに漫然と勉強するのは独学なら（大学の講義で取るっていうなら別にいい）あまりおすすめできませんが、どうせプログラムを書くなら何らかの形で関わり合うので、そういう意味ではやっておいて損はありません。

Comments

[BeatStar]

>> 残り1/4は、知識として知っておく...

ああ、確かにこれはありますね。

[sazi]

アルゴリズムって標準関数とかライブラリとか、ブラックボックスとして利用してるものの中身の話だけじゃ無いと思います。
ビジネスロジックのフローチャットやシーケンス図だってアルゴリズム。

[hayataka2049]

@saziさん
「アルゴリズムデータ構造の分野」ということなので、そういったことには触れませんでした。広義のアルゴリズムという意味ではおっしゃる通りだと思います。

[sazi]

@hayataka2049さん
hayataka2049さんが認識を誤解しているなどとは毛程も思っていません。
質問者の意図が広義で、回答内容が狭義に感じたのでコメントしました。

Answer 2

かなり古い（初版が1975年……44年前です）コンピュータに関する書籍で、
「アルゴリズム＋データ構造＝プログラム」
という題名の書籍があります（N.ヴィルト著）。
今は「アルゴリズムとデータ構造」とか名前が変わってたり、フォロワーによる類似書籍（別言語で解説したものなど）も多いです。
それほどの名著であり、今なお役に立つ書籍です。

つまり、アルゴリズムとデータ構造とは、プログラムの構成要素そのものです。
プログラムとは何かを行う段取りを記述したものですから、行うこと（アルゴリズム）とそのために必要な情報（データ構造）があれば、プログラムになるのです。
※この本が書かれた当時はまだ構造化プログラミングさえ一般的ではありませんでした。そこに構造化の手法を持ち込んだ書籍でもあるのです

プログラムとアルゴリズム及びデータ構造が結びつかない、というのは、結局何も理解していないといってもいいくらいです。両者は不可分なのですから。

まずはこの本から読み直してはいかがでしょうか。公共図書館などであれば蔵書しているかも知れませんし。

Comments

[sage]

私が持っている日本語版の初版は1979年9月15日の発行で、原著のcopyrightは1976年となっています。

Answer 3

配列？スタック？キュー？など、説明は理解できるのてすが プログラミングとどう繋がるのか教えて下さい。

ソフトウェアにおける「ネジ・クギ」ですからね、おうち建てるのに絶対必要だけどその存在は意識されにくいものです。どう繋がるというより部品そのものです。

Answer 4

他の方も回答されていますが、アルゴリズムとデータ構造を学んでも今のプログラミングに直接結びつくわけではありません。
あくまでプログラミングにおける一般教養のようなものです。

Progateにて プログラミングの勉強を一通りして、次のレベルへ挑戦したいと思います。

次のステップとしては、実際にアプリケーションや Web サービスを開発した方が実践的だと思いますし、アルゴリズムとデータ構造はその後でやっても良いような気がします。

Answer 5

データ構造とアルゴリズム (以降、D.A) は何かを作れるようになるためのものというよりは、先人たちの考えを学ぶことです。

こういう考えがあるよ。っていう。

数学の問題を解くのと一緒です。一方向から見るとわかりにくい場合でもいろんな方向から見ると「そういうことか!」ってなることありますよね。

それと一緒です。

データ構造 ( 以降 DS. (from Data Structure) ) はC++でもSTLというライブラリで提供されていますね。
JavaやC#なら言語としてなのかな? 提供されていますね。

C++でのリスト構造はstd::listです。
std::vectorっていうのもありますが、こいつは動的配列です。

動的配列は要素数が要らないけど、削除( 初期値に戻すのではなくて削除 ) や最後尾以外の追加が苦手です。
一応、関数 ( Javaでいうメソッド? ) は用意されていますが、速度がね...(最近のPCだと気にならないかもしれないが...)

std::listはリスト構造です。
剥ぎ取り( 削除 ) や 追加がstd::vectorよりは早い。
だって、前後のパッチを外して追加してパッチを接続すればいいだけだし。

( リスト構造を学べばわかりますよ )

std::queue (キュー) っていうのもあった気がします。こいつは待ち行列っていうやつで、
追加順にやっていく保存領域みたいな?

例えばマルチスレッドとかでスレッドA～Cがメインスレッドに処理を要求するとして、その処理内容等がキューに突っ込んで、メインスレッドが順番に処理する...

みたいな感じかな? 実際に使えるかどうかわからんけど。

std::stack (スタック)は上に積んでいって、上からとっていくやつ。

逆ポーランド計算機でしたっけ?

1 3 +

とやったら スタックを用いて 1, 3, + で 1 + 3 とみなして 4 がスタックに。

みたいなアレ。

参考: 逆ポーランド記法 - Wikipedia

こういう風に、「この場面、この条件ならこいつが楽かも」っていう風に考えるための知識と、

「こういう考え方もあるのか」っていうのを学ぶ。

自分がprogateで習ったプログラミングと、アルゴリズムデータ構造の 分野がどのように関連付いていくのかイメージしずらいです。

多分、教科書・参考書しか読んでいない人に多いタイプかも。

算数・数学だと~~「教科書読みました。でも公式? 知りません。」っていうレベルです。~~
swordoneのお言葉をお借りして言うと、「教科書読みました。でもいつ公式を使うかわかりません。」っていうレベルです。

実際に何か作品を作ってみてください。

参考: ロジック

---

[追記2]

念のため一応書いておきます。

あくまで趣味の範囲でやっているので正しくない部分があるかもしれませんが、まあ、私なりのとらえ方として。

std::vectorは内部ではJavaやC#でいうnew, C++でいうnew/delete, Cでいうmalloc/free を用いて確保しているっぽいです。

// あくまでイメージ。
// 実際には template っていう機能?を使って実装しているようだけど、
// 例だし、面倒なので省略。ここではint型用としてやっています。
class IntVector{
      public:
                 IntVector( int size = 100 ){
                         v = new int[size];
                 }
                 ~IntVector(){ delete v[]; }
                 // ほかにもメンバがあるとして
      private:
                int *v;
};

で、削除したいとする。現在の要素数は10 だとして、4番目のデータを削除したい場合、

// IntVector内だとして。
// また、iteratorを このIntVectorで使えるイテレータだとする
iterator remove( int pos ){
         // 一旦、別容器を用意
         // 現在のint *v の -1 (つまり要素数を一戸減らす)して生成
         int s = size() - 1;
         int *temp = new int[ s ];
         
         // ここでv -> temp する。ただし、vのpos番目はスキップする
         
         // ここでvをいったんdeleteするか上書きかわからんが、
         // とにかくvを空だと想定する
         
         // 再度vを容量確保する
         v = new int[s];
         
         // tempの内容物をvにコピー
         
return /* ここでIntVectorのiteratorを返す */;
}

のようになっていると思う。

もちろん、この例はtemplateじゃなくてintに固定しているし、ところどころ違いますが、
「別容器を用意してそれにいったん移し替えて、サイズ変更して...」的な処理をしていることは
同じだと思う。

現在のPCだと気にならない速度だと思いますが、なるべくしょーもない時間取りは省きたいですよね?

std::listならパーツを取り換えるだけで済むのでstd::vectorよりは早い。
( これは D.A に載っている内容なので省きます。 )

ただし、リスト構造はエリア(厳密にはメモリアドレス)が飛び飛びなので
ランダムアクセスって呼ばれる、要素数を指定したアクセスとかが苦手です。

配列やstd::vectorだと arr[1] とかみたいにアクセスできるけど、

リスト構造は イテレータって呼ばれる、走査するためのやつを使うか、拡張forと呼ばれるやつとかで
最初から最後まで調べないといけない。( もちろん途中で抜けることはできるけど。 )

このメリット・デメリットを理解しているなら、

「フーム、今回はできるだけランダムアクセスできるようにしたいなぁ。追加や削除は...いらねぇなぁ。ってーことは...今回はstd::vectorでいいんじゃね?」

みたいに考えることができる。

Comments

[swordone]

最後に関しては、｢公式覚えたけど問題が解けない｣のほうが近い気がする。

[BeatStar]

swordoneさん

あ、そうですね。言葉をお借りしますね!

Answer 6

配列？スタック？キュー？など、説明は理解できるのてすが プログラミングとどう繋がるのか教えて下さい。

配列やスタック、キューなどのデータ構造を覚えるとそれ等をそのままプログラミングで表現できるようになります。
繋がりと言ってもこれ以上は特にありません。

アルゴリズムデータ構造の 分野がどのように関連付いていくのかイメージしずらいです。

まず、データ構造が存在することのメリットや覚えておいしい部分はご理解されていますでしょうか。
配列やスタック、キューの言葉と局所的な理解だけでは、「ふーん」で終わってしまいますのでまずは其方から理解しないといけません。

何事も学ぶときは大きい（抽象的な）部分から始めて小さい（具体的な）部分を覚えていきます。
そうすると、「あれとこれの繋がりが分からない」という疑問は出てこなくなります。

具体的な部分から学び始めると見当違いな理解をしたり深く理解ができなかったり、後で痛い目に合いますから、大きい部分から学ぶという姿勢は意識したほうがいいです。

ここまで良いでしょうか？

じゃあそもそもデータ構造とは？

データ構造の意味をwikipediaから引っ張ってきました。
次のような意味があるそうです。

データ構造（データこうぞう、英: data structure）は、計算機科学において、データの集まりをコンピュータの中で効果的に扱うため、一定の形式に系統立てて格納するときの形式のことである。

これを見ると以下のことが分かります。

• データ構造はそもそもデータの集まりを効率的に扱うための形式のこと
• データ構造には配列やスタック、キューなどがある
• 反対に言えば配列やスタック、キューは「データの集まりを効率的に扱える形式」の一部

何となく、配列やスタック、キューがなぜあるのか分かってきたのではないでしょうか。

もし分からなければ、「もしデータ構造という概念が存在しなかったら？」というのを考えてみたり、そもそも「効率化」することにどのようなメリットがあるのか、などもっと基礎的な部分に着目すると理解しやすくなるでしょう。

ここまで良いでしょうか？

本題

自分がprogateで習ったプログラミングと、アルゴリズムデータ構造の 分野がどのように関連付いていくのかイメージしずらい

先ほどの話から、データ構造のメリットは分かったと思います。
たくさんのデータを管理したいときに配列やスタック、キューは使えるんだな～と。

意味はご理解できたと思いますが、データ構造をどのようにプログラムで表現できるかはまた別の問題になりますね。データ構造という仕組み自体は同じでもコードとしての書き方は言語によって変わりますので。

データ構造をどのようにプログラムで表現できるか

それは実際に書いてみないと分かりません。

お使いの言語、開発環境で配列やスタック、キューなどを、既存のライブラリ（簡単に言えば人が作ったプログラム）を利用したり、自作したりで試しに触ったり作ったりすると一番理解しやすいと思います。

Answer 7

すごく質問の文章にツッコみどころが多いように感じました。

Progateにて プログラミングの勉強を一通りして、次のレベルへ挑戦したいと思います。

まず、何の言語を書きましょう。

配列？スタック？キュー？など、説明は理解できるのてすが プログラミングとどう繋がるのか教えて下さい。

配列に？を付けている時点で、プログラミングの勉強を出来ていませんね＾＾

アルゴリズムとデータ構造

簡単なものを少しづつこなしましょう。いきなり機械学習等に走るのはおススメ致しません。
Progateで行われているwebのプログラミングでは少し難しいと思います。
その辺はC言語を学ぶと自然に身に付きます。
BeatStarさんやhayataka2049さんが名を挙げたC++、Javaの大本になっている言語です。