Jiahong 的个人博客

凡事预则立,不预则废


  • Home

  • Tags

  • Archives

  • Navigation

  • Search

TensorFlow——计算图管理


整体总结

  • 在 TensorFlow 1.x 里,类型转换是把张量从一种数据类型转换为另一种数据类型的操作,可分为隐式类型转换和显式类型转换
  • 简单总结:
    • TensorFlow 会自动进行类型提升以确保操作数兼容
    • 如果类型不兼容,会抛出错误
    • 使用 tf.cast() 可以手动控制类型转换
    • 布尔类型可以参与数值运算(变成0或1),但建议做显示类型转换

显式类型转换(推荐使用)

  • 若要明确地把一个张量从一种数据类型转换为另一种数据类型,你可以使用 tf.cast 函数,下面是一个显式类型转换的示例:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    import tensorflow.compat.v1 as tf
    tf.disable_v2_behavior()

    # 创建一个整数类型的张量
    a = tf.constant([1, 2, 3], dtype=tf.int32)

    # 显式地将其转换为浮点数类型
    b = tf.cast(a, dtype=tf.float32)

    with tf.Session() as sess:
    result = sess.run(b)
    print("Result:", result)
    print("Data type:", b.dtype)
    • 在这个例子中,借助 tf.cast 函数把 a 从 int32 类型显式转换为 float32 类型
  • 注:在实际使用中,建议尽量采用显式类型转换,这样能让代码的意图更加清晰,也便于调试和维护


隐式类型转换(不建议)

  • 在TensorFlow 1.x中,部分操作会自动进行隐式类型转换。不过,这种转换并非在所有情形下都会发生,并且不同类型之间的运算可能会引发错误。通常,当操作涉及不同数据类型的张量时,TensorFlow会尝试把它们转换为兼容的类型

  • 下面是一个简单的示例:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    import tensorflow.compat.v1 as tf
    tf.disable_v2_behavior()

    # 创建两个不同类型的张量
    a = tf.constant(2, dtype=tf.int32)
    b = tf.constant(3.0, dtype=tf.float32)

    # 进行加法操作,会发生隐式类型转换
    c = a + b

    with tf.Session() as sess:
    result = sess.run(c)
    print("Result:", result)
    print("Data type:", c.dtype)
    • 在这个例子中,a 是 int32 类型,b 是 float32 类型。在执行加法操作时,TensorFlow 会把 a 隐式转换为 float32 类型,然后再进行计算

隐式类型转换规则

  • 在 TensorFlow 中,不同类型(dtype)的张量或常量相加时,TensorFlow 会尝试自动进行类型转换(type casting),以便使两个操作数的类型兼容。如果类型无法安全地转换,就会抛出错误
  • 自动类型提升 :当两个不同类型的张量或常量相加时,TensorFlow 会根据操作数的类型选择一个更“宽”的类型来存储结果。这种行为类似于 NumPy 的类型提升规则:
    • int32 和 float32 相加,结果会被提升为 float32
    • float32 和 float64 相加,结果会被提升为 float64
  • 不兼容的类型引发错误 :如果两个类型的张量无法安全地转换,TensorFlow 会抛出 TypeError 或类似的错误:
    • string 和 int32 是完全不同的类型,无法直接相加
    • complex64 和 float32 可能需要显式转换
  • 布尔类型的操作(特殊) :布尔类型(bool)在 TensorFlow 中被视为数值类型(True 等价于 1,False 等价于 0),但需要使用显示类型转换
    1
    2
    3
    4
    5
    a = tf.constant(True, dtype=tf.bool)     # bool 类型
    b = tf.constant(2, dtype=tf.int32) # int32 类型
    a = tf.cast(a, dtype=tf.int32) # 如果没有这一行,下面做加法时可能会报类型错误
    result = a + b # 自动将 bool 提升为 int32
    print(result) # 输出: tf.Tensor(3, shape=(), dtype=int32)

TensorFlow——计算图管理


一句话说明

  • 在 TensorFlow 1.x 版本中,tf.Graph() 用于创建一个新的计算图,而会话(tf.Session())则用于执行计算图中的操作
  • 本文将分别给出明确创建图(tf.Graph())和不明确创建图创建会话的示例,并说明它们之间的区别

不明确创建图

  • 当不指定图时,TensorFlow 会使用一个全局默认的计算图。以下是一个简单的示例:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    # 在TensorFlow 2.x中可以通过下面的代码替换 `import tensorflow as tf`,仍可在TensorFlow 2.x环境中使用TensorFlow 1.x
    import tensorflow.compat.v1 as tf
    tf.disable_v2_behavior()

    # 定义操作,使用默认计算图
    a = tf.constant(3.0)
    b = tf.constant(4.0)
    c = tf.add(a, b)

    # 创建会话并执行操作
    with tf.Session() as sess:
    result = sess.run(c)
    print("不使用 tf.Graph() 的结果:", result)
  • 在这个示例中,我们没有显式地创建计算图,TensorFlow 会使用默认的计算图来定义操作 a、b 和 c。然后创建一个会话并在该会话中运行操作 c,最终得到计算结果


明确创建图(使用tf.Graph())

  • 也可以使用 tf.Graph() 函数,创建一个新的独立计算图,并在这个图中定义操作。以下是示例代码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    # 在TensorFlow 2.x中可以通过下面的代码替换 `import tensorflow as tf`,仍可在TensorFlow 2.x环境中使用TensorFlow 1.x
    import tensorflow.compat.v1 as tf
    tf.disable_v2_behavior()

    # 创建一个新的计算图
    graph = tf.Graph()

    # as_default() 只在 with 上下文中生效,退出后默认图会恢复为原来的全局默认图
    with graph.as_default():
    # 在新的计算图中定义操作
    a = tf.constant(5.0)
    b = tf.constant(6.0)
    c = tf.add(a, b)

    # 创建会话并指定使用新的计算图
    with tf.Session(graph=graph) as sess:
    result = sess.run(c)
    print("使用 tf.Graph() 的结果:", result)
  • 在这个示例中,我们做了以下操作:

    • 首先使用 tf.Graph() 创建了一个新的计算图 graph
    • 然后使用 graph.as_default() 上下文管理器,将这个新的计算图设置为默认图,并在其中定义操作 a、b 和 c
    • 最后创建一个会话,并通过 graph=graph 参数指定该会话使用我们创建的新计算图,在会话中运行操作 c 并得到结果

多图管理(TensorFlow 1.x)

  • TensorFlow 1.x中创建和管理多个计算图的示例:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    import tensorflow as tf

    # 创建第一个计算图
    graph1 = tf.Graph()
    with graph1.as_default():
    # 在图1中定义变量和操作
    a = tf.constant(5, name='a')
    b = tf.constant(3, name='b')
    c = tf.add(a, b, name='sum')

    # 在图1中初始化所有变量
    init1 = tf.global_variables_initializer()

    # 创建第二个计算图
    graph2 = tf.Graph()
    with graph2.as_default():
    # 在图2中定义不同的变量和操作
    x = tf.constant(10, name='x')
    y = tf.constant(4, name='y')
    z = tf.multiply(x, y, name='product')

    # 在图2中初始化所有变量
    init2 = tf.global_variables_initializer()

    # 创建会话执行图1
    with tf.Session(graph=graph1) as sess1:
    sess1.run(init1)
    result1 = sess1.run(c)
    print("图1的结果:", result1) # 输出: 图1的结果: 8

    # 创建会话执行图2
    with tf.Session(graph=graph2) as sess2:
    sess2.run(init2)
    result2 = sess2.run(z)
    print("图2的结果:", result2) # 输出: 图2的结果: 40

