不会开机的男孩

Stanford 算法课 Part 2 Scheduling

| Comments

当一个人每天都有做不完的事情时,不知道大家又没有这种感觉。各种各样的事情,各种deadline,甚至是一些无关紧要的琐碎事情也会不断的在大脑中被回想,而且还是反复的,没有任何理由的会冒出来。对像我这样非常懒惰的人来说,这就是一个非常致命的打击,因为我需要中断当前的事情,这会让我多消耗不少脑力。。。

这应该算是时间管理中的一部分,如何给自己安排任务。人的大脑和电脑的工作模式还是有一些类似的,比如如果一直不断的记录一大堆事情而不是执行,那么就会影响到他们的工作效率。同样,如果重要的事情不作,最后也会不断的在大脑里面被回想,而造成效率降低。

在我看来,解决这些回想问题最关键的事情就是把这些东西搞定,这样才能把大脑清空,然后去做那些更加有意义的事情。

最近再跟algorithm part2里面正好有一个scheduling application的东西,挺有意思的。这里记录一下。

问题描述

Setup

scheduling 的基本模型是有一个shared resource,比如CPU。但是有许多jobs,比如很多线程,需要使用CPU才能运行。

Question

我们应该如何调度这个jobs的顺序,哪一个job优先于其他job执行,从而让整个计划执行时间最少。

Assume

为了更清楚的定义数学模型,每一个job有2个维度。

  • weight 重要性
  • length 时间

Defintion

Completion time。 第J个任务的完成时间(Completion time)Cj 是 (任务J之前的等待时间 + 任务J的length)* 任务J的weight

思路

这里根据直觉可以很明显的知道 我们需要把重要的事情放在前面,把时间短的事情放置在前面,这样可以很快的打一个勾勾,清空大脑中的这个任务。也就是说Cj 和 Wj 正相关,和 Lj负相关。但是总是有一些事情让人欲罢不能,就是那些很重要,而且做起来还比较费劲,时间花费长的事情,和那些不重要但是时间花费短的事情。真实世界的事情太复杂,还是回到我们这个简单的模型中。

一种常见的思维是设法将问题转换成之前我们已经解决了的思路之中,所以很容易想到我们需要找到单位长度中最重要的事情先做。因为我们的这个模型的任务调度不是抢占式的么。

将上面的单位时间的含义翻译过来就是 wj / lj。 也就是我们的调度程序将按照w / l的值,从大到小排列 scheduling 1

这里我们假定任务i > j。这个图则表示这2个任务相连在一起,stuff表示之前的任务,more stuff表示之后的任务。

scheduling 2

而这里,我们做一次任务i、j的交换,就像这样

image

那个这2个scheduling中,i,j之前的任务的完成时间不会变,之后的任务完成时间也不会变。那么受到影响的只是任务i,j。

image

那么这里显然scheduling 2 也就是后面的那张图的顺序比第一个要小。

然后我们可以想象最后的任务流程,就如果冒泡排序一样,一次次的比较把相对重要的数据一次次的放置到前面。

而当所有相邻的任务都按照这样的规则排列完毕后,得到的就是一个 wj / lj 的从大到小的序列。

Calm Down

| Comments

最近已经发生了很多事情,将来也会发生一些事情,这里为了不让我负能量爆发,就不写这些细节了。昨天和老大聊到晚上3点半,这里我还很dt的查了一下,上一次聊这么晚也就是2个月前。刚刚突然发现有人赞了一下我的微博,哦,很好,长出一口气,终于不是强X的无脑赞了。微博的内容是一篇关于《女人明白要趁早》的读书笔记,书里写过一句这样的话“这世上只有快乐的猪和悲伤的哲学家”,但在我看来,还有另一类人是悲伤的猪,而我显然属于后者。当然这不是我想说的,书中有一些这样的话。

“当你一无所知、一无所有、一无所成的时候,没事不要去想“个人尊严”和“个人价值”这 类虚词儿。一、做好眼前事。二、假以时日。 有完美榜样是好的,能让我们矢志不渝地去为追求完美努力;知道榜样其实不完美也是好的, 避免我们成为偏执狂,或者因为目标难以企及而自暴自弃。”

