比較の背後にある数学 #5:順序付けアルゴリズム

要素のコレクションを並べ替えるには、ある要素が他の要素よりも小さい場合を判断する並べ替え述語を提供する必要があります。この述語は、cppreference.Wait に従って、「等価クラスで厳密な合計順序付けを誘導する」必要があります。 P>

今後の C++ 宇宙船オペレーターは、3 者間比較を実装します。 < の結果を返すことができる単一の関数です 、 ==> しかし、これに関連する「強い等式」や「弱い順序付け」などの用語は、数学の知識がないと多少混乱します。

このシリーズでは、等号と順序付けの背後にある数学について説明し、比較演算子と宇宙船演算子を実装するための具体的なガイドラインを示します。

このシリーズを終了するには、順序付けが必要なアルゴリズムと、3 者間比較を使用してそれらを実装する方法について説明しましょう。

注: <=> の C++ 言語規則 この投稿を書いてから変更されました。現在のルールについては、https://jonathanmueller.dev/talk/cppcon2019/ を参照してください。このブログ投稿は古くなっています。

実装ヘルパー

標準ライブラリには、std::sort() のように順序付けが必要なアルゴリズムとクラスがいくつかあります。 または std::set .しかし、この順序付けは、operator< を定義する述語を渡すことによって実装されます。 、つまり true を返します 最初の引数が 2 番目の引数よりも小さいと見なされる場合。そして型 std::less operator< のみを使用するデフォルトの述語です .

3 者間比較、つまり _ordering のいずれかを返す述語を使用して実装したいと考えています。 C++20 の型 (前の部分を参照)。これにより、アルゴリズムでの使用がいくらか容易になります。

次に default_ordering これは小さなクラスですか:

struct default_ordering
{
    template <typename T, typename U>
    auto operator()(const T& lhs, const U& rhs) const noexcept
    {
        return std::compare_3way(lhs, rhs);
    }
};

前に説明したように、「三方比較」の一般的なスペルは std::compare_3way です。 、しない operator<=> .

また、std::less と比較して 2 つの変更を加えました :まず、順序付け自体はテンプレートではなくメンバー関数です。これにより、2 つの異なる型を相互に比較できます。C++14 は std::less<> を追加しました。 (ここで T デフォルトは void です ) これもそのように見えます。

次に、無条件に noexcept しました 比較は投げるべきではないからです。

標準ライブラリでは std::greater を使用できます std::less の代わりに 順序を逆にしたい場合。ここでは reverse_ordering 次のようになります:

struct reverse_ordering
{
    template <typename T, typename U>
    auto operator()(const T& lhs, const U& rhs) const noexcept
    {
        auto result = std::compare_3way(lhs, rhs);
        switch (result)
        {
        // swap less and greater
        case std::partial_ordering::less:
            return std::partial_ordering::greater;
        case std::partial_ordering::greater:
            return std::partial_ordering::less;

        // don't change if equivalent or unordered
        default:
            return result;
        }
    }
};

新しい 3 者間比較には、複数の種類の順序付けもあります。必要なときに特定の述語を確実にするために、いくつかの述語を書きましょう:

template <class Ordering, typename T, typename U>
using ordering_category = std::decay_t<decltype(std::declval<Ordering>()
                                            (std::declval<T>(), std::declval<U>()))>;

template <class OrderingCategory>
struct is_strong_ordering
: std::is_convertible<OrderingCategory, std::strong_ordering>
{};

template <class OrderingCategory>
struct is_weak_ordering
: std::is_convertible<OrderingCategory, std::weak_ordering>
{};

template <class OrderingCategory>
struct is_partial_ordering
: std::is_convertible<OrderingCategory, std::partial_ordering>
{};

Ordering によって返される順序カテゴリを提供する小さなヘルパーがあります。 T の と U 暗黙の変換 is_partial_ordering によるものです。 順序付けが強い順序付けの場合などにも当てはまります。

それでは、いくつかのアルゴリズムを実装してみましょう。ほとんどのアルゴリズムでは、実際には 2 つのオブジェクト間に完全な関係を持たせる必要はなく、一方が他方よりも小さいかどうかだけが必要であることがわかります。