多图管理的必要性

  • 隔离性 :不同的图完全隔离,变量和操作不会相互干扰。这在以下场景特别有用:
    • 同时运行多个模型
    • 比较不同模型结构
    • 隔离训练和推理图
  • 资源管理 :每个图有自己的资源集合,可以独立释放,避免内存泄漏
  • 命名空间 :不同图中的操作可以有相同的名称而不会冲突
  • 并行执行 :可以在不同线程中同时运行不同的图(每个线程有自己的会话)
  • 调试 :当出现问题时,可以更容易地定位是哪个图出现了错误

多图管理的最佳实践

  • 使用with graph.as_default():上下文管理器来明确操作属于哪个图
  • 会话(Session)和图(Graph)是一一对应的,需要为每个图创建独立的会话,明确关闭不再需要的会话以释放资源
  • 一般情况可以不用明确创建多个图 ,仅维护一个默认的图即可,更好的做法是在单个图中使用不同的名称作用域(namescope)来组织操作
  • 多线程运行时需要维护不同的图,确保图不会被同时访问(注:不同图的变量命名也可以相同,也就是可以使用相同的代码来定义)
  • 在 TensorFlow 2.x 中,默认启用了即时执行(Eager Execution)模式,不再需要显式地创建计算图和会话

关于图的作用域示例

  • as_default() 只在 with 上下文中生效,退出后默认图会恢复为原来的全局默认图:

    1
    2
    3
    4
    with new_graph.as_default():
    op1 = tf.constant(1) # 属于 new_graph

    op2 = tf.constant(2) # 属于全局默认图(不是 new_graph)
  • 嵌套多个 as_default() 的示例(不建议使用)

    1
    2
    3
    4
    5
    6
    7
    8
    g1 = tf.Graph()
    g2 = tf.Graph()

    with g1.as_default():
    a = tf.constant(1) # 属于 g1

    with g2.as_default():
    b = tf.constant(2) # 属于 g2
  • 通过 tf.get_default_graph() 可以检查当前默认图:

    1
    2
    with new_graph.as_default():
    print(tf.get_default_graph() is new_graph) # 输出 True

新增变量及其初始化

  • 在已经创建session后,依然是可以加入新的变量的,但是需要进行初始化才可以使用

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    import tensorflow as tf

    var1 = tf.Variable(3, dtype=tf.float32)
    var2 = tf.Variable(5, dtype=tf.float32)
    add_op1 = tf.add(var1, var2)

    sess = tf.Session()

    init_op = tf.global_variables_initializer() # 初始化所有变量
    sess.run(init_op)

    result1 = sess.run(add_op1)
    print("两个变量的和:", result1)

    # 在Session后继续创建变量
    var3 = tf.Variable(7, dtype=tf.float32)
    add_op2 = tf.add(add_op1, var3)

    init_new_var = tf.variables_initializer([var3]) # 初始化新创建的变量
    sess.run(init_new_var)

    result2 = sess.run(add_op2)
    print("三个变量的和:", result2)

    sess.close() # 显式关闭会话

    # 两个变量的和: 8.0
    # 三个变量的和: 15.0
  • 注意:TensorFlow 1.x中,所有变量都需要初始化(因为变量定义操作不会分配内存,只有在初始化后才会分配内存),重复初始化变量会将变量重置为初始化值

TensorFlow——变量定义及复用

定量定义及复用

  • 运行结果
  • 结果分析
  • 结论
    • trainable = None 与 trainable = True等价,也是trainable参数的默认值,会被添加到训练变量中
      • 只有当trainable = False时不会被添加到训练变量中
    • reuse参数取值为True,None,tf.AUTO_REUSE,False(说明文档没明确列出False,但尝试可以用)
      • True: 表示读取一个旧的同名变量,如没有则抛出异常
      • None: 表示继承父scope的情况,若没有父scope,则默认为创建新变量,此时有同名变量则会抛出异常
      • tf.AUTO_REUSE: 表示使用自动模式,没有同名变量,则创建一个,否则返回同名变量
      • False特殊:
        • 经测试,当reuse参数在variable_scope或者layer中使用时,False等价于None,会继承父scope的情况
      • 注意,reuse参数在variable_scope或者layer中使用时
        • 父:tf.AUTO_REUSE,子None,False => 最终tf.AUTO_REUSE
        • 父:tf.AUTO_REUSE,子True => 最终True
        • 父:True,子None,False => 最终True
        • 父:True,子tf.AUTO_REUSE => 最终tf.AUTO_REUSE
        • 父:None,False, 子 xxx => 最终 xxx
        • 对于多层的级联架构中,依然满足上面的规律,举例来说,中途任意一层有一个
    • reuse参数只在variable_scope或者layer中可以使用,tf.get_variable,name_scope,tf.Variable中都不可用
    • tf.Variable一定会新建变量,而且会在重名时自动修改变量名称
      • 注意, tf.Variable不等价于tf.get_variable中reuse=False的情况,后者在有同名变量时会报错

ML——对数似然及其变分下界


似然函数是什么?

  • 似然函数(Likelihood Function) :描述在给定模型参数下,观测数据出现的概率。对于一组独立同分布的观测数据 \(x_1, x_2, \cdots, x_n\) ,其似然函数 \(L(\theta)\) 可以表示为每个观测数据的概率密度函数的乘积 ,即:
    $$L(\theta)=\prod_{i = 1}^{n}p(x_i|\theta)$$
    • 其中 \(\theta\) 是模型的参数, \(p(x_i|\theta)\) 是在参数 \(\theta\) 下观测数据 \(x_i\) 出现的概率
  • 理解:似然的本质可以理解为概率(更准确说是描述概率值的函数),但一般来说,似然函数是关于参数 \(\theta\) 的函数(不同于普通的概率)

对数似然是什么?

  • 对数似然(Log Likelihood) :就是对似然函数取自然对数,得到:
    $$ll(\theta)=\ln L(\theta)=\sum_{i = 1}^{n}\ln p(x_i|\theta)$$
    • 取对数的主要原因是将乘积转化为求和,方便计算和分析,尤其是在处理大量数据时,乘积的计算可能会导致数值下溢,而对数运算可以避免这种情况

对数似然可以用来做什么?

  • 模型参数估计 :在最大似然估计中,通过最大化对数似然函数来估计模型的参数;因为对数函数是单调递增的,所以最大化似然函数等价于最大化对数似然函数

