Python - ソートする際に左辺、右辺両方を引数にとる比較関数を指定する方法

Question

質問内容

Python の sorted() の key 引数でソートする際に比較関数を指定できるようになっていますが、左辺、右辺両方を引数にとる比較関数を指定する方法はありますでしょうか。
C++ の場合、ソートする関数に以下のように左辺 (left-hand-side, lhs)、右辺 (right-hand-side, rhs) 両方を引数にとる比較関数を指定できますが、ソートする関数を自作する以外で Python でこれを実現する方法がわかりません。

struct Point
{
    double x;
    double y;
};

std::sort(points.begin(), points.end(), 
    [](const Point &lhs, const Point &rhs) -> bool
{ 
    return lhs.y != rhs.y ? lhs.y > rhs.y : lhs.x > rhs.x; 
});

そのような事をしたい背景

右辺、左辺両方を引数にとる比較関数でないと、ソートできないケースが出てきたのが動機です。
sorted() の key 引数に関数を指定できますが、1つの引数をとる関数しか指定できないため、やりたいことが実現できないでいます。
ソート関数自体を実装すればいいと思いますが、標準ライブラリまたは numpy などの外部ライブラリの関数で可能であれば、やり方を教えていただきたいです。

import matplotlib.pyplot as plt
import numpy as np


def draw_2d_points(points):
    """2次元の点列を描画する。
    """
    fig, ax = plt.subplots()
    ax.grid()
    ax.scatter(points[:, 0], points[:, 1])
    for i, p in enumerate(points):
        ax.annotate(i, p, fontsize=14)
    plt.plot()


# 形状が (NumPoints, 2) である格子状の点列を作成する。
X, Y = np.meshgrid(np.arange(10.0), np.arange(10.0), indexing="xy")
points = np.column_stack([X.ravel(), Y.ravel()])  # [(N, M), (N, M)] -> (N*M, 2)

# 点列に [-0.1, 0.1] の一様分布に従う乱数を加算する。
points += np.random.uniform(-0.1, 0.1, points.shape)

# シャッフルする。
np.random.shuffle(points)
draw_2d_points(points)  # 図1

# 単純に y > x 順でソートすると、加えたノイズの影響で左下から順番に並ばない。
points = np.array(sorted(points, key=lambda p: (p[1], [0])))
draw_2d_points(points)  # 図2

# ソート関数自体を実装すれば実現できるが、それ以外に方法がないかという疑問
def bubble_sort(arr, comp):
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):
            if comp(arr[j], arr[j + 1]):
                temp = arr[j].copy()  # a, b = b, a 方式だと view がコピーされてしまうため
                arr[j] = arr[j + 1]
                arr[j + 1] = temp

# 指定したい比較関数
# y の差が 0.5 より大きい場合は y 座標で昇順、そうでない場合は x 座標で昇順ソートする。
my_comp = lambda a, b: a[1] > b[1] if abs(a[1] - b[1]) > 0.5 else a[0] > b[0]

bubble_sort(points, my_comp)
draw_2d_points(points)  # 図3

図1 シャッフル後

図2 y > x 順でソートした場合

図3 y の差が 0.5 より大きい場合は y 座標で昇順、そうでない場合は x 座標で昇順ソートした場合

Answer 1

functools.cmp_to_keyを使えばできると思います。

https://qiita.com/norioc/items/cb533d009aa63453df40

import numpy as np
import functools

my_comp = lambda a, b: a[1] - b[1] if abs(a[1] - b[1]) > 0.5 else a[0] - b[0]

points = np.array(sorted(points, key=functools.cmp_to_key(my_comp))

Comments

[tiitoi]

functools.cmp_to_key を使うと、そのような関数を指定することができたのですね。
知らなかったので、勉強になりました。ご回答ありがとうございます。

Answer 2

bsdfanさんが既に回答しておられますが、ちょっと蛇足的コメントを・・・

---

C/C++やJavaをPythonより先に学ぶと「比較関数を指定する並べ替え」が自然な仕様に思えてしまいます。実際Python 2までは比較関数を指定するアプローチだったみたいです。しかし実は「比較キーを取り出す関数を指定する」ことでも「比較関数を指定する」のと同様の汎用性があるといえます。

比較関数my_compで順序を決めるようにしたいなら「そのような論理で大小が決まるクラスを定義し、key関数でそのクラスのインスタンスを返すようにすればよい」わけです。

class MySortedKey:
    def __init__(self, value):
        self.value

    def __lt__(self, that):
        return my_comp(self.value, that.value)

# bubble_sort(points, my_comp)
points.sort(key=MySortedKey)

ただ、「比較関数を指定した方が比較キーを一々生成するよりメモリー消費をせずに並べ替えができるだろうに」とお考えになるだろうと思います。C/C++のプログラミングを経験するとどうしてもそういうところに目がいきます。Pythonはなぜキー「だけ」を指定するソート機能にしたんでしょうね。

https://docs.python.org/ja/3/howto/sorting.html#the-old-way-using-decorate-sort-undecorate

なんかをみると「安定ソートを実現する際など、並べ替え対象の列とは別の列を生成してからそれを用いてソートする」というイディオムを「プログラマーが一々配慮しなくてもよくする＝＞無用のものにする」というのが動機の一つだったのかもしれないと思いました。そうした方が「より広い範囲の並べ替え機能をより単純なアプローチでカバーできる」というわけです。

---

参考：リファレンスの以下からPython 3のソートノウハウの参考情報にたどり着けます。

Python標準ライブラリー > 組み込み関数 > sorted
https://docs.python.org/ja/3/library/functions.html#sorted

Python標準ライブラリー > 組み込み型 > シーケンス型 > list > sort
https://docs.python.org/ja/3/library/stdtypes.html#list.sort

上記の説明の中の

旧式の cmp 関数を key 関数に変換するには functools.cmp_to_key() を使用してください。

また本件とは直接関係ありませんが、

ソートの例と簡単なチュートリアルは ソート HOW TO を参照して下さい。

なんて記述もあります。Python 3における「並べ替えの際に役立つ基本ノウハウ」を容易に仕込むのに役立つと思います。

Comments

[tiitoi]

なるほど。2系までは比較関数を指定するスタイルだったのですね。
また現状の仕様でも __lt__ を定義することでやりたいことはできたのですね。思いつきませんでした。
大変参考になるご回答ありがとうございます。

[KSwordOfHaste]

自分も最初「キーしか指定するものが用意されてない」ことに疑問をもったのでtiitoiさんの疑問はよくわかる気がしました。関連することをおそらく調べられるであろうことから本回答は蛇足かと思ったのですが「ちょっと前の自分に回答するようなつもりでWHYについてコメントしてみるのも一興」と思い筆をとった次第です。