有效地检测有理数是否相等
有效地检测有理数是否相等
提问于 2016-11-22 03:31:01
我有一个由许多有理数组成的集合，每个有理数的分子和分母都存储为一个大的(数百或数千位)无符号整数。我希望能够有效地测试集合中任何给定的有理数a/b是否等于集合中的任何其他有理数c/d。
当然，最直接的方法是测试a*d == b*c，但我想要比计算完整产品更有效的方法。
关于我的特定用例的一些注意事项：
- 我将要测试的数据对实际上相等的可能性很高(因为我已经在预先计算，并首先通过它们的浮点近似来比较它们)，所以如果它们不相等，提前计算不会节省我太多时间。
- 我可以为每个数字预先计算额外的数据，但每个数字只会在少数比较中使用，所以昂贵的预先计算(例如素数分解)可能不会是worthwhile.
- Occasional假阴性是可以的，但假阳性是不行的。
我认为这在理论上可能是不可能的，但为了以防万一，把它抛给蜂群头脑。
回答 2
Stack Overflow用户
发布于 2016-11-29 01:49:11
通过比较位长度，可以过滤出许多不相等的分数对。设l( a ) = floor(log2(a)) +1 a的位长，若a/b = c/d，则l(a) + l(d) = l(c) + l(b)。
只有在长度之和相等的情况下，才可以在第一次比较长度和比较产品时使用此选项来加快速度。
Stack Overflow用户
发布于 2016-11-29 04:16:27
第二次尝试;)如果您必须重复检查新数字以进行集合包含，则应将相对质数小数存储在有序集合中。如果计数器相等，则集合的比较函数应首先比较计数器，然后再比较分母。比较可以在线性时间内完成，因此在具有M个项的有序集合中找到一个元素需要O(N log )步。减少分数的成本为O(N²)。因此，测试一个数字的容纳性需要O(N²+N log M)个步骤，并计算集合O(MN²)。
编辑：与使用排序或树集不同，您可以使用哈希集，从而将搜索所需的步骤减少到O(N²+ N) = O(N²)。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/40727929
复制相关文章
相似问题