这个世界上面充斥这这样子的言论,你没有办法去反驳它,因为他本身说的就是事实,是正确的,而且是毫无疑问正确的,但是如果只是做到这些是不可能成功,或是更严格讲,这些都不是成功的关键因素,从心理学角度来看,这些话没有办法被证伪。这些话就是一个个成功人士为了安慰屌丝们的心灵鸡汤而已。

对于年轻的人们来说,经历的苦难和挫折大概都是因为阅历,资历不足,内心却比地球还大,一开始就像构建一艘航空母舰。但最后发现这样的航母根本做不出来,或是做出来随便小小的浪头就能把它拍的粉碎。而也有不少人意识到了这一点,做出了一艘艘驱逐舰,潜艇。但最后发现,光这艘船,根本不可能带你穿过那些暴风雨频发的海域。

我们害怕跌入日复一日平淡庸碌的结婚、生子、还房贷、终老一生的生活中去。但是现实就是这个社会最不缺的就是空想家,社会不仅不看你的想法,不在意你的未来,更不在意你的过去,只是看你的现在,你的所作所为。你所能掌握的资源,你能做出多少选择的能力。

大家都会成长,会慢慢看淡这些ups and downs,大家都在说,现在社会多么浮躁,年轻人要学会等待,假以时日,每天坚持,就会变好的。我只想说“呵呵”。平静会很容易的掩饰内心的平庸,诚然平静很重要,但绝对不是逃避,需要cope,而这需要一个强大的内心。只有内心足够强大才能做出抵挡风浪的船,而不是随流漂动的木板,虽然他们都是在水上浮着,当然木板也有好处,船会翻。木板不会。

一个朋友曾今问过我为什么给自己设定一个30岁的目标,因为有太多的东西我们不能左右,在到一定年纪就不得不考虑,作为一个男孩子,不得不去承担一些该来的责任,那么自由时间必定要被压缩,而且有一些事情,年纪大了,也就错过机会了,或是需要付出比年轻时候更多的投入。所以必须趁年轻,因为在再不疯狂就来不及了。

Tal在幸福课中提到一句,平庸和卓越在表面都很平静时是如何区分出来。卓越的人更会相信自己会做到。

额,本来还是想写下去,发现自己已经不知不觉开始写心灵鸡汤了,看来我已经被毒害不少了,再删掉一大段之后,思路瞬间被阻塞了。一阵阵困意袭来,呼~,昨天睡得有一点少了。今天最开心的就是,去东直门上了一节跳舞课,按照我以往对我自己的了解,我应该死宅在家里才对,绝对不会出门,更别说走这么远。

Cocoapods 入门

| Comments

介绍

最近一直在搞cocoapods。 ios 这么多年终于有一个好使的包管理了。真的好激动好激动。。。 之前开发一些App的时候,在一开始的时候,总是需要手动添加framework, library,设置一些 search path,有时候还会忘记那么几个,然后出来一大堆的link error。当一些library更新的时候,还需要自己手动去更换。3句话说就是

  1. 手动增加framework,library
  2. 手动增加编译参数
  3. 手动维护代码更新

完全是一大堆的体力活,当然,这些简单的配置和复制并不会花费太多的时间,但是,还是觉得在浪费生命,而这时候CocoaPods就出来了。我们只需要设置一个Podfile文件,执行

$ pod install 

CocoaPods会帮我们下载好代码,设置好编译参数,配置好framework, library。

安装和更新

$ sudo gem install cocoapods

使用

在project根目录下,create Podfile文件,下面一个例子

platform :ios, '5.0'
pod 'CURestKit', '~>1.0.1' 
pod 'SDWebImage','~>3.4'
pod 'MBProgressHUD', '~> 0.7'
pod 'UALogger', '~> 0.2.3'

CocoaPods 会帮我们从git clone下来配置好的这些代码。后面的部分表示代码的版本号,一般来说和tag挂钩。

