协程/Coroutine上手

概述

协程/Coroutine(协作的线程?),也可称为微线程,在系统中等级在thread之下(也既一个thread可拥有多个coroutine)(由用户态控制具体实现)(与软件模拟多线程类似)

协程可以看做是一个并行的子程序,有自己的独立栈空间与context,程序可以在主进程中转入某协程中进行操作(主进程挂起),同时在协程中也可以转回主进程(协程挂起,栈空间不销毁),并支持等待之后再回到该协程中进行进一步操作

另一个理解:在使用上等效于一个带token的多进程模型,只有拿到token模型可以进行工作,其余进程必须等待
或者说,”串行同步”
由于同时仍然最多只有一个线程在进行操作,故也无需使用多进程锁

实例

传统的生产者-消费者模型是一个线程写消息,一个线程取消息,通过锁机制控制队列和等待,但一不小心就可能死锁。
如果改用协程,生产者生产消息后,直接通过yield跳转到消费者开始执行,待消费者执行完毕后,切换回生产者继续生产,效率极高:

def consumer():
    r = ”
    while True:
        n = yield r
        if not n:
            return
        print(‘[CONSUMER] Consuming %s…’ % n)
        r = ‘200 OK’

def produce(c):
    c.send(None)
    n = 0
    while n < 5:
        n = n + 1
        print(‘[PRODUCER] Producing %s…’ % n)
        r = c.send(n)
        print(‘[PRODUCER] Consumer return: %s’ % r)
    c.close()

c = consumer()
produce(c)

执行结果:

[PRODUCER] Producing 1…
[CONSUMER] Consuming 1…
[PRODUCER] Consumer return: 200 OK
[PRODUCER] Producing 2…
[CONSUMER] Consuming 2…
[PRODUCER] Consumer return: 200 OK
[PRODUCER] Producing 3…
[CONSUMER] Consuming 3…
[PRODUCER] Consumer return: 200 OK
[PRODUCER] Producing 4…
[CONSUMER] Consuming 4…
[PRODUCER] Consumer return: 200 OK
[PRODUCER] Producing 5…
[CONSUMER] Consuming 5…
[PRODUCER] Consumer return: 200 OK

注意到consumer函数是一个generator,把一个consumer传入produce后:
1. 首先调用c.send(None)启动生成器;
2. 然后,一旦生产了东西,通过c.send(n)切换到consumer执行;
3. consumer通过yield拿到消息,处理,又通过yield把结果传回;
4. produce拿到consumer处理的结果,继续生产下一条消息;
5. produce决定不生产了,通过c.close()关闭consumer,整个过程结束。

整个流程无锁,由一个线程执行,produce和consumer协作完成任务,所以称为“协程”,而非线程的抢占式多任务。
Ref:廖雪峰’s blog
可能的局限:由同一个线程同时负责消费和生产,效率显然不够高,同时难以支持更多线程的扩展

项目实例

对于CPP来说,暂时还没有官方支持的协程(可能会于C20加入)

#TODO

协程的优缺点

协程的优点:

(1)无需线程上下文切换的开销,协程避免了无意义的调度(内核负责的调度转变为了线程自己调度,实际上该做的事还得做?/*TODO:去知乎问个问题*/),由此可以提高性能(但也因此,程序员必须自己承担调度的责任,同时,协程也失去了标准线程使用多CPU的能力)

(2)无需原子操作锁定及同步的开销(简化模型)

(3)方便切换控制流,简化编程模型

(4)高并发+高扩展性+低成本:一个CPU支持上万的协程都不是问题。所以很适合用于高并发处理。

协程的缺点:

(1)无法利用多核资源:协程的本质是个单线程,它不能同时将 单个CPU 的多个核用上,协程需要和进程配合才能运行在多CPU上.当然我们日常所编写的绝大部分应用都没有这个必要,除非是cpu密集型应用。

(2)进行阻塞(Blocking)操作(如IO时)会阻塞掉整个程序

Ref:http://www.cnblogs.com/zhangxinqi/p/8337207.html

主要用于异步?//TODO

Coursera machine learning work week3

sigmoid.m

Sigmoid函数是一个信息科学中常用的阀值函数,其意义是将任意离散的值映射到0-1之间以方便进一步处理

新的编辑器真的和狗屎一样,然后我又咕了

约瑟夫环问题的递归解法

题源:2017蓝桥杯国赛

基本问题描述:
已知n个人(以编号1,2,3…n分别表示)围坐在一张圆桌周围。从编号为1的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。而问题一般是判断第k个出列或最后出列的人的编号.

