[NumPy_04] 配列の並び替え np.sort() np.partition()

Posted on 2019/03/21 in programming , Updated on: 2019/04/03

配列の並べ替え（ソート）

for文を使ったソート

NumPy 配列の単純なソートは、数行の Python コードで実現できる。例えば、リストから最小値を繰り返し見つけ、リストがソートされるまでスワップを繰り返す方法。

import numpy as np

def selection_sort(x):
    for i in range(len(x)): # xの長さ分だけ繰り返す
        swap = i + np.argmin(x[i:]) # i番目のx最小値インデックスを探す
        (x[i], x[swap]) = (x[swap], x[i])　# 要素をスワップしていく
    return x

x = np.array([2, 1, 4, 3, 5])
selection_sort(x)
# array([1, 2, 3, 4, 5])

リストを回すこのソートは、単純で有用だが、大規模な配列で処理が遅く使い物にならない。Ｎ個の値のリストに対して、これはＮ回のループを必要とし、その各々はスワップ値を見つけるために~Ｎ回の比較を行うためである。

Numpy を使った高速なソート

np.sort()

np.sort()メソッドを利用することで、上記の Python コードで実行するよりも高速に並べ替え結果が得られる。

x = np.array([2, 1, 4, 3, 5])
np.sort(x)
# array([1, 2, 3, 4, 5])

np.argsort()

同様に、np.argsort()を利用すると、並べ替えた後、要素ではなくそれらの要素のインデックスを返す。

np.argsort(x)
array([1, 0, 3, 2, 4])

# argsort結果を使って元の配列を並べ替え
x[np.argsort(x)]
# array([1, 2, 3, 4, 5])

行、列での並び替え

NumPy ソート機能は、axis引数を使用して多次元配列の特定の行または列に沿ってソートできる。
この機能は、ソートする各列または各行において独立した配列として並べ替えるため、行または列の値の関係はすべて失われる。

X = rand.randint(0, 10, (4,6))
print(X)
# [[6 7 2 0 3 1]
#  [7 3 1 5 5 9]
#  [3 5 1 9 1 9]
#  [3 7 6 8 7 4]]

各列で並び替え : 引数 axis=0 を渡す

np.sort(X, axis=0)
# array([[3, 3, 1, 0, 1, 1],
#        [3, 5, 1, 5, 3, 4],
#        [6, 7, 2, 8, 5, 9],
#        [7, 7, 6, 9, 7, 9]])

各行で並び替え : 引数 axis=1 を渡す

np.sort(X, axis=1)
# array([[0, 1, 2, 3, 6, 7],
#        [1, 3, 5, 5, 7, 9],
#        [1, 1, 3, 5, 9, 9],
#        [3, 4, 6, 7, 7, 8]])

np.partition() 部分並べ替え

配列全体ではなく、単に配列内の最小k値を見つけたい場合、np.partition()を利用する。
引数には、配列と数*Kを取り、任意の順序でパーティションの左側に最小のK値、右側に残りの値を持つ新しい配列を返す。

z = np.array([10000, 100, 10, 1, 100000, 9])

np.partition(z, 2)
# array([     1,      9,     10,  10000, 100000,    100])

np.partition(z, 4)
# array([     1,      9,     10,    100,  10000, 100000])

上の例で、(z, 2)の場合、元の配列から最小値2つ（1と9）を取り出し、配列の左側に持ってくる。残りの要素は任意の順で右側に寄せられる。同様に(z, 4)の場合は、元の配列から最小値4つ（1,9,10,100）が左に寄せられている。

行、列での部分並べ替え

np.sort()関数同様に、2次元配列の行（axis=1）、列（axis=0）においてもnp.partition()関数が利用できる。

X = rand.randint(0, 10, (4, 6))
X
# array([[8, 6, 8, 7, 1, 0],
#        [6, 6, 7, 4, 2, 7],
#        [5, 2, 0, 2, 4, 2],
#        [0, 4, 9, 6, 6, 8]])

np.partition(X, 3, axis=1)
# array([[0, 1, 6, 7, 8, 8],
#        [2, 4, 6, 6, 7, 7],
#        [2, 0, 2, 2, 4, 5],
#        [4, 0, 6, 6, 8, 9]])