感謝のプログラミング 10000時間

たどり着いた結果(さき)は、感謝でした。

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

Javaで2分探索のサンプル

2分探索とは、英語でbinary searchといって、要素がキーの昇順または降順にソートされている配列から効率よく探索を行うアルゴリズムのこと。2分探索の方法は単純で、対象の配列を真ん中から半分に割って、ターゲットの数字が右側にあるか(真ん中の数字より…

スタックとキューのサンプルをJavaで作って遊んでみる。

アルゴリズムとデータ構造の勉強は、部活でフットワークやるみたいに、コツコツやっていきたい。 アルゴリズムは、(現時点では)パズルを解くみたいで面白い。 難しくなると苦しくなるかもしれないけれど。今日は定番のスタックとキュー。 スタックとは スタ…

線形探索のコストを抑える番兵法

番兵法って何? 「探索する値」と全く同じ値を、配列の一番後ろに置く探索の方法を番兵法という。 番兵とは、そのとき格納する「探索する値と全く同じ値」のこと。では、なんで番兵なんて置くのか?というと、線形探索で前から順番に走査するときに、以下の…

Javaで線形探索

線形探索は非常に単純な探索方法で、簡単にいうと、配列の前から順番に探していくだけ。柴田先生の本でいうと、 要素が直線上に並んだ配列からの探索は、目的とするキー値を持つ要素に出会うまで先頭から順に要素を走査することによって実現できます。 とな…

Javaでクイックソート

クイックソートはある基準となる値(=枢軸,pivot)を決め、それ以上のグループとそれ以下のグループに分けて、並べていくソートアルゴリズムである。 枢軸以上と枢軸以下に分けたら、分けたグループの中でまた枢軸を決めて、ソートを再帰的に繰り返していく。 …

文字列探索のKMP法を考えた人すごいと思う。

読書メモ 人間を模倣し、徐々に人間に取って代わっていくようなアルゴリズムを作り出せる能力が、これからの百年を支配するスキルだ。 この能力を持つ人が増えれば増えるほど、仕事はなくなり、人生は今までと異なるものになり、産業は生まれ変わることを余…

文字列探索の「力まかせ法」について、まとめる。

文字列検索では、探しだす文字列を「パターン」と呼び、探索される側の文字列を「テキスト」と呼ぶ。 今回見ていく「力任せ法」というのは、方法論というよりは単なる力技だ。単純法とも呼ばれるこの方法では、たとえば「ABCDEFG」という文字列(テキスト)の…

【アルゴリズムとデータ構造】再帰呼び出しのアルゴリズムの簡単なサンプルを試してみる。

再帰呼び出しとは 再帰呼び出しとは、ある関数Aの内部で自分自身を呼び出して処理を繰り返すこと。 呼び出された関数Aのなかで、さらに関数Aが呼ばれ・・また呼ばれ・・・と自分自身を呼び続けるので再帰呼び出しという。再起呼び出しの例は以下の通り。関数…

キュー(Queue)の仕組みとデータ構造。

キューとは キューというのは、先入れ先出し(First In First Out)と呼ばれるデータ構造である 順番待ちの列を想像するといい。 キューにデータが追加されると、データはキューの最後尾に入る。 で、キューからデータが取り出される時は、キューの先頭から取…

「スタック」は様々なデータを順番に出したり入れたりする時に使うデータ構造。

スタックとは? 後から入ってきたデータが先に出て行く、「後入れ先出し(Last In First Out:FIFO)」のデータ構造。 食器棚に入っているお皿のようなもの。 皿を使う時は、食器棚の上から順番に取っていく。 使い終わったお皿は皿の上にどんどん積んでいく。 …

リストのサーチ(探索)は基本的にリニアサーチのみ。

データ構造「リスト」の検索 リストは配列のように添字を使ってデータを扱うことができない。 そのため、先頭から順に後ろにたどっていくか、反対に末尾から前にたどっていくかしかない。 だから、リストはデータを飛び飛びにアクセスするには向いていない。…

アルゴリズムとデータ構造の「リスト」について

今日はデータ構造について。配列にデータを突っ込んで、データを見ていくという方法を見てきた。 しかしarray[]みたいな配列に数値を入れていくとすると、「配列の大きさが固定されてしまう」という問題が生じる。 で、ユーザーの都合によって、配列の大きさ…

番兵を使えば、力ずくのリニアサーチより約1割強のスピードアップ!

番兵って何? 配列を検索するときに、配列の最後に「探したい数値」を入れる。 それを一番ケツで配列を守るようなイメージから、番兵という。番兵の何がいいか。 配列を一番先頭から検索する時に、n++みたいに増やしていくわけだけど そのときにnは配列の末…

ソートした後で、真ん中付近から調べていくバイナリサーチ

バイナリサーチについて バイナリサーチとは、二分探索と呼ばれるサーチ方法である。 全体を2つに分け、目的の値が分割点の前後どちらにあるかを判断して、検索範囲を狭めていく。ただし、こうやって2つに分けて探索するということは、数値がソートされてい…

「力ずくで検索」リニアサーチ

サーチ(検索)とは サーチとは、たくさんのデータの中から目的のデータがどこにあるか調べる作業である。 リニアサーチ リニアサーチとは、要は「力ずくの検索」のことである。線形探索という。計算量オーダはO(N)。 先頭から順番に調べていって、探している…

AntでJavaを実行する手順のまとめと、線形探索。

ことば 言語の制約はそれを使う人の世界を制限する。 ルートウィッヒ・フォン・ヴィトゲンシュタイン 線形探索 線形探索はソートされていないランダムな並びの配列から探索を行うための唯一の方法。線形探索とは、先頭から順番に当たりをつけていって、一致…

安定しているマージソート.

マージソート マージソートは分割統治法によってソートをオッコなう。 配列を前半部と後半部に分けて、各部をそれぞれソートする。 ソートした前半部の配列と後半部の配列をマージするのがマージソート。 マージソートは安定している。 マージソートが安定し…

だいたい先頭、だいたい最後のクイックソート。

クイックソートの勉強をしてみた。 クイックソートのアルゴリズムは以下の通り。 ①ある適当な数字を決めて、それよりも大きいものは後ろへ、小さいものは前へ移動 ② ①の時点で、「①で選んだ数字より大きいグループ」と「①で選んだ数字より小さいグループ」の…

効率が悪いバブルソート。

ことば 非効率なソフトウェアが醜いのではない。醜いのは、プログラマに不要な仕事をさせる言語だ。 本当の非効率性とは、マシンの時間を無駄にすることではなく、プログラマの時間を無駄にすることだ。コンピュータが速くなればなるほど、このことははっき…

【プログラミング 61時間目】オバマとGoogleCEOのやりとりで話題となったバブルソートとは何か?

オバマとGoogleCEOのやりとりで話題となったバブルソートとは何か? 2007年11月、当時民主党の大統領候補だったバラク・オバマは演説のため、 カリフォルニア州マウンテンヴューのグーグル本社を訪れていた。 現在、ウェブサイトテスト企業OptimizelyのCEOを…