1. ティア表（Tier List）とは
ティア表（Tier List）は、ゲームのキャラ評価や好きな食べ物ランキングなど、
「主観的評価を段階的に分類したい」ときに便利な手法です。
ティア表を作成するサイトはいくつかあります。
しかし、全体を見ながら手動で決めていくと、どこの段階に入れればいいか迷ってしまい、正確なティア表を作成できない可能性があります。
そこで、今回はユーザーが2択を選択していくことでてきたティア表であれば正確なのではと思い、アルゴリズムを実装してみました。
2. できたもの
対象を6種類の果物で実行すると
- ユーザーが2択を選択する（繰り返し）
- 順位が決まったら3ティアに分けられる
という簡単な流れになります。
ティア表作成プログラム
==================================================
対象アイテム: リンゴ, バナナ, オレンジ, イチゴ, メロン, ブドウ
アイテム数: 6個
ティア数: 3 (S, A, B)
比較を開始します。2つのフルーツのうち、どちらが好きか選択してください。
比較 1回目:
1: バナナ
2: オレンジ
どちらが上? (1/2): 2
・
・
・（繰り返し）
・
・
比較 10回目:
1: バナナ
2: メロン
どちらが上? (1/2): 2
==================================================
ティア表の結果
==================================================
【Sティア】
- ブドウ
- リンゴ
【Aティア】
- オレンジ
- イチゴ
【Bティア】
- メロン
- バナナ
総比較回数: 10回
==================================================
3. 全体コード
全体コードはこちらです
import random
from typing import List, Tuple
class TierListCreator:
def __init__(self, items: List[str]):
self.items = items
self.comparisons = 0
self.comparison_results = []
def compare(self, item1: str, item2: str) -> int:
self.comparisons += 1
print(f"\n比較 {self.comparisons}回目:")
print(f"1: {item1}")
print(f"2: {item2}")
while True:
choice = input("どちらが上? (1or2): ").strip()
if choice in ['1', '2']:
result = int(choice)
self.comparison_results.append((item1, item2, result))
return result
print("1か2を入力してください")
def merge_sort(self, items: List[str]) -> List[str]:
if len(items) <= 1:
return items
mid = len(items) // 2
left = self.merge_sort(items[:mid])
right = self.merge_sort(items[mid:])
return self.merge(left, right)
def merge(self, left: List[str], right: List[str]) -> List[str]:
result = []
i = j = 0
while i < len(left) and j < len(right):
choice = self.compare(left[i], right[j])
if choice == 1:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
def create_tiers(self, ranked_items: List[str], num_tiers: int = 5) -> dict:
tier_names = ['S', 'A', 'B', 'C', 'D', 'E', 'F'][:num_tiers]
items_per_tier = len(ranked_items) / num_tiers
tiers = {}
for i, tier_name in enumerate(tier_names):
start = int(i * items_per_tier)
end = int((i + 1) * items_per_tier) if i < num_tiers - 1 else len(ranked_items)
tiers[tier_name] = ranked_items[start:end]
return tiers
def display_tier_list(self, tiers: dict):
print("\n" + "="*50)
print("ティア表の結果")
print("="*50)
for tier_name, items in tiers.items():
print(f"\n【{tier_name}ティア】")
for item in items:
print(f" - {item}")
print(f"\n総比較回数: {self.comparisons}回")
print("="*50)
def main():
print("ティア表作成プログラム")
print("="*50)
# サンプルデータ
items = ["リンゴ", "バナナ", "オレンジ", "イチゴ", "メロン", "ブドウ"]
print(f"\n対象アイテム: {', '.join(items)}")
print(f"アイテム数: {len(items)}個")
# ティア数の設定
num_tiers = 3
print(f"ティア数: {num_tiers} (S, A, B)")
# ティア表作成
creator = TierListCreator(items)
print("\n比較を開始します。2つのフルーツのうち、どちらが好きか選択してください。")
ranked_items = creator.merge_sort(items)
tiers = creator.create_tiers(ranked_items, num_tiers)
creator.display_tier_list(tiers)
if __name__ == "__main__":
main()
4. アルゴリズム解説
マージソートでランキングをつけられており、
- 項目リストを半分に分割
- 左右を再帰的にソート
- 最後に「左の先頭 vs 右の先頭」を比較してマージする
という処理を繰り返し、最終的に昇順のリストを得るアルゴリズムです。
比較処理をユーザー入力に置き換えている点が今回のポイントです。
4.1. 比較関数（compare）
マージソートが比較したい2つの要素を渡すと、compare関数がユーザーに質問を投げかけ、1か2を選択させます。
def compare(self, item1: str, item2: str) -> int:
print(f"1: {item1}")
print(f"2: {item2}")
choice = input("どちらが上? (1or2): ").strip()
return int(choice)
4.2. compareの結果がマージ結果を決める
選択されたほうがより上位と判定され、結果リストに追加されていきます。
if choice == 1:
result.append(left[i])
else:
result.append(right[j])
4.3. 比較回数
総当り比較だと
N(N-1)/2
ですが、マージソート方式の比較では大体
N log N
程度となり、項目数が増えると比較回数が爆発しがちなのを抑えられます。
5. まとめ
今回はマージソートを利用したティア表の作成アルゴリズムについて書きました。
この手法を用いた簡単なアプリを後日作りたいと思います。