俄罗斯方块转弯算法实现

关于俄罗斯方块程序对战程序中实现方块转弯的算法描述。

为了方便描述算法的原理,以方块的左上角为基准,简化问题为一个11的小方块,在rowcol的矩阵中可以最终移动到哪个位置。

现在来看看位置(x y)是否可以移动到(即使是临时的)。 如果它可以被移动到,那么它从哪个位置移动过来。也很简单。 首先,如果上面位置(x-1 y)可以被移动到,那么(x y)也是可以的。 其次,如果左边(x y-1)或右边(x y+1)的位置可以被移动到,那么(x y)也是可以的。

那么评估位置是否可以移动到(即使是临时的)的算法,就可以这么描述:

1.定义一个二维数组,表示某个格是否移动到(即使是临时的),默认为false不可以。
2.初始化第一行的状态,如果方块在(0 i)可放置(和当前矩阵没冲突)则设置state[0][i]为true。
3.从第二行开始遍历,针对每一行i进行以下处理
3.1.对当前行的列j进行遍历,如果当前位置可放置,且同一列上一行的位置可移动到,则state[i][j]为true
3.2.对当前行的列j进行遍历,如果当前位置state[i][j]为true,则往左边(右边)一直检查
3.3.如果左边位置k可放置,则state[i][k]为true,直到k不可放置或k位置已经为true

最后,通过检查state就可以直到哪个位置可以被移动到。判断这个位置是否是最终移动的位置,则可以判断该位置是否最后一行,或同一列的下一个位置是否可以放置。

不过这里还有个问题,就是即使知道某个位置是可以被移动到的,但怎么还原出下落的路线呢?

其实,我们可以记住拐点,就可以知道路线了。 现在我们在(4,3)位置记录上一个拐点(3,3),然后在(3,3)记录再上一个拐点(3,2),以此类推就可以得到下落路线(反向的)。 我们想要的结果是

(0,0)(+,+)(+,+)(+,+)(+,+)
(0,0)(1,0)(1,0)(+,+)(+,+)
(+,+)(+,+)(1,2)(+,+)(+,+)
(+,+)(+,+)(1,2)(3,2)(+,+)
(+,+)(+,+)(+,+)(3,3)(+,+)

具体怎么记录这个拐点呢?可以在上面的算法基础上修改一下即可。 首先,考虑把(x,y)这个拐点值记录为x*ROW+y,这样修改state为整形二维数组。

1.定义一个二维数组,表示某个格是否移动到(即使是临时的),默认为MAX(ROW*COL,一个不可能的拐点),表示不可以。
2.初始化第一行的状态,如果方块在(0 i)可放置(和当前矩阵没冲突)则设置state[0][i]为拐点(0,i),即j。
3.从第二行开始遍历,针对每一行i进行以下处理
3.1.对当前行的列j进行遍历,如果当前位置可放置,且同一列上一行的位置不为MAX,则state[i][j]为state[i-1][j]
3.2.对当前行的列j进行遍历,如果当前位置state[i][j]不为MAX,则往左边(右边)一直检查
3.3.如果左边位置k可放置,则state[i][k]为拐点(i,j),即i*COL+j,直到k不可放置或k位置不为MAX

我眼中的uee黑科技

备注: uee是我厂内部的一个前端框架.

这可能是最后一篇关于uee的文章了,因为已经不关注这个方面的技术很久了。术业有专攻,前端嘛,那可怕的前端摩尔定律,还是让专业人士去操心吧。

上个星期有一天,有同事反馈uee的watch不好使,变量已经修改,但watch回调方法不走进去。今天主要围绕这些类似的问题展开,不过呢,今天不对具体问题进行解析,今天主要讲讲uee的黑魔法,大道至简嘛,抽象(原理)和具体(使用)得两手抓,两手都要硬。

下面的内容,主要针对非专业前端(从其他领域过来的开发人员),或者对uee有兴趣的同事。专业人士请绕路。

先进行术语简介。ng1代表angular1.x版本,ng2代表angular2.x以上版本。

uee的本质是ng1

