如何高效化简分数？自定义浮点数类约分函数性能优化咨询

现有实现的核心问题 #

1. simplify1、simplify2逻辑不完整：仅用最大229的素数试除，若分子分母的公因子大于229，无法完全约分，结果正确性无法保障；且遍历全部素数的额外开销很高，公因子偏大时等同于做无用功。
2. 手动实现的欧几里得算法（simplify3）效率过低：纯Python循环的执行速度远低于Python内置的C实现接口。
3. 过度调用：1974次化简存在大量不必要的中间调用，放大了性能损耗。

具体优化手段 #

1. 替换为内置GCD接口 #

Python 3.5+ 标准库math模块内置的gcd函数是底层C实现，执行效率是纯Python手写辗转相除法的数十倍，同时自动处理了大数运算的优化。注意math.gcd仅返回非负结果，需要额外处理符号、分子为0的边界情况，优化后代码如下：

import math
class fractionnum:
    def __init__(self,up,down):
        self.up=up
        self.down=down

    def simplify(self):
        # 统一符号：约定分母始终为正，符号放在分子
        if self.down < 0:
            self.up = -self.up
            self.down = -self.down
        # 分子为0时直接归一化
        if self.up == 0:
            self.down = 1
            return
        # 计算最大公约数
        common_divisor = math.gcd(abs(self.up), self.down)
        self.up //= common_divisor
        self.down //= common_divisor

仅这一项修改就能让化简函数的性能提升10~30倍。

2. 可选：小素数试除前置（适合高频小数值场景） #

如果你的场景中大部分分数的公因子都是小素数，可以在调用GCD前先除尽2、3、5、7、11这几个高频小素数，进一步降低GCD计算的数值大小：

def simplify(self):
    if self.down < 0:
        self.up = -self.up
        self.down = -self.down
    if self.up == 0:
        self.down = 1
        return
    # 先除尽高频小素数
    small_primes = (2,3,5,7,11)
    for p in small_primes:
        while self.up % p == 0 and self.down % p == 0:
            self.up //= p
            self.down //= p
        if self.up == 1 or self.down == 1:
            return
    common_divisor = math.gcd(abs(self.up), self.down)
    self.up //= common_divisor
    self.down //= common_divisor

3. 减少不必要的化简调用 #

• 中间计算步骤可以延迟化简：比如连续的加减乘运算可以先累计计算，每3~5步再做一次化简，不用每一步运算都化简。
• 增加化简触发阈值：仅当分子或分母的绝对值超过指定阈值（比如10000）时才触发化简，小数值运算时不需要频繁约分。

4. 缓存重复计算结果 #

如果业务场景中存在大量重复的分子分母组合，可以对化简结果做缓存，避免重复计算：

from functools import lru_cache

# 把化简逻辑抽为静态函数加缓存
@lru_cache(maxsize=4096)
def reduce_fraction(up, down):
    if down < 0:
        up = -up
        down = -down
    if up == 0:
        return (0, 1)
    common_divisor = math.gcd(abs(up), down)
    return (up//common_divisor, down//common_divisor)

class fractionnum:
    def __init__(self,up,down):
        self.up=up
        self.down=down
    def simplify(self):
        self.up, self.down = reduce_fraction(self.up, self.down)

内容的提问来源于stack exchange，提问作者The_spider