问题来自今日力扣

偶然发现使用std::function定义dfs函数比原生函数或auto定义慢很多，使用斐波那契简单计算一下时间，代码放在最后。

结果如下，可以看到auto和普通定义的递归函数时间开销差不多，而function定义的递归函数慢了快5倍(当然随着计算量增大，倍数会逐渐减小，但还是很慢就是了)。

check fibo(30)
<dfs_ori > ret: 1346269 done!  6425ms
<dfs_func> ret: 1346269 done!  41189ms
<dfs_auto> ret: 1346269 done!  6492ms

gpt给出的解释如下，以后还是投入auto怀抱了~

在C++中，当你使用std::function来包装一个lambda表达式或函数时，可能会发生拷贝构造的情况。这是因为std::function是一个类型安全的函数包装器，可以包含任何可调用对象（函数指针、成员函数指针、函数对象等），因此在构造std::function对象时，会涉及到对象的拷贝构造或移动构造。

在你的情况中，当使用function<int(int,int,int)> dfs = [&](int a, int b, int c)定义dfs时，lambda表达式会被复制到dfs对象中，这可能导致拷贝构造的开销。

而当你使用auto dfs = [&](auto&& dfs, int a, int b, int c)时，使用auto关键字推断函数对象类型，不会引起多余的拷贝构造。这是因为auto将推断出lambda表达式的真实类型，而不是通过std::function进行类型擦除和包装。

因此，如果遇到性能问题，尤其是在递归调用时，使用auto推断类型可能会更有效，因为它可以避免不必要的拷贝构造，提高性能。

code

#include <bits/stdc++.h>
#include <functional>
#include <chrono>
using namespace std;
using namespace chrono;

int dfs_ori(int n){
    if(n <= 1)
        return 1;
    return dfs_ori(n-1) + dfs_ori(n-2);
}

int main(){
    
    cout << "check fibo(30)" << endl;
    int n = 30;
    
    // dfs ori
    auto start = steady_clock::now();
    
    int ret = dfs_ori(n);
    cout << "<dfs_ori > ret: " << ret << " done!  ";
 
    auto end = steady_clock::now();
 
    auto last = duration_cast<microseconds>(end - start);
 
    cout <<  last.count() << "ms" << endl;
    
    // dfs function
    function<int(int)> dfs_func = [&](int n){
        if(n <= 1)
            return 1;
        return dfs_func(n-1) + dfs_func(n-2);    
    };
    
    start = steady_clock::now();
    
    ret = dfs_func(n);
    cout << "<dfs_func> ret: " << ret << " done!  ";
 
    end = steady_clock::now();
 
    last = duration_cast<microseconds>(end - start);
 
    cout <<  last.count() << "ms" << endl;
    
    // dfs auto
    auto dfs_auto = [&](auto&& dfs_auto, int n) -> int {
        if(n <= 1)
            return 1;
        return dfs_auto(dfs_auto, n-1) + dfs_auto(dfs_auto, n-2);    
    };
        
    start = steady_clock::now();
    
    ret = dfs_auto(dfs_auto, n);
    cout << "<dfs_auto> ret: " << ret << " done!  ";
 
    end = steady_clock::now();
 
    last = duration_cast<microseconds>(end - start);
 
    cout <<  last.count() << "ms";
    
    return 0;
} 

Python中创建对象时，会涉及__init__和__new__两个函数，个人感觉前者较为常见。

创建对象时发生了什么

创建一个类对象首先会调用该类的\_\_new\_\_方法(接下来省略下划线)，new方法本身接受一个类参数cls，一般就是自身，随后会通过super函数得到该类的父类，并调用父类的new方法进行对象的创建（因为所有类都基于object，所以最终都会调用object的new方法）

super函数（实际上是类，这里为了简明，使用相同功能的函数替代）的输入为类cls，和某个实例obj，super做的事情就是找到obj的父类并返回，这里我们使用python的mro函数得到obj对象对应类的父类列表。mro这个类方法是python解决多重继承问题的方案，简单理解就是mro会返回调用类的父类链，列表靠前的元素是靠后元素的子类。那么super的做法就是得到obj对象类的mro列表，取出mro列表中cls的后一个元素，也就是cls的最近父类。