しかし、その情報だけを計算する述語を渡す方が確実に効率的ですか?

一般的なケースでは、それほど多くはありません。アセンブリ レベルでは、単純に減算を行う整数の 3 方向比較用の命令が 1 つあります。その場合、符号が答えになります。同様に、std::strcmp() また、3 者間比較も行います。LLVM には、1 つの結果のみを考慮し、それに応じて最適化する 3 者間比較を検出する最適化機能があります。

ただし、同等性のみが必要な場合は、完全な関係を要求するとコストが高くなります!2 つのコンテナーの同等性が必要な場合は、すぐに false を返すことができるためです。 サイズが異なる場合。3 者間比較では、辞書順で要素ごとに比較する必要があります。

最大要素と最小要素を見つける

私たちのタスクは単純です:要素のシーケンスが与えられた場合、与えられた順序関係に従って「最大/最小」の要素を見つけたいのですが、最初に、「最大のもの」をもう少し正確に定義しましょう。最初にパート 2 をお読みください。

値のセットがある場合 S そのセットのいくつかの順序付けを、要素 m ∈ S と呼びます 最大要素です 他の要素 s ∈ S より小さくない場合 .したがって、順序が の場合 -注文、m ≤ s s ≤ m の場合のみ true 同様に真です。つまり、要素は同等です。そして < の場合 -注文、m < s は真ではありません。同様に、m' ∈ S 最小限の要素です 他のどの要素 s ∈ S よりも大きくない場合 .

セットのいくつかの特別な要素について述べている定義に出くわすときはいつでも、考える必要がある 2 つの質問があります:

