組織情報論
第
7
回 アルゴリズムとデータ構造
3
データ構造の基本と整列・探索
1
講師 佐枝三郎
https://sites.google.com/site/jiusaedasoshikiron2017/
データ構造の基本
データ構造とは
•
プログラム言語で、ソフトウェアを作成することは、
単に計算式を記述して、与えられたデータに対
する計算結果を求めるだけではない
•
コンピュータのメモリ上に、データを扱うための世
界を構築し、その中で与えられたデータを様々
に操作し、必要な結果を出すことである。
•
データ構造
(Data Structure)
は、コンピュータで計
算処理を行う際に、複数データの集まりをある形
式に整理して格納する形式
•
あるプログラムの設計の考え方（アルゴリズム）
と、関連するデータ構造の設計の考え方は密接
に関連する
3
データ構造とは
•
これらのデータ構造は、それに対応したプログラム
(
アルゴリズム
)
が
非常に高速に処理できるように設計されており、データ構造特有の
データの構築方法、取り出し方法が固有のアルゴリズムとして考案さ
れている
•
多くのプログラム言語は、特にオブジェクト指向プログラム言語には、
これらのデータ構造が言語の構成要素として準備されている
•
この講義では、
Python
に準備されたデータ構造やアルゴリズムで実
・非常に大量にあるデータから、特定の
データを取り出すこと
●具体的なデータ構造の例題
・処理したデータをある順番に従って中間
的に保管するもの
・処理したデータを操作しやすい順序で
中間的に保管するもの
●具体的なアルゴリズムの例題
・非常に大量にあるデータを、ある番号
順に並べること
配列
(Array)
スタック （
Stack)
キュー
(Queue)
整列
(Sort)
最初のデータ構造
－ 配列 －
•
配列が最初のデータ構造
•
もともとメモリが配列の形
と
なっており、プログラムが容易
なデータ構造
•
箪笥の引き出しをイメージす
れば、分かりやすい
A0001 B 0002
C C[1] 0003
C[2] 0004
C[3] 0005
C[4] 0006
C[5] 0007
C[6] 0008
C[7] 0009
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]
配列の概念
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]
オブジェクト
(定義はクラス、実態はインスタンス)
オブジェクト型データ構造
•
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
を出す
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
におけるキューの実行例
リスト
(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 オブジェクト
オブジェクトとしてリストを作る
•
リストのメソッドとして、三つの操作ができるようにする
–
データの追加
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
整列
(
ソート
)
のアルゴリズム
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
基本選択法のプログラム
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
基本交換法のプログラム
# ---
基本交換法ソート
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]を呼ぶ
クイックソートの
プログラム
# ---クイックソート
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
倍の速度で処理ができる。
ソート方法 エラプスタイム
探索
(
検索
)
のアルゴリズム
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
配列の二分探索
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 Y41
単純な文字列検索の
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
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 YBM法の名称は、アルゴリズムを開発した、
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より小さいか
単純文字列検索と
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法検索 検索対象文字列の長さ (文字)
処理時間(秒)
