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

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

素数の列挙

素数を列挙するプログラムを考える。
素数は2から始まり、n個まで列挙するのであれば2からn-1までで割り切れないものを見つければ可能です。
最初は効率を無視して仕組みを考えます。

list2-8

#1000以下の素数を列挙(第1版)

counter = 0 #counterの参照を0 (どれくらいの計算量になるか確認するため)

for n in range(2, 1001): #2から1001まででループ
    for i in range(2, n): #2からnまででループ
        counter += 1 #counterに１を追加して参照先を変更
        if n % i == 0: #割り切れると素数ではない
            break #それ以上の繰り返しは不要
    else: #最後まで割り切れなかったら下記を実行(elseはfor文の処理後に行われるもの。今回はbreakがあるためbreakされたらelseは処理されない)
        print(n) #割り切れなかった数字を表示 

print(f'除算を行った回数：{counter}')

2重ループを使っていますね。
気を付けたい点はelseの部分がforに対して並列になっているところでしょうか。
if文の処理は割り切れる数が出た時点で処理を終了して次のループをします。

list2-8では除算の回数が多いため計算回数を減らすプログラムを考えます。

list2-9

#1000以下の素数を列挙(第2版)

counter = 0 #除算の回数
ptr = 0 #得られた素数の個数
prime = [None] * 500 #素数を格納する配列(リストを作成)

prime[ptr] = 2 #2は素数である(リストの0番目に2を格納する)
ptr += 1 #(リストの添字を1増やすイメージ)

for n in range(3, 1001, 2): #対象は奇数のみ(3から1001までの数字を＋2ずつ繰り返す)
    for i in range(1, ptr): #既に得られた素数で割ってみる(1から添字の数だけ繰り返し処理)
        counter += 1
        if n % prime[i] == 0: #
            break
    else:
        prime[ptr] = n #素数として配列に登録
        ptr += 1
        
for i in range(ptr):
    print(prime[i])
print(f'除算を行った回数：{counter}')

更に、改良を考えます

list2-10

#1000以下の素数を列挙

counter = 0 #乗除算の回数
ptr = 0 #得られた素数の個数
prime = [None] * 500 #素数を格納する配列

prime[ptr] = 2 #2は素数である
ptr += 1 #(参照する格納先リストの添字を一つ増やす)
prime[ptr] = 3 #3は素数である
ptr += 1 #(参照する格納先リストの添字を一つ増やす)

for n in range(5, 1001, 2): #対象は奇数のみ
    i = 1 #iは1を参照する
    while prime[i] * prime[i] <= n: #prime[i]×prime[i]以下のnを検討する(Falseの時はelseに行く) 
        counter += 2#prime[i]*prime[i]とn%prime[i]の計算をカウント
        if n % prime[i] == 0: #割り切れると素数ではない
            break#それ以上の繰り返しは不要
        i += 1 #(リスト(prime)の参照する添字を1つ増やす)
    else: #最後まで割り切れなかったら
        prime[ptr] = n#素数として配列に登録
        ptr += 1 ##参照する格納先リストの添字を一つ増やす)
        counter += 1 #(whileの条件部分の計算に対するカウント)

for i in range(ptr): #求めたptr個の素数を表示
    print(prime[i])
print(f'乗除算を行った回数：{counter}')

今回はi×iがn以下の時にループするプログラムになっています。
prime[i]×prime[i]の説明として以下に記述します。

例として100の約数(i×n)で考えると
10×10以降の数字は10×10以前の約数と一致した計算になります。
つまりi×iがn以下の時に割り算をすればよいということになります。
一見するとprime[i]という表記に抵抗出てしまうのですが、一つずつ考えれば納得ですね。

コラム2-7リストの要素とコピー
ここでは、リストについての参照とコピーについて書かれています。
リストの中にリストを作成している場合、階層というものが存在するという話だと思います。

list2C-7

#リストの要素の型が揃う必要がないことを確認
x = [15, 64, 7, 3.14, [32, 55],'ABC']

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

#リストはcopyメソッドによってコピーできるがリストを要素として持つリストのコピーはうまく行えない
x = [[1, 2, 3],[4, 5, 6]]
y = x.copy() #コピーのアクセス対象が[1,2,3][4,5,6](list型オブジェクト)になっている
x[0][1] = 9
print(x)
print(y)
#シャロ―コピーが原因でyにも変更が反映される

上記の事態を避けるためには構成要素のレベルでコピーが必要でディープコピーと呼ぶ。copyモジュール内のdeepcopy関数を使用する。

変更版

import copy
x = [[1, 2, 3],[4, 5, 6]]
y = copy.deepcopy(x)#コピーのアクセス対象が1,2,3,4,5,6(int型オブジェクト)になり、リストを形成している
x[0][1] = 9
print(x)
print(y)

参照先の深さをイメージすると理解が進みそう。
シャロ―コピーでは、リストを参照している状態で、yの参照先がxのリストオブジェクト自体を参照先としているため、xを変更したときでもyはxのリストを参照してしまうため変更してしまいます。ディープコピーでは、数(int型でイミュータブルなオブジェクト)自体を参照する状態になっているため、xのリストが変更されてもyの参照先(リスト内の数)が変更することはないと考えればいいですかね。

以上で2章が終了です。ありがとうございました。