ndarray – 配列の生成

2019-09-10 / tau / コメントする

リテラル

要素をリテラルで指定する。

2次元配列は行列形式できれいに表示されるが、3次元以上は1行表示になる。

print(np.array([0, 1, 2]))
# [0 1 2]

print(np.array([[0, 1, 2], [0, 2, 4], [0, 3, 6]]))
# [[0 1 2]
#  [0 2 4]
#  [0 3 6]]

print([[[0, 1], [2, 3]], [[1, 2], [3, 4]], [[2, 3], [4, 5]],
      [[3, 4], [5, 6]], [[4, 5], [6, 7]], [[5, 6], [7, 8]]])
# [[[0, 1], [2, 3]], [[1, 2], [3, 4]], [[2, 3], [4, 5]], [[3, 4], [5, 6]], [[4, 5], [6, 7]], [[5, 6], [7, 8]]]

print(np.array([0, 1, 2]))

# [0 1 2]

print(np.array([[0, 1, 2], [0, 2, 4], [0, 3, 6]]))

# [[0 1 2]

# [0 2 4]

# [0 3 6]]

print([[[0, 1], [2, 3]], [[1, 2], [3, 4]], [[2, 3], [4, 5]],

[[3, 4], [5, 6]], [[4, 5], [6, 7]], [[5, 6], [7, 8]]])

# [[[0, 1], [2, 3]], [[1, 2], [3, 4]], [[2, 3], [4, 5]], [[3, 4], [5, 6]], [[4, 5], [6, 7]], [[5, 6], [7, 8]]]

リストでもタプルでも結果は同じ。

print(np.array([0, 1, 2, 3]))
print(np.array((0, 1, 2, 3)))

# [0 1 2 3]
# [0 1 2 3]

print(np.array([0, 1, 2, 3]))

print(np.array((0, 1, 2, 3)))

# [0 1 2 3]

自動生成

配列形状を指定して全要素を特定の値で埋める

全要素が0、1の配列

numpy.zeros(shape, [dtype=None], [order='C'])
numpy.ones(shape, [dtype=None], [order='C'])

引数はどちらも同じで、配列形状、データタイプ、行列優先の指定。

多次元配列を生成する場合、配列のサイズをタプルとして引数に渡す。

print(np.zeros(3))
# [0. 0. 0.]

print(np.zeros((2, 3)))
# [[0. 0. 0.]
#  [0. 0. 0.]]

print(np.ones(3))
# [1. 1. 1.]

print(np.ones((2, 3)))
# [[1. 1. 1.]
#  [1. 1. 1.]]

print(np.zeros(3))

# [0. 0. 0.]

print(np.zeros((2, 3)))

# [[0. 0. 0.]

# [0. 0. 0.]]

print(np.ones(3))

# [1. 1. 1.]

print(np.ones((2, 3)))

# [[1. 1. 1.]

# [1. 1. 1.]]

全要素の数値を指定

numpy.full(shape, fill_value, [dtype=None], [order='C'])]

print(np.full(5, -1))
# [-1 -1 -1 -1 -1]

print(np.full((2, 3), np.exp(1)))
# [[2.71828183 2.71828183 2.71828183]
#  [2.71828183 2.71828183 2.71828183]]

print(np.full(5, -1))

# [-1 -1 -1 -1 -1]

print(np.full((2, 3), np.exp(1)))

# [[2.71828183 2.71828183 2.71828183]

# [2.71828183 2.71828183 2.71828183]]

他の配列と同じ形状で特定の値を埋める

全要素が0、1の配列

numpy.zeros_like(a, [dtype=None], [order='C'])
numpy.ones_like(a, [dtype=None], [order='C'])

a = np.array([0, 1, 2])
print(np.zeros_like(a))
print(np.ones_like(a))
# [0 0 0]
# [1 1 1]

b = np.array([[0, 1, 2], [3, 4, 5]])
print(np.zeros_like(b))
print(np.ones_like(b))
# [[0 0 0]
#  [0 0 0]]
# [[1 1 1]
#  [1 1 1]]

a = np.array([0, 1, 2])

print(np.zeros_like(a))

print(np.ones_like(a))

# [0 0 0]

# [1 1 1]

b = np.array([[0, 1, 2], [3, 4, 5]])

print(np.zeros_like(b))

print(np.ones_like(b))

# [[0 0 0]

# [0 0 0]]

# [[1 1 1]

# [1 1 1]]

全要素の値を指定

numpy.full_like(a, fill_value, [dtype=None], [order='C'])]

print(np.full_like(a, -1))
print(np.full_like(b, -2))

# [-1 -1 -1]
# [[-2 -2 -2]
#  [-2 -2 -2]]

print(np.full_like(a, -1))

print(np.full_like(b, -2))

# [-1 -1 -1]

# [[-2 -2 -2]

# [-2 -2 -2]]

初期化せず配列枠だけ確保する

zeros()、ones()と同じで、配列の形だけを確保するが各要素は初期化しない。

この場合も多次元配列ではサイズのタプルを引数で渡す。

print(np.empty(3))
# [6.90878481e-305 6.92648110e-305 6.48616890e-317]

print(np.empty((2, 3)))
# [[7.79018398e-075 2.23185784e-074 1.41890730e-075]
#  [9.39249846e-076 3.97945113e-315 0.00000000e+000]]

print(np.empty(3))

# [6.90878481e-305 6.92648110e-305 6.48616890e-317]

print(np.empty((2, 3)))

# [[7.79018398e-075 2.23185784e-074 1.41890730e-075]

# [9.39249846e-076 3.97945113e-315 0.00000000e+000]]

配列形状を(1, 1)で指定すると、1要素の2次元配列が確保される。

print(np.empty((1, 1)))
# [[2.]]

1 2	print(np.empty((1, 1))) # [[2.]]

配列形状を数値0で指定すると、空の配列が確保される。

a = np.empty(0)
print(a)
a = np.append(a, 1)
print(a)
a = np.append(a, 2)
print(a)

# []
# [1.]
# [1. 2.]

a = np.empty(0)

print(a)

a = np.append(a, 1)

print(a)

a = np.append(a, 2)

print(a)

# []

# [1.]

# [1. 2.]

配列形状で0の次元が含まれると空の配列になる。

print(np.empty((0, 3, 2)))
# []

print(np.empty((3, 0, 2)))
# []

print(np.empty((0, 3, 2)))

# []

print(np.empty((3, 0, 2)))

# []

内包表記

リストの内包表記が使える。

print(np.array([x for x in range(0, 5)]))

# [0 1 2 3 4]

print(np.array([x for x in range(0, 5)]))

# [0 1 2 3 4]

`range()`関数

普通にrange()関数も使える。

