4

クイックソートが機能するには、すべての無限が等しい必要があることに気付きました。

言い換えれば、そのような基準は十分ではありません。

class Entity
{
public: 
   float value() const;
   bool valueIsInfinite() const;
};

class Criterium
{
    bool operator()(Entity left, Entity right)const
    {
        if (left.valueIsInfinite())
            return false;
        return left.value() < right.value();
    }
}

const Criterium criterium;
QVector<Entity> container;

qSort<container.begin(), container .end(), criterium>

基準に従ってすべての無限大が等しいわけではないため、この並べ替えは失敗します。不平等は、エンティティが演算子に入る順序によって異なります。そのような注文は失敗することがわかりました。

私はこのようなものが必要です:

class Criterium
{
    bool operator()(Entity left, Entity right)const
    {
        if (left.valueIsInfinite() && right.valueIsInfinite())
            return false;
        if (left.valueIsInfinite() && !right.valueIsInfinite())
            return false;
        if (!left.valueIsInfinite() && right.valueIsInfinite())
            return true;
        return left.value() < right.value();
    }
}

しかし、代わりに

   float Entity::value() const;
   bool Entity::valueIsInfinite() const;

メソッド、私はただ使いたい

   float Entity::value() const;

そして返してもらう

std::numeric_limits<float>::infinity();

場合には

bool Entity::valueIsInfinite() const;

true を返します。

今、私はこのアプローチをテストしましたが、うまくいくようです。しかし、私は無限が発生する可能性のある他の方法について心配しています。例えば：

float otherInfinity = exp(std::numeric_limits<float>::infinity());

この無限大は同じようです。しかし、私は確信したい。C++ 標準が浮動小数点演算の実装の詳細について言及していないことは知っていますが、gcc を使用すると、すべての場合に安全ですか? つまり、すべての無限大は gcc で等しく作成されますか? さまざまな機会に発生した無限を含む可能性のあるフロートのコンテナーをソートしても安全ですか?

4

2 に答える 2

10

NaN が存在しない場合、無限大は通常の operator で問題ありません<。

  • +∞ < +∞ は false:<反射的ではありません。
  • +∞ < x が true の場合、非無限値に対して x < +∞ は false:<反対称です。
  • +∞ < x が true で x < y が true の場合、+∞ < y が true:<は推移的です。
  • +∞ が x と比較できない (小さくもなく大きくもない) であり、x が y と比較できない場合、+∞ は y と比較できない:<等価性の推移性を表示します。

(同様のプロパティが -∞ に対して有効です)

NaN のないoperator<floatのこれらのプロパティを指定すると、厳密な弱い順序付けになるため、標準ライブラリ スタイルの順序付け操作に適しています。

ただし、NaN では、反対称性が崩れます。NaN < 1 は false であり、1 < NaN も false です。これは、提案された戦略と同様の方法で、すべての非 NaN の前または後にすべての NaN を並べることで解決できます。

struct Criterion
{
    bool operator()(Entity left, Entity right)const
    {
        // NaNs come before non-NaNs
        if (isnan(left.value()) && isnan(right.value()))
            return false;
        if (!isnan(left.value()) && isnan(right.value()))
            return false;
        if (isnan(left.value()) && !isnan(right.value()))
            return true;
        return left.value() < right.value();
    }
}

( isnanC++11 標準ライブラリで見つけることができ、または として非常に簡単に実装できますreturn x != x;)

これにより、NaN < 1 を true として、1 < NaN を false として取得しますが、他のプロパティは引き続き保持されます。

于 2012-07-25T02:17:38.057 に答える
0

これを使用する場合：

bool operator()(Entity left, Entity right)const
{
    return !(left.valueIsInfinite() && right.valueIsInfinite())
        && left.value() < right.value();
}

次に、無限は同じ順序であると見なされます。別のものより前に来るものはないからです...

于 2012-07-25T02:10:20.243 に答える