Pythonの不思議2（素数を数えて落ち着く）


# Pythonの不思議2（素数を数えて落ち着く）

今日もPython日和ですね。Pythonの世界をさまよいます。

- イテレータがやけに便利
- for、while、tryにelse節がある
- リストの先頭要素に対する追加・削除処理が遅い


## イテレータがやけに便利

以下記事を目にしたので、Pythonでやってみました。お題は「1から100未満の素数とその和をfor文を使わず求める」です。

- [なぜfor文は禁止なのか？関数型記述のススメ](https://qiita.com/ukiuni@github/items/abad07524856c65a20ea)
- [Swiftでfor文を使わないで書く](https://qiita.com/gawawa124/items/47e0fa19e8df8bdee930#_reference-e12c1f5ea2bb802587f9)
- [【swift】 1から100未満の素数の和をforを使わずに求める。](https://qiita.com/BMJr/items/92acef984200c116fc9c)

最初の100個の素数についても求めてみたいと思います。また、フィボナッチ数についても求めます。

for文を使わないという制約ですが、Pythonには、**イテレータ**という、やけに便利な道具があるので、これを利用します。

### 説明

イテレータとはデータのストリームを表現するオブジェクトのことで、繰り返しの機構を隠蔽します。自作のクラスをイテレータ化する方法は、[Python チュートリアル／9.8. イテレータ (iterator)](https://docs.python.jp/3/tutorial/classes.html#iterators)に記載があります。以下に転載する記載では、for文と組み合わせる例を挙げていますが、イテレータは様々な関数と組み合わせて利用することができます。

>イテレータの活用は Python へ広く行き渡り、統一感を持たせています。裏では for 文はコンテナオブジェクトに対して iter() 関数を呼んでいます。関数は、コンテナの中の要素に1つずつアクセスする \_\_next\_\_() メソッドが定義されているイテレータオブジェクトを返します。これ以上要素が無い場合は、 \_\_next\_\_() メソッドは StopIteration 例外を送出し、その通知を受け for ループは終了します。組み込みの next() 関数を使って \_\_next\_\_() メソッドを直接呼ぶこともできます; この例は関数がどう働くのかを示しています:
>
>イテレータプロトコルの裏にある仕組みを観察していれば、自作のクラスにイテレータとしての振舞いを追加するのは簡単です。 \_\_next\_\_() メソッドを持つオブジェクトを返す \_\_iter\_\_() メソッドを定義するのです。クラスが \_\_next\_\_() メソッドを定義している場合、 \_\_iter\_\_() メソッドは単に self を返すことも可能です:

重要なのは、イテレータを利用することで、制御（1から100未満とか、最初の100個とか）とデータ（素数とか、フィボナッチ数とか）を分けて定義できるところです。

### 素数

まずは、素数です。


```python
import itertools as it

class Primes:
    def __init__(self):
        self.primes = it.count(2)
    
    def __iter__(self):
        return self
    
    def __next__(self):
        p = next(self.primes)
        # 素数の倍数を取り除く
        self.primes = filter(lambda x: x % p != 0, self.primes)
        return p

# 1から100未満の素数とその和
print(list(it.takewhile(lambda x: x < 100, Primes())))
print(sum(it.takewhile(lambda x: x < 100, Primes())))

# 最初の100個の素数とその和
print(list(it.islice(Primes(), 100)))
print(sum(it.islice(Primes(), 100)))
```

    [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
    1060
    [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541]
    24133


制御が「1から100未満」であっても、「最初の100個」であっても、データ（Primes）の定義が全く変わらないところがミソです。

### フィボナッチ数

次に、フィボナッチ数です。


```python
import itertools as it

class Fibonacci:
    def __init__(self):
        self.a = 0
        self.b = 1
    
    def __iter__(self):
        return self
    
    def __next__(self):
        self.a, self.b = self.b, self.a + self.b
        return self.a

# 1から100未満のフィボナッチ数とその和
print(list(it.takewhile(lambda x: x < 100, Fibonacci())))
print(sum(it.takewhile(lambda x: x < 100, Fibonacci())))

# 最初の100個のフィボナッチ数とその和
print(list(it.islice(Fibonacci(), 100)))
print(sum(it.islice(Fibonacci(), 100)))
```

    [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]
    232
    [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976, 7778742049, 12586269025, 20365011074, 32951280099, 53316291173, 86267571272, 139583862445, 225851433717, 365435296162, 591286729879, 956722026041, 1548008755920, 2504730781961, 4052739537881, 6557470319842, 10610209857723, 17167680177565, 27777890035288, 44945570212853, 72723460248141, 117669030460994, 190392490709135, 308061521170129, 498454011879264, 806515533049393, 1304969544928657, 2111485077978050, 3416454622906707, 5527939700884757, 8944394323791464, 14472334024676221, 23416728348467685, 37889062373143906, 61305790721611591, 99194853094755497, 160500643816367088, 259695496911122585, 420196140727489673, 679891637638612258, 1100087778366101931, 1779979416004714189, 2880067194370816120, 4660046610375530309, 7540113804746346429, 12200160415121876738, 19740274219868223167, 31940434634990099905, 51680708854858323072, 83621143489848422977, 135301852344706746049, 218922995834555169026, 354224848179261915075]
    927372692193078999175


素数の場合と全く同じ枠組みで書けました。この便利さは不思議ですが、はかどりますね！

## for、while、tryにelse節がある

for、while、tryにelse節を定義できるのは、Pythonの特徴の一つだと思います。

### for

forについては、全要素を必ず処理する場合と、そうでなくて途中でbreakする場合があるかと思います。後者の場合、breakしなかったときの処理をelse節に書けるのが、地味に役に立ちます。

以下、[Python チュートリアル／4.4. break 文と continue 文とループの else 節](https://docs.python.jp/3/tutorial/controlflow.html#break-and-continue-statements-and-else-clauses-on-loops)に挙げられている例です。偶然にも、また素数の例が出てきました。[素数を数えて落ち着きましょう！](https://dic.pixiv.net/a/%E3%82%A8%E3%83%B3%E3%83%AA%E3%82%B3%E3%83%BB%E3%83%97%E3%83%83%E3%83%81)


```python
for n in range(2, 10):
    for x in range(2, n):
        if n % x == 0:
            print(n, 'equals', x, '*', n//x)
            break
    else:
        # loop fell through without finding a factor
        print(n, 'is a prime number')
```

    2 is a prime number
    3 is a prime number
    4 equals 2 * 2
    5 is a prime number
    6 equals 2 * 3
    7 is a prime number
    8 equals 2 * 4
    9 equals 3 * 3


上のコードは、下のコードと等価です。flgなんか使わなくて済むので、else節を使いましょう。


```python
for n in range(2, 10):
    flg = 0
    for x in range(2, n):
        if n % x == 0:
            print(n, 'equals', x, '*', n//x)
            flg = 1
            break
    if flg == 0:
        print(n, 'is a prime number')
```

    2 is a prime number
    3 is a prime number
    4 equals 2 * 2
    5 is a prime number
    6 equals 2 * 3
    7 is a prime number
    8 equals 2 * 4
    9 equals 3 * 3


## while

whileでも、breakしなかったときの処理をelse節に書けます。以下のように、else節を使うことで、論理的に一つの固まりであることが強調されますので、else節を使うのが良いかと思います。


```python
file = './data/lorem_ipsum.txt'
with open(file) as f:
    line = f.readline()
    while line:
        print(line)
        if ('Duiss' in line):
            print('見つかった：' + line)
            break
        line = f.readline()
    else:
        print('見つからなかった')
```

    Lorem ipsum dolor sit amet,
    
    consectetur adipiscing elit,
    
    sed do eiusmod tempor incididunt ut labore et dolore magna aliqua.
    
    Ut enim ad minim veniam,
    
    quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat.
    
    Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur.
    
    Excepteur sint occaecat cupidatat non proident,
    
    sunt in culpa qui officia deserunt mollit anim id est laborum.
    
    見つからなかった


### try

try節が例外を送出しなかったときの処理をelse節に書けます。例外の発生を想定する処理のみをtry節に書き、付随する処理をelse節に書くことで、意図が明確になるので、else節を用いるべきかと思います。


```python
file = './data/lorem_ipsum.txt'
try:
    # 例外の発生を想定する処理
    f = open(file)
except IOError:
    print('cannot open', file)
else:
    for line in iter(f.readline, ''):
        print(line)
        if ('Duis' in line):
            print('見つかった：' + line)
            break
    else:
        print('見つからなかった')
    f.close()
```

    Lorem ipsum dolor sit amet,
    
    consectetur adipiscing elit,
    
    sed do eiusmod tempor incididunt ut labore et dolore magna aliqua.
    
    Ut enim ad minim veniam,
    
    quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat.
    
    Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur.
    
    見つかった：Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur.
    


## リストの先頭要素に対する追加・削除処理が遅い

教科書的には、リストはどの要素に対する処理も計算量が変わらないはずですが、Pythonのリストは先頭要素に対する追加や削除の処理が遅いです。これは、内部的にCの配列で表しているためだとか。[Python用語集](https://docs.python.jp/3/glossary.html#term-list)にも、要素へのアクセスがO(1)だから、他の言語のリストよりも配列に近いという記載があります。

> A built-in Python sequence. Despite its name it is more akin to an array in other languages than to a linked list since access to elements are O(1).


```python
long_list = [x for x in range(10000000)]

# 先頭要素
%timeit long_list.insert(0, 1)

# 末尾
%timeit long_list.append(1)
```

    8.19 ms ± 89.7 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
    77.7 ns ± 0.809 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)


Jupyter Notebookのマジックコマンド「%timeit」を使って計測してみたところ、リスト先頭に対するinsertと、リスト末尾に対するappendではミリ（$10^{-3}$）とナノ（$10^{-9}$）の違いが出ました。

[Python チュートリアル／5.1.2. リストをキューとして使う](https://docs.python.jp/3/tutorial/datastructures.html#using-lists-as-queues)にも記載がありますが、dequeを使うことで、この問題を解消することができます。


```python
from collections import deque
long_list = deque([x for x in range(10000000)])

# 先頭要素
%timeit long_list.appendleft(1)

# 末尾
%timeit long_list.append(1)
```

    77.3 ns ± 1.57 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)
    82.7 ns ± 0.7 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)


確かに、同程度のスピードとなりました。

## まとめ

Pythonistaへの道は、まだまだ遠いのであった。