配置好Podfile之后,执行

$ pod install

则会帮我们配置好这些项目。并生成一个XXXX.xcworkspace。 以后project使用这个文件就可以了。CocoaPods其实就是帮我们配置一个静态库作为项目的依赖。

CocoaPods里面有大量的代码,现在最新的版本安装后是在这里

~/.cocoapods/repo/master/ 

制作自己的项目配置

实际开发过程中,我们还有不少代码需要被改动,而CocoaPods上面的代码,大部分都比较旧,都是很稳定的代码,当然也有一些不能用的(大部分是国内的公司做的,大家都懂的)。另外还有一些我们自己写的一些其他代码,暂时还么有被CocoaPods收录的。这时候我们就需要配置自己的项目啦。

这里是我的一个项目配置例子。cocoapods的配置文件就是一个 *.podspec的文件,这是一个例子文件名ShareCenter.podspec。这是一个典型的ruby,

Pod::Spec.new do |s|
s.name         = "ShareCenter"
s.version      = "2.0"
s.summary      = "share client include sina weibo ,tencent weibo, renren"

s.description  = <<-DESC
               share client include sina weibo ,tencent weibo, renren
               DESC

s.homepage     = "https://github.com/studentdeng/ShareCenterExample"
s.license      = 'MIT'
s.author       = { "curer" => "studentdeng@hotmail.com" }
s.platform     = :ios, '5.0'

s.source       = { :git => "https://github.com/studentdeng/ShareCenterExample.git", :tag => s.version.to_s }
s.source_files  = 'ShareCenter', 'ShareCenter/**/*.{h,m}'

s.frameworks   = 'QuartzCore', 'Security', 'CoreGraphics', 'AudioToolbox'
s.library = 'sqlite3.0'
s.vendored_libraries = 'ShareCenter/Vender/sina/libWeiboSDK/libWeiboSDK.a'

s.prefix_header_contents = <<-EOS
#ifdef __OBJC__
#import "ROConnect.h"
#endif /* __OBJC__*/
EOS
end

这个基本上都是自解释的,这里有几个需要说明一下

s.source s.source_files

这里的 source 我们看出是一个git 的地址,这里我们调试的时候,可以先暂时设置成本地git,调试完毕之后就可以发布 增加tag。想要最新的代码只需要这样设置就好

{ :git => "https://github.com/studentdeng/ShareCenterExample.git"}

我们的git项目中,并不是所有的代码都需要被引用到我们的代码中,通常project还会包括一些example,test cases等,这里的 source_files 就是用来指定一些文件夹,或是文件。我这里的设置也很容易理解,就是ShareCenter下面的递归后的所有后缀是h、m的子文件。

s.frameworks s.library

这里配置的就是我们的framework 和 library,这里注意一下library的名字规则就好。

vendored_libraries

这里用来指定外部的静态库。这里我们指定了sina sso认证的SDK

s.prefix_header_contents

这里用来指定预编译的配置,这里一定要鄙视一下renren的超级渣渣SDK。这里提供一种解决方法。

部署我们的配置到cocoapods中

cocoapods的代码配置文件是在这里Specs

这里最好是去fork一个自己的project,然后保存一个自己或是团队的配置,这样不会在更新cocoapods的时候,丢掉自己的配置。当然,如果觉得自己搞的还不错,也可以去pull requests。

在之前提到的目录~/.cocoapods/repo/master/ 下面,我们可以看到已经有超级多的项目了,我们可以也可以通过

$ pod search XXX

来查找项目,或是直接在这个文件夹下面找,可以学习不少project的配置技巧,我这里也是从他们学到的。

最后添加一个project的配置是这样子的。

例如上面的例子, 在~/.cocoapods/repo/master/ 下面创建一个文件夹ShareCenter,然后在创建一个2.0的文件夹表示这是version2.0的配置。 然后在把之前的ShareCenter.podspec复制到2.0目录下面。

也就是最后的目录是这样子的

~/.cocoapods/repo/master/ShareCenter/2.0/ShareCenter.podspec