uee是一个前端mvvm框架,常用于SPA(single page application)的开发,虽然开发指南上没有明目张胆的宣传,但底层是ng1是事实,所以ng1.x的文档总是可以借鉴的,网上找到的关于ng1的吐槽也同样适用。关于什么是MVVM,参考阮大的博客http://www.ruanyifeng.com/blog/2015/02/mvcmvp_mvvm.html

ng1和ng2的区别,和雷锋、雷峰塔的区别差不多,外边新项目考虑ng的话,只会考虑ng2之后的版本。uee后来有个ts(typescript)版本,写法上高仿了ng2的写法,不过这里不关注。

ng1的核心概念比较多,DI,scope,双向绑定,指令,digest都是比较重要的,还是那句话,即使使用uee,熟悉ng1的核心概念没有任何坏处。

关于开发模式

这部分主要针对从传统MVC过来的童鞋,因为开发习惯的原因,总是会考虑操作页面,例如某个操作要让按钮高亮,有同学就可能贪方便直接操作style,但这不是正确的做法。mvvm关注的是数据的管理,界面的变化(dom)是自动的。习惯不纠正,写出来的代码可能很诡异。参考文章http://www.infoq.com/cn/news/2013/11/how-to-think-angularjs

变化来自watch

框架的第一印象就是一个页面上一个占位符,只要对应的变量发生变化,页面就会自动变化。这个特性是非常自然的,直到有一天你需要使用watch来监控一些变量,并在发生变化的时候做些什么。

其实,页面变化的魔法也是使用watch机制。所以某个页面上可能会生成非常多watch表达式。这个就是单向绑定的内容了。

例如下面的例子