print(np.array(range(5))

# [0 1 2 3 4]

print(np.array(range(5))

# [0 1 2 3 4]

`numpy.arange()`～間隔を指定

numpy.arrange([start=0], stop, [step=1], [dtype=None])

numpy.arange()関数はrange()関数よりも高速な生成が可能。

start = time.time()

for n in range(1000):
    a = np.arange(10000)
lap = time.time() - start
print('arange: {0} sec'.format(lap))

for n in range(1000):
    a = np.array(range(10000))
end = time.time() - start
print('range : {0} sec'.format(end - lap))

# arange: 0.003025054931640625 sec
# range : 1.2017848491668701 sec

start = time.time()

for n in range(1000):

a = np.arange(10000)

lap = time.time() - start

print('arange: {0} sec'.format(lap))

for n in range(1000):

a = np.array(range(10000))

end = time.time() - start

print('range : {0} sec'.format(end - lap))

# arange: 0.003025054931640625 sec

# range : 1.2017848491668701 sec

range()関数と同じようにパラメータを設定。dtypeはデータ型を指定。

print(np.arange(10))
print(np.arange(1, 10))
print(np.arange(1, 10, step=2))
print(np.arange(1, 10, step=2, dtype=float))

# [0 1 2 3 4 5 6 7 8 9]
# [1 2 3 4 5 6 7 8 9]
# [1 3 5 7 9]
# [1. 3. 5. 7. 9.]

print(np.arange(10))

print(np.arange(1, 10))

print(np.arange(1, 10, step=2))

print(np.arange(1, 10, step=2, dtype=float))

# [0 1 2 3 4 5 6 7 8 9]

# [1 2 3 4 5 6 7 8 9]

# [1 3 5 7 9]

# [1. 3. 5. 7. 9.]

range()関数は整数しか引数に指定できないが、numpy.arange()関数はfloatの指定が可能。

print(np.arange(5.0))
print(np.arange(0, 5, step=0.5))

# [0. 1. 2. 3. 4.]
# [0.  0.5 1.  1.5 2.  2.5 3.  3.5 4.  4.5]

print(np.arange(5.0))

print(np.arange(0, 5, step=0.5))

# [0. 1. 2. 3. 4.]

# [0. 0.5 1. 1.5 2. 2.5 3. 3.5 4. 4.5]

`numpy.linspace()`～分割数を指定

numpy.linspace(start, stop, [num=50], [endpoint=True], [retstep=False], [dtype=None])

初期値と終了値を指定して、その間を等分割したリストを返す。分割数を指定しないとデフォルトで50分割。基本の型はfloat。

print(np.linspace(0, 5))

# [0.         0.10204082 0.20408163 0.30612245 0.40816327 0.51020408
#  0.6122449  0.71428571 0.81632653 0.91836735 1.02040816 1.12244898
#  1.2244898  1.32653061 1.42857143 1.53061224 1.63265306 1.73469388
#  1.83673469 1.93877551 2.04081633 2.14285714 2.24489796 2.34693878
#  2.44897959 2.55102041 2.65306122 2.75510204 2.85714286 2.95918367
#  3.06122449 3.16326531 3.26530612 3.36734694 3.46938776 3.57142857
#  3.67346939 3.7755102  3.87755102 3.97959184 4.08163265 4.18367347
#  4.28571429 4.3877551  4.48979592 4.59183673 4.69387755 4.79591837
#  4.89795918 5.        ]

print(np.linspace(0, 5))

# [0. 0.10204082 0.20408163 0.30612245 0.40816327 0.51020408

# 0.6122449 0.71428571 0.81632653 0.91836735 1.02040816 1.12244898

# 1.2244898 1.32653061 1.42857143 1.53061224 1.63265306 1.73469388

# 1.83673469 1.93877551 2.04081633 2.14285714 2.24489796 2.34693878

# 2.44897959 2.55102041 2.65306122 2.75510204 2.85714286 2.95918367

# 3.06122449 3.16326531 3.26530612 3.36734694 3.46938776 3.57142857

# 3.67346939 3.7755102 3.87755102 3.97959184 4.08163265 4.18367347

# 4.28571429 4.3877551 4.48979592 4.59183673 4.69387755 4.79591837

# 4.89795918 5. ]

この分割数は区間数ではなく、生成される数列の個数である点に注意。以下の例では0～1の間で10個の数値を生成させるため、区間数は9となる（植木算の考え方）。

print(np.linspace(0, 1, num=10))

# [0.         0.11111111 0.22222222 0.33333333 0.44444444 0.55555556
#  0.66666667 0.77777778 0.88888889 1.        ]

print(np.linspace(0, 1, num=10))

# [0. 0.11111111 0.22222222 0.33333333 0.44444444 0.55555556

# 0.66666667 0.77777778 0.88888889 1. ]

デフォルトでは終端値を含めるが、含めないようにもできる。

print(np.linspace(0, 1, num=10, endpoint=False))

# [0.  0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9]

print(np.linspace(0, 1, num=10, endpoint=False))

# [0. 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9]

生成された数列と分割幅のタプルを返すことができる。

a = np.linspace(0, 9, num=10, retstep=True)
print(a)
print(a[0])
print(a[1])

# (array([0., 1., 2., 3., 4., 5., 6., 7., 8., 9.]), 1.0)
# [0. 1. 2. 3. 4. 5. 6. 7. 8. 9.]
# 1.0

a = np.linspace(0, 9, num=10, retstep=True)

print(a)

print(a[0])

print(a[1])

# (array([0., 1., 2., 3., 4., 5., 6., 7., 8., 9.]), 1.0)

# [0. 1. 2. 3. 4. 5. 6. 7. 8. 9.]

# 1.0

特定の行列の生成

`numpy.identity()`～単位行列

numpy.identity(n)

正方行列の1辺の要素数を指定して、単位行列を生成する。

print(np.identity(3))

# [[1. 0. 0.]
#  [0. 1. 0.]
#  [0. 0. 1.]]

print(np.identity(3))

# [[1. 0. 0.]

# [0. 1. 0.]

# [0. 0. 1.]]

`numpy.tri()`～下三角行列の生成

numpy.tri(n)

左下の要素が1の下三角行列を生成する。

print(np.tri(4))

# [[1. 0. 0. 0.]
#  [1. 1. 0. 0.]
#  [1. 1. 1. 0.]
#  [1. 1. 1. 1.]]

print(np.tri(4))

# [[1. 0. 0. 0.]

# [1. 1. 0. 0.]

# [1. 1. 1. 0.]

# [1. 1. 1. 1.]]

`numpy.tril()`、`numpy.triu()`～行列の三角化

numpy.tril(matrix)
nunmpy.triu(matrix)

与えられた行列を下三角／上三角化。

m = np.reshape(np.arange(16), (4, 4))
print(m)
print(np.tril(m))
print(np.triu(m))

# [[ 0  1  2  3]
#  [ 4  5  6  7]
#  [ 8  9 10 11]
#  [12 13 14 15]]
# [[ 0  0  0  0]
#  [ 4  5  0  0]
#  [ 8  9 10  0]
#  [12 13 14 15]]
# [[ 0  1  2  3]
#  [ 0  5  6  7]
#  [ 0  0 10 11]
#  [ 0  0  0 15]]

m = np.reshape(np.arange(16), (4, 4))

print(m)

print(np.tril(m))

print(np.triu(m))

# [[ 0 1 2 3]

# [ 4 5 6 7]

# [ 8 9 10 11]

# [12 13 14 15]]

# [[ 0 0 0 0]

# [ 4 5 0 0]

# [ 8 9 10 0]

# [12 13 14 15]]

# [[ 0 1 2 3]

# [ 0 5 6 7]

# [ 0 0 10 11]

# [ 0 0 0 15]]

numpy – 配列操作 – 抽出

2019-09-10 / tau / コメントする

概要

配列の要素や行・列の抽出などに関する操作。

準備として、以下の1次元、2次元配列を考える。

a1 = np.array([0, 1, 2, 3])
a2 = np.array([[0, 1, 2], [3, 4, 5], [6, 7, 8]])

print(a1)
print(a2)[0 1 2 3]

# [0 1 2 3]
# [[0 1 2]
#  [3 4 5]
#  [6 7 8]]

a1 = np.array([0, 1, 2, 3])

a2 = np.array([[0, 1, 2], [3, 4, 5], [6, 7, 8]])

print(a1)

print(a2)[0 1 2 3]

# [0 1 2 3]

# [[0 1 2]

# [3 4 5]

# [6 7 8]]

要素の参照

1次元配列の要素の参照は、リストと同じ。

print(a1[0])
print(a1[-1])
print(a1[-2])

# 0
# 3
# 2

print(a1[0])

print(a1[-1])

print(a1[-2])

# 0

# 3

# 2

2次元配列の要素は、[行, 列]で指定。行・列の値の考え方は1次元配列の要素と同じ。

print(a2[1, 2])
print(a2[-1, -2])

# 5
# 7

print(a2[1, 2])

print(a2[-1, -2])

# 5

# 7

行・列の参照

単一の行・列の参照

2次元配列の行の参照は、行番号を指定。

print(a2[0])

# [0 1 2]

print(a2[0])

# [0 1 2]

2次元配列の列の参照はややこしくて、[:,列番号]で指定。1つ目の:は行番号のプレースホルダーみたいなものか。

ただし、列を取り出した結果でも、1次元の配列になる。

print(a2[:,0])

# [0 3 6]

print(a2[:,0])

# [0 3 6]

直接列ベクトルで取り出したい場合は、[:,列番号:列番号+1]で可能。

print(a2[:,2:3])

# [[2]
#  [5]
#  [8]]

print(a2[:,2:3])

# [[2]

# [5]

# [8]]

なお、1次元の配列にndarray.Tを作用させても、1次元配列のままで列ベクトルにはならない。

範囲を指定した行・列の参照

行の範囲を指定して、複数行の行列を返す。

print(a2[1:3])

# [0 3 6]

print(a2[1:3])

# [0 3 6]

列の範囲を指定する場合。

print(a2[:,1:3])

# [[1 2]
#  [4 5]
#  [7 8]]

print(a2[:,1:3])

# [[1 2]

# [4 5]

# [7 8]]

複数の行・列を指定した参照

連続しない複数の行を取り出した行列をつくるには、[行番号, 行番号, …]とする。

print(a2[[0,2,0,2]])

# [[0 1 2]
#  [6 7 8]
#  [0 1 2]
#  [6 7 8]]

print(a2[[0,2,0,2]])

# [[0 1 2]

# [6 7 8]

# [0 1 2]

# [6 7 8]]

複数列を取り出す場合。

print(a2[:,[0,2,0,2]])

# [[0 2 0 2]
#  [3 5 3 5]
#  [6 8 6 8]]

print(a2[:,[0,2,0,2]])

# [[0 2 0 2]

# [3 5 3 5]

# [6 8 6 8]]

参照であることの注意

以上の操作で取り出された配列は、元の配列への参照を保っているため、その要素を変更すると元の配列の要素も変更される。

r = a2[0]
c = a2[:,2]
print(r)
print(c)
r[0] = -1
c[2] = -2
print(r)
print(c)
print(a2)

# 取り出された行・列
# [0 1 2]
# [2 5 8]
# 変更された行・列
# [-1  1  2]
# [ 2  5 -2]
# 元の配列にも影響
# [[-1  1  2]
#  [ 3  4  5]
#  [ 6  7 -2]]

r = a2[0]

c = a2[:,2]

print(r)

print(c)

r[0] = -1

c[2] = -2

print(r)

print(c)

print(a2)

# 取り出された行・列

# [0 1 2]

# [2 5 8]

# 変更された行・列

# [-1 1 2]

# [ 2 5 -2]

# 元の配列にも影響

# [[-1 1 2]

# [ 3 4 5]

# [ 6 7 -2]]

元の配列に影響させたくない場合は、copy.copy()、copy.deepcopy()、np.copy()でオブジェクトをコピーする必要がある。

対角要素の取り出し

np.diag()で、2次元配列の対角要素を取り出した1次元配列が得られる。

ただし、その結果は書き込みできない。

d = np.diag(a2)
print(d)  # [0 4 8]
d[0] = -1 # ValueError: assignment destination is read-only

d = np.diag(a2)

print(d) # [0 4 8]

d[0] = -1 # ValueError: assignment destination is read-only

条件を指定した取り出し

配列に条件式を適用して、各要素が要件に合致していればTrue、合致していなければFalseを要素とする配列を返す。

print(a2%2 == 0)

# [[ True False  True]
#  [False  True False]
#  [ True False  True]]

print(a2%2 == 0)

# [[ True False True]

# [False True False]

# [ True False True]]

上で得られた配列を要素とすることで、条件に合致した要素のみを取り出した1次元配列を得る。

print(a2[a2%2 == 0])

# [0 2 4 6 8]

print(a2[a2%2 == 0])

# [0 2 4 6 8]

Python3 – numpyのインストール

2019-09-10 / tau / コメントする

numpyのインストールは、コマンドラインからpipで。numpyのインストール後にpipのアップグレードを推奨されたので、これも実行。

C:\Users\tomo>pip install numpy
Collecting numpy
  Downloading https://files.pythonhosted.org/packages/c3/13/a991b874825a195aefb9cf53a1a632099622237d8701dbd4a18804fa5144/numpy-1.17.1-cp37-cp37m-win32.whl (10.8MB)
    100% |████████████████████████████████| 10.8MB 1.8MB/s
Installing collected packages: numpy
Successfully installed numpy-1.17.1
You are using pip version 19.0.3, however version 19.2.3 is available.
You should consider upgrading via the 'python -m pip install --upgrade pip' command.

C:\Users\tomo>python -m pip install --upgrade pip
Collecting pip
  Downloading https://files.pythonhosted.org/packages/30/db/9e38760b32e3e7f40cce46dd5fb107b8c73840df38f0046d8e6514e675a1/pip-19.2.3-py2.py3-none-any.whl (1.4MB)
    100% |████████████████████████████████| 1.4MB 1.3MB/s
Installing collected packages: pip
  Found existing installation: pip 19.0.3
    Uninstalling pip-19.0.3:
      Successfully uninstalled pip-19.0.3
Successfully installed pip-19.2.3

C:\Users\tomo>pip install numpy

Collecting numpy

Downloading https://files.pythonhosted.org/packages/c3/13/a991b874825a195aefb9cf53a1a632099622237d8701dbd4a18804fa5144/numpy-1.17.1-cp37-cp37m-win32.whl (10.8MB)

100% |████████████████████████████████| 10.8MB 1.8MB/s

Installing collected packages: numpy

Successfully installed numpy-1.17.1

You are using pip version 19.0.3, however version 19.2.3 is available.

You should consider upgrading via the 'python -m pip install --upgrade pip' command.

C:\Users\tomo>python -m pip install --upgrade pip

Collecting pip

Downloading https://files.pythonhosted.org/packages/30/db/9e38760b32e3e7f40cce46dd5fb107b8c73840df38f0046d8e6514e675a1/pip-19.2.3-py2.py3-none-any.whl (1.4MB)

100% |████████████████████████████████| 1.4MB 1.3MB/s

Installing collected packages: pip

Found existing installation: pip 19.0.3

Uninstalling pip-19.0.3:

Successfully uninstalled pip-19.0.3

Successfully installed pip-19.2.3

クイックソート

2019-09-08 / tau / コメントする

概要

クイックソートは、特定の値（ピボット）を基準にして、データの先頭と最後尾から1つずつ中央に近づけていきながら、ピボットより小さなデータが前に、大きなデータが後ろに配置されるように交換し、その処理を再帰的に行っていく。

考え方

以下2段階に分けて、与えられたデータ列をピボット以上・未満に振り分ける操作と、それらを再帰的に実行していく操作を示す。

ピボットの取り方にはいろいろあるようだが、ここでは与えられたデータの先頭と最後尾の値の平均値とする。

部分列に対する操作

以下の図で、4,6,2,…5のデータの部分列が与えられたとする。その際の操作は以下の通り。

⓪　部分列の先頭と最後尾のデータの平均を計算し、それをピボットとして設定(4.5)
①　左からピボット以上のデータを探索(6≥4.5)、右からピボット未満のデータを探索(1<4.5)
②　探索した左右のデータを交換
③　さらに左からピボット以上のデータを探索(7≥4.5)、右からピボット未満のデータを探索(0<4.5)
④　探索した左右のデータを交換
⑤　さらに探索を進めた結果、左右のポインターが交差
- このとき、境界より左にピボット未満、境界より右にピボット以上のデータが格納されている
- 3を境界とし、境界を含む左側とそれより右側の部分列に分けて、再帰的に探索を行う

再帰処理

部分列の操作を踏まえたうえで、それらの再帰的な処理の様子を下図に示す。図中、それぞれの線種や背景色の意味は以下の通り

二重枠囲みはピボットの値
赤はピボット以上のデータ
青はピボット未満のデータ
黄色は境界値
緑色は位置が確定したデータ

各段階の処理は以下の通り。

①　元の列からピボット以上／未満のデータを振り分け
②　左側の部分列に対する再帰1段目、ピボットによる振り分け
③　左側の部分列に対する再帰2段目、ピボットによる振り分け
④　左側の部分列に対する再帰3段目、ピボットによる振り分け
⑤⑥　左側・右側の再帰終了、0と1の位置確定
⑦　右側の部分列に対する再帰3段目
⑧⑨　左側・右側の再帰終了、2と3の位置確定
⑩　右側の再帰終了、4の位置確定（ここで再帰1段目の左側終了）
⑪　右側の部分列に対する再帰1段目、ピボットによる振り分け
⑫　左側の再帰終了、5の位置確定
⑬　右側の再帰2段目、ピボットによる振り分け
⑭⑮　左側・右側の再帰終了、6と7の位置確定

コード

以下はPythonによる実装。全体のデータ列に対して位置を指定して並べ替えを実行する再帰関数quick_sort_core()を定義し、全体列に対してこれを呼び出す入口の関数quick_sort()を定義。

def quick_sort(data):
    quick_sort_core(data, 0, len(data)-1)

def quick_sort_core(data, org_left, org_right):
    if org_left == org_right: return

    left = org_left
    right = org_right
    pivot = (data[org_left] + data[org_right]) / 2

    while True:
        while data[left] < pivot:
            left += 1
            if left > org_right: return
        while data[right] >= pivot:
            right -= 1
            if right < org_left: return
        if left >= right:
            border = right
            break
        data[left], data[right] = data[right], data[left]

    quick_sort_core(data, org_left, border)
    quick_sort_core(data, border+1, org_right)

def quick_sort(data):

quick_sort_core(data, 0, len(data)-1)

def quick_sort_core(data, org_left, org_right):

if org_left == org_right: return

left = org_left

right = org_right

pivot = (data[org_left] + data[org_right]) / 2

while True:

while data[left] < pivot:

left += 1

if left > org_right: return

while data[right] >= pivot:

right -= 1

if right < org_left: return

if left >= right:

border = right

break

data[left], data[right] = data[right], data[left]

quick_sort_core(data, org_left, border)

quick_sort_core(data, border+1, org_right)

例示したデータに対して実行。

data = [4, 6, 2, 7, 3, 0, 1, 5]
quick_sort(data)
print(data)

# [0, 1, 2, 3, 4, 5, 6, 7]

data = [4, 6, 2, 7, 3, 0, 1, 5]

quick_sort(data)

print(data)

# [0, 1, 2, 3, 4, 5, 6, 7]

要素がすべて同じで、要素数が偶数・奇数の場合も正常に動作。

data = [1, 1, 1, 1]
quick_sort(data)
print(data)

data = [1, 1, 1, 1, 1]
quick_sort(data)
print(data)

# [1, 1, 1, 1]
# [1, 1, 1, 1, 1]

data = [1, 1, 1, 1]

quick_sort(data)

print(data)

data = [1, 1, 1, 1, 1]

quick_sort(data)

print(data)

# [1, 1, 1, 1]

# [1, 1, 1, 1, 1]

同じ要素が複数含まれる場合も正常に動作。

data = [2, 1, 2, 1, 1]
print(data)
quick_sort(data)
print(data)

# [1, 1, 1, 2, 2]

data = [2, 1, 2, 1, 1]

print(data)

quick_sort(data)

print(data)

# [1, 1, 1, 2, 2]

動作状況の確認

並べ替えの動作中の状況を以下のコードで確認。各所にprint()関数をちりばめてみる。

import random

def quick_sort(data):
    quick_sort_core(data, 0, len(data)-1)

def quick_sort_core(data, org_left, org_right):
    print('function start')
    print(data[org_left:org_right+1], end=' ')
    if org_left == org_right:
        print('return')
        return

    left = org_left
    right = org_right
    pivot = (data[org_left] + data[org_right]) / 2
    print('pivot', pivot, '<-', data[org_left], data[org_right])

    while True:
        print(data[org_left:org_right+1], pivot, 'check', data[left], data[right])
        while data[left] < pivot:
            left += 1
            print(data[org_left:org_right+1], 'left+1 ->', data[left])
            if left > org_right:
                print(data[left], '>', data[org_right], 'return')
                return
        while data[right] >= pivot:
            right -= 1
            print(data[org_left:org_right+1], 'right-1 ->', data[right])
            if right < org_left:
                print(data[org_left], '>', data[right], 'return')
                return
        if left >= right:
            border = right
            print(data[left], '>=', data[right], 'border=', data[border])
            break
        data[left], data[right] = data[right], data[left]
        print(data[org_left:org_right+1], 'switched', data[left], data[right])

    quick_sort_core(data, org_left, border)
    quick_sort_core(data, border+1, org_right)

data = [4, 6, 2, 7, 3, 0, 1, 5]
quick_sort(data)
print(data)

import random

def quick_sort(data):

quick_sort_core(data, 0, len(data)-1)

def quick_sort_core(data, org_left, org_right):

print('function start')

print(data[org_left:org_right+1], end=' ')

if org_left == org_right:

print('return')

return

left = org_left

right = org_right

pivot = (data[org_left] + data[org_right]) / 2

print('pivot', pivot, '<-', data[org_left], data[org_right])

while True:

print(data[org_left:org_right+1], pivot, 'check', data[left], data[right])

while data[left] < pivot:

left += 1

print(data[org_left:org_right+1], 'left+1 ->', data[left])

if left > org_right:

print(data[left], '>', data[org_right], 'return')

return

while data[right] >= pivot:

right -= 1

print(data[org_left:org_right+1], 'right-1 ->', data[right])

if right < org_left:

print(data[org_left], '>', data[right], 'return')

return

if left >= right:

border = right

print(data[left], '>=', data[right], 'border=', data[border])

break

data[left], data[right] = data[right], data[left]

print(data[org_left:org_right+1], 'switched', data[left], data[right])

quick_sort_core(data, org_left, border)

quick_sort_core(data, border+1, org_right)

data = [4, 6, 2, 7, 3, 0, 1, 5]

quick_sort(data)

print(data)

動作結果は以下の通りで、再帰的に実行されているのがわかる。

function start
[4, 6, 2, 7, 3, 0, 1, 5] pivot 4.5 <- 4 5
[4, 6, 2, 7, 3, 0, 1, 5] 4.5 check 4 5
[4, 6, 2, 7, 3, 0, 1, 5] left+1 -> 6
[4, 6, 2, 7, 3, 0, 1, 5] right-1 -> 1
[4, 1, 2, 7, 3, 0, 6, 5] switched 1 6
[4, 1, 2, 7, 3, 0, 6, 5] 4.5 check 1 6
[4, 1, 2, 7, 3, 0, 6, 5] left+1 -> 2
[4, 1, 2, 7, 3, 0, 6, 5] left+1 -> 7
[4, 1, 2, 7, 3, 0, 6, 5] right-1 -> 0
[4, 1, 2, 0, 3, 7, 6, 5] switched 0 7
[4, 1, 2, 0, 3, 7, 6, 5] 4.5 check 0 7
[4, 1, 2, 0, 3, 7, 6, 5] left+1 -> 3
[4, 1, 2, 0, 3, 7, 6, 5] left+1 -> 7
[4, 1, 2, 0, 3, 7, 6, 5] right-1 -> 3
7 >= 3 border= 3
function start
[4, 1, 2, 0, 3] pivot 3.5 <- 4 3
[4, 1, 2, 0, 3] 3.5 check 4 3
[3, 1, 2, 0, 4] switched 3 4
[3, 1, 2, 0, 4] 3.5 check 3 4
[3, 1, 2, 0, 4] left+1 -> 1
[3, 1, 2, 0, 4] left+1 -> 2
[3, 1, 2, 0, 4] left+1 -> 0
[3, 1, 2, 0, 4] left+1 -> 4
[3, 1, 2, 0, 4] right-1 -> 0
4 >= 0 border= 0
function start
[3, 1, 2, 0] pivot 1.5 <- 3 0
[3, 1, 2, 0] 1.5 check 3 0
[0, 1, 2, 3] switched 0 3
[0, 1, 2, 3] 1.5 check 0 3
[0, 1, 2, 3] left+1 -> 1
[0, 1, 2, 3] left+1 -> 2
[0, 1, 2, 3] right-1 -> 2
[0, 1, 2, 3] right-1 -> 1
2 >= 1 border= 1
function start
[0, 1] pivot 0.5 <- 0 1
[0, 1] 0.5 check 0 1
[0, 1] left+1 -> 1
[0, 1] right-1 -> 0
1 >= 0 border= 0
function start
[0] return
function start
[1] return
function start
[2, 3] pivot 2.5 <- 2 3
[2, 3] 2.5 check 2 3
[2, 3] left+1 -> 3
[2, 3] right-1 -> 2
3 >= 2 border= 2
function start
[2] return
function start
[3] return
function start
[4] return
function start
[7, 6, 5] pivot 6.0 <- 7 5
[7, 6, 5] 6.0 check 7 5
[5, 6, 7] switched 5 7
[5, 6, 7] 6.0 check 5 7
[5, 6, 7] left+1 -> 6
[5, 6, 7] right-1 -> 6
[5, 6, 7] right-1 -> 5
6 >= 5 border= 5
function start
[5] return
function start
[6, 7] pivot 6.5 <- 6 7
[6, 7] 6.5 check 6 7
[6, 7] left+1 -> 7
[6, 7] right-1 -> 6
7 >= 6 border= 6
function start
[6] return
function start
[7] return
[0, 1, 2, 3, 4, 5, 6, 7]

function start

[4, 6, 2, 7, 3, 0, 1, 5] pivot 4.5 <- 4 5

[4, 6, 2, 7, 3, 0, 1, 5] 4.5 check 4 5

[4, 6, 2, 7, 3, 0, 1, 5] left+1 -> 6

[4, 6, 2, 7, 3, 0, 1, 5] right-1 -> 1

[4, 1, 2, 7, 3, 0, 6, 5] switched 1 6

[4, 1, 2, 7, 3, 0, 6, 5] 4.5 check 1 6

[4, 1, 2, 7, 3, 0, 6, 5] left+1 -> 2

[4, 1, 2, 7, 3, 0, 6, 5] left+1 -> 7

[4, 1, 2, 7, 3, 0, 6, 5] right-1 -> 0

[4, 1, 2, 0, 3, 7, 6, 5] switched 0 7

[4, 1, 2, 0, 3, 7, 6, 5] 4.5 check 0 7

[4, 1, 2, 0, 3, 7, 6, 5] left+1 -> 3

[4, 1, 2, 0, 3, 7, 6, 5] left+1 -> 7

[4, 1, 2, 0, 3, 7, 6, 5] right-1 -> 3

7 >= 3 border= 3

function start

[4, 1, 2, 0, 3] pivot 3.5 <- 4 3

[4, 1, 2, 0, 3] 3.5 check 4 3

[3, 1, 2, 0, 4] switched 3 4

[3, 1, 2, 0, 4] 3.5 check 3 4

[3, 1, 2, 0, 4] left+1 -> 1

[3, 1, 2, 0, 4] left+1 -> 2

[3, 1, 2, 0, 4] left+1 -> 0

[3, 1, 2, 0, 4] left+1 -> 4

[3, 1, 2, 0, 4] right-1 -> 0

4 >= 0 border= 0

function start

[3, 1, 2, 0] pivot 1.5 <- 3 0

[3, 1, 2, 0] 1.5 check 3 0

[0, 1, 2, 3] switched 0 3

[0, 1, 2, 3] 1.5 check 0 3

[0, 1, 2, 3] left+1 -> 1

[0, 1, 2, 3] left+1 -> 2

[0, 1, 2, 3] right-1 -> 2

[0, 1, 2, 3] right-1 -> 1

2 >= 1 border= 1

function start

[0, 1] pivot 0.5 <- 0 1

[0, 1] 0.5 check 0 1

[0, 1] left+1 -> 1

[0, 1] right-1 -> 0

1 >= 0 border= 0

function start

[0] return

function start

[1] return

function start

[2, 3] pivot 2.5 <- 2 3

[2, 3] 2.5 check 2 3

[2, 3] left+1 -> 3

[2, 3] right-1 -> 2

3 >= 2 border= 2

function start

[2] return

function start

[3] return

function start

[4] return

function start

[7, 6, 5] pivot 6.0 <- 7 5

[7, 6, 5] 6.0 check 7 5

[5, 6, 7] switched 5 7

[5, 6, 7] 6.0 check 5 7

[5, 6, 7] left+1 -> 6

[5, 6, 7] right-1 -> 6

[5, 6, 7] right-1 -> 5

6 >= 5 border= 5

function start

[5] return

function start

[6, 7] pivot 6.5 <- 6 7

[6, 7] 6.5 check 6 7

[6, 7] left+1 -> 7

[6, 7] right-1 -> 6

7 >= 6 border= 6

function start

[6] return

function start

[7] return

[0, 1, 2, 3, 4, 5, 6, 7]

バブルソート

2019-09-02 / tau / コメントする

概要

バブルソートは、すべてのデータを一つずつチェックしながら、（昇順の場合）最も大きいデータを後ろに押し出していく。

たとえば以下のような初期データ列があるとする。

3, 4, 1, 2, 0

最初のループでは、全データの中で最大のものが一番最後に来るようにする。

3, 4, 1, 2, 0
3, 4, 1, 2, 0　→　3, 1, 4, 2, 0
3, 1, 4, 2, 0　→　3, 1, 2, 4, 0
3, 1, 2, 4, 0　→　3, 1, 2, 0, 4

3, 1, 2, 0, 4　→　1, 3, 2, 0, 4
1, 3, 2, 0, 4　→　1, 2, 3, 0, 4
1, 2, 3, 0, 4　→　1, 2, 0, 3, 4

1, 2, 0, 3, 4
1, 2, 0, 3, 4　→　1, 0, 2, 3, 4

1, 0, 2, 3, 4　→　0, 1, 2, 3, 4

ループ回数は $(n-1)+(n-2)+\cdots+1=\frac{n(n-1)}{2}$

コード

Pythonによるバブルソートのコード例。

def bubble_sort(data):
    for m in reversed(range(0, len(data))):
        for n in range(0, m):
            print(data, end=' -> ')
            if data[n] > data[n+1]:
                data[n], data[n+1] = data[n+1], data[n]
            print(data)
        print()


data = [3, 4, 1, 2, 0]
bubble_sort(data)

# [0, 1, 2, 3, 4]

def bubble_sort(data):

for m in reversed(range(0, len(data))):

for n in range(0, m):

print(data, end=' -> ')

if data[n] > data[n+1]:

data[n], data[n+1] = data[n+1], data[n]

print(data)

print()

data = [3, 4, 1, 2, 0]

bubble_sort(data)

# [0, 1, 2, 3, 4]

安定ソート

バブルソートは安定ソートである。すなわち、同じソートキーのデータについて、ソート後も元の順序が保持される。

def bubble_sort_2d(data):
    for m in reversed(range(0, len(data))):
        for n in range(0, m):
            print(data, end=' -> ')
            if data[n][1] > data[n+1][1]:
                data[n], data[n+1] = data[n+1], data[n]
            print(data)
        print()


data = [
    [1, 50],
    [2, 40],
    [3, 30],
    [4, 30],
    [5, 40]]
bubble_sort_2d(data)

# [[3, 30], [4, 30], [2, 40], [5, 40], [1, 50]]

def bubble_sort_2d(data):

for m in reversed(range(0, len(data))):

for n in range(0, m):

print(data, end=' -> ')

if data[n][1] > data[n+1][1]:

data[n], data[n+1] = data[n+1], data[n]

print(data)

print()

data = [

[1, 50],

[2, 40],

[3, 30],

[4, 30],

[5, 40]]

bubble_sort_2d(data)

# [[3, 30], [4, 30], [2, 40], [5, 40], [1, 50]]

Python3 – random/乱数

2019-08-18 / tau / コメントする

概要

randomモジュールには、疑似乱数を発生させる関数や、コレクションからランダムな要素を選んだり、コレクションをシャッフルしてくれる関数が用意されている。

なお、numpy.randomモジュールにも便利な乱数生成関数が準備されている。

乱数系列/seed()

random.seed()関数は、引数を指定して乱数系列を固定する。

import random

random.seed(0)

for n in range(5):
    print(random.random())

# 0.8444218515250481
# 0.7579544029403025
# 0.420571580830845
# 0.25891675029296335
# 0.5112747213686085
# 何度繰り返しても同じ値になる

import random

random.seed(0)

for n in range(5):

print(random.random())

# 0.8444218515250481

# 0.7579544029403025

# 0.420571580830845

# 0.25891675029296335

# 0.5112747213686085

# 何度繰り返しても同じ値になる

疑似乱数/random()

random()関数は、0≤r<1の範囲の一様乱数を浮動小数点で返す。

import random

for n in range(0, 5):
    print(random.random())

# 0.18356662737924279
# 0.2535975770454991
# 0.07112643912586292
# 0.9296944359969844
# 0.16323733244990823

import random

for n in range(0, 5):

print(random.random())

# 0.18356662737924279

# 0.2535975770454991

# 0.07112643912586292

# 0.9296944359969844

# 0.16323733244990823

一様乱数/uniform()

uniform(a, b)は、a≤r<bの範囲の一様乱数を浮動小数点で返す。

import random

for n in range(0, 5):
    print(random.uniform(1, 5))

# 3.6379958781920916
# 3.380738588720399
# 1.2535708428173264
# 4.802360086175415
# 2.7348909239420416

import random

for n in range(0, 5):

print(random.uniform(1, 5))

# 3.6379958781920916

# 3.380738588720399

# 1.2535708428173264

# 4.802360086175415

# 2.7348909239420416

整数乱数/randint(), randrange()

randint(a, b)はa≤r≤bの範囲の乱数を整数で返す。第2引数のbも生成されることに注意。

randrange(start, end, step)はstart≤r<stopの範囲でstep間隔の乱数を整数で返す。第2引数のstopは生成されないことに注意。stepを省略した場合は1となる。

import random

for n in range(20):
    print(random.randint(0, 2), end=" ")

for n in range(20):
    print(random.randrange(0, 6, 2), end=" ")

# 0 2 2 1 1 2 1 1 1 1 1 2 2 1 0 0 2 1 2 1
# 2 2 4 4 2 0 4 0 2 4 2 2 2 0 4 2 4 4 2 0

import random

for n in range(20):

print(random.randint(0, 2), end=" ")

for n in range(20):

print(random.randrange(0, 6, 2), end=" ")

# 0 2 2 1 1 2 1 1 1 1 1 2 2 1 0 0 2 1 2 1

# 2 2 4 4 2 0 4 0 2 4 2 2 2 0 4 2 4 4 2 0

ランダム選択/choise()

choise(c)はコレクションcからランダムな要素を一つ選んで返す。

import random

cities = ['Yokohama', 'Osaka', 'Nagoya','Sapporo', 'Fukuoka', 'Kobe']
for n in range(0, 5):
    print(random.choice(cities))

# Kobe
# Nagoya
# Yokohama
# Sapporo
# Yokohama

import random

cities = ['Yokohama', 'Osaka', 'Nagoya','Sapporo', 'Fukuoka', 'Kobe']

for n in range(0, 5):

print(random.choice(cities))

# Kobe

# Nagoya

# Yokohama

# Sapporo

# Yokohama

引数に文字列を指定すると、その中から任意の位置の文字を一つ返す。

import random

a_string = 'ABCDEFG'
for n in range(0, 5):
    print(random.choice(a_string))

# D
# C
# E
# D
# B

import random

a_string = 'ABCDEFG'

for n in range(0, 5):

print(random.choice(a_string))

# D

# C

# E

# D

# B

シャッフル/shuffle()

shuffle(c)はコレクションの内容をシャッフルする。イミュータブルな文字列を指定するとTypeErrorになる。

import random

cities = ['Yokohama', 'Osaka', 'Nagoya','Sapporo', 'Fukuoka', 'Kobe']
random.shuffle(cities)
print(cities)

# ['Nagoya', 'Kobe', 'Fukuoka', 'Osaka', 'Yokohama', 'Sapporo']

import random

cities = ['Yokohama', 'Osaka', 'Nagoya','Sapporo', 'Fukuoka', 'Kobe']

random.shuffle(cities)

print(cities)

# ['Nagoya', 'Kobe', 'Fukuoka', 'Osaka', 'Yokohama', 'Sapporo']

Python3 – オブジェクトへの参照

2019-08-18 / tau / コメントする

概要

Pythonで関数の受け渡しが参照渡しとされているが、改めて変数とオブジェクトの関係を含めて確認してみた。

オブジェクトの参照に関する基本的な考え方は

論理値や数値も含めて全てオブジェクト
変数にはインスタンスのアドレスが格納され、参照される
数値や文字列などイミュータブルなオブジェクトの場合、リテラルの表現が同じものは共通の1つのインスタンスとなる
リストなどミュータブルなオブジェクトは、インスタンスの内容が変更されても参照先は変わらない(逆に言えば、参照先が変わらないのに内容が変更されている可能性がある)

関数の引数の受け渡しは

仮引数は、関数が呼び出し時には元のオブジェクトへの参照を指しているが、イミュータブルオブジェクトが変更された場合は参照先が変わり、呼び出し元の引数に影響を与えない
引数の参照先がミュータブルオブジェクトの場合、インスタンスの内容が変更されても参照先は変わらず、呼び出し元の内容も変更される

変数からオブジェクトへの参照

数値の場合

下記のコードをまず確認する。

a = 1
b = a
c = b

print('a={}, b={}, c={}'.format(a, b, c))
print('$a={}, $b={}, $c={}'.format(id(a), id(b), id(c)))

# a=1, b=1, c=1
# $a=1943168176, $b=1943168176, $c=1943168176
# 3つの変数の値は等しく、参照番地は同じ

a = 1

b = a

c = b

print('a={}, b={}, c={}'.format(a, b, c))

print('$a={}, $b={}, $c={}'.format(id(a), id(b), id(c)))

# a=1, b=1, c=1

# $a=1943168176, $b=1943168176, $c=1943168176

# 3つの変数の値は等しく、参照番地は同じ

ある数値を変数に代入すると、その変数には数値（オブジェクト）のアドレスがセットされる。その変数の内容（アドレス）を別の変数に代入すると、新しい変数も同じアドレスをさすようになる。

次に、同じ数値を指している変数の一つに別の数値を代入すると、その変数は新しい数値オブジェクトのアドレスを指すようになる。

b = 2

# a=1, b=2, c=1
# $a=1943168176, $b=1943168192, $c=1943168176
# bに新しい値をセットすると、参照番地も変わる
# a, cの値、参照番地は変化しない

b = 2

# a=1, b=2, c=1

# $a=1943168176, $b=1943168192, $c=1943168176

# bに新しい値をセットすると、参照番地も変わる

# a, cの値、参照番地は変化しない

以下のように、同じ値の数値は1つのオブジェクトのアドレスが共有される。

c = 2

# a=1, b=2, c=2
# $a=1943168176, $b=1943168192, $c=1943168192
# cにbと同じ値をセットすると、値・参照番地とも同じになる

c = 2

# a=1, b=2, c=2

# $a=1943168176, $b=1943168192, $c=1943168192

# cにbと同じ値をセットすると、値・参照番地とも同じになる

数値計算の場合も、結果が同じ値なら1のオブジェクトが共有される。

a = 3 * 4
b = 2 * 6

# a=12, b=12
# $a=1943168352, $b=1943168352
a# 計算過程に関わらず、計算結果が同じなら同じ番地を参照

a = 3 * 4

b = 2 * 6

# a=12, b=12

# $a=1943168352, $b=1943168352

a# 計算過程に関わらず、計算結果が同じなら同じ番地を参照

変数が絡む演算でも、結果が同じ値なら同じアドレスを指す。

x = 3
a = x * 4
b = 2 * 2 * x

# a=12, b=12
# $a=1943168352, $b=1943168352
# 変数が絡む場合でも計算結果が同じならオブジェクトも同じ

x = 3

a = x * 4

b = 2 * 2 * x

# a=12, b=12

# $a=1943168352, $b=1943168352

# 変数が絡む場合でも計算結果が同じならオブジェクトも同じ

浮動小数点の場合、精度上少しでも異なる値は違うオブジェクトになる。

a = 1.0 / 3
b = 10 / 3 - 3

# a=0.3333333333333333, b=0.3333333333333335
# $a=62840080, $b=62839984
# 浮動小数点の場合、必ずしも予想した同じ値とならない場合がある

a = 1.0 / 3

b = 10 / 3 - 3

# a=0.3333333333333333, b=0.3333333333333335

# $a=62840080, $b=62839984

# 浮動小数点の場合、必ずしも予想した同じ値とならない場合がある

文字列の場合

数値の場合と同じで、変数は文字列オブジェクトのアドレスを指す。

a = 'AA'
b = a

# a=AA, b=AA
# $a=67099680, $b=67099680
# 同じ文字列オブジェクトを参照

a = 'AA'

b = a

# a=AA, b=AA

# $a=67099680, $b=67099680

# 同じ文字列オブジェクトを参照

異なる内容の文字列は、異なるオブジェクトとなる。

b = 'AB'

# a=AA, b=AB
# $a=67099680, $b=67099776
# 新たな文字列は新たなオブジェクトとして生成され参照される

b = 'AB'

# a=AA, b=AB

# $a=67099680, $b=67099776

# 新たな文字列は新たなオブジェクトとして生成され参照される

同じ内容の文字列リテラルは、異なる位置で用いられても1つのオブジェクトとして共有される。

a = 'AB'

# a=AB, b=AB
# $a=67099776, $b=67099776
# 同じ内容の文字リテラルは同じオブジェクトとして参照される

a = 'AB'

# a=AB, b=AB

# $a=67099776, $b=67099776

# 同じ内容の文字リテラルは同じオブジェクトとして参照される

面白いことに、文字列リテラル同士の演算結果が同じなら、これも同じオブジェクトとして共有される。

b = 'A' + 'B'

# a=AB, b=AB
# $a=67099776, $b=67099776
# 文字列リテラルの演算結果が同じ内容なら同一のオブジェクト

b = 'A' + 'B'

# a=AB, b=AB

# $a=67099776, $b=67099776

# 文字列リテラルの演算結果が同じ内容なら同一のオブジェクト

同じオブジェクトを指していても、一方に演算を施すと新たなオブジェクトが生成されるため、異なるオブジェクトを指すようになる。

a += 'C'

# a=ABC, b=AB
# $a=67172064, $b=67099776
# 文字列に変更があると新たな別のオブジェクトになる

a += 'C'

# a=ABC, b=AB

# $a=67172064, $b=67099776

# 文字列に変更があると新たな別のオブジェクトになる

なお、リテラル同士の演算で結果が同じ場合はオブジェクトが共有されたが、変数が絡む場合は、内容が同じであっても異なるオブジェクトとなる。

x = 'A'
a = x + 'B'
b = x + 'B'

# a=AB, b=AB
# $a=67172608, $b=67172064
# 結果が同じでもリテラルのみでない演算の場合は異なるオブジェクト

x = 'A'

a = x + 'B'

b = x + 'B'

# a=AB, b=AB

# $a=67172608, $b=67172064

# 結果が同じでもリテラルのみでない演算の場合は異なるオブジェクト

リストの場合

リストの場合もオブジェクトへの参照が変数に保存される。

a = [0, 1, 2]
b = a

# a=[0, 1, 2], b=[0, 1, 2]
# $a=66799096, $b=66799096
# 同じリストを参照

a = [0, 1, 2]

b = a

# a=[0, 1, 2], b=[0, 1, 2]

# $a=66799096, $b=66799096

# 同じリストを参照

リストの要素を変更した場合、そのリストを指している全ての変数に変更結果が反映される。

a[0] = 1

# a=[1, 1, 2], b=[1, 1, 2]
# $a=66799096, $b=66799096
# 同じリストを参照しているので変更結果も参照先に反映

a[0] = 1

# a=[1, 1, 2], b=[1, 1, 2]

# $a=66799096, $b=66799096

# 同じリストを参照しているので変更結果も参照先に反映

注意点。リストの場合、リテラルが同じでも異なるオブジェクトが生成される。

a = [0, 1, 2]
b = [0, 1, 2]

# a=[0, 1, 2], b=[0, 1, 2]
# $a=67159624, $b=67158704
# リストの場合、同じリテラル表現でも異なるオブジェクトになる

a = [0, 1, 2]

b = [0, 1, 2]

# a=[0, 1, 2], b=[0, 1, 2]

# $a=67159624, $b=67158704

# リストの場合、同じリテラル表現でも異なるオブジェクトになる

オブジェクトが異なるため、片方の変更は他方に反映されない。

a[0] = 1

# a=[1, 1, 2], b=[0, 1, 2]
# $a=67159624, $b=67158704
# リストの内容を変化させても参照番地は変わらない
# 異なるオブジェクトのため、変更は波及しない

a[0] = 1

# a=[1, 1, 2], b=[0, 1, 2]

# $a=67159624, $b=67158704

# リストの内容を変化させても参照番地は変わらない

# 異なるオブジェクトのため、変更は波及しない

関数の引数の参照

数値の場合

関数の引数に数値を渡す場合の流れは以下の通り。

仮引数は引数と同じオブジェクトを指す
関数内で引数が変更されると、新たなオブジェクトを指すようになる
その結果、仮引数に渡した変数は変更されない

def func_num(arg):
    print('arg_before={}, id={}'.format(arg, id(arg)))
    arg +=1
    print('arg_after={}, id={}'.format(arg, id(arg)))
    return arg

var = 1
print('variable={}, id={}'.format(var, id(var)))
result = func_num(var)

print('result={}, id={}'.format(result, id(result)))
print('variable={}, id={}'.format(var, id(var)))

# variable=1, id=1943037104
# arg_before=1, id=1943037104
# arg_after=2, id=1943037120
# result=2, id=1943037120
# variable=1, id=1943037104
# 引数は、数値への参照で渡される
# 関数内で異なる値にセットされると引数の参照番地が変わる
# しかし、その結果は呼び出し元の実引数に影響しない

def func_num(arg):

print('arg_before={}, id={}'.format(arg, id(arg)))

arg +=1

print('arg_after={}, id={}'.format(arg, id(arg)))

return arg

var = 1

print('variable={}, id={}'.format(var, id(var)))

result = func_num(var)

print('result={}, id={}'.format(result, id(result)))

print('variable={}, id={}'.format(var, id(var)))

# variable=1, id=1943037104

# arg_before=1, id=1943037104

# arg_after=2, id=1943037120

# result=2, id=1943037120

# variable=1, id=1943037104

# 引数は、数値への参照で渡される

# 関数内で異なる値にセットされると引数の参照番地が変わる

# しかし、その結果は呼び出し元の実引数に影響しない

文字列の場合

文字列の場合も、関数内での変更は呼び出し元に影響を与えない。

def func_str(arg):
    print('arg_before={}, id={}'.format(arg, id(arg)))
    arg += 'X'
    print('arg_after={}, id={}'.format(arg, id(arg)))
    return arg

var = 'ABC'
print('variable={}, id={}'.format(var, id(var)))
result = func_str(var)

print('result={}, id={}'.format(result, id(result)))
print('variable={}, id={}'.format(var, id(var)))

# variable=ABC, id=72144960
# arg_before=ABC, id=72144960
# arg_after=ABCX, id=72220064
# result=ABCX, id=72220064
# variable=ABC, id=72144960
# 数値の場合と同じで、引数は参照渡しだが呼び出し元の変数は変更されない

def func_str(arg):

print('arg_before={}, id={}'.format(arg, id(arg)))

arg += 'X'

print('arg_after={}, id={}'.format(arg, id(arg)))

return arg

var = 'ABC'

print('variable={}, id={}'.format(var, id(var)))

result = func_str(var)

print('result={}, id={}'.format(result, id(result)))

print('variable={}, id={}'.format(var, id(var)))

# variable=ABC, id=72144960

# arg_before=ABC, id=72144960

# arg_after=ABCX, id=72220064

# result=ABCX, id=72220064

# variable=ABC, id=72144960

# 数値の場合と同じで、引数は参照渡しだが呼び出し元の変数は変更されない

リストの場合

リストを引数に渡した場合、関数内での変更が呼び出し元にも影響を与える。リストのようなミュータブルオブジェクトの場合、それに対する変更は元のインスタンスに対する変更であり、イミュータブルなオブジェクトのように新しいインスタンスが生成されるわけではないため。

元のインスタンスに影響を波及させたくない場合はコピー、ディープコピーを使う。

def func_list(arg):
    print('arg_before={}, id={}'.format(arg, id(arg)))
    arg.append(0)
    print('arg_after={}, id={}'.format(arg, id(arg)))
    return arg
var = [3, 2, 1]
print('variable={}, id={}'.format(var, id(var)))
result = func_list(var)

print('result={}, id={}'.format(result, id(result)))
print('variable={}, id={}'.format(var, id(var)))

# variable=[3, 2, 1], id=71845368
# arg_before=[3, 2, 1], id=71845368
# arg_after=[3, 2, 1, 0], id=71845368
# result=[3, 2, 1, 0], id=71845368
# variable=[3, 2, 1, 0], id=71845368
# リストの場合は内容が変化しても参照は変更されないので
# 呼び出し元の変数が影響を受ける

def func_list(arg):

print('arg_before={}, id={}'.format(arg, id(arg)))

arg.append(0)

print('arg_after={}, id={}'.format(arg, id(arg)))

return arg

var = [3, 2, 1]

print('variable={}, id={}'.format(var, id(var)))

result = func_list(var)

print('result={}, id={}'.format(result, id(result)))

print('variable={}, id={}'.format(var, id(var)))

# variable=[3, 2, 1], id=71845368

# arg_before=[3, 2, 1], id=71845368

# arg_after=[3, 2, 1, 0], id=71845368

# result=[3, 2, 1, 0], id=71845368

# variable=[3, 2, 1, 0], id=71845368

# リストの場合は内容が変化しても参照は変更されないので

# 呼び出し元の変数が影響を受ける

Python3 – キーワードと予約語

2019-08-17 / tau / コメントする

キーワード

>>> import keyword
>>> for s in keyword.kwlist: print(s)
...
False
None
True
and
as
.....
with
yield

>>> import keyword

>>> for s in keyword.kwlist: print(s)

...

False

None

True

and

.....

with

yield

キーワードの一覧は以下の通り。

False, None, True, and, as, assert, async, await, break, class, continue, def, del, elif, else, except, finally, for, from, global, if, import, in, is, lambda, nonlocal, not, or, pass, raise, return, try, while, with, yield

組み込み関数

>>> for s in dir(__builtins__): print(s)
...
ArithmeticError
AssertionError
......
_
__build_class__
__debug__
.....
abs
all
.....
vars
zip

>>> for s in dir(__builtins__): print(s)

...

ArithmeticError

AssertionError

......

__build_class__

__debug__

.....

abs

all

.....

vars

zip

このうちabs以降の一覧は以下の通り。

abs, all, any, ascii, bin, bool, breakpoint, bytearray, bytes, callable, chr, classmethod, compile, complex, copyright, credits, delattr, dict, dir, divmod, enumerate, eval, exec, exit, filter, float, format, frozenset, getattr, globals, hasattr, hash, help, hex, id, input, int, isinstance, issubclass, iter, len, license, list, locals, map, max, memoryview, min, next, object, oct, open, ord, pow, print, property, quit, range, repr, reversed, round, set, setattr, slice, sorted, staticmethod, str, sum, super, tuple, type, vars, zip

公開鍵と秘密鍵

2019-08-15 / tau / コメントする

暗号化

暗号化の流れ

公開鍵(public key)と秘密鍵(secret/private key)を使った暗号化の流れは以下のとおり。

受信側が公開鍵と秘密鍵を準備し、公開鍵を公開
送信側は公開鍵を使って平文を暗号化し、受信側に送信
受信側は秘密鍵を使って暗号文を平文に復号（秘密鍵を持っている受信側しか複合できない）

この手順を、もう少し詳しく見ると以下のとおり。

受信側が、公開鍵として $(p, n)$ 、秘密鍵として $(s, n)$ を準備し、公開鍵を公開する
送信側は、公開鍵を使って平文(plaintext)を暗号化し、暗号文(ciphertext)を生成、受信側に送信
- $T_c = T_p^p \mod n$
受信側は、受け取った暗号文を秘密鍵を使って複合
- $T_p = T_c^s \mod n$

公開鍵・秘密鍵の算出手順

素数の組の準備

まず、受信側で2つの素数 $q, r$ を準備する。例えば $q=5, r=11$ とする。

素数の積nの計算

次に、 $q, r$ の積を計算し、その値を $n$ とする。

(1) $\begin{equation*} n = qr \end{equation*}$

例えば $n=5 \times 11 = 55$ 。

計算準備

$q-1, r-1$ の最小公倍数を計算しておく。

(2) $\begin{equation*} L = LCM(p-1, q-1) \end{equation*}$

例えば、 $L = LCM(4, 10) = 20$ 。

公開鍵の計算

$p, L$ が互いに素であるような $p$ を選ぶ。ここで公開鍵は $(p, n)$ となる。

(3) $\begin{equation*} p \; : \; GCM(p, L) = 1 \end{equation*}$

例えば、 $p = 3$ とすると、公開鍵は $(3, 55)$

秘密鍵の計算

(4) $\begin{equation*} s \; : \; sp \mod L = 1 \end{equation*}$

例えば、 $e = 7$ とすると、 $3 \times 7 \mod 20 = 1$ となり、秘密鍵は $(7, 55)$ 。

簡略化した暗号化の例

鍵の準備

先の公開鍵・秘密鍵の算出で例示した値を使って、暗号化の流れを見てみる。

2つの素数の組 $p=5, q=11$ を準備し、 $n = pq = 5 \times 11 = 55$ を計算した。

さらに $LCM(q-1, r-1)$ の値から、公開鍵 $(p, n)$ 、秘密鍵 $(s, n)$ を以下の様に得た。

(5) $\begin{eqnarray*} (p, n) &=& (3, 55) \\ (s, n) &=& (7, 55) \end{eqnarray*}$

暗号化

平文として数列 $12, 26, 33$ を考え、送信側で公開鍵を使って、この平文を暗号化する。

(6) $\begin{eqnarray*} 12 &\rightarrow& 12^p \mod n = 12^3 \mod 55 = 1728 \mod 55 = 23\\ 26 &\rightarrow& 26^p \mod n = 26^3 \mod 55 = 17576 \mod 55 = 31 \\ 33 &\rightarrow& 33^p \mod n = 33^3 \mod 55 = 35937 \mod 55 = 22 \end{eqnarray*}$

復号

受信側は受け取った暗号文を、秘密鍵を使って複合する。

(7) $\begin{eqnarray*} 23 &\rightarrow& 23^s \mod n = 23^7 \mod 55 = 3404825447 \mod 55 = 12\\ 31 &\rightarrow& 31^s \mod n = 31^7 \mod 55 = 27512614111 \mod 55 = 26\\ 22 &\rightarrow& 22^s \mod n = 22^7 \mod 55 = 2494357888 \mod 55 = 33 \end{eqnarray*}$

電子証明

電子証明の流れ

公開鍵と秘密鍵を使う順序を逆にすると、電子証明に仕える。その流れは以下のとおり。

発信側が公開鍵と秘密鍵を準備し、公開鍵を公開
発信側は秘密鍵を使って平文を暗号化し、受信側に送信
受信側は公開鍵を使って暗号文を平文に復号し、証明を確認（秘密鍵を持っている発信側しか公開鍵で正しい平文に復号可能な暗号文を生成できない）

簡略化した電子証明の例

暗号化の例と同じ公開鍵・秘密鍵を使って、電子証明の例を確認する。

証明書の暗号化

発信側で証明書の平文 $12, 26, 33$ を準備し、これを秘密鍵を使って暗号化。

(8) $\begin{eqnarray*} 12 &\rightarrow& 12^s \mod n = 12^7 \mod 55 = 35831808 \mod 55 = 23\\ 26 &\rightarrow& 26^s \mod n = 26^7 \mod 55 = 8031810176 \mod 55 = 16 \\ 33 &\rightarrow& 33^s \mod n = 33^7 \mod 55 = 42618442977 \mod 55 = 22 \end{eqnarray*}$

受信側は、公開鍵を使って暗号文を復号し、平文を確認（秘密鍵で暗号化した文のみ、公開鍵で適正に複合できる）。

(9) $\begin{eqnarray*} 23 &\rightarrow& 23^p \mod n = 23^3 \mod 55 = 12167 \mod 55 = 12\\ 16 &\rightarrow& 16^p \mod n = 16^3 \mod 55 = 4096 \mod 55 = 26 \\ 22 &\rightarrow& 22^p \mod n = 22^3 \mod 55 = 10648 \mod 55 = 33 \end{eqnarray*}$

ハッシュ

2019-08-15 / tau / コメントする

ハッシュ関数のことを考えてみようと、自分なりにトライしてみた。

簡単すぎる例
文字列の文字コードを足し込んでいくという単純な方法。

剰余を使った例
剰余を使った例。文字列が短い場合はある程度の長さに拡張して、キーとなる数で割った余りをハッシュとしている。

リテラル

自動生成

配列形状を指定して全要素を特定の値で埋める

全要素が0、1の配列

全要素の数値を指定

他の配列と同じ形状で特定の値を埋める

全要素が0、1の配列

全要素の値を指定

初期化せず配列枠だけ確保する

内包表記

range()関数

numpy.arange()～間隔を指定

numpy.linspace()～分割数を指定

特定の行列の生成

numpy.identity()～単位行列

numpy.tri()～下三角行列の生成

numpy.tril()、numpy.triu()～行列の三角化

概要

要素の参照

行・列の参照

単一の行・列の参照

範囲を指定した行・列の参照

複数の行・列を指定した参照

参照であることの注意

対角要素の取り出し

条件を指定した取り出し

概要

考え方

部分列に対する操作

再帰処理

コード

動作状況の確認

概要

コード

安定ソート

概要

乱数系列/seed()

疑似乱数/random()

一様乱数/uniform()

整数乱数/randint(), randrange()

ランダム選択/choise()

シャッフル/shuffle()

概要

変数からオブジェクトへの参照

数値の場合

文字列の場合

リストの場合

関数の引数の参照

数値の場合

文字列の場合

リストの場合

キーワード

組み込み関数

暗号化

暗号化の流れ

公開鍵・秘密鍵の算出手順

素数の組の準備

素数の積nの計算

計算準備

公開鍵の計算

秘密鍵の計算

簡略化した暗号化の例

鍵の準備

暗号化

復号

電子証明

電子証明の流れ

簡略化した電子証明の例

証明書の暗号化

`range()`関数

`numpy.arange()`～間隔を指定

`numpy.linspace()`～分割数を指定

`numpy.identity()`～単位行列

`numpy.tri()`～下三角行列の生成

`numpy.tril()`、`numpy.triu()`～行列の三角化