如果希望更多的了解cocoapods,还是需要去Github上面 :D

Redis服务器启动流程

| Comments

整个系统初始化流程图

让我们从 redis.c -> main() 开始

读取配置文件

在初始化完毕一些系统时间之后,redis开始初始化服务器配置。

initServerConfig

在这个函数中,初始化全局变量

struct redisServer server; /* server global state */

struct redisServer 结构体描述了服务器的状态。这种庞大的数据结构实在是看的烦躁。 这里可以很方便的看到redis的系统默认配置。另外还初始化了系统命令表。

server.commands = dictCreate(&commandTableDictType,NULL);
populateCommandTable();

这里我们可以找到redis的命令所对应的函数名称。

struct redisCommand redisCommandTable[] = {
    {"get",getCommand,2,"r",0,NULL,1,1,1,0,0},
    {"set",setCommand,3,"wm",0,noPreloadGetKeys,1,1,1,0,0},
    {"setnx",setnxCommand,3,"wm",0,noPreloadGetKeys,1,1,1,0,0},
    {"setex",setexCommand,4,"wm",0,noPreloadGetKeys,1,1,1,0,0},
    {"psetex",psetexCommand,4,"wm",0,noPreloadGetKeys,1,1,1,0,0},
    {"append",appendCommand,3,"wm",0,NULL,1,1,1,0,0},
    //...
}


struct redisCommand {
    // 命令的名字
    char *name;
    // 命令的实现函数
    redisCommandProc *proc;
    // 命令所需的参数数量
    int arity;
    // 字符形式表示的 FLAG 值
    char *sflags; /* Flags as string represenation, one char per flag. */
    // 实际的 FLAG 值,由 sflags 计算得出
    int flags;    /* The actual flags, obtained from the 'sflags' field. */
    /* Use a function to determine keys arguments in a command line.
     * Used for Redis Cluster redirect. */
    // 可选,在以下三个参数不足以决定命令的 key 参数时使用
    redisGetKeysProc *getkeys_proc;
    /* What keys should be loaded in background when calling this command? */
    // 第一个 key 的位置
    int firstkey; /* The first argument that's a key (0 = no keys) */
    // 第二个 key 的位置
    int lastkey;  /* THe last argument that's a key */
    // 两个 key 之间的空隔
    int keystep;  /* The step between first and last key */
    // 这个命令被执行所耗费的总毫秒数
    long long microseconds;
    // 这个命令被调用的总次数
    long long calls;
};

这里可以看出,redis的命令配置,保存在底层数据结构dic中。

服务器初始化

initServer

这里设置信号回调函数,和继续初始化

struct redisServer server; /* server global state */

结构外,创建了SharedObjects。

createSharedObjects

initServer->createSharedObjects

redis这里将除了把一些常用的字符串保存起来,目的就是为了减少不断申请释放时CPU时间,内存碎片等等,常用的返回客户端的命令,消息等。如

shared.ok = createObject(REDIS_STRING,sdsnew("+OK\r\n"));
shared.err = createObject(REDIS_STRING,sdsnew("-ERR\r\n"));

//...

shared.wrongtypeerr = createObject(REDIS_STRING,sdsnew(
    "-WRONGTYPE Operation against a key holding the wrong kind of value\r\n"));
//...

还初始化了一个很大的共享数字对象。

#define REDIS_SHARED_INTEGERS 10000

for (j = 0; j < REDIS_SHARED_INTEGERS; j++) {
    shared.integers[j] = createObject(REDIS_STRING,(void*)(long)j);
    shared.integers[j]->encoding = REDIS_ENCODING_INT;
}

aeCreateEventLoop

initServer->aeCreateEventLoop



/* Include the best multiplexing layer supported by this system.
* The following should be ordered by performances, descending. */
#ifdef HAVE_EVPORT
    #include "ae_evport.c"
#else
    #ifdef HAVE_EPOLL
        #include "ae_epoll.c"
    #else
        #ifdef HAVE_KQUEUE
            #include "ae_kqueue.c"
        #else
            #include "ae_select.c"
        #endif
    #endif