<div>\{\{content\}\}</div>,就是会生成类似watch("content", function(){//修改div内容})的逻辑。

变化如何被感知 digest过程

现在页面有这么多watch,怎么鉴别有发生变化了?

客户端js是单线程执行的,所以不能写个死循环。可以想象到的做法有2种,一种就是死循环加个timeout或者interval,一种是被动触发。ng1是采用被动触发的,只是就是一些特殊的页面事件会导致检查的发生,这个检查的过程叫digest,俗称dirty check 脏检查。

主要的事件有,页面初始化,页面发生操作(例如点击,输入)等,至于一些异步行为,例如timeout,ajax等,正常是不会触发的,不过使用框架包装过的调用方式,也是会触发的。如果和其他框架例如jq插件等集成的话,或者需要确保调用到digest的话,就需要使用框架提供的apply这个功能,它会确保操作会被页面感知到,相信很多同学也见识过了。

不过,这里还有个细节: 联动更新,例如watch表达式a的时候改了表达式b,同时watch表达式b的时候又会修改a,那么页面中有一个表达式的值可能是旧的。ng1规避的做法比较简单,就是一次digest之后,发现有变更的话,再次执行一次digest,直到所有的表达式的值都稳定了,或者是超过了最大检查次数才停止。

示例伪代码如下:

watches =[] //保存所有的watch表达式和表达式的当前值
for each watch in watches //循环所有的watch表达式
    if watch中的变量发生变化(包括第一次初始化)
        记录表达式的新值
        执行回调,这个过程可能修改了其他变量

if 没有任何表达式发生变化
  exit
else
  重新执行一遍,直到检查达到最大次数

变化没起作用的常见原因

  • 跨页面修改数据

框架的作用域顶多就是一个html页面。但如果项目有复杂的集成方式,那么就可能有多个页面并存的情况,通过a页面去更新b页面的数据变得没那么自然。首先,无论是直接修改变量还是通过所谓的emit事件通知,都有可能没生效(要等b页面下一次digest才能感知到),直接修改dom的话,则存在其他一些问题。所以规避的方式,通常的做法只能调用b页面的某个方法,而这个方法通过嵌套apply来修改变量。

  • 修改数据但没有触发digest

这种常见于采用第三方js插件,或者直接使用普通的ajax,timeout异步操作等情况,同理只能使用apply。

  • ABA问题

ABA概念可以参考知乎文https://www.zhihu.com/question/23281499 就是修改了但没看出变化,例如改了之后又改回去。这种比较特殊,ng会认为你没有变化。开头提到的那个例子,就是某种情况下,一次digest过程中出现了变量又改回原值的情况。所以确实有这种需要,就得多点信息来标记你做了修改,例如增加个时间戳的字段。

  • 变量引用发生变化

意思就是说你修改的和你显示的,已经不是同一个对象了。这个涉及js对象和scope的一些特性,可以参考https://github.com/angular/angular.js/wiki/Understanding-Scopes 这个问题曾经也出现过

谈双向绑定

前面提到了单向绑定,当然双向绑定更是一个非常神奇的特性,特别是你写了一个页面控件,想和某个变量进行绑定,可能就需要考虑了。它的实现过程是这样的: 当变量发生变化的时候,需要修改页面,很明显这个可以通过建立watch表达式实现。另一方面,页面变化的时候,需要修改变量,这个可以通过dom事件,触发包裹在apply中的变量变更操作。掌握这个基本原理的话,在需要定位自带组件问题的情况下,就会减少很多阻碍。

谈自定义gadget

gadget是uee的概念,类似于ng2的component概念,是一种页面组件,包括页面,脚本,样式的大集合。需要了解一点,凡是自定义标签,在ng1中,都采用directive特性实现,只是directive以复杂难懂著称,在使用便利性上,gadget还是做得不错的。如果有需要调试gadget或者ui component的内部实现的情况,就需要掌握指令的各种奇怪接口。

业务开发中的同步与异步

在其他项目习惯了ajax同步操作带来的开发便利性,开始使用uee的时候,可能会发现强大如fire的请求,是没办法做同步的!例如请求a以后,再请求b,这种变得比较麻烦,实现通常是这样的,一是把请求合并,只搞一次就可以了,不过说的容易,实际处理会有很多限制。一种就是在回调方法中发起下一个请求,不过这么写少量还可以,多了就存在一个callback hell的问题。所以应该考虑引入异步控制库让代码更符合人的思维,例如这个async,https://caolan.github.io/async/docs.html

我的看法

uee作为一个前端框架,使用上还是可以的,gadget表现出来的特性也是不错的。不过,也有一些毛病(可能他们觉得是特性)。

一个比较奇怪的就是webroot占位符,宣称可以表示根路径,用来引用静态资源的时候很方便,这套路好难理解,硬生生和后端绑定一起了。而且处理静态资源分离的时候,规则也没那么自然。

另外一个类似fire这种大而全的怪物,源码长达数千行,我总感觉使用fire之后MVVM的边界反而更模糊了。

还有就是,其实uee不是完全定位在纯前端的框架,还包括一个gateway来对接(虽然不是强绑定),包括了一种类似mvc的绑定风格和一种服务总线的绑定实现。说白了,绑定实现是很忌讳的事情,如果它提供一个spring mvc的实现,我会觉得比较安心。

目前最流行的前端开源框架,有ng2,react,vue, ng2的套路比较深,是一个一站式框架,而其他两个更倾向于做好view这一块,其他由外部插件去实现。uee虽然也以时俱进,借鉴了ng2采用原生ts的方式,推出了ts版本,写法和ng2也比较像,不过累感不爱呀,这一次ng2的组件特性已经非常强大了,被人诟病的脏检查也改进了,窃以为直接native也是可以接受的。

简单说说jsonp原理

前几天参加面试,好几个面试者简历都写着jsonp,解决跨域之类的调用。于是问一下知不知道jsonp的实现原理,结果没一个答得上来,有点小失望。

这里简单描述一下关键点,权当一个记录。

假设a网页调用b网站的服务

  • a网站会准备一个方法,例如callme(args)
  • a网站在页面插入一个script标签,src指向b网站的地址,并带上callme作为参数
  • b网站处理后,把结果和回调方法的名字组成一个字符串返回,例如callme(‘ok’)
  • 由于是script标签,所以字符串会被当成js解析执行,相当于调用到了callme方法
  • 主要利用了script可以跨站点访问的特性,且只能用GET请求,需要服务端做点配合,并且需要信任服务器(安全考虑)。jquery的jsonp ajax只是封装了这个过程,让你看上去和普通ajax没什么区别,其实却一点关系都没有。

jsonp这种小魔法的原理,网上一搜就可以找到,还是要有点好奇心的。

浅谈编程中的位操作

昨天有同学谈起网络编程中各种奇怪的位运算,所以单独整理一下实践中的位运算,权当复习。

基本的位运算 位运算符包括与,或,非,异或,这属于common sence了,只要给出一段01二进制串,每个程序员应该都可以处理。

类型

无论编程语言中的类型怎样,只要涉及网络通信,存储,最终都会涉及一个字节的转换过程。对于java来说,主要考虑整型,浮点型,字符串,其中整型和字符串是最常用的。

  • 整型,在java都是有符号数,根据不同类型都有固定的字节长度,并采用补码形式。关于补码,可以看看这篇文章关于2的补码
  • 浮点型,包括单精度和双精度,采用IEEE的浮点表示法,比较少使用,可以通过深入理解计算机系统2.4.2 IEEE浮点表示,这个章节了解浮点数的二进制形式。
  • 字符串,java的字符串采用unicode字符表示,存储的时候通常得考虑字符编码,所谓字符编码,就是字符和字节的对应关系。有些api会允许直接写入或读取字符串,但是对底层采用的字符编码要心里有底。

大端法,小端法

例如一个数,0x12345678, 存储到0x01到0x04这4个字节,那么有2种方式,一种是12345678,叫大端法,一种是78563412,叫小端法。就是看最低有效位(78)是在高地址(04)还是低地址(01)。这方面找了个文章理解字节序,可以了解一下。

tcpip协议规定网络传输统一采用大端法。指的是ip,tcp等协议的头部信息。见TCP/IP详解5.2章节 应用层网络协议有时会看到这个描述,没说明的话,默认也是按大端法开发,比较适应阅读。

数据转换

应用层协议上经常会涉及一些数据位的转换,但是有时不能类型强制转换,例如:某个协议上用一个无符号byte,例如b,那么可以通过b & 0xff得到一个int。这个类型强转的区别在于它会保留符号位。

浅谈系统线程数限制

Linux进程与线程

概念就不提了,Richard Stevens的描述:

fork is expensive. Memory is copied from the parent to the child, all descriptors are duplicated in the child, and so on. Current implementations use a technique called copy-on-write, which avoids a copy of the parent’s data space to the child until the child needs its own copy. But, regardless of this optimization, fork is expensive. IPC is required to pass information between the parent and child after the fork. Passing information from the parent to the child before the fork is easy, since the child starts with a copy of the parent’s data space and with a copy of all the parent’s descriptors. But, returning information from the child to the parent takes more work. Threads help with both problems. Threads are sometimes called lightweight processes since a thread is “lighter weight” than a process. That is, thread creation can be 10–100 times faster than process creation. All threads within a process share the same global memory. This makes the sharing of information easy between the threads, but along with this simplicity comes the problem.

Linux中创建进程用fork操作,线程用clone操作。通过ps -ef看到的是进程列表,线程可以通过ps -eLf来查看。 用top命令的话,通过H开关也可以切换到线程视图。

具体到Java线程模型,规范是没有规定Java线程和系统线程的对应关系的,不过目前常见的实现是一对一的。 参考http://openjdk.java.net/groups/hotspot/docs/RuntimeOverview.html#Thread%20Management|outline

问题排查思路

如果创建不了Java线程,报错是

Exception in thread “main” java.lang.OutOfMemoryError: unable to create new native thread

下面是常见的问题原因:

内存太小

在Java中创建一个线程需要消耗一定的栈空间,默认的栈空间是1M(可以根据应用情况指定-Xss参数进行调整),栈空间过小或递归调用过深,可能会出现StackOverflowError。

对于一个进程来说,假设一定量可使用的内存,分配给堆空间的越多,留给栈空间的就越少。这个限制常见于32位Java应用,进程空间4G,用户空间2G(Linux下3G,所以通常堆可以设置更大一些),减去堆空间大小(通过-Xms、-Xmx指定范围),减去非堆空间(其中永久代部分通过PermSize、MaxPermSize指定大小,在Java8换成了MetaSpace,默认不限制大小),再减去虚拟机自身消耗,剩下的就是栈空间,假设剩下300M,那么理论上就限制了只能开300线程。不过对于64位应用,由于进程空间近乎无限大,所以可以不考虑这个问题。

ulimit限制

线程数还会受到系统限制,系统限制通过ulimit -a可以查看到。

https://ss64.com/bash/ulimit.html

caixj@Lenovo-PC:~$ ulimit -a
core file size          (blocks, -c) 0
data seg size           (kbytes, -d) unlimited
scheduling priority             (-e) 0
file size               (blocks, -f) unlimited
pending signals                 (-i) 7823
max locked memory       (kbytes, -l) 64
max memory size         (kbytes, -m) unlimited
open files                      (-n) 1024
pipe size            (512 bytes, -p) 8
POSIX message queues     (bytes, -q) 819200
real-time priority              (-r) 0
stack size              (kbytes, -s) 8192
cpu time               (seconds, -t) unlimited
max user processes              (-u) 7823
virtual memory          (kbytes, -v) unlimited
file locks                      (-x) unlimited

相关的限制有

max memory size - 最大内存限制,在64位系统上通常都设置成unlimited  
max user processes - 每用户总的最大进程数(包括线程) 
virtual memory - 虚拟内存限制,在64位系统上通常都设置成unlimited 

这些参数可以通过ulimit命令(当前用户临时生效)或者配置文件/etc/security/limits.conf(永久生效)进行修改。   检查某个进程的限制是否生效,可以通过/proc/PID/limits查看运行时状态。

参数sys.kernel.threads-max限制

https://www.kernel.org/doc/Documentation/sysctl/kernel.txt

This value controls the maximum number of threads that can be created
using fork().

During initialization the kernel sets this value such that even if the
maximum number of threads is created, the thread structures occupy only
a part (1/8th) of the available RAM pages.

The minimum value that can be written to threads-max is 20.
The maximum value that can be written to threads-max is given by the
constant FUTEX_TID_MASK (0x3fffffff).
If a value outside of this range is written to threads-max an error
EINVAL occurs.

The value written is checked against the available RAM pages. If the
thread structures would occupy too much (more than 1/8th) of the
available RAM pages threads-max is reduced accordingly.

表示系统全局的总线程数限制。设置方式有:

# 方式1 运行时限制,临时生效
echo 999999 > /proc/sys/kernel/threads-max
# 方式2 修改/etc/sysctl.conf,永久生效
sys.kernel.threads-max = 999999

参数sys.kernel.pid_max限制

https://www.kernel.org/doc/Documentation/sysctl/kernel.txt

PID allocation wrap value.  When the kernel's next PID value
reaches this value, it wraps back to a minimum PID value.
PIDs of value pid_max or larger are not allocated.

表示系统全局的PID号数值的限制。设置方式有:

# 方式1 运行时限制,临时生效
echo 999999 > /proc/sys/kernel/pid_max
# 方式2 修改/etc/sysctl.conf,永久生效
sys.kernel.pid_max = 999999

参数sys.vm.max_map_count限制

https://www.kernel.org/doc/Documentation/sysctl/vm.txt

This file contains the maximum number of memory map areas a process
may have. Memory map areas are used as a side-effect of calling
malloc, directly by mmap, mprotect, and madvise, and also when loading
shared libraries.

While most applications need less than a thousand maps, certain
programs, particularly malloc debuggers, may consume lots of them,
e.g., up to one or two maps per allocation.

The default value is 65536.

表示单个程序所能使用内存映射空间的数量限制。设置方式有:

# 方式1 运行时限制,临时生效
echo 999999 > /proc/sys/vm/max_map_count
# 方式2 修改/etc/sysctl.conf,永久生效
sys.vm.max_map_count = 999999

在其他资源可用的情况下,单个vm能开启的最大线程数是这个值的一半,可以通过cat /proc/PID/maps | wc -l查看目前使用的映射数量。

至于为什么只有一半,结合一些材料和源码分析了一下:

常见的警告信息是这样的,见JavaThread::create_stack_guard_pages()

Attempt to protect stack guard pages failed.
Attempt to deallocate stack guard pages failed. 

见current_stack_region()的图示,结合一下R大的相关解释:http://hllvm.group.iteye.com/group/topic/37717

如下图所示,通常的Java线程,会包括一个glibc的guard page和HotSpot的guard pages,其中JavaThread::create_stack_guard_pages()就是创建HotSpot Guard Pages用的,这里正常应该会有2次VMA,所以最大值只能有一半,从/proc/PID/maps中也可以看到增加一个线程会增加2个地址相连的映射空间。

// Java thread:
//
//   Low memory addresses
//    +------------------------+
//    |                        |\  JavaThread created by VM does not have glibc
//    |    glibc guard page    | - guard, attached Java thread usually has
//    |                        |/  1 page glibc guard.
// P1 +------------------------+ Thread::stack_base() - Thread::stack_size()
//    |                        |\
//    |  HotSpot Guard Pages   | - red and yellow pages
//    |                        |/
//    +------------------------+ JavaThread::stack_yellow_zone_base()
//    |                        |\
//    |      Normal Stack      | -
//    |                        |/
// P2 +------------------------+ Thread::stack_base()
//
// Non-Java thread:
//
//   Low memory addresses
//    +------------------------+
//    |                        |\
//    |  glibc guard page      | - usually 1 page
//    |                        |/
// P1 +------------------------+ Thread::stack_base() - Thread::stack_size()
//    |                        |\
//    |      Normal Stack      | -
//    |                        |/
// P2 +------------------------+ Thread::stack_base()
//
// ** P1 (aka bottom) and size ( P2 = P1 - size) are the address and stack size returned from
//    pthread_attr_getstack()

cgroup限制

现在新点的操作系统采用systemd的init程序,支持cgroup控制特性。docker的资源隔离底层技术就是这个。

其中有个重要的限制就是最大任务数TasksMax,通过设置cgroup的pids.max来限制。例如suse sp2的发行说明,见https://www.suse.com/releasenotes/x86_64/SUSE-SLES/12-SP2/#fate-320358

If you notice regressions, you can change a number of TasksMax settings.

To control the default TasksMax= setting for services and scopes running on the system, use the system.conf setting DefaultTasksMax=. This setting defaults to 512, which means services that are not explicitly configured otherwise will only be able to create 512 processes or threads at maximum.

For thread- or process-heavy services, you may need to set a higher TasksMax value. In such cases, set TasksMax directly in the specific unit files. Either choose a numeric value or even infinity.

Similarly, you can limit the total number of processes or tasks each user can own concurrently. To do so, use the logind.conf setting UserTasksMax (the default is 12288).

nspawn containers now also have a TasksMax value set, with a default of 16384.

上面的描述,说明

对于登录会话,有个默认的限制UserTasksMax,配置在/etc/systemd/logind.conf,限制了某个用户的默认的总任务数,例如上面限制了最大12288,修改这个配置文件可以通过systemctl restart systemd-logind重新加载

对于服务来说,配置在/etc/systemd/system.conf的DefaultTasksMax参数,默认是512(不同的发行版很可能不一样),如果需要定制,需要根据服务独立配置  

上面提到的是cgroup的默认全局设置,也可以细化到某个进程的限制。具体功能可以参考Linux Cgroup系列(03):限制cgroup的进程数(subsystem之pids)

通过find /sys/fs/cgroup -name “pids.max” 可以看到各种细化的配置,例如./pids/user.slice/user-1000.slice/pids.max就是id为1000的用户的限制,相当于覆盖了上面logind.conf的默认设置,修改这个值会立即生效。

要查看某个进程的具体限制,可以通过/proc/PID/cgroup查看运行时状态,其中里边有pids.max就是对应的限制情况。详细点的可以看看这个案例:https://zhuanlan.zhihu.com/p/29192624