Page 8 of 12 for 派猴子来的救兵

6 Mar, 2017
斗地主
前两天看到一个斗地主残局(斗地主都有残局了..), 如下图. 我便想写个程序算一下结果如何. 记录一下, 锻练一下自己说清楚事情的能力.

想法是用程序模拟两个人对局. 就每人依次出牌. 如果一个人牌打完了, 对手就会要求悔棋. 一直到悔到最后没办法悔了就输了.

每个人都先从最简单的牌开始出,最开始出单张,打到最后发现单张不行,就出对子.
比如说, 农民先出一张3, 打到最后发现没办法赢, 再尝试先出一张4. 打到最后发现单张没办法赢, 就出2张3. 依次继续.
大小顺序我们可以随便定, 我是按这样来的: 单张,一对,三张,三带一,顺子,四带2,普通炸,王炸,Pass
解释一下最后的Pass是什么意思: 竟然想不到简单的例子, 就直接拿上图举例. 农民先出A, 地主小怪. 按顺序的话, 应该是出炸,但最后会发现炸会输,按我们定义好的顺序,接下来就是Pass,也就是说,地主出小怪, 我选择不出牌.

其中几个需要仔细斟酌一下的细节:
1. 什么时候需要悔牌?
  - 一个人的牌出完了, 对手要求悔牌
  - A悔牌之后, 发现自己上一轮是Pass, 那只能继续往前悔牌
2. 什么时候算赢?
  - 农民第一次出牌已经需要Pass了, 说明他输了
  - 地主要求农民悔牌的时候, 农民已经是第一张牌, 说明地主输了
3. 需要保存/传递哪些信息
  1. 按顺序记录当前出过的所有牌
  2. 当前出牌的人
  3. 当前桌面上的牌是什么 (可以放第1项里面)
  4. 如果是刚刚悔牌, 需要保存/传递刚悔的是什么牌
  5. 是不是处于悔牌状态(具体到我的代码实现中, 这个值是需要传递的. 在你的实现中,可以通过第4项直接得到). 这个关系到下一次可以出什么牌. 比如说桌面是444带J, 如果我不是悔牌, 那我的3张必须比4大,单张随意. 如果我是悔牌, 那么三张可以一样, 但单张必须比之前的大.
简单的伪代码:
```
while True:
    cureent_player.next
    if len(paths) == 1 and desktop is Pass:
        第一牌就只能Pass,没得打了,判cureent_player输

    if destop is Pass and previous_desktop is Pass:
        //注意这里是需要从Pass往前悔三次牌, 这种回退是一定可以的
        rollback(cureent_player,previous_player, cureent_player)
    if cureent_player.win:
        if rollback(cureent_player,previous_player) is False:
            无牌可悔,cureent_player赢
```
具体代码见https://github.com/childe/doudizhu

英语太差, 有几个变量名字解释一下:
- Round 是指选手出的一次牌. 比如444带J是一个Round对象. Pass也是一个Round对象
- minimal Two.minimal(cards)本意是指在所有cards里面, 选出最小的对子牌. 这个方法用在对手刚Pass, 而自己悔牌,需要从单张升级到对子的时候. 但可能没有对子,需要继续寻找有没有3张,3带1,顺子等.
就这么多了, 我代码水平太次, 真正实现起来,还是Debug了好久,代码可读性也不是很理想. 另外希望没有打扰到你的思路, 对程序员来说, 递归可能是一种更加自然的思路. 但用Python实现的话,有可能会抛递归层次太深的异常. 毕竟我在i5上面跑了整5分钟, 日志打印了300MB…
18 Jan, 2017
DNS隧道
前一段时间, 回到家发现电信欠费不能上网了, 赶紧充值的同时, 想到DNS隧道.

host www.baidu.com 发现是可以正常返回的. 但当时手头没有现成的DNS隧道工具, 萌发了自己写一个的想法.

原理应该算是比较简单的, 但是在实现的过程中遇到了一些麻烦, 现在还未完成…

先把这些困难记录一下, 也练练把事情说清楚的能力.
1 Jan, 2017
dns发送消息过长
1. 你可能也听过这句话, UDP是基于帧的, TCP是基于流的.
2. IP包是有长度限制的. 超过一定长度, TCP的话, 内核会帮你分成多个包发出去. UDP呢?
我之前只有印象, IPTCP协议详解中, 不记得哪一章了, 有提到, UDP的长度是有最大限制的, 各系统不同, 可能达到不了理论上的IP包最大值. 但我却从没有想到, 如果超过了会怎么样.

