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

Finding the Most Efficient Way to Reduce a Fraction

正如标题所暗示的那样,我一直在努力寻找减少分数的最有效方法 (i.e. 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(thus always doing N computations)中的最小值,如下:

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

这让我震惊,因为我认为在最坏的情况下,由于得到 un-reducible 分数的运气不好,它们应该大致相等!所以我计算了生成器得出无法减少的分数的次数,我得到了大约 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

稍微好一点...但仍然更糟!怎么会这样?!我不明白。之后我看了很多很多不同的东西,但最后还是想不通。然而,我确实发现了一些更有趣的事实,例如一旦分数可以减少两次 (i.e. 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

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

对于 'most efficient' 解决方案,您只是在寻找 n, d 的 GCD,因此 Euclidean algorithm solves this in O(log(max(n,d)) multiplications. Unless you're a theoretician or dealing with massive numbers, it's probably not worth trying to optimize much beyond that. See, for example, the wiki on greatest common divisors 了解有关 GCD 计算的更多信息,但总而言之,您会必须使用输入在 'thousands of digits' 范围内的快速乘法算法才能开始优于普通乘法。

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

在您正在测量的短 time-scales 中,性能可能是高度不可预测的。因此,对许多短循环进行计时可能会告诉您更多有关语言循环实现效率的信息,而不是代码的算法效率。

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