def super(cls, obj):
    mro = obj.__class__.mro()
    return mro[mro.index(cls) + 1]

当然，super函数的输入也不一定是obj，比如super(cls, obj_cls)，因为我们想在new函数中调用父类的方法，此时对象还没创建，所以只能传obj对应的类。对应的操作无非就是通过obj_cls.mro()来得到父类列表了。

注1：super函数既适用于实例也适用于类本身，例如super(cls, cls)返回的是cls的父类，而super(cls, cls_obj)返回的是一个cls的父类实例；两者的区别在于调用init或其他实例方法时是否要传入self，这个细节可以看接下来的代码注释

类实例创建完成后，就会调用该实例的init方法进行初始化，init函数至少有一个参数self，这就指向之前new方法创建出来的对象。

一段例子

以一段代码为例，首先定义class B，父类是object(缺省也可以，从python3开始默认的基类就是object)；定义class A，父类是B；A和B都各自重写了new/init两个函数。接下来创建A对象，结果见注释。

class B(object):
    def __new__(cls):
        print("B.__new__ called")
        return super(B, cls).__new__(cls)

    def __init__(self):
        pass

class A(B):

    def __new__(cls):
        print("A.__new__ called")
        print(cls.mro())
        return super(A, cls).__new__(cls)

    def __init__(self):
        print("A.__init__ called")
        super(A, self).__init__() # 注1：如果super传入的不是实例self，而是类对象本身，那么这行代码应该写成 super(A, A).__init__(self)

A()

# output
# A.__new__ called
# [<class '__main__.A'>, <class '__main__.B'>, <class 'object'>]
# B.__new__ called
# A.__init__ called

结果解释：

• 首先A()会调用A本身的new方法，从而打印出了A.__new__ called

• 随后super(A, cls)返回了cls的父类，实际上这里的cls也就是A，写成super(A, A)或者super(cls, cls)都可以

  • 得到父类的方法是：首先调用cls的mro类方法，返回父类列表lst，lst中定位到第一个参数A的位置，返回下一个元素。通过打印A.mro()可以知道，A的下一个元素是B，所以super(A, cls)返回了class B
• 接下来调用super(A, cls).__new__(cls)，即B.__new__(cls)，因此输出B.__new__ called
• 同理，super(B, cls).__new__(cls)等同于object.__new__(cls)，也就是一切对象创建的起点，然后嵌套(嵌套这里表达欠妥，可见注3)返回，此时我们得到一个创建出来的A对象a
• 最后这个对象a会调用自身的init方法，即a.__init__(a)，从而输出A.__init__ called

注2：以上代码中很多可以省略，例如__init__(self)中的self，super(A, cls)中的A和cls，这里写出来是为了更好的解释每个函数的作用

在菱形继承中，init调用顺序更加复杂，但本质上还是和super函数涉及到的mro列表有关，可见以下代码

class A(object):
    def __init__(self):
        print("A init")
        super().__init__()

class B(A):
    def __init__(self):
        print("B init")
        print("B's mro: " + str(B.__mro__))
        print("self's mro: " + str(type(self).__mro__))
        super().__init__() # 根据self实例对应类的mro列表调用init函数，如果这里使用super(B, B).__init__()，就会跳过C的实例化

class C(A):
    def __init__(self):
        print("C init")
        super().__init__()

class D(B, C):
    def __init__(self):
        print("D init")
        super().__init__()

d = D()

# output
# D init
# B init
# B's mro:(<class '__main__.B'>, <class '__main__.A'>, <class 'object'>)
# self's mro:(<class '__main__.D'>, <class '__main__.B'>, <class '__main__.C'>, <class '__main__.A'>, <class 'object'>)
# C init
# A init

撒花，mro相关内容可能之后会更吧（

Typecho加个email提醒咋这么费劲呢....

复盘

• 腾讯云的主机升级php挺费劲的，试过remi源直接安装php8，但是typecho识别出来的还是老版本.

  • Solution: 源码安装，2核2G大概编个20min，可参考这里