变分是什么?

  • 近似推断方法的目标是在难以直接计算概率分布的情况下,对目标分布进行近似求解
  • 常见近似推断方法有蒙特卡罗采样法(Monte Carlo Sampling)和变分推断法(Variational Inference, VI)两种
    • 蒙特卡罗采样法 :基于大数定律,通过从已知分布中进行大量随机采样,利用这些样本的统计特性来近似目标分布的期望、方差等统计量
      • 举例:要计算一个复杂函数在某个概率分布下的期望,可以通过从该分布中采样大量的点,计算函数在这些点上的值,然后求平均值来近似期望;
      • 方法:主要通过各种采样算法,如拒绝采样、重要性采样、马尔可夫链蒙特卡罗(MCMC)等方法来生成样本。以 MCMC 为例,它通过构建一个马尔可夫链,使其平稳分布为目标分布,然后从这个马尔可夫链中采样得到样本
    • 变分推断法 :一种基于优化的方法,通过定义一个分布族(比如高斯分布族),然后在这个分布族中寻找一个与目标分布最接近的分布(通常通过最小化两者之间的 KL 散度来实现)
      • 举例:对于一个难以直接处理的后验分布,我们可以假设一个具有特定形式(如高斯分布)的变分分布,然后通过调整变分分布的参数,使其尽可能接近真实的后验分布;
      • 方法:通过优化算法,如梯度下降、随机梯度下降等,来调整变分分布的参数,以最小化 KL 散度
  • 变分(Variational)这个词常常指隐含近似推断的思想,常常是通过优化函数(或分布)来近似复杂概率分布,解决复杂概率分布问题

对数似然的变分下界

  • 任意函数 \(F\) 的变分下界(Variational Lower Bound) :是一个用于估计函数 \(F\) 下界的函数 ,最大化变分下界可以间接实现最大化原始目标函数 \(F\)
  • 对数似然的变分下界(Variational Lower Bound) :是一个用于估计对数似然函数下界的函数 ,最大化变分下界可以间接实现最大化原始目标对数似然函数
  • 假设我们有一个概率模型,其中观测数据为 \(x\) ,隐变量为 \(z\) ,模型的参数为 \(\theta\) 。对数似然函数 \(\log p(x|\theta)\) 可以通过对联合概率 \(p(x,z|\theta)\) 进行积分得到,即:
    $$\log p(x|\theta)=\log\int_z p(x,z|\theta)dz$$
  • 变分推断的基本思想是引入一个变分分布 \(q(z)\) ,然后通过优化这个变分分布来逼近真实的后验分布 \(p(z|x,\theta)\) 。对数似然的变分下界 \(L(q)\) 定义为:
    $$L(q)=\mathbb{E}_{q(z)}[\log p(x,z|\theta)]-\mathbb{E}_{q(z)}[\log q(z)]$$
    • 其中 \(\mathbb{E}_{q(z)}\) 表示关于分布 \(q(z)\) 的期望

变分下界的推导

  • 根据 Jensen’s 不等式,对于凹函数 \(f\) 和随机变量 \(Y\) ,有 \(f(\mathbb{E}[Y])\geq\mathbb{E}[f(Y)]\)
  • 对于对数似然函数,我们有:
    $$
    \color{red}{\log p(x|\theta)}=\log\int_z p(x,z|\theta)dz=\log\mathbb{E}_{q(z)}\left[\frac{p(x,z|\theta)}{q(z)}\right]\color{red}{\geq}\mathbb{E}_{q(z)}\left[\log\frac{p(x,z|\theta)}{q(z)}\right]=\color{red}{L(q)}$$
    • 所以 \(L(q)\) 是对数似然 \(\log p(x|\theta)\) 的一个下界

变分下界的作用与应用

  • 近似推断 :通过最大化变分下界 \(L(q)\) ,可以找到一个最优的变分分布 \(q^*(z)\) ,使得它尽可能接近真实的后验分布 \(p(z|x,\theta)\)
    • 这样就可以用 \(q^*(z)\) 来近似计算后验分布的各种统计量,如均值、方差等,从而实现对隐变量的推断
  • 模型训练 :在一些基于概率模型的机器学习算法中,如变分自编码器(VAE),对数似然的变分下界被用作优化目标
    • 通过最大化变分下界 ,可以最大化对数似然函数 ,可以学习到模型的参数 \(\theta\)
  • 评估模型性能 :变分下界的值可以作为模型性能的一个评估指标
    • 当变分下界的值越大,说明模型对数据的拟合程度越好,同时也意味着变分分布 \(q(z)\) 对真实后验分布 \(p(z|x,\theta)\) 的近似效果越好

ML——归一化与标准化

本文总结归一化与标准化的理解和使用, 涉及到无量纲,中心化等知识, 但是并不完全


归一化

Normalization

  • 把数据变成[0,1]或[-1,1]的小数

  • 把有量纲表达式变成无量纲表达式,便于不同单位或量级的指标能够进行比较和加权

  • 归一化是一种简化计算的方式,即将有量纲的表达式,经过变换,化为无量纲的表达式,成为纯量

    • 无量纲的理解:
      • 通过某种数值变换去掉单位,的影响,比如”kg”和”g”都可以表示体重,但是前者的数字比后者小
      • 不管是”kg”还是”g”作为单位,无量纲后他们的数值应该是一样的
      • 无量纲的本质是说: 变换后, 单位不再影响数据的数值
  • 应用:

    • LR等用梯度下降时, 先使用数据归一化可以使得梯度下降速度加快(否则可能下降方向并不是最好方向)

归一化的不同方法

线性归一化
  • Min-Max Normalization
    $$ x_i’ = \frac{x_i-min(X)}{max(X)-min(X)}$$
  • 平均归一化
    $$ x_i’ = \frac{x_i-mean(X)}{max(X)-min(X)}$$
  • 上面两种归一化在新数据加入时最大最小值会变化,所以不能在线归一化
非线性归一化
  • 对数函数转换等

标准化

Standardization

  • 使每个特征中的数值平均变为0(将每个特征的值都减掉原始资料中该特征的平均)、标准差变为1
  • 数学描述
    $$x_i’ = \frac{x-mean(X)}{std(X)}$$

中心化

  • 平均值为0,对标准差无要求
  • 数学描述
    $$x_i’ = x-mean(X)$$

归一化 vs 标准化

不同点

  • 归一化是将样本的特征值转换到同一量纲下把数据映射到[0,1]或者[-1, 1]区间内,仅由变量的极值决定,因区间放缩法是归一化的一种
  • 标准化是依照特征矩阵的列处理数据,其通过求z-score的方法,转换为标准正态分布,和整体样本分布相关,每个样本点都能对标准化产生影响

相同点

  • 都能取消由于量纲不同引起的误差
  • 都是一种线性变换(都是对向量X按照比例压缩再进行平移)
  • 个人理解: 标准化可以看作是一种特殊的归一化

中心化 vs 标准化

  • 标准化 = 中心化 + 数据除以标准差(使得数据标准差为1)
  • 有些地方也把零均值归一化(Z-Score Normalization)称为标准化,公式与标准化相同

总结

  • 一些模型一般需要归一化
    • LR: 加快梯度下降过程(因为不同维度使用相同的学习率,所以容易造成走弯路)
    • KNN: 防止计算距离时大数吃小数的情况发生
    • PCA: 归一化后 \(X^TX\) 才能表示数据的协方差矩阵
    • 神经网络

关于神经网络为什么需要归一化?

