在 RK4 算法中使用 lambda 函数

Question

在 Python 显示 here 中有两种实现经典 Runge-Kutta 方案的方法。第一个使用 lambda 函数，第二个不使用它们。

哪个会更快，为什么？

Answer 1

我改编了给定 link 中的代码，并使用 cProfile 比较两种技术：

import numpy as np
import cProfile as cP

def theory(t):
    return (t**2 + 4.)**2 / 16.

def f(x, y):
    return x * np.sqrt(y)

def RK4(f):
    return lambda t, y, dt: (
            lambda dy1: (
            lambda dy2: (
            lambda dy3: (
            lambda dy4: (dy1 + 2*dy2 + 2*dy3 + dy4)/6
                      )( dt * f( t + dt  , y + dy3   ) )
                      )( dt * f( t + dt/2, y + dy2/2 ) )
                      )( dt * f( t + dt/2, y + dy1/2 ) )
                      )( dt * f( t       , y         ) )


def test_RK4(dy=f, x0=0., y0=1., x1=10, n=10):
    vx = np.empty(n+1)
    vy = np.empty(n+1)
    dy = RK4(f=dy)
    dx = (x1 - x0) / float(n)
    vx[0] = x = x0
    vy[0] = y = y0
    i = 1
    while i <= n:
        vx[i], vy[i] = x + dx, y + dy(x, y, dx)
        x, y = vx[i], vy[i]
        i += 1
    return vx, vy


def rk4_step(dy, x, y, dx):
    k1 = dx * dy(x, y)
    k2 = dx * dy(x + 0.5 * dx, y + 0.5 * k1)
    k3 = dx * dy(x + 0.5 * dx, y + 0.5 * k2)
    k4 = dx * dy(x + dx, y + k3)
    return x + dx, y + (k1 + k2 + k2 + k3 + k3 + k4) / 6.


def test_rk4(dy=f, x0=0., y0=1., x1=10, n=10):
    vx = np.empty(n+1)
    vy = np.empty(n+1)
    dx = (x1 - x0) / float(n)
    vx[0] = x = x0
    vy[0] = y = y0
    i = 1
    while i <= n:
        vx[i], vy[i] = rk4_step(dy=dy, x=x, y=y, dx=dx)
        x, y = vx[i], vy[i]
        i += 1
    return vx, vy

cP.run("test_RK4(n=10000)")
cP.run("test_rk4(n=10000)")

得到：

         90006 function calls in 0.095 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.095    0.095 <string>:1(<module>)
    40000    0.036    0.000    0.036    0.000 untitled1.py:13(f)
        1    0.000    0.000    0.000    0.000 untitled1.py:16(RK4)
    10000    0.008    0.000    0.086    0.000 untitled1.py:17(<lambda>)
    10000    0.012    0.000    0.069    0.000 untitled1.py:18(<lambda>)
    10000    0.012    0.000    0.048    0.000 untitled1.py:19(<lambda>)
    10000    0.009    0.000    0.027    0.000 untitled1.py:20(<lambda>)
    10000    0.009    0.000    0.009    0.000 untitled1.py:21(<lambda>)
        1    0.009    0.009    0.095    0.095 untitled1.py:28(test_RK4)
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
        2    0.000    0.000    0.000    0.000 {numpy.core.multiarray.empty}


         50005 function calls in 0.064 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.064    0.064 <string>:1(<module>)
    40000    0.032    0.000    0.032    0.000 untitled1.py:13(f)
    10000    0.026    0.000    0.058    0.000 untitled1.py:43(rk4_step)
        1    0.006    0.006    0.064    0.064 untitled1.py:51(test_rk4)
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
        2    0.000    0.000    0.000    0.000 {numpy.core.multiarray.empty}

所以我会说“lambda”实现中的 overhead 使其变慢。

不过请注意，我似乎以某种方式失去了一些精确度，因为结果尽管彼此一致，但比示例中的要差得多：

>>> vx, vy = test_rk4()
>>> vy
array([   1.        ,    1.56110667,    3.99324757, ...,  288.78174798,
        451.27952013,  675.64427775])
>>> vx, vy = test_RK4()
>>> vy
array([   1.        ,    1.56110667,    3.99324757, ...,  288.78174798,
        451.27952013,  675.64427775])

Answer 2

如果您 pre-process 使用实现 tail-call 优化的 Coconut 转译器的代码，那么它们是完全等价的（与更快的版本 un-processed 一样快） , 因此您可以使用更方便的样式。

# Save berna1111's code as rk4.coco; no modifications necessary.
$ coconut --target 3 rk4.coco & python3 rk4.py
         50007 function calls in 0.055 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.097    0.097 <string>:1(<module>)
    40000    0.038    0.000    0.038    0.000 rk4.py:243(f)
        1    0.000    0.000    0.000    0.000 rk4.py:246(RK4)
    10000    0.007    0.000    0.088    0.000 rk4.py:247(<lambda>)
        1    0.010    0.010    0.097    0.097 rk4.py:250(test_RK4)
        1    0.000    0.000    0.097    0.097 {built-in method builtins.exec}
        2    0.000    0.000    0.000    0.000 {built-in method numpy.core.multiarray.empty}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}


         50006 function calls in 0.057 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.057    0.057 <string>:1(<module>)
    40000    0.030    0.000    0.030    0.000 rk4.py:243(f)
    10000    0.019    0.000    0.049    0.000 rk4.py:265(rk4_step)
        1    0.007    0.007    0.057    0.057 rk4.py:273(test_rk4)
        1    0.000    0.000    0.057    0.057 {built-in method builtins.exec}
        2    0.000    0.000    0.000    0.000 {built-in method numpy.core.multiarray.empty}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

Answer 3

@berna1111 和@matt2000 都正确。由于函数调用，lambda 版本会产生额外的 over-head。 Tail-call 优化将尾调用转换为 while 循环（即自动将 lambda 版本转换为 while 版本）消除函数调用开销。

请参阅了解为什么 Python 不自动执行此优化，您必须使用像 Coconut 这样的工具来执行 pre-process 通过。

在 RK4 算法中使用 lambda 函数

Using lambda functions in RK4 algorithm

python

optimization

performance

runge-kutta