2

浮動精度の問題については、浮動小数点数のカスタム比較関数を定義しました。

bool cmp(double a, double b)
{
    if(abs(a - b) <= eps) return false;
    return a < b;
}

次に、浮動小数点数の配列に対して sort を呼び出します。不適切な比較関数が原因で、並べ替えがセグメント エラーになると聞いたことがあります。cmpソートで正しく機能するのだろうか？一方でcmpは、関連付けルールを満たしています。しかし一方でcmp(x - eps, x) == false&&cmp(x, x + eps) == falseは という意味ではありませんcmp(x - eps, x + eps) == false。

ソートしたいのはpair<double, double>. 例えば：

(1,2), (2,1), (2.000000001, 0)

2 と 2.000000001 を同じと見なし、結果が次のようになることを期待したいと思います。

(1,2), (2.000000001, 0), (2,1)
4

3 に答える 3

5

std::sort厳密な弱い順序付けを定義する比較子が必要です。これは、とりわけ、次の条件を満たす必要があることを意味します。

  • と の 2つの項目を定義aしますb。a === b!cmp(a, b) && !cmp(b, a)
  • 同等性は推移的です: a === b&& b === c=>a === c

質問ですでに述べているように、関数cmp()はこれらの条件を満たしていないため、関数を .NET で使用することはできませんstd::sort()。アルゴリズムの結果が予測不可能になるだけでなく、実際にこの予測不可能性を探していない限り、これは悪いことです (参照) randomize:trueただしfalse、他のアルゴリズムでは、アルゴリズムが無限ループに入る可能性があります。

したがって、答えはノーです。プログラムがフリーズする危険を冒したくない限り、関数cmp()を使用することはできません。std::sort()

于 2012-10-05T11:34:43.157 に答える
4

なぜあなたはおおよそのより少ない比較をするのをわざわざするのですか？それは意味がありません。

配列を実際の値で厳密に並べ替えるだけです。

次に、近似比較関数を使用して、どの要素が等しいと見なすかを決定します。

（英語での同等物は、悪名高い「ほぼより良い」でしょう。考えてみてください。）

于 2012-10-05T11:14:30.140 に答える
-1

同様の値をグループ化する浮動小数点の比較関数を定義することができます。これを行うには、次のように丸めます。

bool cmp(double a, double b)
{
    const double eps = 0.0001;
    int a_exp;
    double a_mant = frexp(a, &a_exp); // Between 0.5 and 1.0
    a_mant -= modf(a_mant, eps); // Round a_mant to 0.00001
    a = ldexp(a_mant, a_exp); // Round a to 0.00001 * 10^a_exp
    // and the same for b
    int b_exp;
    double b_mant = frexp(b, &b_exp); 
    b_mant -= modf(b_mant, eps);  
    b = ldexp(b_mant, b_exp);
    // Compare rounded results.
    return a < b;
}

今はcmp(a,b)==trueそれを意味しa<b、a==bそしてa>b両方ともを意味しcmp(a,b)==falseます。

于 2012-10-05T11:44:57.667 に答える