数值问题
  • 归一化可以避免很多不必要的数值问题
    • 我理解的一种情况: 输入太大时, 权重太小, 容易造成精度问题, 数值太小时同理
  • 归一化可以避免梯度爆炸等问题
    • 个人理解: 如果数值很大的话, 梯度一般也会对应很大, 连续乘以后就容易造成梯度爆炸, 数值太小, 同理, 容易造成梯度消失
  • 加快学习
    • 与LR一样, 使用梯度下降优化神经网络参数时, 如果数值差别太大, 可能造成优化时梯度优化走弯路(因为不同维度使用的是相同的学习率)
  • 避免某些数值小的神经元输出被数值大的输出吞掉的情况
    • 个人理解: 虽然说我们找到合适权重后,可以使得二者到下一个神经元的差值没那么大, 但是我的理解是初始化的时候不知道数值,所以权重是随机的,之后如果两个神经元数值差距太大的话,是否会大值吞小值很难说

关于LR为什么需要归一化?

不是必要的

  • 因为LR使用梯度下降法求解参数时, 特征之间差别太大容易影响收敛速度, 归一化可以提升LR的收敛速度, 同时不影响分类结果

关于SVM为什么需要归一化?

是必要的

  • 因为SVM寻找的是所谓的间隔(margin), 就是两个支持向量的间隔
  • 如果不归一化的话, 这个间隔会因为不同特征的单位等, 数值被放大或者缩小, 从而造成无法评估间隔 , 所以归一化对于SVM很重要

ML——归纳偏置概念理解


整体说明

  • 在机器学习和深度学习中,归纳偏置(Inductive Bias)是指学习算法在面对未知数据时所倾向的特定类型的假设或规律
  • 当模型去预测其未遇到过的输入的结果时,会做一些假设,而学习算法中的归纳偏置就是这些假设的集合
  • 归纳偏置是机器学习算法在学习过程中对某种类型假设的偏好

归纳偏置的作用

  • TLDR:没有归纳偏置的模型在面对新数据时无法有效泛化。归纳偏置通过引入合理的先验知识,缩小假设空间,提高学习效率
    • 例如“无免费午餐定理”指出,没有任何算法在所有问题上表现最优
  • 数据效率 :在少量数据下,合理的偏置能快速收敛到可行解
  • 泛化能力 :避免过拟合,例如奥卡姆剃刀原则(偏好简单假设)
  • 领域适配 :针对问题设计合适的偏置(如CNN对图像、RNN对序列)

有哪些常见归纳偏置?

  • 模型架构 :如卷积神经网络(CNN)的“局部性假设”(相邻像素关联性强),位移不变性
  • 正则化 :L1正则化偏好稀疏解,L2偏好小权重
  • 优化目标 :支持向量机(SVM)追求最大化分类间隔
  • 特征选择 :决策树优先选择信息增益高的特征
  • 一些算法自带归纳偏置 :
    • 线性回归 :假设数据关系是线性的
    • K近邻(KNN) :假设相似输入有相似输出
    • 贝叶斯模型 :依赖先验概率分布假设

归纳偏置带来的问题

  • 若偏置与真实数据分布不符(如用线性模型拟合非线性关系),会导致欠拟合。此时需调整模型假设

Sklearn——总体介绍

Sklearn 总体介绍


总结介绍图

操作系统——同步vs异步-阻塞vs非阻塞

  • 参考链接
    • https://www.zhihu.com/question/19732473/answer/20851256
    • https://www.zhihu.com/question/26393784/answer/513257548

同步与异步

  • 同步与异步关注的是消息通信机制 :被调用者是否有回传功能在任务结束时通知调用者

    同步

  • 同步 :就是在发出一个调用时,在没有得到结果之前,该调用就不返回。但是一旦调用返回,就得到返回值了
    • 比如写一个函数调用另一个函数,必须等待返回结果才继续下一步骤,因为同步调用是被调用者没有回调通知的功能,所以必须等

异步

  • 异步 :调用在发出之后,这个调用就直接返回了,所以没有返回结果
  • 调用者不会立刻得到结果,被调用者完成工作后会通知调用者【通过回调函数等方式】
  • 比如在Future和Callable配合使用时
    • 调用者可以启动Callable对应的线程执行任务,然后马上返回,获取到一个Future对象
    • Callable完成工作后,会将返回值存放到Future【相当于一个回调】
    • 调用者可以通过检查Future对象,调用其.get()方法得到返回值
      • 【如果没有返回的话,会被阻塞,但是启动任务和调用get()期间,调用者是可以做自己的事情的,所以是异步非阻塞调用,然后get()阻塞式接受结果】

区别分析

  • 同步与异步的重点区别在于是否有返回通知的功能:https://www.zhihu.com/question/26393784/answer/513257548
  • 是否马上返回感觉只是一个附属的结论,因为异步能通知,所以才能马上离开

阻塞与非阻塞

  • 阻塞和非阻塞关注的是程序在等待调用结果(消息,返回值)时的状态 :被调用者是否被阻塞

    阻塞

  • 阻塞 :阻塞调用是指调用结果返回之前,当前线程会被挂起。调用线程只有在得到结果之后才会返回
    • 如果被调用者没有完成工作,就一直等待

非阻塞

  • 非阻塞 :非阻塞调用指在不能立刻得到结果之前,该调用不会阻塞当前线程
    • 如果被调用者还没有完成工作,就返回默认值

区别分析

  • 同步与异步的区别在于等待结果时的状态 :https://www.zhihu.com/question/19732473/answer/20851256

写在最后

  • 同步一般伴随着阻塞,因为同步时不等待的话拿不到结果
    • 没见过同步的非阻塞是调用,除非是不需要结果的调用,只是为了发送一个通知给被调用者
  • 异步一般伴随着非阻塞,不然就浪费了异步的功能
    • 异步调用后可以选择两种调用拿到结果
      • 阻塞式get + 轮训
      • 阻塞式get

Docker——Docker使用笔记

本文用于记录一些Docker使用过程中的经验,最新添加的一些部分包含 AI 辅助创作


整体说明

  • Docker 是一个开源的容器化平台,可以让开发者将应用程序及其依赖项打包到一个可移植的容器中,然后发布到任何支持 Docker 的环境中
  • Docker 的核心基本概念
    • 镜像(Image) :包含运行应用所需的代码、库、环境变量和配置文件的模板,占用硬盘物理存储
    • 容器(Container) :镜像的运行实例 ,可以被创建、启动、停止、删除
      • 一个镜像可以启动多个容器,启动的容器会占用内存,就像一个虚拟系统
    • 仓库(Repository) :存储和分发 Docker 镜像的地方(如 Docker Hub)

Docker 常用命令

镜像(Image)相关 Docker 命令

  • 镜像相关 Docker 命令示例
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    # 搜索镜像
    docker search [镜像名]

    # 拉取镜像
    docker pull [镜像名]:[标签] # 不指定标签默认latest

    # 查看本地镜像
    docker images

    # 删除镜像
    docker rmi [镜像ID或镜像名]

