整数划分


我不怎么做算法题,今天才碰到整数划分,结果还是个经典递归/dp题目

参考链接给的是递归解法。

#include<iostream>
using namespace std;

int equationCount(int n,int m)
{
    if(n==1||m==1)
        return 1;
    else if(n<m)
        return equationCount(n,n);
    else if(n==m)
        return 1+equationCount(n,n-1);
    else
        return equationCount(n,m-1)+equationCount(n-m,m);
}

int main(void)
{
    int n;
    while(scanf("%d",&n)!=EOF&&(n>=1&&n<=120))
    {
        printf("%d\n",equationCount(n,n));
    }
    return 0;
}

递归和DP是一体两面,比如台阶dp

l = []
l.append(0)
l.append(1)
l.append(2)
n=int(input())
for i in range(3,n+1):
    l.append(l[i-1]+l[i-2])

print(l[n])

判断进程

lsof

netstat -tcp closewait

netstat -na awk ‘/^tcp/ {++S[$NF]} END {for(a in S) print a, S[a]}’

ref

  • https://www.cnblogs.com/dolphin0520/archive/2011/04/04/2005098.html

  • https://www.zhihu.com/question/56577396 这个问题讲了整数划分的背景

  • https://blog.csdn.net/dst111188/article/details/78554698 递归和DP的关系,空间换时间。核心的转换公式都是一样的。

  • http://blackblog.tech/2018/08/24/LeetCodeReview6/ 列了一些leetcode上的DP题目的解法。很有心了

  • https://blog.csdn.net/sxhelijian/article/details/8978794

  • https://blog.csdn.net/sxhelijian/article/details/8978850 上面这两个链接是c/c++输入模板

看到这里或许你有建议或者疑问或者指出我的错误,请留言评论或者邮件mailto:wanghenshui@qq.com, 多谢!

觉得写的不错可以点开扫码赞助几毛 微信转账
Read More


招人啦


