「新・明解Pythonで学ぶアルゴリズムとデータ構造」で勉強日記#6

【出典】「新・明解Pythonで学ぶアルゴリズムとデータ構造」
前回の記事はこちら

2-2配列

いよいよリストやらタプルやらの使い方がわかりそうな予感がします。
今まで、どうやって活用すればいいのかわかっていなかったので楽しみです。

配列の要素の最大値を求める

最初に、配列の要素の最大値を求める手続きを考えるようです。
配列aの要素が4個として、三つの要素a[0], a[1], a[2], a[3]の最大値を、以下のプログラムで求めます。

a = [22, 57, 11, 91]
maximum = a[0]
if a[1] > maximum: maximum = a[1]
if a[2] > maximum: maximum = a[2] #要素数が3であればif文を2回実行
if a[3] > maximum: maximum = a[3] #要素数が4であればif文を3回実行

maximum

まず、配列の要素数とは無関係に、先頭要素a[0]の値をmaximumに代入する作業を行い、その後if文を実行する過程で必要に応じてmaximumの値を更新します。
要素数がnであれば、if文の実行は、n-1回必要で、その際、maximumとの比較やmaximumへの代入の対象となる添字（インデックスのことで、以後統一）は、1,2,・・・と増えていきます。
そのため、配列aの要素の最大値を求めるアルゴリズムのフローチャートは次のようになります。

このアルゴリズムに基づいて、配列aの要素の最大値を求める関数の関数定義と、その関数によって最大値を求める様子を配列の要素数が5としたとき

def max_of(a):
    maximum = a[0]
    for i in range(1, len(a)):
        if a[i] > maxmum:
            maximum = a[i]

という関数を定義し、最大値を求めることができます。

仮に[22, 57, 11, 91, 32]という配列があったとき
22>57 → 57
57>11 → 57
57>91 → 91
91>32 → 91
となことがわかります。
リストの表記（s[]←こういうやつ）に慣れが必要だなと感じますが、今回の記事を通して、少しでも慣れることがで切ればいいなと思います。（記号が多いと頭の整理が必要ですよね。）
（余談ですが本書の流れに沿ている都合で関数定義をしています。）

配列の要素の最大値を求める関数の実装

関数の”実装”というとなんか難しい感じがしますが、関数を定義して使うという解釈でいいのかな？

list2-2

#シーケンスの要素の最大値を表示する
from typing import Any,Sequence

#max_ofの定義
def max_of(a: Sequence) -> Any:
    '''シーケンスaの要素の最大値を表示する'''
    maximum = a[0]
    for i in range(1, len(a)):
        if a[i] > maximum:
            maximum = a[i]
    return maximum

#関数max_ofをテストする

if __name__ == '__main__':
    print('配列の最大値を求めます。')
    num = int(input('要素数：'))
    x = [None] * num #要素数numのリストを生成
    
    for i in range(num):
        x[i] = int(input(f'x[{i}]:'))
        
    print(f'最大値は{max_of(x)}です。')

急に複雑になるやつ…。とりあえず定義のところは分かりますが、急に->みたいな記号使われると頭がパニックです。
意味としてはaのシークエンスの型はなんでも対応します的なニュアンスでいいですかね？
ということで次で解説してくれています。

#アノテーションと型ヒント
まずは、プログラムの先頭行
from typing import Any,Sequence
に着目します。

このインポートによって、AnyとSequenceが単純名で利用できるようになるそうです。
Anyは制約のない(任意の)型であることを表し、Squenceはシーケンス型を表します。
シーケンス型にはlist型,bytearray型,str型,tupple型,bytes型がある(つまり連続的なイメージでいいですか？)ため、関数max_ofの関数頭部のアノテーション(特定のデータに対して情報タグ(メタデータ)を付加することらしい【出典】デジタル大辞泉)は次の表明を行うことになります。
・受け取る仮引数aの型として、シーケンス型であることを期待する。
・返却するのは任意の型である。
以上より関数max_ofは次のような特性を持ちます。
・関数内では、配列aの要素の値は変更しない。
・呼び出し側が与える実引数の型は、変更可能なリスト、変更不能なタプルや文字列など、シーケンスであれば何でもよい。
・呼び出し側が与えるシーケンスの要素としては、値比較演算子＞で比較可能でさえあれば、異なる型（int型float型）が混在してもよい。
・最大の値の要素を返却する（最大の値の要素がint型の要素であればint型の値を返却し、float型の要素であればfloat型を返却する。）
なお、関数内で要素の値を変更する配列型の仮引数に対するアノテーションは、Sequenceではなく、MutableSequenceとしなければならない。
※その場合、実引数として、ミュータブルリストは与えられるが、イミュータブルな文字列型、タプル型、バイト列型の実引数は与えられなくなる。
文字ばかりでわかりづらいですが、つまるところいろんな型に対応できますよということですかね？

