sot07 最近の更新履歴 城西国際大学_経営情報学部_組織情報論2017

23 

Loading....

Loading....

Loading....

Loading....

Loading....

全文

(1)

組織情報論

7

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

3

データ構造の基本と整列・探索

1

講師 佐枝三郎

https://sites.google.com/site/jiusaedasoshikiron2017/

データ構造の基本

(2)

データ構造とは

プログラム言語で、ソフトウェアを作成することは、

単に計算式を記述して、与えられたデータに対

する計算結果を求めるだけではない

コンピュータのメモリ上に、データを扱うための世

界を構築し、その中で与えられたデータを様々

に操作し、必要な結果を出すことである。

データ構造

(Data Structure)

は、コンピュータで計

算処理を行う際に、複数データの集まりをある形

式に整理して格納する形式

あるプログラムの設計の考え方(アルゴリズム)

と、関連するデータ構造の設計の考え方は密接

に関連する

3

データ構造とは

これらのデータ構造は、それに対応したプログラム

(

アルゴリズム

)

非常に高速に処理できるように設計されており、データ構造特有の

データの構築方法、取り出し方法が固有のアルゴリズムとして考案さ

れている

多くのプログラム言語は、特にオブジェクト指向プログラム言語には、

これらのデータ構造が言語の構成要素として準備されている

この講義では、

Python

に準備されたデータ構造やアルゴリズムで実

・非常に大量にあるデータから、特定の

データを取り出すこと

●具体的なデータ構造の例題

・処理したデータをある順番に従って中間

的に保管するもの

・処理したデータを操作しやすい順序で

中間的に保管するもの

●具体的なアルゴリズムの例題

・非常に大量にあるデータを、ある番号

順に並べること

配列

(Array)

スタック (

Stack)

キュー

(Queue)

整列

(Sort)

(3)

最初のデータ構造

- 配列 -

配列が最初のデータ構造

もともとメモリが配列の形

なっており、プログラムが容易

なデータ構造

箪笥の引き出しをイメージす

れば、分かりやすい

A

0001 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] 000b

C[10] 000c

D D[1] 000d

D[2] 000e

D[3] 000f

コンピュータのメモリ 5

配列の概念

1

一般的に、配列は同じ種類の要素が並んだ集合である。

配列の要素は、同じ種類である必要はない。

数値、文字列、配列などが混ざってもよい。

論理的には、配列の要素数の上限はない。

物理的にはメモリの上限に制約される。

配列はn次元に拡張することができる。

1

次元、

2

次元、

3

次元...

1

次元配列の例

95 84 57 81 43 100

配列TEST : テストの結果データが6科目について格納されている。

TSET[1] TEST[2] TSET[3] TEST[4] TSET[5] TEST[6]

(4)

配列の概念

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

ar

=['

城西大学

', '

城西国際大学

', '

城西短期大学

']

この変数は文字列の配列になる。

配列とは、なかに順番にデータが並んでいる容器のこと。

EXCEL

の一次元の列のイメージで考えればよい。

(5)

Python

のデータ型と配列

2

なぜ、

Python

では数値も文字列も配列も一つの変数に代入

できるのか。

実は変数に代入されたのは、データ

[

数値、文字列、配列

]

指すポインター

(

そのデータの始まるアドレス

)

であるから。

1024 var

1024

12.345

2048 var

2048

城西国際大学

3096 var

3096

10024 10036 10096

10036

城西国際大学

10024

城西短期大学

10096

城西大学

数値の場合

文字列の場合

配列の場合

9

Python

の配列

1次元の配列

Python

で標準的に装備されている。

animal = [‘dog’, ‘cat’, ’tiger’, ‘lion’, ‘human’]

sosu = [1, 2, 3, 5, 7, 11, 13]

2次元の配列

配列の配列として作成はできる。

• 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]

(6)

オブジェクト

(定義はクラス、実態はインスタンス)

オブジェクト型データ構造

Python

などはオブジェクト指向言語であり、これらの言語では、

データ構造とプログラム手続きをまとめたものをオブジェクトという

すなわち、ある「データ構造」とそれを使うためのプログラム

(

アル

ゴリズム

)