<オール>
  • この要素は常に存在しますか?
  • そのプロパティを持つ要素が複数存在することはありますか?
  • 質問 1 にはすぐに「いいえ」と答えることができます。すべての数の集合は両端で無限であるため、最大要素または最小要素はありません。ただし、無限のメモリがないため、これらの集合はプログラミングには関係ありません。とにかく、すべてのセットは有限です。

    しかし、最大 (最小) 要素のない (空でない) 有限集合はありますか?

    良い答えは:いいえ、ありません。空でない有限集合にはすべて最大要素と最小要素があるため、アルゴリズムは常に何かを返すことができます。

    また、2 番目の質問にもすぐに「いいえ」と答えることができます:最大要素が複数回ある場合はどうなるでしょうか? または、真の等価性がなく、最大要素が複数の他の要素?

    では、その質問を絞り込んでみましょう。複数の非同等の最大要素が存在する可能性がありますか?私たちのアルゴリズムの目的では、同等の要素はすべての意図と目的に対して「等しい」と見なされます。弱い順序付けは、強い順序付けと同じくらい優れています。

    そして、あなたはその質問にノーと言いたくなるかもしれません:最大要素が他のすべての要素よりも小さくない場合、それよりも大きい要素はあり得ません! そして、これは真です... (厳密な) 全順序について. 数の有限集合は常に 1 つの最大要素 (最大数) を持ちます。

    全体の順序付けでは、「少なくない」は「より大きいまたは同等」を意味します。しかし、部分的な順序付けの場合、「小さくない」は「比類のない」という意味にもなります。

    セット {ø, {1}, {2}} のセットを考えてみましょう 、つまり空のセット、1 を含むセット および 2 を含むセット .前に見たように、サブセット関係 半順序です。さらに、{1} ø ⊆ {1} のような極大要素です {2} ⊆ {1} ではありません 、だから {1} は他の要素よりも小さくありません。しかし {2} 同じ理由で最大要素です!どちらでもない {1} または {2} 比較できないため、他の要素よりも小さいため、両方とも最大要素です。

    そのため、有限集合の場合、常に少なくとも 1 つの最大/最小要素が存在しますが、半順序の場合、複数の非等価要素が存在する可能性があります。

    最大 (最小) 要素が 1 つしかない場合は、m ∈ S という特別な名前を付けます。 最高です 要素が他のすべての要素より大きいか等しい場合、条件はわずかに異なります:s ≤ m すべての s ∈ S に対して true でなければなりません .同様に、少なくとも 要素は、他のすべての要素より小さいか同等です。

    これまで見てきたように、すべてのセットに最大の要素があるわけではありませんが、1 つある場合は 1 つしかありません。また、全順序付けがある場合、最大の要素は 1 つしか存在できないため、常に 1 つになります。最大の要素全順序集合の最大値とも呼ばれます 、最小要素最小 .

    したがって、すべての最大要素を見つけるアルゴリズム、存在する場合は最大要素を見つけるアルゴリズム、および全順序付けの最大要素を見つけるアルゴリズムが必要です。

    標準ライブラリ アルゴリズム std::max_element() 実際には、シーケンスの最大の要素を返します。比較述語は完全な順序付けである厳密な弱い順序付けを定義する必要があるため、常に 1 つ存在します (またはシーケンスは空です)。

    それでは、まず始めましょう:

    template <typename ForwardIt, class Ordering>
    ForwardIt maximum(ForwardIt begin, ForwardIt end, Ordering order)
    {
        // we need a total ordering, i.e. at least `std::weak_ordering`
        static_assert(is_weak_ordering<decltype(order(*begin, *begin))>::value);
    
        if (begin == end)
            return end;
        
        // the first one is the maximum so far
        auto maximum = begin;
        for (cur = std::next(begin); cur != end; ++cur)
        {
            if (order(*maximum, *cur) < 0)
                // found an element that is bigger
                maximum = cur;
        }
    
        return maximum;
    }
    
    template <typename ForwardIt>
    ForwardIt maximum(ForwardIt begin, ForwardIt end)
    {
        return maximum(begin, end, default_ordering{});
    }
    

    これは標準のアルゴリズムであり、特別なことは何もありません。イテレータを最大値、つまり end まで返します。 シーケンスが空の場合。順序付けのないバージョンは default_ordering を渡すだけです .

    半順序付けのアルゴリズムは、複数の最大要素が存在する可能性があるため、より興味深いものです。したがって、結果は実際には反復子のコンテナーになります:

    template <typename ForwardIt, class Ordering>
    std::vector<ForwardIt> maximal_elements(ForwardIt begin, ForwardIt end, Ordering order)
    {
        std::vector<ForwardIt> result; // the candidates
        for (auto cur = begin; cur != end; ++cur)
        {
            // remove all candidates that are less than the current one 
            auto new_result_end = std::remove_if(result.begin(), result.end(),
                    [&](ForwardIt iter) { return ordering(*iter, *cur) < 0; });
            result.erase(new_result_end, result.end()); 
    
            // insert current one if it is not less for all candidates
            auto is_maximal = std::all_of(result.begin(), result.end(),
                    [&](ForwardIt iter) { return ordering(*cur, *iter) != std::partial_ordering::less; });
            if (is_maximal)
                result.push_back(cur);
        } 
        return result;
    }
    

    このアルゴリズムはより複雑です.これまでのところ最大の要素のコンテナがあります.候補よりも大きい要素が見つかった場合は候補が削除され、それより小さくない場合は新しい要素が追加されます.

    「not less」の綴りは ordering(*cur, *candidate) != std::partial_ordering::less であることに注意してください。 または !(ordering(*cur, *candidate) < 0) しかしそうではない ordering(*cur, *candidate) >= 0 .最後は false です std::partial_ordering::unordered の場合 それはまったく問題ありませんが!

    さらに、これは 2 次アルゴリズムであることに注意してください。しかし、それ以上のことはできません。極端な場合、どの要素も比較できず、すべての要素を他のすべての要素と比較する必要があると判断する必要があります。

    そして最後に greatest_element() アルゴリズムは単純です:

    template <typename ForwardIt, class Ordering>
    ForwardIt greatest_element(ForwardIt begin, ForwardIt end, Ordering order)
    {
        auto maximals = maximal_elements(begin, end, order);
        if (maximals.size() == 1)
            return maximals.front();
        else
            return end;
    }
    

    最大要素が 1 つだけある場合はそれを返し、それ以外の場合は end を返します。 .

    最小限のバージョンと最適化 (つまり、maximum() を使用) maximal_elements() で 全体の順序付けがある場合) は、読者の演習として残します。

    要素の並べ替え

    要素のシーケンスと順序付けが与えられた場合、その順序付けに従って要素を並べ替え、並べ替えたいと思うかもしれません。完全な順序付けの場合、それを行う方法は 1 つしかありません。それを行うアルゴリズムは皆さんよく知っているので、これ以上議論するつもりはありませんが、部分的な順序付けについては、比較できない要素があるため、より興味深いものです:相互に関連する順序付けには 2 つの方法があり、どちらも正しいです!

    しかし、半順序でシーケンスをソートするアルゴリズムも知っているでしょう。これを有向グラフとして扱うことができます。頂点はシーケンスの要素であり、a からのエッジがあります。 ba ≤ b の場合 .次に、トポロジカル ソートを実行できます グラフ上で。結果は、a の頂点の順序です。 b の前に来ます それらが接続されている場合、つまり a ≤ b の場合 .

    悲しいことに、落とし穴があります。トポロジカル ソートは常に成功するとは限らず、グラフ内のサイクルを処理しません。

    ただし、頂点 a の潜在的な循環を考慮してください 、 bc どこで a ↦ bb ↦ cc ↦ a .それは a ≤ b を意味します と b ≤ cc ≤ a .したがって、推移的なプロパティによっても b ≤ ac ≤ b 、これは頂点が等しいことを意味します。

    そして、これは理にかなっています。それらを順序付ける一意の方法がないため、トポロジカル ソートではそれらを順序付けることができません。それらはすべて同等です。

    ここではコードを書きませんが (このブログ記事を今日公開したいので)、部分的な並べ替えを使用して並べ替える計画は次のとおりです。グラフを作成し、トポロジカルに並べ替えます。直接次々とサイクルの。

    トポロジカル ソートの複雑さは、通常、頂点とエッジの両方で線形ですが、グラフの構築は一般的に 2 次です。特定の要素よりも大きい要素を知るには、それらすべてをチェックする必要があります。

    ソートされたシーケンスでの検索

    並べ替えられたシーケンスを取得したら、バイナリ検索を使用して特定の要素を検索できます。アルゴリズムは、中央の要素とターゲット要素を比較します:

    • 同等であれば、完了です。
    • 中間が少ない場合は、後半を見て繰り返します。
    • 中間が大きい場合は、前半を見て繰り返します。

    これは、アルゴリズムが全順序付けでのみ機能することを直接的に意味します。中間の要素がターゲットと比較できない場合、どこを見ればよいかわかりません!

    また、ソートされたシーケンスは実際には必要ないことに注意してください。ターゲットよりも小さいすべての要素、次にターゲット、さらにターゲットよりも大きいすべての要素があれば十分です。要素の実際の順序は、以上は関係ありません。

    std::lower_bound() の簡単な実装 ターゲット以上の最初の反復子を返す は、次のようになります。

    template <typename ForwardIt, typename T, typename Ordering>
    ForwardIt lower_bound(ForwardIt begin, ForwardIt end, const T& target, Ordering order)
    {
        // we need a total ordering
        static_assert(is_weak_ordering<decltype(order(*begin, target))>::value);
    
        auto length = std::distance(begin, end);
        while (length != 0)
        {
            // get the middle element
            auto half_length = length / 2;
            auto mid         = std::next(begin, half_length);
    
            if (order(*mid, target) < 0)
            {
                // less than, look at the second half
                begin = std::next(mid);
                length -= half_length + 1;
            }
            else
                // greater, look at the first half
                length = half_length;
        }
        return begin;
    }
    

    ここで、default_ordering という事実を使用できます。 2 つの異なるタイプの引数を取ることができます:std::string のシーケンスを持つことができます const char* を探します .一時的な std::string を作成せずに比較を行うことができます

    これまでは同じ型の比較しか見てこなかったので、最後に混合型の比較について話しましょう。数学的に順序付けは一連の値で定義され、C++ 型には特定の一連の値があることを思い出してください。

    混合タイプの比較では、2 つのタイプの値のセットが同じであるか、セット間にマッピングが存在する必要があります。最初のカテゴリの例は std::string です。 と std::string_view — どちらも「文字列」を表すため、値のセットは同じです。2 番目のカテゴリの例は std::chrono::seconds です。 と std::chrono::milliseconds 、それらは異なるものを表していますが、それらを簡単に変換して共通の値のセットを作成できます。std::stringconst char* const char* であるため、より興味深いものです 単に char へのポインタである可能性もあります しかし、一般的な意味は「C 文字列」であるため、その表現を使用する比較が定義されています。

    ルール: 2 つの型が相互に暗黙的に変換可能であるが、変換のコストが高すぎる場合は、混合型比較を作成します。

    変換は、型が同じ値のセットまたは互換性のある値のセットを持っていることを示す良い指標です。また、コンストラクターとキャストの設計に関するガイドラインに従うことができます。std::string の比較 と const char* その規則に従います。

    ルール: 2 つの型が明示的に変換可能であるが、変換のコストがそれほど高くない場合は暗黙的に変換可能である場合は、混合型比較を作成します。

    これは std::string_view です std::stringexplicit のみです 費用がかかりすぎるからです。ただし、比較は変換する必要がないため、変換可能にする必要があります。

    注文済みコンテナ

    最後に std::set を見てみましょう -like コンテナーは、3 者間比較を使用して実装されます。実装は単純で、述語を少し変更するだけです。ただし、設計はもう少し興味深いものです。

    まず、これは望ましくないと主張します:

    template <typename T, class Ordering = default_ordering>
    class ordered_set;
    

    デフォルトが default_ordering の場合 カスタム述語を指定せずに比較演算子を実装した型のみを使用できます。また、ほとんどの型にはそれらを含めるべきではないと以前に主張しましたが、これは煩わしいことです。

    例:std::complex 数学的に意味のあるデフォルトの順序を提供することはできません。ただし、 log n を行うには 一部が必要な二分探索によるルックアップ 順序付け:意味をなす必要はありません。

    そこで、新しいデフォルト key_ordering を使用することを提案します :

    template <class Key>
    struct key_ordering
    {
        template <class U>
        std::weak_ordering operator()(const Key& key, const U& lookup) noexcept
        {
            return default_ordering{}(key, lookup);
        }
    };
    

    これはテンプレートになり、デフォルトは default_ordering です .しかし、型はそれを特殊化して、ルックアップのためだけに異なる順序を提供することができます.std::complex たとえば、そうしたいと思うでしょう。

    しかし std::vector また、それを特殊化し、コンテナが最初に長さでソートされ、次に内容でソートされる順序を提供することもできます.これは明確に定義された順序ですが、直感的に期待するものではないため、 operator< ほとんどのコンテナが異なる数の要素を持っていると、はるかに高速になるため、operator< よりも望ましいでしょう。 (特定の順序が必要な場合を除きます)。

    また、結果を std::weak_ordering にハードコーディングしました :二分探索は半順序では機能しません。

    std::string のルックアップを可能にするために、2 番目のパラメーターのテンプレートを引き続き保持します。 const char* で 、たとえば。カスタマイズにより、そこで型を制限できます。C++14 以降、これは std::set でもサポートされています。 これは「透過的な比較」と呼ばれます。ただし、カスタム コンパレータは明示的にオプトインする必要があります。

    このメカニズムを使用したセットの例は、私の flat_set です from foonathan/array.順序付けインターフェースは現時点で少し異なりますが、適応させる予定です.

    結論

    3 者間比較を使用してアルゴリズムを記述することは、通常の比較述部を使用してアルゴリズムを記述することとそれほど違いはありません。ただし、追加のカテゴリは、より一般的なアルゴリズムを提供したり、要件をより自然に表現したりするのに適しています。

    3 者間比較への切り替えは、新しい key_ordering を導入する機会でもあります 特に順序付けられたセットとマップ用に設計されています。この順序付けは意味をなす必要がないため、順序付けのない型に対してより高速に導入できます。

    3 者間比較を使用することの唯一の欠点は、同等性のみを求めるアルゴリズムの追加コストです。これらは、operator== に基づいて記述する必要があります。 .

    このシリーズが気に入った場合は、今すぐ私に連絡してください.他の演算子の背後にある数学についても書くかもしれません.