【使用Python实现算法】03 标准库（数字与数学模块）

本期向大家介绍一些 Python 中用于处理数字和数学方面的标准库。

math 数学模块

作为 LeetCode Python 环境中默认导入的标准库模块之一，math模块提供了很多非常有用的数字和数学方面的函数。

数论与表示函数（number theoretic and representation functions）

gcd与lcm，用于计算多个整数的最大公约数与最小公倍数。

assert math.gcd(12, 18) == 6
assert math.gcd(3, 5, 7) == 1

assert math.lcm(12, 18) == 36
assert math.lcm(3, 5, 7) == 105

ceil：向上取整，floor：向下取整，trunc：移除小数部分。 对于正数来说，trunc与floor是等价的。 对于负数来说，trunc与ceil是等价的。

assert math.ceil(1.2) == 2
assert math.floor(1.2) == 1
assert math.trunc(1.2) == 1

assert math.ceil(-3.5) == -3
assert math.floor(-3.5) == -4
assert math.trunc(-3.5) == -3

comb：计算组合数，perm：计算排列数，factorial：计算阶乘。

assert math.comb(5, 2) == 10
assert math.perm(5, 2) == 20
assert math.factorial(5) == 120

isclose：判断两个浮点数是否足够接近，默认的精度是1e-9。

assert math.isclose(1.0, 1.0 + 1e-10) == True
assert math.isclose(1.0, 1.0 + 1e8) == False
assert math.isclose(1.0, 1.0 + 1e8, rel_tol=1e8) == True

prod：计算输入的 iterable 中所有元素的积。 积的默认 start 值为 1。

assert math.prod([1, 2, 3, 4]) == 24
assert math.prod([1, 2, 3, 4], start=2) == 48
assert math.prod(iter([]), start=1) == 1

幂函数与对数函数

exp：返回 e 次 x 幂，其中 e = 2.718281… 是自然对数的基数。这通常比 math.e ** x 或 pow(math.e, x) 更精确。

log，log2, log10分别计算 x 以e，2，10为底的对数（对于求正整数的二进制位数，可以使用int.bit_length替代math.log2）。

三角函数

sin，cos，tan：计算三角函数值。

assert math.sin(math.pi / 2) == 1.0
assert math.isclose(math.cos(math.pi / 3), 0.5)
assert math.isclose(math.tan(math.pi / 4), 1.0)

asin，acos，atan：计算反三角函数值。

assert math.asin(1) == math.pi / 2
assert math.isclose(math.acos(0.5), math.pi / 3)
assert math.atan(1.0) == math.pi / 4

dist：计算两个点（可以超过二维）的欧几里得距离。

assert math.dist([0, 0], [1, 1]) == math.sqrt(2)
assert math.dist([0, 0, 0], [3, 4, 12]) == 13.0

fractions 有理数（分数）模块

fractions标准库提供了精确的有理数（分数）类型Fraction。

可以使用多种形式初始化Fraction对象

>
    >
    >
     from fractions import Fraction
>
    >
    >
     Fraction(16, -10)
Fraction(-8, 5)
>
    >
    >
     Fraction(123)
Fraction(123, 1)
>
    >
    >
     Fraction()
Fraction(0, 1)
>
    >
    >
     Fraction('3/7')
Fraction(3, 7)
>
    >
    >
     Fraction(' -3/7 ')
Fraction(-3, 7)
>
    >
    >
     Fraction('1.414213 \t\n')
Fraction(1414213, 1000000)
>
    >
    >
     Fraction('-.125')
Fraction(-1, 8)
>
    >
    >
     Fraction('7e-6')
Fraction(7, 1000000)
>
    >
    >
     Fraction(2.25)
Fraction(9, 4)
>
    >
    >
     Fraction(1.1)
Fraction(2476979795053773, 2251799813685248)
>
    >
    >
     from decimal import Decimal
>
    >
    >
     Fraction(Decimal('1.1'))
Fraction(11, 10)

属性与方法

numerator:简分数形式的分子。 denominator:简分数形式的分母。 as_integer_ratio():回由两个整数组成的元组，两数之比等于该分数的值且其分母为正数。