がいっしょになった「かたまり」をオブジェクトである

これから説明するデータ構造の

Python

による例でも、データ構造

はオブジェクトとしてできている

基本的なデータ構造として、スタック、キュー、リストの三つを紹介

する

データ構造

(数値変数、文字変数、配列...)

メソッド

(関数、オブジェクトデータを使うプログラム)

いくつでも作れる

11

三つのオブジェクト型データ構造

スタック

(Stack)

スタックは、、データを後入れ先出し

(LIFO: Last In First Out; FILO: First

In Last Out)

の構造で保持する。スタックはコンピュータシステムやプ

ログラムで広く利用されている。

キュー

(Queue)

– キュー[待ち行列とも言う]は、データを先入れ先出し(FIFO: First In First Out) の配列で保持する。キューからデータを取り出すときは、先に入れられたデー タから順に取り出される。キューにデータを入れることをエンュー(Enqueue)、

取り出すことをデキュー(Dequeue)という。プリンタへの出力処理など、データ

を入力された順番通りに処理するときに用いられる。

リスト

(List)

– リストは一覧であり、データの一覧を作るデータ構造である。リストはデータが 一列に並んでいるように操作できる。配列も同様であるが、配列は箱の中に データが一列に並んでいると考える。リストはそれぞれのデータを独立と考え、 データの中に次のデータの場所を示す情報(ポインタという)を持ち、順番に次

(7)

スタック

(Stack)

スタックは球

(

データ

)

を底のある筒に入れるイメージのオブ

ジェクトである。

球を筒に順番に入れれば、どんどん筒の中に押し込まれる。

球を取り出したければ、当然最後に入れた球が出てくる。

最初は筒には球が入っていない状態である。

連続して球を入れれば筒の中に蓄えられ、連続して出せばい

ずれかには筒には球が入っていない状態になる。

筒の長さに上限があり、入る球の最大数が決まっていると

考えてもよい。

スタックはデータを格納するオブジェクトであるから、デー

タを格納、取り出しの操作が必要となる。これをメソッドとも

いう

スタックにデータを押し込む

例:

push[data]

スタックにからデータを取り出す

例:

a = pop[]

13

スタックのイメージ

初期状態

A

A

を入れる

A

B

B

を入れる

A

B

C

C

を入れる

A

B

C

を出す

A

B

を出す

A

を出す

(8)

Python

におけるスタックの利用法

Python

では、リストというデータ構造がスタックの機能も

持っている

Python

のリスト構造は、配列、スタック、キュー、リストそのもの

などの様々な形式での利用ができる

Python

のスタック

(

スタックの名前を

stack

とする

)

スタックへの値の格納

stack.append[

]

• Appendというメソッドは、リストの末尾に[]の中の値付け加える処理 • 数値を入れる場合は、stack.append[100]

• 文字列を入れる場合は、stack.append[‘城西国際’]

スタックの値の取り出し

x = stack.pop[]

• Pop[]とはstack[リスト構造]の末尾のデータを取り出すことを意味して

いる

• スタックの内容を代入された変数のデータ型は、スタックから取り出し

た値と同じになる

Python

におけるスタックの実行例

15

キュー

(Queue)

キューは待ち行列ともいう。

キューは右と左の両側が開いている筒のイメージである。

右側から筒に球を入れると、どんどん中に押し込まれてい

く。

筒から球を取り出す場合は、左側から中に入っている球を

取り出す。

すなわち、筒にある球の最初に入れられた球が取り出さ

れる構造である。

最初は筒には球が入っていない状態である。

連続して球を入れれば筒の中に蓄えられ、連続して出せ

ばいずれかには筒には球が入っていない状態になる。

筒の長さに上限があり、入る球の最大数が決まっていると

(9)

キューのイメージ

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

におけるキューの実行例

(10)

リスト

(List)

リスト構造は一覧形式のデータという意味である。

配列の一覧形式のデータである。

配列は箪笥のように区分けされた小さい箱が、順番に

並んでいる構造である。

リストは同じ小箱でも、一体化した箪笥ではなく、小箱

それぞれが紐でつながっている構造である。

リスト構造に対する処理は、一連の箱の頭から順番

にやるイメージとなる。