有些人在解决这类问题时会把编号视为0~n-1,最后将结果+1而得原问题的解,但在此我就不这样做了.

解题思路:

此题最简单的做法可以使用模拟法完成,但不论是用数组模拟还是链表模拟,复杂度都比较高(链表模拟法每次删人需要迭代n次,总复杂度为O(mn),而数组模拟法复杂度甚至更高).

该题问题的关键在于当有人被T出后队列中剩余的编号列表就不再连续了,此时再想使用数值计算的方法难以得到下一个位置,不得已才需要使用模拟的办法得到位置.

另一种办法是每次去除人后将新环的编号重排,这样编号顺序就再次连续了,而我们所要做的就是得到新编号与旧编号之间的对应关系计算方法(以便最后能够回推得到最终的答案).这样的话寻找第k次删除人的编号问题就变成了从其第k-1次重排的编号中回推得到它在原始队列中的…编号,复杂度只有O(k)/O(n)(但是这有一个问题,如果要按顺序得出每个出列的人的编号,这样做的复杂度就没有什么优势了).

举例来说:

起始n=10,m=6

初始情况为:

1   2   3   4   5   6   7   8   9   10

删除一人后:

1 2 3 4 5 ① 7 8 9 10

队列重排:

5 6 7 8 9 ① 1 2 3 4

再删一人:

5 ② 7 8 9 ① 1 2 3 4

我们现在要找到②处在原始序列中对应的编号,首先发现它在新队列中编号为6,而计算首次删除的①在队列中编号也为6,即新队列的编号是在前队列的基础上+6,那么将其相加后再对前队列的总人数求余即可得到他在前队列中的编号了((6+6)%10).

以此类推我们也可以从第k次删除后的情况反推出其在初始时的位置.

递归版代码:

java多线程编程的常见问题

(写个屁,自己根本就不懂

  • 如下,在多线程环境下,synchronized块中的方法获取了lock实例的monitor,如果实例相同,那么只有一个线程能执行该块内容
  • 直接用于方法: 相当于上面代码中用lock来锁定的效果,实际获取的是Thread1类的monitor(equal to synchronized(this)?)(具体来说是为了防止多个thread同时调用一个同一对象的该方法)。更进一步,如果修饰的是static方法,则锁定该类所有实例。

在AlertDialog中使用自定义layout

#傻逼安卓写的我自闭了…
#想起来上学期组里竟然写过这东西…连抄带查搞了半天才搞明白…
在安卓中默认的对话框只能接受单一文字输入,如果想要支持输入多种类型的内容的话必须使用自定义的layout
首先,我们先在主函数中获取layout并传入构造函数中

在构造函数中,只需要调用builder的setView方法并把自己的自定义layout传入其中即可使用自己的layout(我在这里使用的是constraintlayout,不确定其他layout可不可行).
与此同时,我们还可以同时调用setTitle,setIcon等方法对该dialog进行美化.

注意到在dialogbuilder中有3个方法,这可以设置该dialog中3个不同的按钮,我们可以对三个按钮设置不同的点击事件,可以方便执行返回或暂存等操作(这里只写了一个).
最终成果如下图:      #一眼就能看出来我是哪抄的了吧

简单的梯度下降代码实践

2018CCPC网络预选赛1010/hdu6447 离散化/DP/线段树

http://acm.hdu.edu.cn/showproblem.php?pid=6447

题意:
从(0,0)(0,0)走到(10^9,10^9)(10^9,10^9),其中每次只能往(x+1,y),(x+1,y+1),(x,y+1)三个目标走,期间有n个村庄,但每个村庄只能从其(x-1,y)或(x,y-1)走到其上才能获得该村庄的金钱vk,问最后可以获得的最大金钱

分析:
最大值规划问题很自然的会想到用DP做,但此处单纯对每个城镇进行DP的话每次需要遍历所有城镇,复杂度是O(n^2),难以解决.
另一个想法是以坐标作为基准进行DP,这样的话我们需要先将城镇坐标进行离散化,然后用dp[n]储存到达第n列时达到的最大金钱,并将城镇按照从上到下,从右到左进行排序.
之后迭代遍历每个城镇,对于第n列的某城镇k,dp[n]=max(dp[n],max(dp[1~n-1)+vk),城镇的排列顺序保证了迭代完成后dp[]能计算出到达每一列时的最大金钱,而区间查询可以使用线段树或树状数组进行优化,
最终达到的复杂度为O(nlogn)

代码如下:(事实上由于这个线段树写的特别渣,导致最终通过时间大概是990ms左右,也有TLE的可能…)