因为在尝试实现DNS隧道, 需要确认一下这个问题. 刚才用GO语言试了一下, 如果消息过长, 是会报错的: write udp 127.0.0.1:59933->127.0.0.1:10000: write: message too long
8 Dec, 2016
nginx 500 错误: client_body_temp Permission denied
nginx做代理, proxy_pass代理后面的应用. 用户反应大量请求的时候, 会得到500错误.

我看了是access日志之后, 发现request body为空. 以为是用户调用出错.

后来配合用户做tcpdump, 发现client还在发送request body, 没发完呢, nginx就直接返回500, 然后close connection了. client还在坚持继续发完了request body, 然后close.

然后上网搜索, 我盲目的关键词居然很快就找到了答案. https://wincent.com/wiki/Fixing_nginx_client_body_temp_permission_denied_errors google 真好.

报错是因为request body比较大的时候, nginx会先把一部分数据缓存到磁盘, 但写磁盘的目录又没有权限, 所以直接抛出了500报错.

解决方案也简单, 就是给权限, 或者重新配置一下 client_body_temp_path

多看一眼error.log就能直接找到解决方案的. 不过在tcpdump的过程中学到了sack的的用法, 也挺好的.
23 Nov, 2016
vim和python中正则匹配的lookahead模式
lookahead

之前只知道python中的lookahead模式(?=…)怎么写, 今天看到vim的help文档, 看了好一会没看明白. google了一下才清楚了,记录一下.

举例说明一下, 我想匹配这条”狗”是谁的, 只把主人匹配出来, 但猫我不管.
```
In [136]: re.match(r'^my(?= dog)','my dog').group()
Out[136]: 'my'

In [139]: re.match(r'^my(?= dog)','my cat') is None
Out[139]: True
```
也就是说, 我只取了my这个词, 后面的dog没有消费, 但是一定要保证my后面跟的是dog

positive lookahead

与之对应的还有 positive lookbehind assertion, 也举例说明一下.

我想匹配”我的”狗, 而不是别人的, 如下.
```
In [154]: re.search(r'(?<=my )dog','my dog').group()
Out[154]: 'dog'

In [156]: re.search(r'(?<=my )dog','her dog') is None
Out[156]: True
```
注意这里没有用match, 而是用的search. 因为这两种模式只是”确保”前后有东西, 而不消费任何内容. python里面的match其实是要从头匹配的, dog并非顶头的内容, 所以用match匹配不到.

VIM

在vim里面也有相应的功能, 但语法有些不一样, 不多说了, 直接举例.
1. 匹配dog, 但必须是我的.
```
/\(my \)\@<=dog
```
1. 匹配主人, 但必须是狗的主人
```
/\w\+\( dog\)\@=
```

27 Oct, 2016

一行python代码求素数

看了如何读懂并写出装逼的函数式代码就想实验一下, 然后看到朋友圈有人转, «一行python代码», 求拿求素数爽了一把, 写完之后再也不想多看一眼了

先来个只是不用for循环的:

print filter(lambda n:'' if any(filter(lambda i:n%i==0,range(2,1+int(n**.5)))) else n, range(2,100)) 

然后增加一点细节把filter去掉

print (lambda f:f(f))(lambda f:lambda n: [] if n==1 else f(f)(n-1) + (lambda n:[n] if ((lambda f:f(f))(lambda f: lambda n, i: n if i**2 > n else '' if n % i == 0 else f(f)(n, i+1)))(n,2) else [])(n))(100)

12 Oct, 2016
hangout中GeoIP2的性能统计
在hangout里面, 有个GeoIP2插件, 可以根据IP添加地理信息. 我们在使用这个插件之后, 发现处理速度有些下降, 于是通过日志统计了一下这个插件的性能.

我们是跑在marathon + docker平台上的, 可能统计会有所偏差.

