LoginSignup
19
21

More than 5 years have passed since last update.

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

Last updated at Posted at 2015-08-11

ざっくり言うと

プログラムを書く上でデータ構造の理解と、
それの扱い方(操作と走査の方法)を覚えることは
とても重要です。

データ構造とは

大きく分けると、配列とハッシュの2つ
配列とハッシュには特性によっていくつかに分けられる。
Javaで言うと、配列、リスト、Mapにあたる。
Rubyでは配列とハッシュ。
PHPでは連想配列。
各言語により実装が異なる為、
それぞれ自分の扱う言語ではどのようなデータ構造があるかを理解する必要があります。

Rubyの例

Array

# 定義
a = []

# 走査
a.each do |b|
  puts b
end

# 追加
a[0] = 'a'
a << = 'a'

Hash

# 定義
a = {}

# 走査
a.each do |key,value|
  puts value
end

# 追加
a[:key] = 'a'

PHPの例

連想配列

// 定義
$array = array();
$array = array(
    'key' => 'hoge'
);

// 追加
array_push($array, 'hoge');
$array['key'] = 'hoge';

// 走査
foreach(array as $key => $value) {
    var_dump($value);
}

扱い方はシンプル

シンプルに扱えるようにデータの格納も工夫が必要です。

極端な例

fruit = {
  :name => [
    'apple',
    'orange',
    'banana',
  ],
  :price => [
    100,
    200,
    300,
  ],
  :zaiko => [
    5,
    5,
    10,
  ]
}

fruit[:name].count.times do |i|
  p (fruit[:name][i] + 'の値段は' + fruit[:price][i].to_s +  ' 在庫は' + fruit[:zaiko][i].to_s)
end
"appleの値段は100 在庫は5"
"orangeの値段は200 在庫は5"
"bananaの値段は300 在庫は10"

微妙・・・。
以下の方がシンプル(個人的な感想です。)

fruit = [
  {
    :name => 'apple',
    :price => 100,
    :zaiko => 5,
  },
  {
    :name => 'orange',
    :price => 200,
    :zaiko => 5,
  },
  {
    :name => 'banana',
    :price => 300,
    :zaiko => 10,
  }, 
]

fruit.each do |f|
  p (f[:name] + 'の値段は' + f[:price].to_s + ' 在庫は' + f[:zaiko].to_s)
end
"appleの値段は100 在庫は5"
"orangeの値段は200 在庫は5"
"bananaの値段は300 在庫は10"

データの持ち方により、
ロジックが行うことが多くなる。
ロジックが多くなればコード量が増え、
バグが潜む可能性も上がり、
可読性は下がります。

データ構造とアルゴリズムが重要な極端な例

外部リンク(霧島)

上記問題はデータ数がべらぼうに多い為、
データの持ち方とアルゴリズムをしっかり考えないと
計算が終わるのを待てないプログラムになります。

実際プログラムを(仕事上)書く上で
上記の問題のように計算量が多いことはあまりないと思いますが、
プログラムの実行にかかる時間はチリツモの為、
データ量が少なくても普段からデータの持ち方とアルゴリズムを考えて
書くことは重要です。
日々データ量が増えるようなシステムであれば、
いつか寿命が来て、性能改善に追われることになるでしょう。

データ構造、アルゴリズムの知識がない場合の弊害

また、これらデータの持ち方やアルゴリズムを即時に考えられない場合の弊害は以下が考えられます。

  • 単純にコーディングが出来ない。
    • 書くのが遅い。その上、バグっている。
  • 見積もりミス
    • 見積もり段階で脳内でどこまで落とし込めるかは見積もりの精度に関わってきます。(見積もりにはWebや業務知識も必要な為、これだけあればいいわけではありません。)
  • 管理サイドからのサポート
    • 実際に自分で手を動かさない場合のサポートは脳内で設計ができていないと出来ません。
    • 手を動かして、一緒に考える。そんな時間はありません。

練習をしましょう。

データの設計、データ走査、アルゴリズムは反復練習だと思います。
外部リンク(えん修羅)
上記問題は、ジョジョにレベルが上がっていくため取り込みやすいかと思います。

競技プログラミング系の問題を解くのは非常にいい練習になると思います。
外部リンク(paiza)

外部リンク(霧島)
こちらの例は、以下のアルゴリズムで解く事ができます。
外部リンク(ナップサック問題)
アルゴリズムがわかってもそれを自分の言語で実装ができなければ解けない為、
データ構造の操作のよい練習になるかと思います。

※ paizaと私は全くの無関係であることをここに記載しておきます。

19
21
1

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
19
21