リスト構造のよいところは、紐の付け替えで順番が決

まるということであり、ある箱の削除はその箱を飛ばし

て前の箱と次の箱を結べばよいことになる。

19

リストのイメージ

6 5 4 3 2 1

1

2

3

4

5

6

(11)

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 オブジェクト

(12)

オブジェクトとしてリストを作る

リストのメソッドとして、三つの操作ができるようにする

データの追加

add(

新規データ

)

末尾にデータを付ける

データの挿入

insert(

既存データ、新規データ

)

あるデータ

の後ろに新規データを付ける

データの削除

delete(

既存データ

)

すでにあるデータを削

除する

リストオブジェクトの使用方法とプログラム例

アニメーションによるリストオブジェクトの動き

Python

による実装例

23

作成したリストの動き

[

データの追加

]

nil

nil root

nil

nil bottom

初期化状態

新井

nil

1番目のデータ

富田

nil

2番目のデータ

吉田

nil

3番目のデータ

高橋

nil

4番目のデータ 1

新井 富田

2

一番目追加 二番目追加 三番目追加 四番目追加

3

吉田

4

(13)

作成したリストの動き

[

データの削除

]

nil nil root nil nil bottom

新井

nil

1番目のデータ

富田

nil

2番目のデータ

吉田

nil

3番目のデータ

高橋

nil

4番目のデータ 1

新井 富田

2

3

吉田

4

高橋

「富田」というデータ

[Cell]

を削除する。

富田 か?

Yes

3

25

作成したリストの動き

[

データの挿入

]

nil nil root nil nil bottom

新井

nil

1番目のデータ

富田

nil

2番目のデータ

吉田

nil

3番目のデータ

高橋

nil

4番目のデータ 1

新井 富田

2

3

吉田

4

高橋

「富田」というデータ

[Cell]

の後に「佐枝」を挿入する。

富田 か?

Yes

佐枝

3

5番目のデータ

5

(14)

整列

(

ソート

)

のアルゴリズム

27

整列

(

ソート

)

とは

ソートはデータのレコードをあるキー項目の値

で、昇順あるいは降順に並べること

例えば

EXCEL

では、次ページのようなメニューに

なっている。

ソートのアルゴリズム

基本選択法: 一回ずつ最小値

(

最大値

)

を、最上位

に動かす方法

基本交換法: 一回ずつ隣り合った二つの値の大き

さを比べ、必要なら置き換える。

基本挿入法:

(15)

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

(16)

基本選択法のプログラム

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

(17)

基本交換法のプログラム

# ---

基本交換法ソート

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]を呼ぶ

(18)

クイックソートの

プログラム

# ---クイックソート

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

倍の速度で処理ができる。

ソート方法 エラプスタイム

(19)

探索

(

検索

)

のアルゴリズム

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

(20)

配列の二分探索

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:

print

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

Key[M]=学籍番号 Key[M]>学籍番号 Key[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

– 「北海道を代表する土産菓子「白い恋人」を製造・販売する石屋製菓[札幌市] は28日、吉本興業と子会社「よしもとクリエイティブ・エージェンシー」など3社に 対し、商標法と不正競争防止法に基づき、菓子「面白い恋人」の販売と包装の

使用差し止めを求める訴えを札幌地裁に起こした。」

– 検索文字列 「吉本興業」 crowds

(21)

単純な文字列検索アルゴリズム

検索対象の文字列(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を1進める

Matchをfalse

とし、while

ループを出る パタン[ip]と

文字列[it+ip]が 異なるか

yes

no

文字列とパタン を引数から取得

[文字列ーパタン]の長 さ+1だけ繰り返す

戻り値にnilを 設定

Matchをfalseに設定

Ip= 0

パタンの長さだけ 繰り返す

itを1進める

戻り値に

It[パタンの開始 位置]を設定

Matchがtrueか

yes no

(22)

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からそれぞれ 1を引く

it < 文字列の長さ

文字列[it]に対応したpTalbleの値が、 パタンの長さ-ipより小さいか

(23)

単純文字列検索と

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法検索 検索対象文字列の長さ (文字)

処理時間(秒)

Updating...

参照

Updating...

関連した話題 :