容器(Container)相关 Docker 命令

  • 创建和启动容器

    1
    2
    3
    4
    5
    # 创建并启动容器,docker run = docker create + docker start
    docker run [选项] 镜像名 [命令]

    # 示例: 创建并启动一个nginx容器
    docker run -d -p 8080:80 --name mynginx nginx
    • 常用选项包括
      • -d: 后台运行
      • -p 主机端口:容器端口:端口映射
      • -v 主机目录:容器目录: 目录挂载,可多次使用 -v 参数挂在多个目录
      • --name 容器名:指定容器名称
      • -it:组合选项,-i 保持标准输入打开,-t 分配伪终端(终端交互模式)
      • 更多详细选项见附录
  • 容器相关常用操作

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    # 查看运行中的容器
    docker ps

    # 查看所有容器(包括停止的,刚启动的也算是停止的)
    docker ps -a

    # 创建容器,参数和 docker run 几乎一致
    docker create xxx

    # 启动/停止/重启容器
    docker start [容器ID/容器名]
    docker stop [容器ID/容器名]
    docker restart [容器ID/容器名]

    # 进入容器内部,不影响启动中的 docker 并与之交互
    docker exec -it [容器ID/容器名] /bin/bash

    # 删除容器
    docker rm [容器ID/容器名]

    # 查看容器日志
    docker logs [容器ID/容器名]

其他重要命令

  • 查看Docker系统信息

    1
    docker info
  • 清理无用的容器、镜像等

    1
    2
    # 清空所有悬空(dangling)镜像
    docker system prune

创建自定义镜像及构建

  • 创建 Dockerfile 文件:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    # 基础镜像
    FROM ubuntu:20.04

    # 维护者信息
    MAINTAINER Your Name <your@email.com>

    # 安装依赖
    RUN apt-get update && apt-get install -y python3

    # 复制文件到容器
    COPY ./app /app

    # 工作目录
    WORKDIR /app

    # 暴露端口
    EXPOSE 8000

    # 容器启动命令
    CMD ["python3", "app.py"]
  • 基于上述的 dockerfile 文件构建镜像:

    1
    2
    # . 表示在当前目录下读取 dockerfile 文件以构建镜像
    docker build -t myapp:1.0 .
    • -t, --tag 指定标签
    • -f, --file 指定 Dockerfile 文件,默认在当前目录下搜索 Dockerfile 文件
    • 命令最后的这里的 . 表示 “当前工作目录”,即你在终端中执行 docker build 命令时所在的目录,也称为构建上下文
      • 这是指 Docker 引擎在构建镜像时可以访问的文件目录
      • 当执行 docker build 时,Docker 会将这个目录下的所有文件(除了 .dockerignore 中排除的文件)打包发送给 Docker 引擎,供 Dockerfile 中的指令(如 COPY、ADD)使用
      • 通常这个目录下包含一些配置文件或代码等必须的东西
  • 运行自定义镜像:

    1
    docker run -d -p 8000:8000 myapp:1.0

Docker 服务相关操作

  • 服务相关的常见操作

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    # 查看服务是否启动
    systemctl status docker

    # 启动Docker服务
    sudo systemctl start docker

    # 停止Docker服务
    sudo systemctl stop docker

    # 重启Docker服务
    sudo systemctl restart docker

    # 设置开机启动
    sudo systemctl enable docker
  • 在修改镜像源等操作后,经常还可能涉及到 docker 后台进程的重新加载,再重启 docker 服务,使得修改生效

    1
    2
    sudo systemctl daemon-reload
    sudo systemctl restart docker

高阶用法:多容器 Docker Compose

  • 对于多容器应用,可以使用 Docker Compose 管理:
    • 第一步:创建 docker-compose.yml 文件
    • 第二步:使用 docker-compose 命令启动所有服务
  • 详情待补充

高阶用法:修改镜像并提交

整体说明

  • Docker 中,提交(commit) 是指将容器的当前状态保存为一个新的镜像的操作
  • 当你对一个运行中的容器做了修改(比如安装了软件、配置了环境、添加了文件等),可以通过 docker commit 命令将这些修改固化为一个新的镜像 ,以便后续可以基于这个新镜像创建出具有相同状态的容器
  • 提交操作包含如下含义:
    • 保存容器的修改:当你在容器内做了一系列配置后,不需要重新编写 Dockerfile 就能将这些修改保存为新镜像
    • 快速创建自定义镜像:对于简单的环境定制,commit 比编写 Dockerfile 更快捷
    • 临时保存工作状态:可以作为开发过程中的临时快照

docker commit 命令的基本用法

  • 用法示例:

    1
    2
    3
    4
    5
    6
    7
    8
    # 用法模版
    docker commit [选项] 容器ID/容器名 新镜像名[:标签]

    # 提交容器时指定作者、描述信息,并添加暴露端口的指令
    docker commit -a "JoeZJH joezjh@gmail.com>" \
    -m "download and install Node.js" \
    -c "EXPOSE 3000" \
    mycontainer mynodeapp:1.0
  • 可用的选项(options)主要用于设置新镜像的元数据信息,常用选项如下:

    • -a 或 --author
      • 指定新镜像的作者信息,格式通常为 姓名 <邮箱>
      • 例如:-a "JoeZJH <joezjh@gmail.com>"
    • -c 或 --change
      • 在提交时为新镜像添加 Dockerfile 指令(如 CMD、ENV、EXPOSE 等),可以多次使用该选项添加多个指令
      • 例如:-c "EXPOSE 8080" -c "CMD ['nginx']"
    • -m 或 --message
      • 为本次提交添加描述信息(类似 Git 的 commit 消息)
      • 例如:-m "添加了 Python 环境和自定义配置"
    • -p 或 --pause
      • 提交时是否暂停容器(默认值为 true,即自动暂停容器以保证数据一致性)
      • 若需在容器运行中提交,可指定 -p false,但可能导致数据不一致

完整示例

  • 第一步:先启动一个基础容器并进行修改:

    1
    2
    3
    4
    5
    6
    7
    8
    # 启动一个ubuntu容器并进入
    docker run -it --name myubuntu ubuntu:20.04 /bin/bash

    # 在容器内安装nginx(模拟修改操作)
    apt-get update && apt-get install -y nginx

    # 退出容器
    exit
  • 第二步:将修改后的容器提交为新镜像:

    1
    docker commit myubuntu myubuntu-nginx:1.0
  • 第三步:查看新创建的镜像:

    1
    2
    docker images
    # 会看到 myubuntu-nginx:1.0 这个新镜像
  • 基于新镜像创建容器:

    1
    2
    docker run -it myubuntu-nginx:1.0 /bin/bash
    # 此时容器内已经预装了nginx

docker commit 注意事项

  • docker commit 与 Dockerfile 的区别:
    • commit 是通过容器修改生成镜像(黑箱操作,不清楚具体做了哪些修改)
    • Dockerfile 是通过明文指令构建镜像(可追溯、可重复、易维护)
    • 推荐使用 Dockerfile 而非 docker commit 来管理镜像 ,尤其是在生产环境
  • 频繁 commit 会导致镜像体积增大(因为每次提交都会增加新的层,可能会包含不必要的临时文件或缓存)
  • 可以通过 -a(作者)和 -m(提交信息)选项添加元数据:
    1
    docker commit -a "Your Name" -m "Install nginx" myubuntu myubuntu-nginx:1.0

附录:docker run 选项详解

  • 注:可以通过 docker run --help 查看所有选项的完整说明

容器标识与命名

  • --name <容器名>:为容器指定一个自定义名称,而非随机生成
    • 示例:docker run --name myapp nginx
  • --hostname <主机名>:设置容器内的主机名(/etc/hostname)
    • 示例:docker run --hostname container-host nginx
  • --network-alias <别名>:为容器在网络中设置别名(便于同一网络内的容器通过别名访问)

