Ccmmutty logo
Commutty IT
0 pv2 min read

pandas.DataFrame().sort_valuesはデフォルトで不安定なソートアルゴリズムを使用する

https://cdn.magicode.io/media/notebox/blob_NVZWRPV

概要

pandas.DataFrameで任意の列の値を用いてソートを行う際,sort_values[1]^{[1]}メソッドを使用するが,デフォルトのソートアルゴリズムはクイックソートであり,不安定なソートになっている。
しかし,状況によってはマージソートなどで安定にソートしたいこともある。その場合は,引数でkind="mergesort"もしくはkind="stable"を与えることで実現できる。

実装例

以下にソートの対象列に重複する値が多い場合のデータを用意し,kindを指定しているか否かで結果の違いを確認するサンプルコードを示す。
import numpy as np
import pandas as pd

np.random.seed(812)

# 雑にデータを作る。
data = []
for i in range(ord("a"), ord("a") + 1000):
    data.append([chr(i), np.random.randint(24, 26)])

df = pd.DataFrame(data, columns=["name", "age"])
print(df.head())
# age 列でソートする
sorted_default_df = df.sort_values("age")
sorted_mergesort_df = df.sort_values("age", kind="mergesort")

print(sorted_default_df.head())
print(sorted_mergesort_df.head())
出力は以下のようになる。
name  age
0    a   25
1    b   24
2    c   24
3    d   25
4    e   25

    name  age
666    ˻   24
352    ǁ   24
819    Δ   24
820    Ε   24
569    ʚ   24

  name  age
1    b   24
2    c   24
6    g   24
7    h   24
8    i   24

結果

DataFrameのindexに注目する。 安定ソートならばname列がbである行が先頭に来るはずが,デフォルトのsort_values()では666行目が先頭に来ており,そのあとのindexも昇順でも降順でもなくなっている。 対して,kind="mergesort"を指定した場合は,順序が保たれた状態でソートされていることがわかる。
クイックソートとマージソートの違いとして,マージソートの使用するメモリはクイックソートの倍必要になることがあげられる[2]^{[2]}。マージソートを使用する際にはメモリが十分に足りていることを確認してから使用すればよいだろう。

参考文献

  1. pandas.DataFrame.sort_values
  2. ソートを極める! 〜 なぜソートを学ぶのか 〜

Discussion

コメントにはログインが必要です。