正如标题所示，我一直在尝试找到最有效的方法来简化一个分数 (例如 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_
我使用了一个粗糙的计时器和一个随机数生成器对它们进行了时间比较：
def gen():
return randint(1,1000), randint(1,1000)
然而，让我感到惊讶的是，我的函数表现得明显更差。我没有保存许多结果，但这里有一个结果相当具有代表性：
给定100,000个样本
简单：按速度排序
1. frac big O - 2.3903738830000023秒
2. frac recursive - 8.184171485秒
这让我感到震惊，因为我认为在最坏的情况下，由于运气不好得到了无法约分的分数，它们应该大致相等！所以我计算了生成器产生无法约分的分数的次数，结果大约是60%的时间，然后我想：
“好吧，如果我把它们都变成偶数，那么根据上述逻辑（206/202），我的函数肯定会更快。”
def gen_even():
return randrange(2,2002,2), randrange(2,2002,2)
结果如下：
样本数为100,000
简单：按速度排序
frac.big_O()-- 4.2074602940000005秒frac.recursive()-- 7.840177308999998秒
稍微好了一点...但仍然不够好！这怎么可能？我不明白。在此之后，我看了很多不同的东西，但最终还是没搞清楚。不过，我还是发现了一些有趣的事实，例如，一旦分数可以约分两次（即12/8:6/4:3/2），那么我的函数就会以更多的约分次数为因素变得更好。
例如，对于这个生成函数：
def genx4():
return randint(1,1000)*4, randint(1,1000)*4
结果看起来是这样的：
100,000个样本
简单：按速度排序
1. frac recursive -- 6.605415995秒 2. frac big O -- 8.567245255秒
如果用*1000替换*4，它们看起来像这样
仅使用100个样本！
简单：按速度排序
1. frac recursive -- 0.014295906999997499秒 2. frac big O -- 2.250979277999999秒
但是为什么只在这里才有效呢？我不知道，所以如果任何读到这里的好心人有什么想说的话，从减少分数到为什么我的递归函数比上面更糟等不同可能的解决方案，请随意发表，同时非常感谢您的时间！
timeit。 - Mark Ransom