Pythonソートの速さを比べてみた: インスタンスのリストをソート

## はじめに

Pythonインスタンスのリストを、複数方法でソートし、速さを比較してみました。

## 検証シナリオ

Bookクラスのインスタンスリストをtitleの降順でソートします。
```
class Book:
  def __init__(self, title: str, author: str, price: int):
    self.title = title
    self.author = author
    self.price = price
```

## ソート方法

以下の5つの方法でソートし、処理時間を比較します。

- 1\. sorted()関数、key指定にlambdaを使ってソート
- 2\. sorted()関数、key指定にattrgetterを使ってソート
- 3\. リストのsort()メソッド、key指定にlambdaを使ってソート
- 4\. リストのsort()メソッド、key指定にattrgetterを使ってソート
- 5\. バブルソートを使ってソート

## サンプルコード

```sort.py
# Bookクラスのインスタンスリストをtitle降順でソート

from operator import attrgetter
from copy import deepcopy
import time

# Bookクラス: 比較演算と文字列化を定義
class Book:
  def __init__(self, title: str, author: str, price: int):
    self.title = title
    self.author = author
    self.price = price

  # 2つのインスタンスの'より小さい'比較演算
  def __lt__(self, book):
    return self.title.lower() < book.title.lower()

  # インスタンスの文字列化
  def __str__(self):
    return '"{}": \\{}'.format(self.title, self.price)

# 1. sorted()関数とlambdaを使ってソートし、ソート済みリストを返す(元のリストを変更しない)
def sorted_with_lambda(book_list):
  sorted_list = sorted(book_list, key=lambda b: b.title, reverse=True)
  return sorted_list

# 2. sorted()関数とattrgetterを使ってソートし、ソート済みリストを返す(元のリストを変更しない)
def sorted_with_attrgetter(book_list):
  sorted_list = sorted(book_list, key=attrgetter('title'), reverse=True)
  return sorted_list

# 3. リストのsort()メソッドとlambdaを使ってソートし、ソート済みリストを返す(元のリストを変更)
def list_sort_with_lambda(book_list):
  book_list.sort(key=lambda b: b.title, reverse=True)
  return book_list

# 4. リストのsort()メソッドとattrgetterを使ってソートし、ソート済みリストを返す(元のリストを変更)
def list_sort_with_attrgetter(book_list):
  book_list.sort(key=attrgetter('title'), reverse=True)
  return book_list

# 5. バブルソートを使ってソートし、ソート済みリストを返す(元のリストを変更)
def bubble_sort(book_list):
  for i in range(len(book_list) - 1, 0, -1):
    for j in range(0, i):
      # クラスBookの比較演算を使用
      if book_list[j] < book_list[j + 1]:
        # 要素を交換
        book_list[j], book_list[j + 1] = book_list[j + 1], book_list[j]
  return book_list

# インスタンスリストを出力(Bookクラスの文字列化メソッドを使用)
def print_book_list(book_list):
  for b in book_list:
    print(str(b))

# ソートの処理時間を計測(ループ回数、出力あり・なしを指定)
def measure(func, book_list, loop_count, to_print):
  print('========= {} ========='.format(func.__name__))
  start = time.perf_counter()
  for i in range(loop_count):
    sorted_list = func(deepcopy(book_list))
    if to_print:
      print_book_list(sorted_list)
  end = time.perf_counter()
  print('-------------------')
  print('処理時間: {:.3f} 秒'.format(end - start))

if __name__ == "__main__":
  book_list = [
    Book('Pythonプログラミング', '山田太郎', 300),
    Book('漫画で学ぶPython', '橋爪太郎', 400),
    Book('こんなときどうする', '金子太郎', 300),
    Book('アルゴリズムをPythonで学ぶ', '田頭太郎', 400),
    Book('プログラミング基礎', '渡辺太郎', 200),
    Book('ソートを速くしよう', '大倉太郎', 300),
    Book('実践で学ぶプログラミング基礎', '山田太郎', 300),
    Book('一週間でPythonマスター', '八鍬太郎', 100),
    Book('フローチャートを書いてみよう', '鈴木太郎', 300),
    Book('シーケンス図を書いてみよう', '庄司太郎', 400),
  ]

  LOOP_COUNT = 100000  # ソートの反復回数
  TO_PRINT = False  # リスト出力する・しない
  # LOOP_COUNT = 1  # ソートの反復回数
  # TO_PRINT = True  # リスト出力する・しない

  measure(sorted_with_lambda, book_list, LOOP_COUNT, TO_PRINT)
  measure(sorted_with_attrgetter, book_list, LOOP_COUNT, TO_PRINT)
  measure(list_sort_with_lambda, book_list, LOOP_COUNT, TO_PRINT)
  measure(list_sort_with_attrgetter, book_list, LOOP_COUNT, TO_PRINT)
  measure(bubble_sort, book_list, LOOP_COUNT, TO_PRINT)
```

## 実行1: それぞれのソート済みリストを出力してみる

- ソースコードで、以下2行を指定し実行
    - `LOOP_COUNT = 1  # ソートの反復回数`
    - `TO_PRINT = True  # リスト出力する・しない`
- 結果、いずれのソート済みリストも、title降順でソートされる

```
> python sort.py

========= sorted_with_lambda =========
"漫画で学ぶPython": \400
"実践で学ぶプログラミング基礎": \300
"一週間でPythonマスター": \100
"プログラミング基礎": \200
"フローチャートを書いてみよう": \300
"ソートを速くしよう": \300
"シーケンス図を書いてみよう": \400
"アルゴリズムをPythonで学ぶ": \400
"こんなときどうする": \300
"Pythonプログラミング": \300
-------------------
処理時間: 0.003 秒
... ...
```

## 実行2: 各ソートを10万回ずつ実行し、処理時間を計測

- ソースコードで、以下2行を指定し実行
    - `LOOP_COUNT = 100000  # ソートの反復回数`
    - `TO_PRINT = False  # リスト出力する・しない`
        - リスト出力を処理時間に含めないため、ソート済みリストを出力しない
- 計3回実行し、各ソートの処理時間を計測

```
> python sort.py
> python sort.py
> python sort.py
```

|ソート方法|1回目計測(秒)|2回目計測(秒)|3回目計測(秒)|
|-------|:-------:|:-------:|:-------:|
|1. sorted()とlambda|6.386|6.047|6.262|
|2. sorted()とattrgetter|6.016|5.848|6.051|
|3. sort()とlambda|5.759|5.791|5.954|
|4. sort()とattrgetter|5.754|5.781|5.933|
|5. バブルソート|7.830|8.195|7.973|


## 考察

- 組み込み関数が自前バブルソートより断然速い(予想とおり)
- 僅差ですが、sort()がsorted()より速い
- 僅差ですが、key指定はattrgetterがlambdaより速い


## おわりに

Pythonソートの速さを比較してみました。
Pythonが使用するソートアルゴリズムが気になりますが、ひとまず。