软件分享网站,不一样的婚恋网站怎么做,上海搬家公司排名第一,中英文网站建站上一篇介绍了 co_await 的例子。与 co_await 类似#xff0c;在C23的协程特性里#xff0c; co_yield 用于从协程执行过程中暂停#xff0c;并返回值。这个功能乍一听起来很奇怪#xff0c;网上的例子大多是用一个计数器来演示多次中断协程函数#xff0c;返回顺序的计数值…上一篇介绍了 co_await 的例子。与 co_await 类似在C23的协程特性里 co_yield 用于从协程执行过程中暂停并返回值。这个功能乍一听起来很奇怪网上的例子大多是用一个计数器来演示多次中断协程函数返回顺序的计数值。这看起来毫无意义。
其实这个功能主要想演示的就是协程 co_yield 具备打断一个函数的执行并多次返回值的能力。这种能力允许实现一种隐式状态机每次使用时返回下一个状态。这对于极为复杂的状态计算来说是很有用的。它协程避免了显式的设置状态记忆句柄大大简化了实现难度。同时由于可以任意打断执行便于在中间获取、展示一些数据状态、甚至单步调试对构造一些教学程序意义重大。典型的是观察堆排序的中间态不需要大幅度修改排序算法插入很多的printf而是在函数外部做。
我们以产生任意P(N,M)、C(N,M)这样的排列、组合数序列为例子看看传统算法和协程的区别。
1. 回溯法迭代排列组合
传统的回溯法求取一个排列的算法如下
void pnm_calc(const int n, const int m)
{std::vectorint vec_buf,vec_bz;int swim 0;bool finished false;for (int i0;im;i) vec_buf.push_back(0);for (int i0;in;i) vec_bz.push_back(0);do{int ch 0;if (swimm){while (vec_bz[ch])ch;vec_buf[swim] ch;vec_bz[ch] 1;swim;}if (swimm){//打印for (int i0;im;i)printf(%d,,vec_buf[i]);printf(\n);bool hit false;do{if (swimm swim 0) vec_bz[vec_buf[swim]] 0;--swim;if (swim0){int nextv vec_buf[swim];do{nextv;if (nextv n)break;if (vec_bz[nextv]0)hit true;} while (hit false);if (hittrue){vec_bz[vec_buf[swim]] 0;vec_buf[swim] nextv;vec_bz[nextv] 1;swim;}}elsefinished true;} while (finished false hit false);}}while(finished false);
};
int main(int argc, char *argv[])
{pnm_calc(4,3);return 0;
}
输出
0,1,2,
0,1,3,
0,2,1,
0,2,3,
...
3,1,2,
3,2,0,
3,2,1,2 传统状态机封装
上述打印显示结果演示的是回溯法本身。若为了更好地使用组合数需要对算法进行封装以便于批量的获取、运用组合数的各组结果。比如考虑到总数可能很大需要分批次返回结果等功能显著增加了工作量。
#include vector
#include cstdio
struct tag_NM_State
{std::vectorunsigned short vec_buf;std::vectorunsigned short vec_bz;int swim;bool finished;
};
/*!\brief pnm 快速算法使用带有记忆效应的 tag_NM_State 记录穷尽进度很好的避免了重新计算的耗时\fn pnm\param n N集合数\param m M, 子集\param vec_output 存储结果的集合,本集合会自动增长\param state 状态存储\param limit 本次最多样本数\return int 本次给出的样本数*/
int pnm(int n, int m, std::vectorstd::vector unsigned short vec_output,tag_NM_State * state, int limit/* 0*/)
{std::vectorunsigned short vec_buf state-vec_buf, vec_bz state-vec_bz;int swim state-swim;bool finished state-finished;const bool firstRun vec_output.size()?false:true;if (vec_bz.size()0){for (int i0;im;i) vec_buf.push_back(0);for (int i0;in;i) vec_bz.push_back(0);swim 0;finished false;}if (finishedtrue)return 0;int group 0;do{int ch 0;if (swimm){while (vec_bz[ch])ch;vec_buf[swim] ch;vec_bz[ch] 1;swim;}if (swimm){if (!firstRun)memcpy(vec_output[group].data(),vec_buf.data(),m*sizeof(unsigned short));elsevec_output.push_back(vec_buf);group;bool hit false;do{if (swimm swim 0) vec_bz[vec_buf[swim]] 0;--swim;if (swim0){int nextv vec_buf[swim];do{nextv;if (nextv n)break;if (vec_bz[nextv]0)hit true;} while (hit false);if (hittrue){vec_bz[vec_buf[swim]] 0;vec_buf[swim] nextv;vec_bz[nextv] 1;swim;}}elsefinished true;} while (finished false hit false);if (grouplimit limit0)break;}}while(finished false);return group;
}int main(int argc, char *argv[])
{QCoreApplication a(argc, argv);using std::vector;tag_NM_State state;const int n 4, m 3, group 10;vectorvectorunsigned short result;int ret pnm(n,m,result,state,group);while (ret0){printf(\ngroup contains %d results:\n,ret);for (int i0;iret;i){printf(\n\t);for (int j0;jm;j)printf(%d ,result[i][j]);}ret pnm(n,m,result,state,group);}printf(\nFinished\n);return 0;
}
分批输出 group contains 10 results:0 1 20 1 30 2 10 2 30 3 10 3 21 0 21 0 31 2 01 2 3
group contains 10 results:1 3 01 3 22 0 12 0 32 1 02 1 32 3 02 3 13 0 13 0 2
group contains 4 results:3 1 03 1 23 2 03 2 1
Finished
详细算法参考 https://goldenhawking.blog.csdn.net/article/details/80037669
3. 协程封装
使用C23 协程后使用变得非常简洁
int main(int argc, char *argv[])
{const int n 4 , m 3;nmCalc pnm pnm_calc(n,m);while (pnm.next()){const int * res pnm.currResult();printf(\n\t);for (int j0;jm;j)printf(%d ,res[j]);}
}
每次调用 pnm.next() 就返回下一组结果且无需记忆状态。
但这也是有代价的为了达到上述的效果协程封装如下
#ifndef NMCALC_H
#define NMCALC_H
#includecoroutine
#includevector
class nmCalc
{
public:struct promise_type {//记录本次排列组合的结果const int * m_currResult;auto get_return_object() { return nmCalc{ handle::from_promise(*this) }; }auto initial_suspend() { return std::suspend_always{}; }auto final_suspend() noexcept { return std::suspend_always{}; }void unhandled_exception() { return ;}void return_void(){}auto yield_value(const int * result ) {this-m_currResultresult; return std::suspend_always{}; }};using handle std::coroutine_handlepromise_type;
private:handle hCoroutine;nmCalc(handle handle) :hCoroutine(handle) {}
public:nmCalc(nmCalc other)noexcept :hCoroutine(other.hCoroutine) { other.hCoroutine nullptr; }~nmCalc() { if (hCoroutine) hCoroutine.destroy(); }//请求下一组结果调用后 co_yield继续。bool next() const { return hCoroutine (hCoroutine.resume(), !hCoroutine.done()); }const int * currResult() const { return hCoroutine.promise().m_currResult; }
};nmCalc pnm_calc(const int n, const int m)
{std::vectorint vec_buf,vec_bz;int swim 0;bool finished false;for (int i0;im;i) vec_buf.push_back(0);for (int i0;in;i) vec_bz.push_back(0);do{int ch 0;if (swimm){while (vec_bz[ch])ch;vec_buf[swim] ch;vec_bz[ch] 1;swim;}if (swimm){//返回一组结果!!!!!co_yield vec_buf.data();bool hit false;do{if (swimm swim 0) vec_bz[vec_buf[swim]] 0;--swim;if (swim0){int nextv vec_buf[swim];do{nextv;if (nextv n)break;if (vec_bz[nextv]0)hit true;} while (hit false);if (hittrue){vec_bz[vec_buf[swim]] 0;vec_buf[swim] nextv;vec_bz[nextv] 1;swim;}}elsefinished true;} while (finished false hit false);}}while(finished false);
};4. 体会与思考
这种封装方式显著提高了算法流程的紧凑程度。无需考虑如何巧妙的保留状态而是直接借助协程随时打断并返回。
这在算法极其复杂的情况下尤其有效。同时对于单步演示比如按一下按钮出一次也很方便主要代码参考
https://gitcode.net/coloreaglestdio/qtcpp_demo/-/tree/master/qt_coro_test
运行效果