运行模式与交互

  • -d 或 --detach:后台运行容器(守护进程模式),不占用终端
    • 示例:docker run -d nginx
  • -it:组合选项,-i 保持标准输入打开,-t 分配伪终端(终端交互模式)
    • 示例:docker run -it ubuntu /bin/bash(进入容器交互界面)
  • --rm:容器停止后自动删除(适合临时任务,避免残留容器)
    • 示例:docker run --rm -it alpine ping baidu.com

资源限制

  • --memory <内存大小> 或 -m:限制容器使用的最大内存(如 1g、512m)
    • 示例:docker run -m 1g nginx
  • --cpus <核心数>:限制容器使用的 CPU 核心数(如 0.5 表示半核,2 表示双核)
    • 示例:docker run --cpus 2 redis
  • --gpus <参数>:分配 GPU 资源(需主机支持 NVIDIA Docker)
    • 示例:docker run --gpus all nvidia/cuda:11.0-base nvidia-smi(使用所有 GPU)

IPC 进程间通信设置

  • --ipc:
    • IPC(Inter-Process Communication,进程间通信)设置
    • 如 --ipc=host 表示容器将使用主机的 IPC 命名空间
    • 作用:允许容器内的进程与主机系统或其他共享相同 IPC 命名空间的容器进行通信,常用于需要共享内存的场景(如多进程训练)
  • --shm-size:
    • shm 是 /dev/shm 的缩写,即共享内存 tmpfs(临时文件系统),属于容器内进程间通信(IPC)的一部分,用于进程间快速共享数据
    • 如 --shm-size=512m 设置容器内共享内存的大小为 512MB
    • 作用:某些应用(如 PyTorch 的数据加载器 DataLoader、数据库、浏览器等)会使用 /dev/shm 作为临时缓存或共享内存区域
    • 默认大小通常为容器内存的 1/2(但不超过 64MB),如果应用需要更大的共享内存空间,需手动指定(如 --shm-size=512m)
      • 避免因默认共享内存不足导致的错误

端口映射

  • -p <主机端口>:<容器端口> 或 --publish:将容器内的端口映射到主机端口,实现外部访问
    • 格式:[主机IP:]主机端口:容器端口(主机IP可选,默认绑定所有IP)
      • 示例:
        • docker run -p 8080:80 nginx(主机8080端口映射到容器80端口)
        • docker run -p 127.0.0.1:8080:80 nginx(仅本地可访问)
  • -P 或 --publish-all:自动映射容器暴露的所有端口(随机映射到主机的高位端口)

数据持久化

  • -v <主机路径>:<容器路径> 或 --volume:挂载主机目录或数据卷到容器,实现数据持久化
    • 格式:主机路径:容器路径[:权限](权限如 ro 表示只读)
    • 示例:
      • docker run -v /host/data:/container/data nginx(主机目录挂载)
      • docker run -v myvolume:/container/data nginx(数据卷挂载,myvolume 为卷名)
  • --mount:更灵活的挂载方式(支持更多参数,如 type=bind 绑定目录、type=volume 数据卷等)
    • 示例:docker run --mount type=bind,source=/host/data,target=/container/data nginx

环境变量与配置

  • -e <键=值> 或 --env:设置容器内的环境变量
    • 示例:docker run -e "DB_HOST=localhost" -e "DB_PORT=3306" mysql
  • --env-file <文件路径>:从文件中读取环境变量(每行一个 键=值)
    • 示例:docker run --env-file .env nginx(.env 为环境变量文件)
  • --config <文件路径>:指定容器的配置文件(较少用)

网络配置

  • --network <网络名>:指定容器加入的网络(默认使用 bridge 网络)
    • 示例:docker run --network mynet nginx(加入自定义网络 mynet)
  • --dns <DNS地址>:设置容器的 DNS 服务器
    • 示例:docker run --dns 8.8.8.8 --dns 8.8.4.4 ubuntu
  • --add-host <主机名:IP>:在容器的 /etc/hosts 中添加主机映射
    • 示例:docker run --add-host "test:192.168.1.100" ubuntu

容器生命周期与依赖

  • --restart <策略>:设置容器退出后的重启策略(常用于服务型容器)
    • 可选策略包括
      • no:不重启(默认)
      • always:总是重启
      • on-failure[:次数]:失败时重启(可指定最大次数)
      • unless-stopped:除非手动停止,否则总是重启
    • 示例:docker run --restart always nginx
  • --link <容器名:别名>:链接到另一个容器(已过时,推荐用网络替代)

其他常用选项

  • --entrypoint <命令>:覆盖容器的默认入口命令(ENTRYPOINT)
    • 示例:docker run --entrypoint /bin/bash nginx(用 bash 替代默认的 nginx 启动命令)
  • -u <用户> 或 --user:指定容器内的运行用户(避免以 root 运行)
    • 示例:docker run -u 1000:1000 ubuntu(用 UID 1000、GID 1000 的用户运行)
  • --log-driver <驱动>:设置容器日志的驱动(如 json-file、syslog 等)

ACM——编程中应该注意的一些关键问题

持续更新


位运算

用移位代替乘除法

  • 移位的效率远高于乘除法
  • 除以2时一般直接右移一位即可
  • 乘以2时一般直接左移一位即可

用位运算判断奇偶性

  • 将整数与1做与运算,值为1表示为奇数,为0表示为偶数

判断二进制数中1的个数

方法一: n=(n-1)&n
  • n = (n-1) & n 可以将二进制数n中的最后一位1变成0
  • 不停执行该语句,直到n为0,执行次数即二进制数n中1的数量
方法二: result=n&flag
  • flag初始化为与n相同的类型(二进制位数一致)
  • flag从1,2,4….,为2的次方数,即初始化为1,每次向左移动一位,直到flag为0为止(此时说明flag移位溢出了,n的每一位都进行过比较了)
  • 累计result为1的次数就是二进制数n中1的数量
错误方法: result=n&1
  • 这种方法不设置flag变量,每次将n左移一位,直到n为0
  • 当n为负数时会引发无线循环,所以此方法是错的

小数的精度

比较两个小数是否相等

  • 无论a,b类型是否相等(float, double),都不能直接使用==符号直接比较
  • 定义以下函数实现比较即可|a-b| < \(\epsilon\) (\(\epsilon\) 是一个误差允许的极小值)
    1
    2
    3
    4
    5
    bool Equal(double num1, double, num2){
    if(num1-num2 < 0.0000001 && num1-num2 > -0.0000001)
    return true;
    return flase;
    }

为什么存在精度问题

  • 因为十进制的小数存到内存时是二进制,此时有很多无线循环,但是二进制位数有限,所以有误差

  • 一般来说,double类型足以满足我们日常计算的精度,在无需很高精度时使用float可以减少内存占用

  • 实例:

    1
    2
    3
    4
    5
    6
    7
    8
    double a = 0.9;
    float b = 0.9;
    if(a == (double)b)
    printf("a==b is true")
    else
    printf("a==b is flase")
    # output:
    a==b is false
    • 对于小数0.9,表示为二进制后小数部分是无线循环小数,在float类型时与double类型时由于保留的小数位不同,所以值不同

最大最小整数

最小负数

1
2
3
4
# int
int INT_MIN = 0x80000000; //32位
# long
long LONG_MIN = 0x8000000000000000; //64位

最大正数

