3

考虑一类类型的双打

class path_cost {
   double length;
   double time;
};

如果我想按字典顺序排列 的列表path_costs，我有问题。继续阅读:)

如果我像这样对相等性测试使用完全相等

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;
}

那么排序算法可能会严重失败，因为 <-operator 不再是可传递的（也就是说，如果 a < b 和 b < c 则 a < c 可能不成立）

有任何想法吗？解决方案？我考虑过对实线进行分区，以便每个分区内的数字被认为是相等的，但这仍然留下了太多相等测试失败但不应该失败的情况。

（James Curran 更新，希望能解释问题）：鉴于数字：

  • 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 Mose Hansen 更新）这不是纯粹的理论。当给定非传递排序运算符时，标准排序算法往往会崩溃或更糟。这正是我一直在努力解决的问题（男孩调试起来很有趣；））

4

5 回答 5

4

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

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

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

于 2010-07-14T17:14:50.380 回答
1

我不认为你将能够做你想做的事。本质上，您似乎是在说，在某些情况下，您想忽略 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(n-1) 和 D(n+1) 的容差范围内，因此相当于他们。D(0) 也是 B 并且 D((10*(AB))/(C))=A 所以 A 和 B 可以说是等价的。

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

然后问题就变成了查看您的数据以找出如何最好地对其进行分区，因为我对您的数据一无所知，所以我无能为力。:)

PS 当给定算法时，算法是否真的会崩溃，或者只是在遇到特定的无法解决的情况时崩溃？

于 2010-07-14T15:06:43.503 回答
1

我可以想到两种解决方案。

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

或者您可以扩展您的公差补丁，使其成为等价关系并恢复传递性。有标准的联合查找算法来完成与等价关系的任何关系。应用 union-find 后，您可以将每个等价类中的长度替换为一致值（例如平均值），然后进行您想做的排序。医生浮点数以防止虚假重新排序感觉有点奇怪，但它应该工作。

事实上，Moron 提出了一个很好的观点。您可以先按长度排序，而不是联合和查找，然后将公差范围内的邻居链接在一起，然后在第二个键上的每个组内进行子排序。这与我的第二个建议具有相同的结果，但它是一个更简单的实现。

于 2010-07-14T15:34:23.930 回答
0

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

于 2010-07-14T14:02:00.270 回答
0

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

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

如果即使这样也失败了，这意味着这double根本不适合您的目的。这种情况不太可能发生，但如果您需要非常高精度的计算，就会出现这种情况。在这种情况下，您必须使用任意精度包（例如 Java 中的 BigDecimal 或C 中的GMP之类的东西）。同样，只有在没有其他方法时才选择此选项。

于 2010-07-14T14:13:49.163 回答