#endif

接下来创建eventloop。这里调用 aeApiCreate 创建event loop。redis这里根据不同平台会选择不同的event方式, Linux 使用epoll,BSD上面使用kqueue,其他选择select

初始化网络连接

if (server.port != 0) {
    server.ipfd = anetTcpServer(server.neterr,server.port,server.bindaddr);
    if (server.ipfd == ANET_ERR) {
        redisLog(REDIS_WARNING, "Opening port %d: %s",
            server.port, server.neterr);
        exit(1);
    }
}

if (server.unixsocket != NULL) {
    unlink(server.unixsocket); /* don't care if this fails */
    server.sofd = anetUnixServer(server.neterr,server.unixsocket,server.unixsocketperm);
    if (server.sofd == ANET_ERR) {
        redisLog(REDIS_WARNING, "Opening socket: %s", server.neterr);
        exit(1);
    }
}

创建系统cron定时器

aeCreateTimeEvent(server.el, 1, serverCron, NULL, NULL);

aeCreateTimeEvent
aeCreateTimeEvent accepts the following as parameters:
eventLoop: This is server.el in redis.c
milliseconds: The number of milliseconds from the current time after which the timer expires.
proc: Function pointer. Stores the address of the function that has to be called after the timer expires.
clientData: Mostly NULL.
finalizerProc: Pointer to the function that has to be called before the timed event is removed from the list of timed events.

aeCreateTimeEvent 创建一个定时器,redis会在这个serverCron中清理系统变量,判断是否需要写入文件等操作。

在event loop中绑定回调函数

if (server.ipfd > 0 && aeCreateFileEvent(server.el,server.ipfd,AE_READABLE,
    acceptTcpHandler,NULL) == AE_ERR) redisPanic("Unrecoverable error creating server.ipfd file event.");            

设置启动event loop

// 设置事件执行前要运行的函数
aeSetBeforeSleepProc(server.el,beforeSleep);

// 启动服务器循环
aeMain(server.el);

// 关闭服务器,删除事件
aeDeleteEventLoop(server.el);

aeMain函数和之前用的很多的windows中的message queue非常相似。redis不断循环等待执行event。这里不论是定时器还是socket event,都会在这个event loop中被执行。

void aeMain(aeEventLoop *eventLoop) {

eventLoop->stop = 0;

while (!eventLoop->stop) {

    // 如果有需要在事件处理前执行的函数,那么运行它
    if (eventLoop->beforesleep != NULL)
        eventLoop->beforesleep(eventLoop);

    // 开始处理事件
    aeProcessEvents(eventLoop, AE_ALL_EVENTS);
    }
}

方便整理,这里重复一下一开始的流程图

整个系统初始化流程图

处理客户端命令流程

处理客户端命令流程图

之前我们已经注册了socket acceptTcpHandler 回调函数,现在的流程是

acceptTcpHandler->acceptCommonHandler->createClient->aeCreateFileEvent

if (aeCreateFileEvent(server.el, c->fd, AE_READABLE,
    readQueryFromClient, c) == AE_ERR) {
    freeClient(c);
    return NULL;
}

这里又向event loop中加入一个新的事件callback函数:aeCreateFileEvent 用于把event loop中的监听的事件和回调函数绑定在一起。

readQueryFromClient 则是客户端一切命令的入口函数。

void readQueryFromClient(aeEventLoop *el, int fd, void *privdata, int mask) {
    redisClient *c = (redisClient*) privdata;
    char buf[REDIS_IOBUF_LEN];
    int nread;
    // ...

    nread = read(fd, buf, REDIS_IOBUF_LEN);
    // ...
    if (nread) {
        size_t oldlen = sdslen(c->querybuf);
        c->querybuf = sdscatlen(c->querybuf, buf, nread);
        c->lastinteraction = time(NULL);
        /* Scan this new piece of the query for the newline. We do this
        * here in order to make sure we perform this scan just one time
        * per piece of buffer, leading to an O(N) scan instead of O(N*N) */
        if (c->bulklen == -1 && c->newline == NULL)
            c->newline = strchr(c->querybuf+oldlen,'\n');
    } else {
        return;
    }
    Processinputbuffer(c);
}