再利用可能なモジュールの構築

pythonでは単一のスクリプトプログラムがモジュールとなります。
拡張子.pyを含まないファイル名がそのままモジュール名となるため、本プログラムのモジュール名はmaxになります。

これ、関数の勉強してたときなんかに既成ファイルから引っ張れるぜってところまでは知っていたのですが、自分で作れるんだあと思って夢が広がりました。
じゃあライブラリとかも最初に作った人がいてくれたおかげで楽な記述ができるんだと思うと頭が上がらないですね。（ほかの言語とかもやっぱりそういうのあるのかな？）

さて、本プログラム後半のif文では__name__と'__main__'の等価性が判定されています。
左オペランドの__name__はモジュールの名前を表す変数であり、次のように決定されます。

スクリプトプログラムが：
・直接実行されたとき　変数__name__は'__main__'
・インポートされたとき 変数__name__は本来のモジュール名（今回の場合はmax）

pythonはすべてをオブジェクトとみなすため、モジュールもオブジェクトとなります。(初耳ですわ)
モジュールは、別のプログラムから初めてインポートされたタイミングで、そのモジュールオブジェクトが生成・初期化される仕組みになっています。
そのため、プログラム後半のif文の判定は、'max.py'を直接起動したときのみ真とみなされif __name__ == '__main__':以下のコードが実行されるそうです。つまりほかのファイルから読み込んだときは動かないということですね。(実装イメージがまだできないけど)
ほかのスクリプトプログラムからインポートされたときは偽とみなされるためif __name__ == '__main__':以下は実行されない。
※モジュールオブジェクトの中には、__name__のほかにも、__loader__、___package__、__spec__、__path__、__file__などの変数(属性)が入っている。

急に出てきて！？ってなりますが、ちゃんと抑えれば怖くないですね。とりあえず便利な機能程度に今は覚えておきます…。()

モジュールのテスト

list2-2のモジュール'max'で定義された関数'max_of'をほかのスクリプトプログラムから呼び出してみる。
値の読み込み時に要素数を決定する
list2-3はキーボードからint型の整数値を次々と読み込んでいき、終了が指示されたら('End'と入力されたら)読み込みを終了する(その時点で要素数が確定する)ように実現したプログラムです。
※本プログラムを含め、関数'max_of'を呼び出すプログラムは、'max.py'と同一フォルダに格納する必要がある。

list2-3

#max_of_test.py

#配列の要素の最大値を求めて表示(要素の値を読み込む)

from max import max_of

print('配列の最大値を求めます。')
print('注："End"で入力終了。')
      
number = 0
x = [] #空リスト

while True:
      s = input(f'x[{number}]:')
      if s == 'End':
          break
      x.append(int(s)) #末尾に追加
      number += 1

print(f'{number}個読み込みました。')
print(f'最大値は{max_of(x)}です。')

'from max import max_of'はモジュールmaxで定義されている'max_of'を単純名で利用できるようにするためのimport文。
プログラムでは、まず最初にリストxを、空の配列(空リスト)として生成しています。
while文は無限ループであり、次々と文字列を読み込む。読み込んだ文字列がEndであれば、break文の働きによってwhile文を強制終了する。
読み込んだ文字列sが'End'出ない場合は読み込んだ(文字列sをint関数によって変換した)整数値を、配列xの末尾に追加する。
変数numberは0で初期化され、整数値を読み込むたびにインクリメントされるため、読み込んだ整数値の個数(配列xの要素数と一致する)が保持される。
※インポートするモジュール'max.py'の'max_of'以外は__name__ == '__main__'が成立しないためif __name__ == '__main__':以下の文は実行されない。(アンダーバーが消えてるので注意。出し方わからんです。)

配列の要素の値を乱数で決定する

配列の要素はキーボードから読み込み、全要素の値は乱数で決定する。

list2-4

#配列の要素の最大値を求めて表示(要素の値を乱数で生成)

import random
from max import max_of

print('乱数の最大値を求める')
num = int(input('乱数の個数：'))
lo = int(input('乱数の下限：'))
hi = int(input('乱数の上限：'))
x = [None] * num #要素数numのリストを生成

for i in range(num):
    x[i] = random.randint(lo, hi)
    
print(f'{(x)}')
print(f'最大値は{max_of(x)}です。')

ここで、「おー」と思ったのは空リストの生成ですね。Noneとかなかなかうまく使えないので、こういう例があると助かります。

タプルの最大値/文字列の最大値/文字列のリストの最大値を求める

