Pythonソートの速さを比べてみた: インスタンスのリストをソート #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が使用するソートアルゴリズムが気になりますが、ひとまず。