readQueryFromClient读取客户端命令,交给Processinputbuffer处理。

void processInputBuffer(redisClient *c) {
    //...

    if (processCommand(c) == REDIS_OK)
        resetClient(c);
}

int processCommand(redisClient *c) {
    //...
    call(c,REDIS_CALL_FULL);
}

这里call回根据command定义的callback函数,执行相对应的redis命令代码。

当command执行完毕之后,准备将结果传递给客户端。这里可以看到注册了sendReplyToClient回调函数。

int prepareClientToWrite(redisClient *c) {
    if (c->flags & REDIS_LUA_CLIENT) return REDIS_OK;
    if (c->fd <= 0) return REDIS_ERR; /* Fake client */
    if (c->bufpos == 0 && listLength(c->reply) == 0 &&
        (c->replstate == REDIS_REPL_NONE || c->replstate == REDIS_REPL_ONLINE) &&
        aeCreateFileEvent(server.el, c->fd, AE_WRITABLE, sendReplyToClient, c) == AE_ERR)
            return REDIS_ERR;
    return REDIS_OK;
}

读到这里,我们已经看到了。redis在处理event loop的时候,不仅仅是处理客户端的连接,很多redis内部的流程也是通过event loop实现的。这个是event driven常常遇到的方式。

内容资料、图片、代码参考

Box2d 05 RevoluteJoint and b2WeldJoint

| Comments

资料代码,思路来自 raywenderlich。这个只是自己学习时的笔记,非原创。

b2RevoluteJoint

  • 将刚体固定在一个点上,刚体可以围绕这个点旋转
  • 可以提供马达,提供刚体旋转的动力

所以,通过b2RevoluteJoint的第一个特性,我们可以很方便的模拟跷跷板。而第二个特性,我们可以很方便的实现汽车运动,或是弹弓类似的东西,今天实现一个类似疯狂小鸟的demo

创建b2RevoluteJoint很简单,但是里面有一些属性还是让人比较纠结,特别是好多中文blog,不知道是笔误还是无心,都是错的 =, =!

b2RevoluteJointDef armJointDef;
armJointDef.Initialize(groundBody, armBody, b2Vec2(233.0 / PTM_RATIO, FLOOR_HEIGHT / PTM_RATIO));

armJointDef.enableLimit = true;
armJointDef.lowerAngle = CC_DEGREES_TO_RADIANS(9);
armJointDef.upperAngle = CC_DEGREES_TO_RADIANS(75);

armJointDef.enableMotor = true;
armJointDef.maxMotorTorque = 200;
armJointDef.motorSpeed = - 10;

armJoint = (b2RevoluteJoint *)world->CreateJoint(&armJointDef);

这3个很好理解,就是对我们的旋转做限制。单位是弧度。

  • enableLimit
  • lowerAngle
  • upperAngle

这3个稍微不好理解

  • enableMotor: 表示是否开启我们的旋转马达
  • motorSpeed: 表示我们希望马达给我们提供的速度是多少,小于0表示顺时针
  • maxMotorTorque: 表示马达给我们提供的扭矩有多少。

简单的说,就是maxMotorTorque为我们提供改变速度的力。motorSpeed表示我们希望达到的最大速度是多少。

b2WeldJoint

b2WeldJoint又是一个很好理解的连接器。b2WeldJoint通过一个点把2个刚体绑定在一起运动。

b2WeldJointDef weldJointDef;
weldJointDef.Initialize(bulletBody, armBody, b2Vec2(230.0f/PTM_RATIO,(155.0f+FLOOR_HEIGHT)/PTM_RATIO));
weldJointDef.collideConnected = false;

bulletJoint = (b2WeldJoint*)world->CreateJoint(&weldJointDef);

在弹弓实例下,我们可以将炮弹绑定在我们的发射架上,当发射架运动到一定角度时,我们可以释放这个连接器,炮弹就可以射出了。

source code