質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

89.10%

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

解決済

回答 2

投稿

  • 評価
  • クリップ 0
  • VIEW 402

tiitoi

OpenCV総合1位

質問内容

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 座標で昇順ソートした場合

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 2

checkベストアンサー

+2

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))

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/07/11 13:17

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

    キャンセル

+1

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における「並べ替えの際に役立つ基本ノウハウ」を容易に仕込むのに役立つと思います。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/07/11 13:21 編集

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

    キャンセル

  • 2019/07/11 14:07

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

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 89.10%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

同じタグがついた質問を見る