1
2
3
4
# int
int INT_MAX = 0x7FFFFFFF; //32位
# long
long LONG_MAX = 0x7FFFFFFFFFFFFFFF; //64位

第一要务:输入检查

  • 无论何时,函数实现的第一步都应该是检查输入是否合法

常见的检查

  • 指针:是否为空
  • 整数:是否满足条件(大于0,小于0等)
  • 多个整数之间的关系:是否满足大小关系等

访问数组时必须首先确认

  • 数组已初始化
  • 访问的Index没有超过数组

关于折半搜索和查找

  • 一般来说low从0开始,high从数组长度开始(注意,有时候high如果从len-1开始则可能造成无法访问到最后一个位置?)
    • 相关题目:LeetCode 35题 Search Insert Position

mid定义为(low + high)/2

  • 如果mid的定义如下

    1
    mid = (low + high) / 2
  • 那么每次查找结束时更新时应该作如下更新

    1
    2
    low = mid + 1
    high = mid
  • 或者

    1
    2
    low = mid + 1
    high = mid - 1
  • 如果此时使用下面的语句作为更新

    1
    low = mid
    • low == high - 1有low == mid,上面的式子将造成死循环

mid定义为(low + high + 1)/2

  • 如果mid的定义如下

    1
    mid = (low + high + 1) / 2
  • 那么每次查找结束时更新时应该作如下更新

    1
    2
    low = mid
    high = mid - 1
  • 或者

    1
    2
    low = mid + 1
    high = mid - 1
  • 如果使用下面的语句作为更新

    1
    high = mid
    • low == high - 1有high == mid,上面的式子将造成死循环
  • 二分查找相等的数时往往可以使用

    1
    2
    low = mid + 1
    high = mid - 1
  • 但是查找的是当前数组不存在的节点的存放位置时要注意查找时

    1
    2
    low = mid + 1
    high = mid
    • 这样确保i和j退出时相等
    • 相关题目:LeetCode 35 Search Insert Position

相关题目

  • 详细情况参考LeetCode 34题 Find First and Last Position of Element in Sorted Array

深度优先遍历和回溯法的异同

  • 深度优先方法(DFS, Depth First Search)使用栈实现,广度优先方法(BFS, Breadth First Search)使用队列实现

  • 一般来说在树中遍历时才有深度优先搜索这种说法,不然比如数组的全部组合遍历都叫做回溯法,而不是DFS

  • 对于树而言,回溯法也是遵循深度优先遍历原则实现的

  • 回溯法可以访问已经访问过的节点,而深度优先一般来说不会再访问已经访问过的节点

  • DFS是把所有可能的情况考虑到就行了,但回溯法可能会重视访问节点的顺序[LeetCode 79 Word Search]

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    def solution(nums):
    path, result = [], []
    * 如果nums含有重复元素,需要重新排序
    def backtrace(index):
    if 满足存储条件:
    result.append(path[:])
    if 不需要继续迭代:
    return
    * 迭代访问内部节点(不同情况访问方式不同,详情看下面)
    * 一种简单的可能是
    for i in range(*视具体情况变化):
    * 如果nums含有重复元素,需要判断是否跳过(如果nums当前节点与上一个节点重复,则跳过)
    path.append(nums[i])
    * 不同情况不同回溯方式
    * 当path里面不能重复访问同一元素时
    * backtrace(i+1)
    * 当path里面能重复访问同一元素时
    * backtrace(i)
    path.pop()
    backtrace(0)
    return result
  • 特殊情况,如果path不能访问同一元素而且不同顺序相同元素算是不同路径的时候,我们可能必须使用rest对象在迭代中记录当前未被访问的对象

    • 此时由于不同顺序相同元素算是不同路径,所以我们不能用每次只能向前访问的方法来实现去除重复(及[index:], 这种每次只能向前访问的方法会将先[a, b], [b, a]视为重复而去除,只保留[a, b]当(a < b时))

关于递归函数内部的节点访问方式

其实在使用回溯法访问一个数组时,可以考虑这个我们在访问一棵树,从空节点开始,然后每次迭代所有符合的子节点

| 路径是否可以访问同一节点多次 | 顺序不同节点相同是否算不同路径 | 原始数组中是否包含重复元素 | 预处理 |每一层迭代代码 |
| :——: | :——: | :——: | :——: |
| 是 | 是 | 是 | data.sort() | for i in [:]:
  if与前一个相等:
    continue
  visit(i)
  backtrace()
最后移除重复路径|
| 是 | 是 | 否 | - | for i in [:]:
  visit(i)
  backtrace() [待更新]|
| 是 | 否 | 是 | data.sort() | for i in [index:]:
  if与前一个相等:
    continue
  visit(i)
  backtrace(i)
最后移除重复路径|
| 是 | 否 | 否 | - | for i in [index:]:
  visit(i)
  backtrace(i)|
| 否 | 是 | 是 | data.sort()
rest存储剩余元素| for i in rest:
  if与前一个相等:
    continue
  visit(i)
  backtrace(rest-i)|
| 否 | 是 | 否 | rest存储剩余元素 | for i in rest:
  visit(i)
  backtrace(rest-i) |
| 否 | 否 | 是 | data.sort() | for i in [index:]:
  if与前一个相等:
    continue
  visit(i)
  backtrace(i+1) |
| 否 | 否 | 否 | - | for i in [index:]:
  visit(i)
  backtrace(i+1)|

相关理解
  • 当节点相同顺序不同是相同路径时,使用每次迭代只向后而不向前访问的方式可以避免重复(因为先a后b,与先b后a重复)

    • 路径可含有重复节点时,向后迭代从当前节点开始,包括当前节点backtrace(i)
    • 路径不可包含重复节点时,向后迭代从当前节点的下一个开始,不包括当前节点backtrace(i+1)
  • 当路径不可包含重复节点时,还可使用rest存储尚未访问的节点或每次迭代时只向后即可解决问题

  • 当数组中包含重复节点时,可以现将其排序,然后在迭代时跳过与前一个节点相同的节点

  • 一个万能的写法是:

    • 每次迭代访问所有节点
    • 将所有符合条件的路径加入结果
    • 最后将重复路径删除即可
  • 1,3这两种情况实际中很少出现,我们不能提前用某种算法确保加入的数据不重复,这时需要我们最终从result中去除重复的(或者每次都查看result中是否有与当前路径相同的路径)

    • 第1,3两种情况中,即使我们保证访问顺序完全相同的路径不会重复出现,但是由于数组中可能有重复值,且每个元素可能被访问多次
      • 比如[2,1,1]中,容易造成同一个元素a[1]被访问两次的到的[1,1]路径与两个元素a[1],a[2]分别被访问一次得到的[1,1]路径结果完全相同,此时我们只能通过最终手段保证返回结果中路径的唯一性
    • 保证路径的唯一性在Python中可以使用将路径转换为tuple(path)的方式实现路径的比较,且可以放入set中
    • 第1, 3两种情况的不同之处在于第1种情况中不同顺序的路径是不同的,所以无需对路径进行排序,第3种情况中不同顺序相同结点的路径也是相同结点,则需要先对路径进行排序,再转换为tuple才行
  • 第4种情况对应LeetCode 39 Combination Sum

  • 第7种情况对应LeetCode 40 Combination Sum II

  • 第8种情况对应LeetCode 216 Combination Sum III

  • 第5种情况对应LeetCode 47 Permutations II


