組織情報論
第7回 アルゴリズムとデータ構造 3
データ構造の基本と整列・探索
1
講師 佐枝三郎
https://sites.google.com/site/jiusaedasoshikiron2017/
データ構造の基本
2
データ構造とは
• プログラム言語で、ソフトウェアを作成することは、
単に計算式を記述して、与えられたデータに対
する計算結果を求めるだけではない
• コンピュータのメモリ上に、データを扱うための世
界を構築し、その中で与えられたデータを様々
に操作し、必要な結果を出すことである。
• データ構造(Data Structure)は、コンピュータで計
算処理を行う際に、複数データの集まりをある形
式に整理して格納する形式
• あるプログラムの設計の考え方（アルゴリズム）
と、関連するデータ構造の設計の考え方は密接
に関連する
3
データ構造とは
• これらのデータ構造は、それに対応したプログラム(アルゴリズム)が
非常に高速に処理できるように設計されており、データ構造特有の
データの構築方法、取り出し方法が固有のアルゴリズムとして考案さ
れている
• 多くのプログラム言語は、特にオブジェクト指向プログラム言語には、
これらのデータ構造が言語の構成要素として準備されている
• この講義では、Pythonに準備されたデータ構造やアルゴリズムで実
・非常に大量にあるデータから、特定の
データを取り出すこと
●具体的なデータ構造の例題
・処理したデータをある順番に従って中間
的に保管するもの
・処理したデータを操作しやすい順序で
中間的に保管するもの
●具体的なアルゴリズムの例題
・非常に大量にあるデータを、ある番号
順に並べること
配列 (Array)
スタック （Stack)
キュー (Queue)
整列 (Sort)
探索 （Search)
最初のデータ構造 － 配列 －
• 配列が最初のデータ構造
• もともとメモリが配列の形 と
なっており、プログラムが容易
なデータ構造
• 箪笥の引き出しをイメージす
れば、分かりやすい
A 0001
B 0002
C C[1] 0003
C[2] 0004
C[3] 0005
C[4] 0006
C[5] 0007
C[6] 0008
0009 C[7]
C[8] 000a
C[9] 000ｂ
C[10] 000ｃ
D D[1] 000ｄ
D[2] 000e
D[3] 000f
コンピュータのメモリ 5
配列の概念 1
• 一般的に、配列は同じ種類の要素が並んだ集合である。
• 配列の要素は、同じ種類である必要はない。
– 数値、文字列、配列などが混ざってもよい。
• 論理的には、配列の要素数の上限はない。
– 物理的にはメモリの上限に制約される。
• 配列はｎ次元に拡張することができる。
– 1次元、2次元、3次元．．．
• 1次元配列の例
95 84 57 81 43 100
配列TEST : テストの結果データが6科目について格納されている。 TSET[1] TEST[2] TSET[3] TEST[4] TSET[5] TEST[6]
6
配列の概念 2
• 多次元配列
– 配列の要素が複数あるデータ構造
– データの種類はすべて同一なものである
– 2次元ならふたつの添字[index]が必要となる
– EXCELのシートのイメージ
70 75
95 90
62 68
82 80
中間試験 期末試験
数学 国語 英語 物理
1 山田太郎
2 工藤美香
3 荒川洋介
番号 氏名 性別 年齢
男 32
女 25
男 29
• 構造体配列
– 配列の基礎的単位が、複数の異なった種類のデータで構成されている
– 同一形式の単位が、1次元または多次元配列を構成している
– リレーショナルデータベースのテーブルや、ファイルのレコードと同じ形
式
7
Pythonのデータ型と配列 1
• Pythonの変数は型はない。Pythonのデータに型がある。
• var = 12.345
数値を変数に代入するとこの変数は数値となる。
• var = '城西国際大学'
文字列を変数に代入するとこの変数は文字列になる。
• var =[10, 20, 50, 100, 200]
この変数は数値の配列になる。
• vａｒ=['城西大学', '城西国際大学', '城西短期大学']
• この変数は文字列の配列になる。
• 配列とは、なかに順番にデータが並んでいる容器のこと。
• EXCELの一次元の列のイメージで考えればよい。
Pythonのデータ型と配列 2
• なぜ、Pythonでは数値も文字列も配列も一つの変数に代入
できるのか。
• 実は変数に代入されたのは、データ[数値、文字列、配列]を
指すポインター(そのデータの始まるアドレス)であるから。
1024 var
1024 12.345
2048 var
2048
城西国際大学 3096 var
3096
10024 10036 10096
10036
城西国際大学
10024
城西短期大学 10096
城西大学
数値の場合 文字列の場合 配列の場合
9
Pythonの配列
• １次元の配列
– Pythonで標準的に装備されている。
– animal = [‘dog’, ‘cat’, ’tiger’, ‘lion’, ‘human’]
– sosu = [1, 2, 3, 5, 7, 11, 13]
• ２次元の配列
– 配列の配列として作成はできる。
• a = [1,2,3,4,5]
• b = [10,20,30,40,50]
• c = [50, 60,70,80, 90,1000]
• d = [a, b, c]
– あるいは、別に用意されたarrayオブジェクトを用いることになる
• 構造体配列
– Rubyの配列は、要素が数値、文字列、配列すべてが許される。
• a1 = [1,’dog', 20, 'cat’]
• a2 = [100,'tiger', 200, 'lion’]
• a3 = [1,'man', 20, 'woman’]
• c = [a1,a2,a3]
10
オブジェクト
(定義はクラス、実態はインスタンス)
オブジェクト型データ構造
• Pythonなどはオブジェクト指向言語であり、これらの言語では、
データ構造とプログラム手続きをまとめたものをオブジェクトという
• すなわち、ある「データ構造」とそれを使うためのプログラム(アル
ゴリズム)がいっしょになった「かたまり」をオブジェクトである
• これから説明するデータ構造のPythonによる例でも、データ構造
はオブジェクトとしてできている
• 基本的なデータ構造として、スタック、キュー、リストの三つを紹介
する
データ構造
(数値変数、文字変数、配列．．．)
メソッド
(関数、オブジェクトデータを使うプログラム)
いくつでも作れる
11
三つのオブジェクト型データ構造
• スタック(Stack)
– スタックは、、データを後入れ先出し (LIFO: Last In First Out; FILO: First
In Last Out) の構造で保持する。スタックはコンピュータシステムやプ
ログラムで広く利用されている。
• キュー(Queue)
– キュー[待ち行列とも言う]は、データを先入れ先出し (FIFO: First In First Out) の配列で保持する。キューからデータを取り出すときは、先に入れられたデー タから順に取り出される。キューにデータを入れることをエンュー (Enqueue) 、 取り出すことをデキュー (Dequeue) という。プリンタへの出力処理など、データ を入力された順番通りに処理するときに用いられる。
• リスト(List)
– リストは一覧であり、データの一覧を作るデータ構造である。リストはデータが 一列に並んでいるように操作できる。配列も同様であるが、配列は箱の中に データが一列に並んでいると考える。リストはそれぞれのデータを独立と考え、 データの中に次のデータの場所を示す情報(ポインタという)を持ち、順番に次 のデータを追いかけてデータの処理ができる。
スタック(Stack)
• スタックは球(データ)を底のある筒に入れるイメージのオブ
ジェクトである。
– 球を筒に順番に入れれば、どんどん筒の中に押し込まれる。
– 球を取り出したければ、当然最後に入れた球が出てくる。
• 最初は筒には球が入っていない状態である。
– 連続して球を入れれば筒の中に蓄えられ、連続して出せばい
ずれかには筒には球が入っていない状態になる。
• 筒の長さに上限があり、入る球の最大数が決まっていると
考えてもよい。
• スタックはデータを格納するオブジェクトであるから、デー
タを格納、取り出しの操作が必要となる。これをメソッドとも
いう
– スタックにデータを押し込む 例： push[data]
– スタックにからデータを取り出す 例： a = pop[]
13
スタックのイメージ
初期状態
A
A
を入れる
A
B
B
を入れる
A
B
C
C
を入れる
A
B
C
を出す
A
B
を出す
A
を出す
14
Pythonにおけるスタックの利用法
• Pythonでは、リストというデータ構造がスタックの機能も
持っている
– Pythonのリスト構造は、配列、スタック、キュー、リストそのもの
などの様々な形式での利用ができる
• Pythonのスタック (スタックの名前をstackとする)
– スタックへの値の格納 stack.append[値]
• Appendというメソッドは、リストの末尾に[]の中の値付け加える処理
• 数値を入れる場合は、 stack.append[100]
• 文字列を入れる場合は、 stack.append[‘城西国際’]
– スタックの値の取り出し x = stack.pop[]
• Pop[]とはstack[リスト構造]の末尾のデータを取り出すことを意味して いる
• スタックの内容を代入された変数のデータ型は、スタックから取り出し た値と同じになる
• Pythonにおけるスタックの実行例
15
キュー(Queue)
• キューは待ち行列ともいう。
• キューは右と左の両側が開いている筒のイメージである。
• 右側から筒に球を入れると、どんどん中に押し込まれてい
く。
• 筒から球を取り出す場合は、左側から中に入っている球を
取り出す。
• すなわち、筒にある球の最初に入れられた球が取り出さ
れる構造である。
• 最初は筒には球が入っていない状態である。
• 連続して球を入れれば筒の中に蓄えられ、連続して出せ
ばいずれかには筒には球が入っていない状態になる。
• 筒の長さに上限があり、入る球の最大数が決まっていると
考えてもよい。
キューのイメージ
C
A B C
B A A D B
を入れる。
A B C
を入れる。
C
B D
を入れる。
A
を出す。
A
を入れる。 初期状態
17
Pythonにおけるキューの利用法
• Pythonでは、リストというデータ構造でキューの機能も代
替できる
– Pythonのリスト構造は、配列、スタック、キュー、リストそのもの
などの様々な形式での利用ができる
• Pythonのキュー (キューの名前をqueueとする)
– キューの値の格納 queue.append[値]
• 値の格納はスタックとまったく同じ
• 数値を入れる場合は、 queue.append[100]
• 文字列を入れる場合は、 queue.append[‘城西国際’]
– キューの値の取り出し x = queue.pop[0]
• Pop[0]とはqueue[リスト構造]の最初のデータを取り出すことを意味し ている
• スタックの内容を代入された変数のデータ型は、スタックから取り出し た値と同じになる
• Pythonにおけるキューの実行例
18
リスト (List)
• リスト構造は一覧形式のデータという意味である。
• 配列の一覧形式のデータである。
• 配列は箪笥のように区分けされた小さい箱が、順番に
並んでいる構造である。
• リストは同じ小箱でも、一体化した箪笥ではなく、小箱
それぞれが紐でつながっている構造である。
• リスト構造に対する処理は、一連の箱の頭から順番
にやるイメージとなる。
• リスト構造のよいところは、紐の付け替えで順番が決
まるということであり、ある箱の削除はその箱を飛ばし
て前の箱と次の箱を結べばよいことになる。
19
リストのイメージ
6 5 4 3 2 1
1
2
3 4
5
6
配列 リスト
Pythonのリストと操作方法
• Pythonのリストは、データの集合として定義され
ている
– list = [100,200,400,300,600]
– list = [‘japan’, ‘america’, ‘england’, ‘france’]
• データの操作
– データの追加 list.append[データ]
– データの削除 list.remove[データ]
– データの挿入 list.insert[n,データ]
• nはn番目のデータの前に挿入するかの指示[最初のデータ
は0番目とする]
• Python でリストのデータ操作を行う
21
オブジェクトとしてリストを作る
• データを入れる箱をCellオブジェクトとし、データを入れる部
分と、次の箱を指し示すポインタの二つの変数を持たせる。
– Cellのクラス変数は、データを格納するdataと、次のCellを示すpointer
の二つとする。
– Cellの初期化はデータ部分を初期化時の引数からもらい、ポインタは
「None[何のないしるし]」を入れておく。
• リストのオブジェクト(クラス)を作成する。
– リストの初期化では、リストの状態を表す二つの変数を定義する。
– rootはCellオブジェクトであり、最初のデータが入ったCellの場所を示
すポインタを持っている。
– bottomもCellオブジェクトであり、最後のデータの入ったCellの場所を
示すポインタを持っている。
Data Pointer Cell オブジェクト
22
オブジェクトとしてリストを作る
• リストのメソッドとして、三つの操作ができるようにする
– データの追加 add(新規データ) 末尾にデータを付ける
– データの挿入 insert(既存データ、新規データ) あるデータ
の後ろに新規データを付ける
– データの削除 delete(既存データ) すでにあるデータを削
除する
• リストオブジェクトの使用方法とプログラム例
– アニメーションによるリストオブジェクトの動き
– Pythonによる実装例
23
作成したリストの動き [データの追加]
nil nil root
nil nil bottom
初期化状態
新井 nil
1番目のデータ
富田 nil
2番目のデータ
吉田 nil
３番目のデータ
高橋 nil
4番目のデータ 1
新井 富田
2
一番目追加 二番目追加 三番目追加 四番目追加
吉田 3
4 高橋
作成したリストの動き [データの削除]
nil nil root
nil nil bottom
新井 nil
1番目のデータ
富田 nil
2番目のデータ
吉田 nil
３番目のデータ
高橋 nil
4番目のデータ 1
新井 富田
2 吉田 3
4 高橋
「富田」というデータ[Cell]を削除する。
富田 か？
Yes
3
25
作成したリストの動き [データの挿入]
nil nil root
nil nil bottom
新井 nil
1番目のデータ
富田 nil
2番目のデータ
吉田 nil
３番目のデータ
高橋 nil
4番目のデータ 1
新井 富田
2 吉田 3
4 高橋
「富田」というデータ[Cell]の後に「佐枝」を挿入する。
富田 か？
Yes
佐枝 3
5番目のデータ 5
26
整列(ソート)のアルゴリズム
27
整列(ソート)とは
• ソートはデータのレコードをあるキー項目の値
で、昇順あるいは降順に並べること
• 例えばEXCELでは、次ページのようなメニューに
なっている。
• ソートのアルゴリズム
– 基本選択法： 一回ずつ最小値(最大値)を、最上位
に動かす方法
– 基本交換法： 一回ずつ隣り合った二つの値の大き
さを比べ、必要なら置き換える。
– 基本挿入法：
– クイックソートなど
EXCELのソート指定例
29
基本選択法のPAD図
開始
終了 N ← 配列数 i = 0
data[i]と data[j] を取り換える data[i] >=
data[j] Yes
No while i < N
No 名前 住所 510 山田 ・・・・ 210 新井 ・・・・ 102 西田 ・・・・ 530 角田 ・・・・ 240 高橋 ・・・・ 810 松山 ・・・・ 463 飯山 ・・・・ 264 内田 ・・・・ 290 永井 ・・・・ 893 藤田 ・・・・ 157 斉藤 ・・・・ 035 横田 ・・・・
while j < N j = i
i = i + 1 j = j + 1
30
基本選択法のプログラム
def selectSort[self,n, data]:
i=0
while i < n:
j=i
while j < n:
if data[j] < data[i]:
w=data[j]
data[j]=data[i]
data[i]= w
j +=1
i+=1
data： ソート対象の配列
n： 配列の最大値
31
基本交換法のPAD図
開始
終了
N ← 配列数 i = 0
data[j]と data[j+1] を取り換える data[j] <=
data[j+1] Yes
No while i < N
No 名前 住所 510 山田 ・・・・ 210 新井 ・・・・ 102 西田 ・・・・ 530 角田 ・・・・ 240 高橋 ・・・・ 810 松山 ・・・・ 463 飯山 ・・・・ 264 内田 ・・・・ 290 永井 ・・・・ 893 藤田 ・・・・ 157 斉藤 ・・・・ 035 横田 ・・・・
while j < N - i j = 0
i = i + 1 j = j + 1
基本交換法のプログラム
# --- 基本交換法ソート
def bubbleSort[self,n, data]:
i=0
while i < n:
j=0
while j < n - i - 1:
if data[j] > data[j+1] :
w=data[j]
data[j]=data[j+1]
data[j+1]= w
j +=1
i += 1
data： ソート対象の配列
n： 配列の最大値
33クイックソートのPAD図
開始
終了 データの配列と
bottom, topを引数から取得
bottom >= top
Yes
While l <= h かつ data[l] <= div
No 名前 住所 510 山田 ・・・・ 210 新井 ・・・・ 102 西田 ・・・・ 530 角田 ・・・・ 240 高橋 ・・・・ 810 松山 ・・・・ 463 飯山 ・・・・ 264 内田 ・・・・ 290 永井 ・・・・ 893 藤田 ・・・・ 157 斉藤 ・・・・ 035 横田 ・・・・
while l > h l = l + 1
divにdata[bottom]を設定 l = bottom
h = top
return [戻る]
While l <= h かつ data[h] > div h = h + 1
l < h
data[l]とdata[h]を取り Yes 換える
data[h]とdata[bottom]を 取り換える
Bottomとh-1を引数に設定し て、自分[qsort]を呼ぶ h+1とtopを引数に設定し
て、自分[qsort]を呼ぶ
34
クイックソートの
プログラム
# --- クイックソート
def quickSort[self, bottom, top, data ]: l = bottom
h = top
if bottom >= top: return div = data[bottom] while l < h:
while l <= h and data[l] <= div : l += 1
while l <= h and data[h] > div : h -= 1
if l < h:
temp = data[l] data[l] = data[l] data[l] = data[h] data[h] = temp temp = data[bottom] data[bottom] = data[h] data[h] = temp
self.quickSort[bottom, h - 1, data] self.quickSort[h + 1, top,data]
data： ソート対象の配列
bottom： 処理対象の最小値
top： 処理対象の最大値
35
3 種類のソート方法の処理時間計測
• 0から1000までの範囲の整数を、乱数で1000件作成し、
配列に蓄える。
• これまでに紹介した3種類のソート方法で処理を行い、
処理時間を計測する。
• クイックソートは、他の基本的な方法に比べて、30-40
倍の速度で処理ができる。
ソート方法 エラプスタイム
基本選択法 94.75ミリセック
基本交換法 137.03ミリセック
クイックソート 3.81ミリセック
探索(検索)のアルゴリズム
37
配列の二分探索
• キーとデータの組み合わせの配列があり、そこから探索するキー
に対応するデータを取り出す。
• 例えば学籍番号と氏名、住所、電話番号の列がN個である表が
ある。
• キーは降順(一番上が最小)に並んでいるものとする。
• この探索の方針は、対象のキーと比較する場所を、まず全体の
真ん中、次はあるはずの半分の配列の真ん中．．．．と範囲を狭
めていく考え方である。
学籍番号(Key) 氏名 (Name) 電話番号 (Tel) BG2017-001 山田太郎 043-23-1240 BG2017-040 西田勉 043-23-4430 BG2017-080 今田聡 043-23-5362 BG2017-090 上杉幹夫 043-23-3241 BG2017-310 木村俊樹 043-23-4701
BG2017-410 新藤進 043-23-5288 38
配列の二分探索 PAD
開始
終了 while L < H 学籍番号を
入力
L ← 1
H ← 配列の最大値
# self.key, self.name, self.tel は
# クラス変数として設定済み def byseach(number, N)
low = 1 high = N
while low < high:
m = int((low + high) /2) if self.key[m] == number:
self.name[m],self.tel[m] return
elif self.key[m] > number: low = m + 1
else:
high = m – 1
print “This key is not found”
・Key[i]に対する 氏名、電話番号 Name[i],Tel[i] を出力 配列にはないこと ・終了
を出力
M ← (L+H)/2
Ｋey[M]=学籍番号 Ｋey[M]>学籍番号 Ｋey[M]<学籍番号
H ← M - 1 L ← M + 1
39
文字列検索のアルゴリズム
• 文字列の検索は、長い文章の中に、ある短文や単語が存在す
るか、ある場合は、どの位置にあるかを探索することである。
• 例1：
– 「Unexpectedly large crowds of voters turned out on Monday to cast their votes in Egypt’s first parliamentary election since the ouster of President Hosni
Mubarak, a ballot that seemed to blend vindication of the democratic struggle with uncertainty over the revolution’s final outcome.」
– 検索文字列 「crowds」
• 例2：
– 「北海道を代表する土産菓子「白い恋人」を製造・販売する石屋製菓[札幌市] は２８日、吉本興業と子会社「よしもとクリエイティブ・エージェンシー」など３社に 対し、商標法と不正競争防止法に基づき、菓子「面白い恋人」の販売と包装の 使用差し止めを求める訴えを札幌地裁に起こした。」
– 検索文字列 「吉本興業」 crowds
吉本興業 吉本興業 吉本興業 吉本興業
単純な文字列検索アルゴリズム
検索対象の文字列 (Text)
検索する文字列 (Pattern)
A B C D E F A B B Y G H I J K L M
A B B Y A B B Y
検索文字列発見
検索文字列発見 検索文字列発見
検索文字列発見
位置は 位置は 位置は
位置は7文字目から 文字目から 文字目から 文字目から
A AB ABB BABY BBAY BBAY YBB YB Y
41
単純な文字列検索のPAD図
開始
終了 It = 0
Matchをtrueとし、 ipを１進める
Matchをfalse とし、while ループを出る パタン[ip]と
文字列[it+ip]が 異なるか
yes
no 文字列とパタン
を引数から取得
[文字列ーパタン]の長 さ＋１だけ繰り返す
戻り値にnilを 設定
Matchをfalseに設定 Ip= 0
パタンの長さだけ 繰り返す
iｔを１進める
戻り値に It[パタンの開始 位置]を設定 Matchがtrueか
yes no
42
BM 法による文字列検索アルゴリズム
検索対象の文字列 (Text)
検索する文字列 (Pattern)
A B C D E F A B B Y G H I J K L M
A B B Y A B B Y
検索文字列発見
検索文字列発見 検索文字列発見
検索文字列発見
位置は 位置は 位置は
位置は7文字目から 文字目から 文字目から 文字目から
A BA BBA YBB YB Y
BM法の名称は、アルゴリズムを開発した、 BoyerとMooreの頭文字を取ったものである
43
BM法による文字列検索のPAD図
開始
終了
文字の種類分、配列pTable[ ]を取得 し、すべてにパタンの長さを設定
itに文字列[it]に対応した pTalbleの値を加える。 文字列とパタン
を引数から取得
パタンの長さだけ繰り返す
ipにパターンの 長さ-1を設定
pTable[ ]のパタンに現れる文字の位置 に、パタン上のその文字から最後まで の長さを設定
一致
it+1を戻り値に返す ip == 0
yes
文字列[it]とパタン[ip]が 一致する間
it にパタンの長さ-1を設定
itとipからそれぞれ １を引く
it < 文字列の長さ
文字列[it]に対応したpTalbleの値が、 パタンの長さ-ipより小さいか
発見できないので戻り値 にnilを設定する
単純文字列検索とBM法文字列検索
の比較
• 単純文字列検索は事前処理がないため、短い文章の検索では処理速
度が速い。しかし、毎回1文字づつ移動して調べるので、長い文章では
非常に遅くなる。
• BM法検索では、反対に事前処理のオーバーヘッドがあるため、ある程
度以上の長さの文章の場合、圧倒的に処理速度が速くなる。
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9
0 500 1000 1500 2000 2500
単純検索 BM法検索 検索対象文字列の長さ(文字)
処理時間(秒)
45