每批60000条数据, 处理好之后, bulk到ES. 日志会记录bulk的时间, 和bulk结束拿到response的时间, 根据这两个时间统计.
```
使用GeoIP2之前的
filter:  234055次 平均8.51832039051秒 (不包括GeoIP2, 但有其他的Filter)
bulk:  234048次 平均 5.99807413009秒

之后的
filter: 9145次 平均 13.0438958994秒 (在之前Filter的基础上, 添加了GeoIP2)
bulk:  9146次 平均 3.70712070851秒
```
后面bulk快可能是因为ES做过扩容.
但是filter时间多了4.5秒, 每批6W条数据, 平均一条数据0.000075秒.
11 Oct, 2016
elasticsearch中rebalance策略分析及参数调整
在做一些维护的时候, 比如删除/关闭索引, ES会触发rabalance, 但有时候觉得它过于敏感了.

分析一些ES的rebalance策略是怎么样的, 有些不确定, 属于猜测.

举例现在web-2016.10.03正在weak节点上做rebalance:
```
web-2016.10.03 4 p RELOCATING 450308191 757.5gb 10.0.0.1 10.0.0.1-> 10.0.0.2 0zDpSrgmT1mSrtEywH86zg 10.0.0.2
```
源10.0.0.1上面有52个shard, 目的10.0.0.2有48个shard. 总的shard 是33400, web-2016.10.03一共10shards, 无复制片, 共129个Node.

先按公式计算每个Node的weight (这个公式我不是很确定, 之前见到过, 但找不到了, 一部分凭印象, 部分参考代码https://github.com/elastic/elasticsearch/blob/2.4/core/src/main/java/org/elasticsearch/cluster/routing/allocation/allocator/BalancedShardsAllocator.java, 还有一部分算是蒙的吧)

计算中需要三个参数, 见https://www.elastic.co/guide/en/elasticsearch/reference/current/shards-allocation.html#_shard_balancing_heuristics

1的权重是 0.45(52-33400/129)+0.55(1-10/129)
2的权重是 0.45(48-33400/129)+0.55(0-10/129)

两个权重的差值是 0.45(52-48) - 0.55(1-0) = 2.34, 大于1.

第二个部分先认为是固定不变的(源不大可能大于1,毕竟总shard是10个, 加上复制片才20, 总节点远超过这个. 目标也一般是0) 所以主要影响因素就是0.45*(52-48), 如果想控制, 相差<=3的时候不做迁移, 阈值设置成2就可以.
20 Sep, 2016
elasticsearch中的common terms query
翻译自https://www.elastic.co/guide/en/elasticsearch/reference/2.3/query-dsl-common-terms-query.html

common terms query 是stopword一个替代方案(但我感觉比单纯的stopword好多了). 它可以提升精确度, 还不会牺牲性能.

The Problem

在Query中, 每个Term都消耗一定的资源. 搜索”The brown fox”需要三次term query, 这三个term都会在索引中的所有文档中执行,但是 “The” 这个term对相关性的影响比其他两个term要小.

之前的解决方法是把”the”这种高频词当成stopword, 可以减少索引大小, 在搜索的时候也会减少query次数.

但是, 虽然高频词对相关性的影响小, 但是他们依然很重要. 如果把stopword去掉, 会丧失精确性, 比如说”happy”, “not happy”就区分不了了. 而且, “The The” , “To be or not to be” 这种文本就丢失了.

解决方案

common terms query把query temrs分成2组, 一组是更重要的(低频词), 一组是不太重要的(高频词,之前被当成stopword).

第一步, 先搜索更重要的term, 它们是低频词, 对相关性的影响更大.

第二步, 再对高频词执行第二次搜索. 但是它不对所有匹配的文档打分, 只对第一步中匹配的文档打分. 这样的话, 高频词也可以提升结果的相关性, 同时还不会增加很多负载.

上面这个第二步没有很理解, 为什么不会增加很多负载. 因为对query的执行原理不清楚 :(

如果query里面的term全是高频词,那么query会按照 AND queyr来执行(默认是or). 这样的话, 虽然每个term都匹配好多文档, 但AND之后,结果集就会小很多.
也可以用 minimum_should_match 这个参数控制用 OR query, 最好使用一个大点的值~
11 Sep, 2016
TCP连接中的状态变迁
关于TCP的状态变迁, 这张截自TCP/IP协议详解一书的这张图,简单明了.

这篇文章总结一下各状态变迁对应的编程语言中对应哪一个方法调用.

lookahead

positive lookahead

VIM

The Problem

解决方案