• 几个插件都不维护了，找到一个比较新的这里, 但是存在数据库相关的问题

  • Solution: 见issue

虽然复盘完也就两个小问题，但是当时真的搞半天，原因可能有

• typecho调试比较幽默，报错才有信息看，后面参考了一个php log才舒服一点，见stackoverflow
• 时间为大晚上，缺水

Note

发送邮件我选择了同步发送，所以评论响应有点慢，请多见谅

RLHF PPO的时候为了节约成本，训练时一个batch的数据会多次利用，即多次更新actor model和critic model。

和Reference KL distance用于限制PPO模型和原始SFT模型之间的距离(防止PPO训歪，这一项是加在Reward model产生的R中，如deepspeed chat)一样，多次更新actor model也需要有原始actor model作为约束，因此actor loss计算中会有一项$logits/old\_logits$(重要性采样)

actor loss代码如下(from deepspeed chat)

    def actor_loss_fn(self, logprobs, old_logprobs, advantages, mask):
        ## policy gradient loss
        log_ratio = (logprobs - old_logprobs) * mask
        ratio = torch.exp(log_ratio)
        pg_loss1 = -advantages * ratio
        pg_loss2 = -advantages * torch.clamp(ratio, 1.0 - self.cliprange,
                                             1.0 + self.cliprange)
        pg_loss = torch.sum(torch.max(pg_loss1, pg_loss2) * mask) / mask.sum()
        return pg_loss

那么一个batch第一次迭代的时候actor loss对应的ratio是1(因为actor model没有更新，两次forward产生的logits一致)，那这次更新critic model只依赖所谓的advantages(与R和V有关,另外actor model不更新,因为advantages和它无关)。

今日力扣是关于单调栈的，刚开始我使用stack实现，最后题目要求返回vector，因为c++把stack视为容器而不是迭代器，所以使用pointer来计算stack的起始终止位置，如以下代码。

class Solution {
public:
    vector<int> mostCompetitive(vector<int>& nums, int k) {
        stack<int> stk;
        int n = nums.size();
        for(int i=0;i<n;i++){
            while(!stk.empty() && nums[i] < stk.top() && stk.size() + n - i - 1>= k)
                stk.pop();
            stk.push(nums[i]);
        }
        int *begin = &stk.top() + 1 - stk.size();
        return vector<int>(begin, begin + k);
    }
};

但以上代码过不了最后几个用例，报heap-overflow，判断可能是stack的内存连续性问题。因为stack默认使用deque(即双端数组)作为底层容器，实际上一个逻辑数组在内存中分块存储的。以下是llama-70b的回答。

That's correct. `std::deque` does not guarantee contiguous memory allocation. It's a double-ended queue that typically uses a sequence of fixed-size arrays (called "blocks" or "chunks") to store its elements. Each block has a fixed capacity, and when the deque grows or shrinks, new blocks are allocated or deallocated as needed.

The elements in a `std::deque` are not stored in a single contiguous block of memory. Instead, the deque maintains a sequence of pointers to these blocks, which allows it to efficiently insert or remove elements at any position.

This design provides several benefits, such as:

1. Efficient insertion and deletion at any position, with an average time complexity of O(1).
2. Good cache locality for iterating over the elements.
3. Ability to handle large datasets without running out of contiguous memory.

However, this design also means that `std::deque` does not provide a contiguous block of memory, which can be a limitation in certain situations, such as:

1. When you need to pass a pointer to a contiguous array to a C-style API or a function that expects a contiguous array.
2. When you need to use pointer arithmetic or indexing into the array.

In contrast, `std::vector` does guarantee contiguous memory allocation, which is why it's often preferred when contiguous memory is required.

In the case of `std::stack`, when you use the default underlying container (`std::deque`), you don't have a guarantee of contiguous memory. But when you specify `std::vector` as the underlying container, you do get contiguous memory, which is why the original code worked when using `stack<int, vector<int>>`.

解决方案： stack<int> → stack<int, vector<int>>