python - 找到减少分数的最有效方法

Question

正如标题所暗示的那样，我一直在努力寻找减少分数的最有效方法(即 10/20 -> 1/2)，我想出了这个。

def recursive(n, d):
    i=1
    loop = True

    while loop == True:
        i += 1
        if n % i == 0:
            if d % i == 0:
                loop = False

        if i > min(n, d):
            return f'{n} / {d}'

    nn = n // i
    nd = d // i
    return recursive(nn, nd), f'{n}/{d} Common D: {i}'

我的思考过程是在最坏的情况下，这将计算到分子、分母对的最小值 - n/d 在 (N) 中进行计算过程。如果分数首先要减少，它就会这样做。这样做会减少 (N)，即首先需要计数的数量。

例如，给定一个随机分数，如 206/202，它会立即将其一分为二并再次调用该函数，新的调用只需要计数到 101，因此执行有关 (N/2) 次计算。

为了测试这一点，我做了一个控制函数，它总是计数到 n/d 对中的最小值(因此总是进行 N 次计算)，如下所示:

def big_O(n, d):
    list_ = [f'{n} / {d} OG']
    for iteration in range(2 ,min(n, d)+1):
        if n % iteration == 0:
            if d % iteration == 0:
                list_.append(f'{n//iteration} / {d//iteration} Common D: {iteration}')
    return list_

然后我用一个 janky timer I had on hand和一个随机数生成器:

def gen():
    return randint(1,1000), randint(1,1000)

尽管令我惊讶的是，我的函数执行得非常糟糕，但我并没有保存很多结果，但这里有一个非常能说明其余结果:

给定 100,000 个样本

SIMPLE: ORDERED BY SPEED

1. frac big O -- 2.3903738830000023 seconds
2. frac recursive -- 8.184171485 seconds

这让我感到震惊，因为我认为在最坏的情况下，由于获得不可约分数的运气不好，它们应该大致相等!所以我计算了生成器得出无法减少的分数的次数，我在大约 60% 的时间内得到了一些东西，我心想，

"Ok, what if I make them all even. Then given the logic above (206/202), surely my function should be faster."

def gen_even():
    return randrange(2,2002,2), randrange(2,2002,2)

结果是!

有 100,000 个样本

SIMPLE: ORDERED BY SPEED

1. frac.big_O() -- 4.2074602940000005 seconds
2. frac.recursive() -- 7.840177308999998 seconds

稍微好一点……但还是更糟!怎么会这样？!我不明白。之后我看了很多很多不同的东西，但最后还是想不通。然而，我确实发现了一些更有趣的事实，例如一旦分数可以减少两次 (即 12/8 : 6/4 : 3/2) 然后我的函数开始变得更好了还有多少减少量。

例如这个生成函数:

def genx4():
    return randint(1,1000)*4, randint(1,1000)*4

结果是这样的:

100,000 个样本

SIMPLE: ORDERED BY SPEED

1. frac recursive -- 6.605415995000001 seconds
2. frac big O -- 8.567245255000003 seconds

如果你用 *1000 替换 *4 它们看起来像这样

只有 100 个样本!

SIMPLE: ORDERED BY SPEED

1. frac recursive -- 0.014295906999997499 seconds
2. frac big O -- 2.250979277999999 seconds

除了为什么它只在这里好？!我不知道，所以如果读到这里的任何人有什么要说的，从关于减少分数的不同可能解决方案到为什么我的递归函数在上述情况下更差，请继续，也谢谢非常感谢您的宝贵时间!

Answer 1

对于“最有效”的解决方案，您只需寻找 n, d 的 GCD，因此 Euclidean algorithm在 O(log(max(n,d)) 乘法中解决这个问题。除非你是理论家或处理大量数字，否则可能不值得尝试优化太多。例如，请参见, the wiki on greatest common divisors 了解有关 GCD 计算的更多信息，但总而言之，您必须使用输入在“数千位”范围内的快速乘法算法才能开始优于普通乘法。

对于令人惊讶的计时结果，这可能是由于 while loop overhead与 Python 内部的 for 循环相比。尝试反汇编这两个函数——for 循环迭代在 C 中完成，而 while 循环迭代在 Python 字节码中完成，后者速度较慢。

在您测量的短时间范围内，性能可能非常难以预测。因此，对许多短循环进行计时可能会告诉您更多有关语言循环实现效率的信息，而不是代码的算法效率。

当您的输入变大时，您只会看到与渐近预测相符的结果这一事实并不令人惊讶——这是渐近分析的核心思想。