list2-5はタプルの最大値、文字列(内の文字)の最大値/文字列のリストの最大値を求めるプログラム

list2-5

#配列の要素の最大値を求めて表示(タプル/文字列/文字列のリスト)

from max import max_of

t = (4, 7, 5.6, 2, 3.14, 1)
s = 'string'
a = ['DTS', 'AAC', 'FLAC']

print(f'{t}の最大値は{max_of(t)}です。')#7
print(f'{s}の最大値は{max_of(s)}です。')#t
print(f'{a}の最大値は{max_of(a)}です。')#FLAC

文字列のみの場合は文字コード、文字列リストの場合は文字列の数で判定される…。なんか面白いことできそうな…。？？

list2-5(max/min)

#配列の要素の最大値を求めて表示(タプル/文字列/文字列のリスト)max,min関数を使用

t = (4, 7, 5.6, 2, 3.14, 1)
s = 'string'
a = ['DTS', 'AAC', 'FLAC']

#最大値
print(f'{t}の最大値は{max(t)}です。')#7
print(f'{s}の最大値は{max(s)}です。')#t
print(f'{a}の最大値は{max(a)}です。')#FLAC
#最小値
print(f'{t}の最小値は{min(t)}です。')#1
print(f'{s}の最小値は{min(s)}です。')#g
print(f'{a}の最小値は{min(a)}です。')#AAC(文字列の数、文字コードの順で検索される)

コラム2-3 リストとタプル(その２)

前回出てきたコラムの続きですね。

別々に生成されたリスト/タプルの同一性

別々に生成されたリストはすべての要素が同じ値をもっていても、別の実体を持つ。

list1 = [1,1,1]
list2 = [1,1,1]
print(list1 is list2)
print(list1 is list1)

[1,1,1]は[]演算子によって新しいリストを生成する式であり、いわゆるリテラル(直接記述される数値や文字列)ではない。

つまり、式であることを認識できていれば大丈夫ですかね。なんか前にちらっと触れていた気もしますが忘れたのでまた復習します。

リスト/タプルの代入

リスト（を参照している変数）を代入しても、値でなく参照がコピーされるため、要素自体（要素の並び）はコピーされない。

参照の確認

lst1 = [1,1,1]
lst2 = lst1
print(lst1 is lst2)

lst1[2] = 9
print(lst1)
print(lst2)#lst1を参照している。

is関数なんてあるんですね。
Excelなんかでも真偽判定の重要性は思い知ったので、こういう使い方できる情報はありがたいです。

リストの走査
リストを走査する4種類のプログラムを下記に示してます。

list2C-1

#リストの全要素を走査（要素数を事前に取得）
x = ['john', 'geoge', 'paul', 'ringo']#[]を()にするとタプルになる

for i in range(len(x)):
    print(f'x[{i}] = {x[i]}')
print('_'*13)

list2C-2

#リストの全要素をenumerate関数で走査
x = ['john', 'geoge', 'paul', 'ringo']

for i,name in enumerate(x):
    print(f'x[{i}] = {name}')
print('_'*13)    

i, nameを使うことで、enumerate関数を使って同じ出力ができます。

list2C-3

#リストの全要素をenumerate関数で走査(1からカウント)
x = ['john', 'geoge', 'paul', 'ringo']

for i,name in enumerate(x, 1):
    print(f'{i}番目 = {name}')
print('_'*13)    

enumerate(x, 1)とすることで、カウントの開始を1にします。(0～3が1～4に代わる)

list2C-4

#リストの全要素を走査(インデックス値を使わない)

x = ['john', 'geoge', 'paul', 'ringo']

for i in x:
    print(i)

また、インデックスの値が不要な場合は簡素に書くこともできます。

・イテラブル
文字列、リスト、タプル、集合、辞書などの型をもつオブジェクトは、いずれもイテラブル＝反復可能である'という共通点があります。
イテラブルオブジェクト（リストなど）を組み込み関数であるiter関数に引数として与えるとそのオブジェクトに対するイテレータが返却されるそうです。
イテレータ：データの並びを表現するオブジェクト。
イテレータの__next__メソッドを呼び出すか、組み込み関数であるnext関数にイテレータを与えるとその並びの要素が順次取り出される。取り出すべき要素が尽きた場合はStopIteration例外が送出されるとのこと。

iter/next関数の例

x = ['john', 'geoge', 'paul', 'ringo']

t = iter(x)
while True: #Trueの間繰り返す
    try: #例外処理(例外が発生したときに処理する)
        print(next(t))
    except StopIteration: #except エラー名
        break #StopIterationが出たらループ終了

エラーが出たときに処理が行われるという。便利そうなやつですね。

今回は以上です。ありがとうございました。