教科書的な内容は疲れるな。でもコツコツやらねば。 ちょっと実装しようかなと思ったけど、今日はオシマイ。明日からは、「プログラミングの宝箱 アルゴリズムとデータ構造」も使ってみる。

データ構造の実現 基本データ型 例、数値型(整数、文字、浮動小数点数) 基本データ型をベースにして、ポインタ、配列、構造体(stract)、共用体(union)、関数を組み合わせて任意のデータ型をつくれる 基本データ型は言語によって大差は無いが、C言語には文字…

今度はデータ構造だ。 用語 擬似コーディング 擬似プログラム 段階的詳細化(stepwise refinement) 擬似プログラムを細部をつめながらプログラミング言語に置き換えること 抽象データ型(abstract data type) データの型とその型に対する一連の操作の組 例、「…

線形探索法と2分探索法とハッシュ法の短所を比較 短所 線形探索法はデータを登録順に保存しているが、探索が遅い 2分探索法は探索が線形探索より早いが、あらかじめソートが必要だし、データの登録順を保存できない ハッシュ法はハッシュ関数が便利だが、デ…

ハッシュ法ですね。 hashing。 ハッシュ関数って何？ キーの値から添え字を得る関数をハッシュ関数という。 たとえば？ 例えば、大きさ100の配列を使って、整数のキーをもつデータを扱うには ハッシュ関数hash(key)を、h(key) = key % 100、などとして ハッ…

お、もう日付が変わるなー。 じゃあ、もうおしまいにしよう。 疲れる前に止める。堅苦しくないのが続ける秘訣。次はハッシュ法だよ。

2-2-3はデータ挿入のコストの話。 そうか、検索だけじゃなくて挿入のコストを考えなきゃいけないときも多いよな。 リニアとバイナリのデータ挿入における違い。 リニアはソート不要なので、リストの最後にデータをくっつけるだけ。 一方、バイナリは常にリス…

2分探索法の肝をメモ ポイント 最初にデータをソートすることが必要 着目範囲の上限と下限を常に設定する 上限と下限から真ん中を算出し、目的のキーと真ん中を比較する キーと真ん中との大小をみることで、真ん中を上下に移動させる。 真ん中を移動するとき…

おっと、わすれてた。2-4は途中で力尽きて放棄してたんだ。 線形探索法の計算量 ループの中は各回に1回づつ実行される処理なので、ループ内はO(1)。 そしてwhileループの平均実行回数はO(n/2)となる。 これは、ちょっと回すと結局O(n)になってしまう。 あと…

ということで、今日はバイナリサーチこと、2分探索法をやる。 binary search。いい響き。 2分探索法って 前回の線形探索法との違いは、ほとんど以下の関数に集約される。 前回のsearch()を以下に置き換えればok。 int binary_search(int key){ int low, high…

なんか、前回の日記からずいぶんと間があいてしまったなー。 時間が空いた理由は、きっちりやろうとしすぎていたからかな。 ともかく手が伸びなかったのだから心の奥底で気が重かったんだと思う。改善策は、ここのところ考えていたので導けた。いままでは「…

定本 Cプログラマのためのアルゴリズムとデータ構造の第2章の読書メモです。 線形計画法による探索の計算量 計算量について考える。使う例は、n個のデータを格納したリストから、ある特定のキーを持つデータを探索するもの。 単純な探索プログラムのデータ数…

疲れたのでおしまい。 次は計算量の乗算をやるらしい。 バイナリサーチはリニアサーチをいじるだけだから早く終りそう。 おつかれ。

発見というか、忘れているだけかも。 #defineの行末は「;」なし 関数名と同じ変数は作れない int型で表現できる範囲が、意外と狭い。 randはsrandで初期化する 引数を受け付けない関数の宣言は、関数名(void)にする。 構造体はハッシュだなー

プログラム用の環境として、Windows XP上にVMware Playerを起動しています。 イメージはDebian Sarge Linuxです。 Puttyを使ってアクセスしています。 エディタはEmacsです。 アルゴリズムに無知ですが、この辺は他の方のブログを見ながらなんとか出来ました…

ぐは、びっくりした。 明日・・・と言いつつ、もう一週間たっていた。 でも、こういうときにブログにメモがあると助かります。 ブログをはじめてよかった。 ま、今週はいろいろ忙しかったので。

定本 Cプログラマのためのアルゴリズムとデータ構造の第2章の読書メモです。 基本操作の計算量を定義する 関数呼び出しを含む演算や代入処理 Oは処理系や扱うデータ構造中のデータ量に依存 データ量に関わらない処理 O(1) O(f(n))とO(g(n))を連続で実行して…

今日はブログを用意したりなんだりで時間を使ったし、まだ昼飯食べて無いから今日はこれで終る。明日は二分探索をやるみたいだ。

定本 Cプログラマのためのアルゴリズムとデータ構造の第2章の読書メモです。 計算量(Complexity)という抽象的な尺度を使う。 O:オーダー n : 入力データの大きさ、回数 O() : nの関数として表現する計算量 計算量は抽象的な尺度。 同じ計算量でも1秒だったり…

定本 Cプログラマのためのアルゴリズムとデータ構造の第2章の読書メモです。 アルゴリズムの性能評価 計算機と同じように実行時間のベンチマークで測定するのが自然。 実行時間のベンチマークテスト 決められた課題プログラムを実行して処理時間を性能の尺度…

いまさらですが、ブログと勉強は相性が良いですね。 とくにプログラミングにはピッタリのようです。 定本 Cプログラマのためのアルゴリズムとデータ構造の第1章はサックリ読めました。 言っていることがもっともなので、スっと理解できました。 では2章へ。

定本 Cプログラマのためのアルゴリズムとデータ構造の第1章の読書メモです。とても基本的な学習するうえでのモチベーションについて書いてあります。 なぜアルゴリズムとデータ構造を学ぶのか 問題分析能力向上 適切なアルゴリズムやデータ構造の選択眼を養…

アルゴリズムの勉強を始めるにあたり、定本 Cプログラマのためのアルゴリズムとデータ構造と言う本を購入しました。 渋谷のブックファーストに帰りに寄って買いました。 ストーリーがちゃんとしているので楽しく読めそうです。

アキヒトです。はじめまして。とある目標があってプログラミングを始めました。効率よく勉強したことを記憶するために、 勉強したことをブログに書くことにしました。これから少しずつアルゴリズムとデータ構造を勉強します。補足や突っ込みを気軽にお願いし…