华为云NoSQL团队招聘C/C++开发(3到5年工作经验最好

  • 熟练掌握Linux下C/C++开发,熟悉C++11更好,有良好的的编码习惯
  • 熟练掌握Linux下性能调优和debug工具
  • 熟悉一款nosql产品是加分项,包括但不限于rocksdb/redis/mongodb…
  • 如果对事务,一致性,扩展性,高可用等领域有自己的见解可再加一分

补充一下,3-5年经验,定级16左右。待遇的话,应该是从优的,具体要跟HR谈。

工作地点深圳,西安,杭州皆可。CloudBU NoSQL部门 空间很大,nosql的产品基本都做,机会不错。 组内项目挺多,缺人,氛围偏互联网,组内成员不乏大厂过来的大小牛。 有意的朋友,欢迎站内垂询,或发简历到huda@huawei.com

ps

已经走了,给老东家留着这个招聘吧,长期有效,发简历到时候可以提我的这个博客,说不定有友情分


看到这里或许你有建议或者疑问或者指出我的错误,请留言评论或者邮件mailto:wanghenshui@qq.com, 多谢!

觉得写的不错可以点开扫码赞助几毛 微信转账
Read More

relocation error version GLIBC_PRIVATE not defined in file


拷贝库到某某目录,执行

 export LD_LIBRARY_PATH=$PWD:$LD_LIBRARY_PATH

导入,遇到了一堆类似的错误。做个记录。以后弄清楚


ref

  1. https://lists.debian.org/debian-glibc/2016/03/msg00153.html
  2. https://askubuntu.com/questions/831592/glibc-private-not-defined-in-file-libc-so-6 貌似是resolv库拷贝引发的不兼容
  3. https://unix.stackexchange.com/questions/367597/almost-no-commands-working-relocation-error-symbol-getrlimit-version-glibc 解决办法,unset LD_LIBRARY_PATH,没说具体原因
  4. 打开vim提示错误vim: : ATUSHHH-! : Error 43692576的罪魁祸首 https://stackoverflow.com/questions/31155824/dlopen-in-libc-and-libdl

看到这里或许你有建议或者疑问或者指出我的错误,请留言评论或者邮件mailto:wanghenshui@qq.com, 多谢!

觉得写的不错可以点开扫码赞助几毛 微信转账
Read More

__FILE__路径显示过长


有运行时解决办法,把 __FILE__结果裁剪一下,太弱智了

#define __FILENAME__ (strrchr(__FILE__, '/') ? strrchr(__FILE__, '/') + 1 : __FILE__)

见参考链接,居然还采纳了你敢信??

正确的编译期做法是第二个答案

如果是cmake

set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -D__FILENAME__='\"$(subst  ${CMAKE_SOURCE_DIR}/,,$(abspath $<))\"'")

另外@houjw-hx 提到notdir,更清爽,在此补充表示感谢

set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -D__FILENAME__='"$(notdir $<)"'")

确实简单一些。不太了解cmake这些小接口,我都是搜到能对付用的就直接用了。。

如果是makefile

CXX_FLAGS+=-D__FILENAME__='\"$(subst $(SOURCE_PREFIX)/,,$(abspath $<))\"'"

然后把__FILE__替换成__FILENAME__或者把上面的__FILENAME__替换成__FILE__

可能会有告警,但是无关紧要

但是如果设置了-Werror可能会编译不过,需要设定-Wno-builtin-macro-redefined

cmake

set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -Wno-builtin-macro-redefined")

不然会有<command line>:41:9: error: redefining builtin macro [-Werror,-Wbuiltin-macro-redefined] 编译错误


ref

  1. https://stackoverflow.com/questions/8487986/file-macro-shows-full-path/16658858# 第一个答案是运行时裁剪,第二个答案更好。
  2. https://public.kitware.com/pipermail/cmake/2013-January/053117.html cmake做法
  3. https://blog.csdn.net/huojianying123456/article/details/70176755 makefile做法
  4. https://blog.csdn.net/yindongjie1221/article/details/90614261 这个写了一大堆,太复杂了。没用
  5. https://stackoverflow.com/questions/53182242/how-to-override-the-value-of-time-and-date-macros-using-command-line-opt 告警处理方法

看到这里或许你有建议或者疑问或者指出我的错误,请留言评论或者邮件mailto:wanghenshui@qq.com, 多谢!

觉得写的不错可以点开扫码赞助几毛 微信转账
Read More

subprocess一次挂死问题


用python脚本拉起后台进程,拉起的代码是这样的

cmds = cmd.split("|")
previous_result, p = None, None
for c in cmds:
    p = subprocess.Popen(shlex.split(c), stdin=previous_result, stdout=subprocess.PIPE, stderr=subprocess.PIPE, close_fds=True)
    previous_result = p.stdout
result, err = p.communicate()

我有两个二进制,一个二进制用的是glog做打印日志,默认输出到stderr,用这个拉起没有问题

另一个二进制使用的print打印日志,默认输出到stdout,用这个拉起会hang住

原因见参考链接1 默认是 shell=True , 如果调用了communicate,表示和stdout交互,除非显式输入EOF,否则会一直等待输入。解决方法就是加上shell=False ,不调用communicate

subprocess.Popen(shlex.split(cmd), stdin=subprocess.PIPE, stdout=subprocess.PIPE,stderr=subprocess.PIPE, close_fds=True, shell=False)

这样输出到stdout的二进制也能拉起。 我考虑过调整日志输出,不输出到stdout, 太麻烦了。作罢


ref

  1. https://stackoverflow.com/questions/2408650/why-does-python-subprocess-hang-after-proc-communicate

看到这里或许你有建议或者疑问或者指出我的错误,请留言评论或者邮件mailto:wanghenshui@qq.com, 多谢!

觉得写的不错可以点开扫码赞助几毛 微信转账
Read More

移动构造函数的生成时机


场景是想确定什么时候调用移动构造函数,参考链接有解释

  • X does not have a user-declared copy constructor,

  • X does not have a user-declared copy assignment operator,
  • X does not have a user-declared move assignment operator,
  • X does not have a user-declared destructor, and
  • the move constructor would not be implicitly defined as deleted.

比如下面这段代码

#include <iostream>
#include <tuple>

struct A{
A(){std::cout<<"ctor\n";}
};

int main()
{
   A a;
   A b(std::move(a));
}

无法判断

#include <iostream>
#include <tuple>

struct A{
A(){std::cout<<"ctor\n";}
A(const A& a)=delete;//{std::ignore = a; std::cout<<"copy"<<'\n';}
};

int main(){
   A a;
   A b(std::move(a));
}

这样会提示

prog.cc: In function 'int main()':
prog.cc:15:20: error: use of deleted function 'A::A(const A&)'
    A b(std::move(a));
                    ^
prog.cc:7:1: note: declared here
 A(const A& a)=delete;//{std::ignore = a; std::cout<<"copy"<<'\n';}

当有析构的时候也无法生成move ctor,比如

#include <iostream>
#include <tuple>
#include <memory>
struct A{
A(int a=0):a_(std::make_unique<int>(a)){std::cout<<"ctor\n";}
//A(const A& a)=delete;//{std::ignore = a; std::cout<<"copy"<<'\n';}
//A(A&& a){std::ignore = a; std::cout<<"move"<<'\n';}
~A(){std::cout<<"dtor\n";}
std::unique_ptr<int> a_;
};

int main()
{
   A a;
   A b(std::move(a));
}
/*
prog.cc:16:20: error: use of deleted function 'A::A(const A&)'
    A b(std::move(a));
                    ^
prog.cc:5:8: note: 'A::A(const A&)' is implicitly deleted because the default definition would be ill-formed:
 struct A{
        ^
prog.cc:5:8: error: use of deleted function 'std::unique_ptr<_Tp, _Dp>::unique_ptr(const std::unique_ptr<_Tp, _Dp>&) [with _Tp = int; _Dp = std::default_delete<int>]'
In file included from /opt/wandbox/gcc-5.4.0/include/c++/5.4.0/memory:81:0,
                 from prog.cc:4:
/opt/wandbox/gcc-5.4.0/include/c++/5.4.0/bits/unique_ptr.h:356:7: note: declared here
       unique_ptr(const unique_ptr&) = delete;
*/

由于有dtor,没有默认生成move ctor,而是生成了copy ctor,而unique_ptr的copy ctor是删除的导致错误

如何捕捉编译器调用了什么构造函数?有没有例外情况?

貌似汇编能看出来https://godbolt.org/z/Nn4iod


ref

  1. https://zh.cppreference.com/w/cpp/language/move_constructor
  2. https://stackoverflow.com/questions/8283589/are-move-constructors-produced-automatically

看到这里或许你有建议或者疑问或者指出我的错误,请留言评论或者邮件mailto:wanghenshui@qq.com, 多谢!

觉得写的不错可以点开扫码赞助几毛 微信转账
Read More

base from member

一个遇到的技巧


场景是这样的,基类需要子类的成员变量来初始化父类

#include <streambuf>  // for std::streambuf
#include <ostream>    // for std::ostream

class fdoutbuf : public std::streambuf {
public:
    explicit fdoutbuf(int fd);
    //...
};

class fdostream : public std::ostream {
protected:
    fdoutbuf buf;
public:
    explicit fdostream(int fd) : buf(fd), std::ostream(&buf) {}
};

这种场景是无法编译通过的,因为需要基类先初始化

但交换初始化列表和基类构造函数的位置

    explicit fdostream(int fd) :  std::ostream(&buf), buf(fd) {}

这样语义不对,buf十有八九是错的。

需要提前把buf初始化。所以加了一个中间层,把buf放到另外一个基类里,让这个基类先于原来的基类。

class fdoutbuf : public std::streambuf {
public:
    explicit fdoutbuf(int fd);
    //...
};

struct fdostream_pbase {
    fdoutbuf sbuffer;
    explicit fdostream_pbase(int fd) : sbuffer(fd) {}
};

class fdostream : private fdostream_pbase, public std::ostream{
    typedef fdostream_pbase  pbase_type;
    typedef std::ostream     base_type;
public:
    explicit fdostream(int fd): pbase_type(fd), base_type(&sbuffer)  {}
    //...
};

就解决了。

boost提供了一个base_from_member类,用于托管你要抽离出来的字段

用法是这样的

#include <boost/utility/base_from_member.hpp>
#include <streambuf>  // for std::streambuf
#include <ostream>    // for std::ostream

class fdoutbuf : public std::streambuf {
public:
    explicit fdoutbuf(int fd);
    //...
};

class fdostream : private boost::base_from_member<fdoutbuf> , public std::ostream {
    // Helper typedef's
    typedef boost::base_from_member<fdoutbuf>  pbase_type;
    typedef std::ostream                        base_type;

public:
    explicit fdostream(int fd) : pbase_type(fd), base_type(&member) {}
    //...
};

base_from_member有个member字段就是要抽离出来托管的字段。

实际上这个类也没那么复杂,自己写一个base_from_member或者自己写个类似的类,不用base_from_member这种模板继承也是可以的

template < typename MemberType, int UniqueID = 0 >
class boost::base_from_member
{
protected:
    MemberType  member;
    base_from_member();
    template< typename T1 >
    explicit  base_from_member( T1 x1 );
    //...
};

ref

  1. 介绍
    1. http://sns.hwcrazy.com/boost_1_41_0/libs/utility/base_from_member.html boost相关中文翻译
    2. http://www.josuttis.com/cppcode/ronsmember.html
    3. https://remonstrate.wordpress.com/tag/base-from-member/
    4. https://remonstrate.wordpress.com/2011/01/26/boost-%e7%9a%84-utility/ 这个博客其实还可以。文章不错
    5. https://stackoverflow.com/questions/4815956/base-from-member-idiom-in-c
    6. https://en.wikibooks.org/wiki/More_C%2B%2B_Idioms/Base-from-Member
  2. 一个类似的应用例子 https://stackoverflow.com/questions/16613191/stl-initializing-a-container-with-an-unconstructed-stateful-comparator 值得一看

看到这里或许你有建议或者疑问或者指出我的错误,请留言评论或者邮件mailto:wanghenshui@qq.com, 多谢!

觉得写的不错可以点开扫码赞助几毛 微信转账
Read More

std::condition_variable::notify_one 使用细节


官方的这个例子,真给我看傻了

#include <iostream>
#include <string>
#include <thread>
#include <mutex>
#include <condition_variable>
 
std::mutex m;
std::condition_variable cv;
std::string data;
bool ready = false;
bool processed = false;
 
void worker_thread()
{
    // Wait until main() sends data
    std::unique_lock<std::mutex> lk(m);
    cv.wait(lk, []{return ready;});
 
    // after the wait, we own the lock.
    std::cout << "Worker thread is processing data\n";
    data += " after processing";
 
    // Send data back to main()
    processed = true;
    std::cout << "Worker thread signals data processing completed\n";
 
    // Manual unlocking is done before notifying, to avoid waking up
    // the waiting thread only to block again (see notify_one for details)
    lk.unlock();
    cv.notify_one();
}
 
int main()
{
    std::thread worker(worker_thread);
 
    data = "Example data";
    // send data to the worker thread
    {
        std::lock_guard<std::mutex> lk(m);
        ready = true;
        std::cout << "main() signals data ready for processing\n";
    }
    cv.notify_one();
 
    // wait for the worker
    {
        std::unique_lock<std::mutex> lk(m);
        cv.wait(lk, []{return processed;});
    }
    std::cout << "Back in main(), data = " << data << '\n';
 
    worker.join();
}

为什么在notify_one之前需要unlock?

为什么notify_one不用在锁里?不怕丢吗(当然这个例子里不会丢,一共就俩线程)

notify_one有这么个注释

The effects of notify_one()/notify_all() and each of the three atomic parts of wait()/wait_for()/wait_until() (unlock+wait, wakeup, and lock) take place in a single total order that can be viewed as modification order of an atomic variable: the order is specific to this individual condition_variable. This makes it impossible for notify_one() to, for example, be delayed and unblock a thread that started waiting just after the call to notify_one() was made.

The notifying thread does not need to hold the lock on the same mutex as the one held by the waiting thread(s); in fact doing so is a pessimization, since the notified thread would immediately block again, waiting for the notifying thread to release the lock. However, some implementations (in particular many implementations of pthreads) recognize this situation and avoid this “hurry up and wait” scenario by transferring the waiting thread from the condition variable’s queue directly to the queue of the mutex within the notify call, without waking it up.

Notifying while under the lock may nevertheless be necessary when precise scheduling of events is required, e.g. if the waiting thread would exit the program if the condition is satisfied, causing destruction of the notifying thread’s condition_variable. A spurious wakeup after mutex unlock but before notify would result in notify called on a destroyed object.

这个注释能解释第一个notify_one不加锁

另外,wait必须要有条件,无条件wait容易丢失notify 已经写到官方建议里了 https://github.com/isocpp/CppCoreGuidelines/blob/master/CppCoreGuidelines.md#cp42-dont-wait-without-a-condition

主要是notify_one多线程消费场景,不知道被谁消费了,所以指定某个满足条件的去wait wait一个触发条件。这样配对用

在这个讨论里, 有个结论,也有人提问

unlocking the mutex before notifying is an optimisation, and not essential. I intentionally didn’t do that, to keep the example simple. There could be a second guideline about that point, but it’s not related to the “always use a predicate” rule. I would object strongly to complicating the example by doing that.

anyway 提前unlock算是个人选择(有优化),不提前unlock也没啥大的影响


说句题外话

最近在看一个时间队列实现,这个cond var用的让我有点迷惑

class TimerQueue {
public:
    TimerQueue() {
        m_th = std::thread([this] { run(); });
    }
 
    ~TimerQueue() {
        cancelAll();
        add(0, [this](bool) { m_finish = true; });
        m_th.join();
    }
 
    uint64_t add(int64_t milliseconds, std::function<void(bool)> handler) {
        WorkItem item;
        item.end = Clock::now() + std::chrono::milliseconds(milliseconds);
        item.handler = std::move(handler);
 
        std::unique_lock<std::mutex> lk(m_mtx);
        uint64_t id = ++m_idcounter;
        item.id = id;
        m_items.push(std::move(item));
        lk.unlock();
 
        // Something changed, so wake up timer thread
        m_checkWork.notify();
        return id;
    }
  ....

注意是先lk.unlock再notify,这个unlock有必要么?

后来发现是用cond var封装了一个 信号量,自己用内部的mtx。和这个没啥关系。

这个代码给我整晕了。rocksdb的timerqueue抄了这个,但是体验没那么迷糊


ref

  • https://www.crazygaze.com/blog/2016/03/24/portable-c-timer-queue/
  • https://en.cppreference.com/w/cpp/thread/condition_variable

看到这里或许你有建议或者疑问或者指出我的错误,请留言评论或者邮件mailto:wanghenshui@qq.com, 多谢!

觉得写的不错可以点开扫码赞助几毛 微信转账
Read More

Keepalive

layout: post title: tcp keepalive categories: [linux] tags: [tcp,keepalive,c]


int opt_val = 1;
setsockopt(sock_fd, SOL_SOCKET, SO_KEEPALIVE, &opt_val, sizeof(opt_val)) 

启用后,socket 默认的检测参数使用内核参数,使用 sysctl -a|grep tcp_keepalive查看,或者使用以下命令查看:

cat /proc/sys/net/ipv4/tcp_keepalive_time
cat /proc/sys/net/ipv4/tcp_keepalive_intvl
cat /proc/sys/net/ipv4/tcp_keepalive_probes

修改内核的参数可以使用 vim /etc/sysctl.conf 修改,然后使用 sysctl -p 应用

如果需要设置自定义的心跳参数,则需要使用 setsockopt 函数设置:

setsockopt (sock_fd,  SOL_TCP,  TCP_KEEPIDLE,  &idle, sizeof(idle)) 
setsockopt (sock_fd,  SOL_TCP,  TCP_KEEPINTVL,  &intvl, sizeof(intvl)) 
setsockopt (sock_fd,  SOL_TCP,  TCP_KEEPCNT,  &cnt,  sizeof(cnt))

以上几个参数含义为:

  • TCP_KEEPIDLE:多久没有交互时,发送一个心跳包
  • TCP_KEEPINTVL:每次探活间隔多久
  • TCP_KEEPCNT:一共探活多少次
Read More

^