多个双打

的字典序考虑如果我要为了字典序的path_costs列表的类类型的双打多个双打

class path_cost { 
    double length; 
    double time; 
};

，我有一个问题。请继续阅读:)

如果我使用确切的相等，等价测试，像这样

bool operator<(const path_cost& rhs) const { 
    if (length == rhs.length) return time < rhs.time; 
    return length < rhs.length; 
}

产生的顺序很可能是错误的，因为一个小的偏差（例如，由于在的计算数值不准确长度）可能导致长度测试失败，例如

{ 231.00000000000001, 40 } < { 231.00000000000002, 10 }

错误地持有。

如果我替代地使用像这样

bool operator<(const path_cost& rhs) const { 
    if (std::fabs(length-rhs.length)<1-e6)) return time < rhs.time; 
    return length < rhs.length; 
}

的公差，则排序算法可以可怕失败由于< - 运算符不再传递（即，如果一个< B和B < C，则一个< c可能不成立）

任何想法？解决方案？我曾考虑过划分实际行，以便每个分区内的数字都被认为是相等的，但这仍然会在平等测试失败但是不应该出现太多情况。

（由James柯伦，希望解释问题UPDATE）：给出的数字：

A = {231.0000001200，10}
B = {231.0000000500，40}
C = {231.0000000100，60}
- 则为a.length & b.length个通过7-E7不同，所以我们使用时间，和A < B.
- b.length个& C.Length由4-E7不同，所以我们使用时间，和B < C.
- 则为a.length & C.Length 1.1-E6不同，所以我们使用长度，A > C.

（由Esben摩西汉森更新）这不是纯粹的理论。当给定非传递式排序算子时，标准排序算法往往会崩溃或更糟糕。这正是我一直在争论的（和男孩是有趣的调试;））

来源

2010-07-14 Esben Mose Hansen

你真的只想要比较功能吗？

为什么不先按长度排序，然后将这些对分成您认为相同的长度，然后按时间在每个组中排序？

按照长度进行排序，您可以应用所需的任何启发式，以确定长度的“相等”，以进行分组。

来源

2010-07-14 17:14:50

这实际上并不是一个坏主意，尽管很简单。需要做一些工作才能做到恰到好处，但这绝对是可以做到的。 – 2010-07-14 19:07:28

我不熟悉你的应用程序，但我愿意打赌，点之间的距离图比浮点数的舍入误差大很多数量级。因此，如果两个条目仅有四舍五入错误，它们基本上是相同的，它们在列表中出现的顺序没有区别。从常识的角度来看，我没有理由担心。

来源

2010-07-14 14:02:00

正如我上面写的那样，问题是当传递性失败时，常见的排序算法不再被很好地定义，在我的情况下，它们只是崩溃。 – 2010-07-14 14:40:26

如果您不尝试调整数字，您不会遇到那种失败。如果他们始终以微小的数量排队，他们将始终如一地 - 正确地排序。浮点数没有什么神秘之处，它们在中期比较中不会改变它们的值。总结：不要混淆数字，你不会有传递性问题。 – 2010-07-14 14:57:19

我没有调整任何数字，所以这不是问题。我记得，问题是一个排序的范围被推断为包含一个值，但实际上没有。因此它结束了运行范围的末端，并进入未分配的内存=>崩溃。你会注意到，例如std :: sort要求排序运算符是“严格弱排序”，这意味着传递性。 – 2010-07-14 19:13:19

对于普通的double s，您永远无法获得100％的精度。你说你害怕使用公差会影响程序的正确性。你真的测试过了吗？你的程序实际需要什么样的精确度？

在最常见的应用中，我发现只要有一个像1e-9的容差就足够了。当然，这一切都取决于你的应用程序。您可以估计您所需的准确度水平，并将公差设置为可接受的值。

如果即使失败了，也就是说double根本无法满足您的需求。这种情况极不可能发生，但如果您需要非常高精度的计算，则会出现这种情况在这种情况下，您必须使用任意的精度包（例如Java中的BigDecimal或类似C的GMP）。再次，只有在没有其他方式时选择此选项。

来源

2010-07-14 14:13:49 MAK

我试过了，它失败了。问题是，在一定的概率下，传递性失败，应用程序出现故障。我有一个解决方法（涉及在中间结果中使用长双），但我想知道一般问题。当然，以前有人看过这个问题？容差与我们使用的相当接近。这些数字部分来自标签设置/ A *算法，部分来自硬币或LP解决方案。 – 2010-07-14 14:38:51

我不认为你将能够做到你想要的。基本上你似乎是说在某些情况下，你想忽略a> b并假装a = b的事实。我敢肯定，你可以构造一个证明，如果a和b在差值小于一定值时等价，那么a和b对于a和b的所有值都是等价的。沿着线的东西：

对于C的公差和两个数A和B，其中不失一般性A的损失> B，则存在D(n) = B+n*(C/10)其中0<=n<=(10*(A-B))/(C)使得平凡d（n）是d的公差范围内（正-1）和D（n + 1），因此等同于它们。另外D（0）是B和D（（10 *（A-B））/（C））= A，所以A和B可以说是等价的。

我认为解决这个问题的唯一方法就是使用分区方法。比如乘以10^6，然后转换为int shoudl分区相当不错，但意味着如果您有1.00001 * 10^-6和0.999999 * 10^-6，那么它们会出现在不同的分区中，这可能不是我们想要的。

然后，问题就变成了查看你的数据，以找出如何对其进行最佳分区，这是我无法帮助的，因为我对数据一无所知。 :)

P.S.算法实际上是否在给定算法时崩溃，或者只是在遇到特定的无法解决的情况时？

来源

2010-07-14 15:06:43 Chris

排序算法非常非常偶然地崩溃---我们只在一个数据集上遇到问题，并且只有在编译时使用-O2（这与我们认为的协处理器的80位内部表示形式有关）。发生崩溃的原因是该算法在列表的一端因排序而不可能发生的情况下发生。 – 2010-07-15 08:37:36

这很有道理。我想知道是否有一些魔法使它能够以某种方式测试比较函数，以查看它是否可行。如果是这样的话，我会留下深刻的印象。 ;-)并感谢一个有趣的问题。我以前没有真正想过这种事情。 :) – Chris 2010-07-15 08:45:18

我能想出两个解决方案。

您可以仔细选择排序算法，当比较不及格时不会失败。例如，quicksort不应该失败，至少如果你自己实现它。（如果您担心quicksort的最坏情况行为，您可以先将该列表随机排列，然后对其进行排序。）

或者您可以扩展宽容补丁，使其成为等价关系并恢复传递性。有标准union-find algorithms来完成与等价关系的任何关系。在应用union-find之后，您可以用每个等价类的长度替换为一致值（比如平均值），然后按照您想要的排序进行排序。对医生浮点数来防止虚假的重新排序感到有点奇怪，但它应该起作用。

其实，莫伦说得很好。您可以先按长度排序，然后将容差范围内的邻居链接在一起，然后在第二个键的每个组内执行子排序，而不是联合并查找。这与我的第二个建议有相同的结果，但这是一个更简单的实现。

来源

2010-07-14 15:34:23

回答

相关问题