f = Fraction(3, 9)
assert f.numerator == 1
assert f.denominator == 3
assert f.as_integer_ratio() == (1, 3)

limit_denominator(max_denominator=1000000):找到并返回一个 Fraction 使得其值最接近 self 并且分母不大于 max_denominator。 此方法适用于找出给定浮点数的有理数近似值：

assert Fraction('3.1415926535897932').limit_denominator(1000) == Fraction(355, 113)

或是用来恢复被表示为一个浮点数的有理数：

数学计算

Fraction 对象可以像int对象和float对象一样进行各种数学计算，并且可以和其他数值类型混用。

assert Fraction(1, 2) + Fraction("1/3") == Fraction(5, 6)
assert Fraction(1, 2) * 2 == 1
assert pow(4, Fraction(1, 2)) == 2

random 随机数模块

random模块用于生成伪随机数。

整数类函数

randrange：从指定范围内返回一个随机数。

assert random.randrange(10) in range(10)
assert random.randrange(1, 10) in range(1, 10)
assert random.randrange(2, 10, 2) in [2, 4, 6, 8]

randint(a, b)：返回随机整数 N 满足 a = N = b。相当于 randrange(a, b+1)。

序列用函数

choice(seq)：从非空序列 seq 返回一个随机元素。 shuffle(x[, random])：就地将序列 x 随机打乱位置。 sample(population, k, *, counts=None)：返回从总体序列或集合中选择的唯一元素的 k 长度列表。 用于无重复的随机抽样。

实值分布

random()：返回 [0.0, 1.0) 范围内的下一个随机浮点数。 uniform(a, b)：返回一个随机浮点数 N ，当 a = b 时 a = N = b ，当 b a 时 b = N = a 。

在算法实现中使用 random 模块

LeetCode 中有一些设计类题目的主题与随机数有关，例如在无限长度的数据流中生成随机数。比较合适的解决方案是蓄水池抽样算法，算法实现中需要用到标准库的random模块。

class Solution:
    def __init__(self):
        self.size = 0
        self.candidate = -1

    def insert(self, num: int) ->
     None:
        self.size += 1
        if random.randrange(self.size) == 0:
            self.candidate = num

    def getRandom(self) ->
     int:
        return self.candidate

我之前还在寻找列表中半数以上的元素的题目中使用过random模块，时间复杂度为 O(n)，不会使用额外空间。

def getMostFreq(nums: list[int]) ->
     int:
    while True:
        if nums.count(n := random.choice(nums)) >
     len(nums) // 2:
            return n

statistics 数值统计模块

statistics模块提供了用于计算数字数据的数理统计量的函数。

平均值以及对中心位置的评估

这些函数用于计算一个总体或样本的平均值或者典型值。 mean()：数据的算术平均数（“平均数”）。 fmean()：快速的，浮点算数平均数。 geometric_mean()：数据的几何平均数 harmonic_mean()：数据的调和均值 median()：数据的中位数（中间值） median_low()：数据的低中位数 median_high()：数据的高中位数 median_grouped()：分组数据的中位数，即第 50 个百分点。 mode()：离散的或标称的数据的单个众数（出现最多的值）。 multimode()：离散的或标称的数据的众数（出现最多的值）列表。 quantiles()：将数据以相等的概率分为多个间隔。

对分散程度的评估

这些函数用于计算总体或样本与典型值或平均值的偏离程度。 pstdev()：数据的总体标准差 pvariance()：数据的总体方差 stdev()：数据的样本标准差 variance()：数据的样本方差

对两个输入之间关系的统计

这些函数计算两个输入之间关系的统计值。 covariance()：两个变量的样本协方差。 correlation()：两个变量的皮尔逊相关系数。 linear_regression()：简单线性回归的斜率和截距。

总结

利用 Python 标准库中的这些数字和数学相关的模块，可以有效提高算法实现中数值计算部分的编码效率。

声明：本文内容由网友自发贡献，本站不承担相应法律责任。对本内容有异议或投诉，请联系2913721942#qq.com核实处理，我们将尽快回复您，谢谢合作！