对列表中数字列表的排序

1
List[List[number]]
  • 找出所有列表的所有数中最大的数M

  • 定义一个函数,用一个M+1进制的数对每个内层列表进行映射表示

    • 系数:

      • 需要递增排序的位前面系数为1
      • 需要递减排序的位前面系数为-1
      • 无需排序的位前面系数为0
    • 示例:

      1
      2
      def key(x):
      return x[0]*(M+1)**3 - x[1]*(M+1)**2 - x[2]*(M+1) + x[3]
      • 对第一和第四位按照递增排序,第二和第三位按照递减排序
  • 映射函数定义后可以使用sort函数排序

    1
    l.sort(key=key)
  • 也可以使用lambda函数定义

    1
    l.sort(key=lambda x: x[0]*(M+1)**3 - x[1]*(M+1)**2 - x[2]*(M+1) + x[3])

使用 memo 存储中间结果

memo可理解为备忘录,但是和传统的备忘录设计模式有一定区别,后者的目标是恢复对象之前的某个状态,前者的目标更应该理解为动态规划的思想dp存储计算中间值

  • 对某些可能会多次被求解的子空间(子数组,子集等), 且子空间能够独立的情况
    • 这种题目对应一般可以使用DFS求解,但是由于子空间能够独立,使用DFS会多次求解子空间,从而产生超时的情况
    • 子空间能够独立的就应该使用memo
  • 如果能够唯一标识(能作为字典的Key值)这些空间数据,即可使用memo存储
  • memo 为一个已子空间唯一标识为 Key, 子空间的对应求解结果为Value
  • 相关题目: LeetCode 140, Word Break II

在使用特殊字符节省空间

  • 在使用DFS搜索空间中的路径时,往往需要记录访问过的点,不能重复访问
  • 常用的做法是开辟一个新的相同大小的visited数组,记录是否访问过当前结点
  • 一种更好的做法是每次记录当前结点的值, 然后修改为一个特殊字符, DFS 完成后恢复成原始字符, 这种做法无需开辟新的空间

示例:0-1背包问题求解

  • 动态规划典型示例(Python求解示例)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    # 假设:n是物品数,W是背包容量,W是
    # 方案一:时间O(nW),空间O(nW)
    def knapsack01(weights, values, capacity):
    n = len(weights)
    dp = [[0]*(capacity+1) for _ in range(n+1)]
    for i in range(1, n+1):
    for j in range(1, capacity+1):
    if weights[i-1] > j:
    dp[i][j] = dp[i-1][j]
    else:
    dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]] + values[i-1])
    return dp[n][capacity]

    # 方案二:时间O(nW),空间O(W)
    def knapsack01_optimized(weights, values, capacity):
    n = len(weights)
    dp = [0]*(capacity+1)
    for i in range(1, n+1):
    for j in range(capacity, weights[i-1]-1, -1): # 注意此时需要逆序遍历,且仅遍历到weights[i-1](包含)为止
    dp[j] = max(dp[j], dp[j-weights[i-1]] + values[i-1])
    return dp[capacity]

    # 方案二(更容易理解的版本):时间O(nW),空间O(W)
    def knapsack01_optimized2(weights, values, capacity):
    n = len(weights)
    dp = [0 for _ in range(capacity+1)]
    for i in range(1, n+1):
    for j in range(capacity, 0, -1): # 注意需要逆序遍历
    if j < weights[i-1]:
    pass # dp[i][j] = dp[i-1][j] => dp[j] = dp[j] => 可以直接pass
    else:
    dp[j] = max(dp[j], dp[j-weights[i-1]] + values[i-1])
    return dp[capacity]

    # 测试用例
    weights = [2, 3, 4, 5]
    values = [3, 4, 5, 6]
    capacity = 8

    max_value = knapsack01(weights, values, capacity)
    print(f"Maximum value: {max_value}")
    max_value = knapsack01_optimized(weights, values, capacity)
    print(f"Maximum value: {max_value}")
    max_value = knapsack01_optimized2(weights, values, capacity)
    print(f"Maximum value: {max_value}")

    # 其他方法说明
    ## 若遇到capacity过大的情况,可考虑使用贪心求解法近似求解:每次加入单位容量价值最大的物品

示例:字符串匹配问题

  • 问题描述:给你一个字符串和一个正则表达式,请你来实现一个支持.和*的正则表达式匹配
    • .匹配任意单个字符
    • *匹配零个或多个前面的那一个元素
    • 要求匹配整个字符串而不是部分字符
  • 动态规划典型示例(Python求解示例)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    # 判断是否匹配单个字符
    def match_char(se, rege):
    return True if rege == '.' else se == rege

    # 时间复杂度O(mn),空间复杂度O(mn);字符串s和正则表达式reg的匹配
    def match_str(s, reg):
    m, n = len(s), len(reg)
    dp = [[True] * (n+1) for _ in range(m+1)]

    # 字符串和正则表达式同时为空时,可以匹配
    dp[0][0] = True

    # 初始化边界:当字符串为空时,正则表达式可能是"x*"的形式
    for j in range(1, n+1):
    if reg[j-1] == '*':
    dp[0][j] = dp[0][j-2] # s=""时,reg可以是"x*"
    else:
    dp[0][j] = False

    # 初始化边界:当正则表达式为空时,字符串只能为空,否则不匹配
    for i in range(1, m+1):
    dp[i][0] = False

    for i in range(1, m+1): # 注意访问从1开始
    for j in range(1, n+1): # 注意访问从1开始
    if reg[j-1] != '*':
    if match_char(s[i - 1], reg[j - 1]):
    # 直接匹配,动态规划看去掉匹配的尾部字符后,两个字符串s[:i-1],reg[:j-1]是否匹配
    dp[i][j] = dp[i-1][j-1]
    else:
    # 不匹配,直接赋值为False,在初始化为False的情况下,这里可以不调用
    dp[i][j] = False
    else: # reg[j-1] == '*'
    if match_char(s[i - 1], reg[j - 2]):
    # 1)dp[i-1][j]:"x*"匹配对应字符,需要保证截止到当前的正则表达式能匹配s[:i-1]的字符
    # 2)dp[i][j-2]:"x*"不匹配对应字符,相当于本次"x*"匹配空字符串"",需要保证正则表达式在"x*"完成当前所有字符的匹配
    # 3)(可选):dp[i-1][j-2]这表示"x*"匹配对应字符且"x*"在这之前不匹配任何字符,这是情况1)的一个子集
    # # 对3)进一步的理解是:因为当reg[j-1] == '*'时,dp[i-1][j] = dp[i-1][j-2]一定成立,故而可以去掉一个部分呢
    dp[i][j] = dp[i-1][j] or dp[i][j-2]
    else:
    # 由于无法匹配,所以字符保留,"x*"不匹配对应字符,正则表达式必须在"x*"完成当前所有字符的匹配
    dp[i][j] = dp[i][j-2]
    return dp[m][n]

    s = "abcdddbc"
    reg = "ab.*b*c"
    print(match_str(s, reg))
1…565758…64
Joe Zhou

Joe Zhou

Stay Hungry. Stay Foolish.

631 posts
53 tags
GitHub E-Mail
© 2026 Joe Zhou
Powered by Hexo
|
Theme — NexT.Gemini v5.1.4