今日头条爬虫之:解析JS得到signature

  只要你开始写爬虫了,或早或晚的你都会去接触到JavaScript。然后等你爬虫做久了,你就会成为你个资深的前端开发工程师。
  在之前的文章中提过,在定向爬虫中极其不推荐使用selenium,速度太慢。那对于JavaScript总要有个解决方案,速度相对快的解决方案有两个:
将js代码翻译成python。严肃别笑,这是可行的,在js混淆不盛行的时候我真的这么干过。
第一你要非常有时间,毕竟你可能对js不熟。但JavaScript是每个前端工程,啊呸,爬虫工程师绕不过的南墙。
  在js混淆盛行的现在,反正我是不会选这个方法,你选你大佬,你可以站在爬虫鄙视链的顶端。
  略微分析,直接去执行有效的js代码,取得你想要的结果。
为什么说有效,因为现在的js里会混淆大量无效干扰你的js,比如极验。
JavaScript的执行需要js引擎,于是引入今天的主角PyV8。

Google V8 is Google’s open source JavaScript engine.
V8 is written in C++ and is used in Google Chrome, the open source browser from Google.
V8 implements ECMAScript as specified in ECMA-262, 3rd edition, and runs on Windows XP and Vista, Mac OS X 10.5 (Leopard), and Linux systems that use IA-32 or ARM processors.
V8 can run standalone, or can be embedded into any C++ application.

PyV8的安装:
pip install pyv8
  如果顺利的话就可以进行下面的步骤了,如果报错就需要根据你们自身的系统去谷歌一下解决方案,windows直接有.exe安装程序。Linux与MacOS需要安装对应依赖,在这不赘述,相信大家的找资料能力,实在解决不了可以私聊我,乐意效劳。

PyV8的使用:
  最好的文档肯定是官方文档,这里仅能给出几个我常用的,以及一些我的使用心得,以防大家踩坑。
import PyV8注意大小写。

PyV8.JSContext() 创建JSContext对象,因为有enter()方法,可以这样用
with PyV8.JSContext() as ctxt:
接下来就使用ctxt来执行js脚本,其使用方法多半有两种,涉及的关键属性是locals:

locals
Local variables within context

与JavaScript中变量交互(使用最多):
获得JavaScript中变量

import PyV8
with PyV8.JSContext() as ctxt:
    ctxt.eval("""
                var_ex1 = 1;
                var_ex2 = 1.0;
                var_ex3 = "test";
                var_ex4 = true;
            """)
    vars = ctxt.locals
    var_ex1 = vars.var_ex1
    print var_ex1

传入python中变量

import PyV8
with PyV8.JSContext() as ctxt:
    ctxt.locals.test = 12
    print int(ctxt.eval("test"))

与JavaScript中函数交互:

把Enc绑定到js中的Enc方法

Enc = ctxt.locals.Enc
#执行Enc方法,传入python的参数:params,_deskey,用python接受返回值
str = Enc(params, _deskey, '', '')

  其实大家也都看出来了,差别不大,其中核心目的都是为了执行JavaScript代码,写成哪种风格就纯属个人喜好了。

PyV8.JSLocker() 值得注意的是PyV8并非是线程安全的,因此在多线程环境下要加入全局锁。
  下面的代码也是第一点的另一种写法,显式的enter与退出,想必一看就懂。

ctxt = PyV8.JSContext()
with PyV8.JSLocker():
    self.ctxt.enter()
    vl5x = self.ctxt.eval(js) 
    self.ctxt.leave()

PyV8的实战:
  那说了不少,真正在爬虫中应该怎么用?下面给出本文福利,实战今日头条(破解反爬关键参数)。
  今日头条在一两个月前的更新中,在url中加入一个参数_signature,该参数是将参数user_id传入js后执行回传的。
  经过你的一番令人折服的操作(抓包、断点调试js),这是爬虫基本功,就不一个步骤一个步骤贴详细过程了。
  你找到目标js的地址:https://s3.pstatp.com/toutiao/resource/ntoutiao_web/page/profile/index_8f8a2fb.js(抓包)
  并分析出里面的的有效函数(断点调试js)
  user_id对你又是可见的。于是皆大欢喜,下面就可以实现计算_signature的代码了。

def get_signature(self,user_id):
   """
   计算_signature    
   :param user_id: user_id不需要计算,对用户可见
   :return: _signature
   """
   req = requests.Session()
   # js获取目的
   jsurl = 'https://s3.pstatp.com/toutiao/resource/ntoutiao_web/page/profile/index_8f8a2fb.js'
   resp = req.get(jsurl,headers = self.headers)
   js =  resp.content
   effect_js = js.split("Function")
   js = 'var navigator = {};\
           navigator["userAgent"] = "Mozilla/5.0 (Windows NT 6.1; WOW64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/49.0.2623.87 Safari/537.36";\
        ' +  "Function" + effect_js[3] + 
             "Function" + effect_js[4] + 
        ";function result(){ return TAC.sign(" + user_id + ");} result();"
   # PyV8执行步骤
   with PyV8.JSLocker():
      self.ctxt.enter()  #已在上面初始化过
      vl5x = self.ctxt.eval(js) 
      self.ctxt.leave()
   self.LOG.info("圣诞快乐")

   return vl5x

  至此完成。将参数加上,就可以按照正常逻辑爬取今日头条了。
祝你早日成长为一个优秀的前端工程师,最后周末愉快~

排行榜的的数据库设计

排行榜在游戏中非常常见的功能之一,在游戏中有各种排行榜,如工会活跃度,玩家的英雄战斗力排行等。当数据上亿时,如果使用数据库直排是致命的慢,远远超出用户接受的响应时间。也对数据库造成非常大的压力。本文将会讲述千万用户级别的用户排行系统的一些设计理念并讲述数据库直排以及使用桶排和内存数据优化排行榜。

在讲述设计前,有必要先了解一些基础理论,文章将会先讲述什么排行榜的类别,排行规则和排名分布,然后进一步结合以往写的一个简单的排行系统Nagi,讲述数据库直排和使用桶排技术,以及内存缓存技术等。

排行榜的类别

刷新频率

如果以排行榜的刷新频率来分类可分为及时排行榜,和周期排行榜。

及时排行榜
~~~~~~~~~~~

排行榜的排名能及时反映用户的排变名化,但可能是近似的排名。

周期性排行榜
~~~~~~~~~~~~~

排行榜将会在一定周期内刷新排名,如日排行,周排行,月排行等

准确性分类

精准排名
~~~~~~~~~~

能够准确的反应当前玩家的某段时间,或者当前的排名。

近似排名
~~~~~~~~

近似排名能够反映用户的排名变化和接近真实排名也许会稍稍低于真实排名,或者高于真实排名。总之可能与真实的排名有一定差别。

排行规则

排名规则,这里并不是如竞技场,使用交换排名的方式,一个新用户进入竞技场时只要简单的统计下当前竞技场用户数量就可以初始化其排名,随着玩家挑战高名次的玩家,如果胜利就交换名次这类规则。而是诸如工会活跃度可能是当前工会所有工会成员的活跃度总和作为工会活跃度、或工会所有玩家战斗力总和作为工会战斗力。这类因为最后由唯一属性(如工会活跃度,工会战斗力)决定排名的归为简单排名(唯一属性排名)。

你可能会为担忧如何计算工会的战斗力。那么考虑一个简单的游戏功能如签到排名,规则是用户每天签到将会记录用户最近连续签到的天数,如果某天用户忘记签到,那么用户签到天数将会从零开始重新计算,除非用户补签。如果用户签到天数越多,那么用户排名越高这类就是简单的排名,仅有单一属性决定玩家的排名。但是由于这个排名可能因为大多数用户都在游戏开始就持续的签名,这样就会有很多玩家排名一致,但为了保证每个用户都有不同的排名,于是将由用户id来区分排名,id越小排名越靠前,这类排名签到天数结合用户id就有多个属性决定排名就是复合属性排名。

用户排名的分布

在设计排名系统时一定要注意到用户排名的分布,正如上面讲到签到系统,是非常符合‘二八法则’的,大多数用户的排名将会非常接近或者相同。这类分布也可能会相近于正太分布。两端的用户越来越少,中间用户越来多。这样造成大量用户的排名相同。所以如果有可能应该制定比较好的游戏规则,使用户的排行分散均匀。

- 阅读剩余部分 -

在RedHat/CentOS下安装Docker(不升级内核)

由于内核版本问题,最初仅Ubuntu可以较好的支持Docker。不过,由于RedHat系列OS(REHL、CentOS)是目前主流的Linux服务器操作系统,所以令RedHat系列OS支持Docker很有必要。目前Docker和RedHat已经展开深入合作,并在2013年年底推出了可以在RedHat系列OS上运行的Docker0.7。

目前有一些博客介绍了如何在CentOS上安装Docker。但是这些博客都是针对老版本的Docker,安装方法是在升级操作系统内核版本的基础上完成。问题是,我们不可以随意升级生产环境的操作系统内核版本,而且Docker0.7的主旨就是:Docker使用者可以在不升级内核的前提下,在RedHat环境这使用Docker。因此,这里撰写一篇博客,介绍如何在RedHat/CentOS环境下,安装新版本的Docker。

一、禁用selinux
由于Selinux和LXC有冲突,所以需要禁用selinux。编辑/etc/selinux/config,设置两个关键变量。
SELINUX=disabled
SELINUXTYPE=targeted

二、配置Fedora EPEL源
1 sudo yum install http://ftp.riken.jp/Linux/fedora ... ease-6-8.noarch.rpm

三、添加hop5.repo源

cd /etc/yum.repos.d
sudo wget http://www.hop5.in/yum/el6/hop5.repo

四、安装Docker
sudo yum install docker-io

yum安装过程中,可以发现安装的软件只有docker和lxc相关包,没有内核包,例如kernel-ml-aufs。

五、初步验证docker
输入docker -h,如果有如下输出,就证明docker在形式上已经安装成功。

docker -h

Usage of docker:
-D=false: Enable debug mode
-H=[]: Multiple tcp://host:port or unix://path/to/socket to bind in daemon mode, single connection otherwise
-api-enable-cors=false: Enable CORS headers in the remote API
-b="": Attach containers to a pre-existing network bridge; use 'none' to disable container networking
-bip="": Use this CIDR notation address for the network bridge's IP, not compatible with -b
-d=false: Enable daemon mode
-dns=[]: Force docker to use specific DNS servers
-g="/var/lib/docker": Path to use as the root of the docker runtime
-icc=true: Enable inter-container communication
-ip="0.0.0.0": Default IP address to use when binding container ports
-iptables=true: Disable docker's addition of iptables rules
-p="/var/run/docker.pid": Path to use for daemon PID file
-r=true: Restart previously running containers
-s="": Force the docker runtime to use a specific storage driver
-v=false: Print version information and quit

六、手动挂载cgroup
在RedHat/CentOS环境中运行docker、lxc,需要手动重新挂载cgroup。
我们首选禁用cgroup对应服务cgconfig。
sudo service cgconfig stop # 关闭服务
sudo chkconfig cgconfig off # 取消开机启动

然后挂载cgroup,可以命令行挂载
mount -t cgroup none /cgroup # 仅本次有效

或者修改配置文件,编辑/etc/fstab,加入
none /cgroup cgroup defaults 0 0 # 开机后自动挂载,一直有效

七、调整lxc版本
Docker0.7默认使用的是lxc-0.9.0,该版本lxc在redhat上不能正常运行,需要调整lxc版本为lxc-0.7.5或者lxc-1.0.0Beta2。前者可以通过lxc网站(http://sourceforge.net/projects/lxc/files/lxc/)下载,后者需要在github上下载最新的lxc版本(https://github.com/lxc/lxc,目前版本是lxc-1.0.0Beta2)。
这里特别说明一点,由于Docker安装绝对路径/usr/bin/lxc-xxx调用lxc相关命令,所以需要将lxc-xxx安装到/usr/bin/目录下。

八、启动docker服务
sudo service docker start # 启动服务
sudo chkconfig docker on # 开机启动

九、试运行
sudo docker run -i -t Ubuntu /bin/echo hello world

初次执行此命令会先拉取镜像文件,耗费一定时间。最后应当输出hello world。

作者:speakingbaicai

Golang测试方法(一)

本篇文章内容来源于Golang核心开发组成员Andrew Gerrand在Google I/O 2014的一次主题分享“Testing Techniques”,即介绍使用Golang开发 时会使用到的测试技术(主要针对单元测试),包括基本技术、高级技术(并发测试、mock/fake、竞争条件测试、并发测试、内/外部测 试、vet工具等)等,感觉总结的很全面,这里整理记录下来,希望能给大家带来帮助。原Slide访问需要自己搭梯子。另外这里也要吐槽一 下:Golang官方站的slide都是以一种特有的golang artical的格式放出的(用这个工具http://go-talks.appspot.com/可以在线观看),没法像pdf那样下载,在国内使用和传播极其不便。

一、基础测试技术

  • 1、测试Go代码

Go语言内置测试框架。

内置的测试框架通过testing包以及go test命令来提供测试功能。

下面是一个完整的测试strings.Index函数的完整测试文件:

//strings_test.go (这里样例代码放入strings_test.go文件中)
package strings_test

import (
    "strings"
    "testing"
)

func TestIndex(t *testing.T) {
    const s, sep, want = "chicken", "ken", 4
    got := strings.Index(s, sep)
    if got != want {
        t.Errorf("Index(%q,%q) = %v; want %v", s, sep, got, want)//注意原slide中的got和want写反了
    }
}

如下:

$go test -v strings_test.go
=== RUN TestIndex
— PASS: TestIndex (0.00 seconds)
PASS
ok      command-line-arguments    0.007s

go test的-v选项是表示输出详细的执行信息。

将代码中的want常量值修改为3,我们制造一个无法通过的测试:

$go test -v strings_test.go
=== RUN TestIndex
— FAIL: TestIndex (0.00 seconds)
    strings_test.go:12: Index("chicken","ken") = 4; want 3
FAIL
exit status 1
FAIL    command-line-arguments    0.008s
  • 2、表驱动测试

Golang的struct字面值(struct literals)语法让我们可以轻松写出表驱动测试。

package strings_test

import (
        "strings"
        "testing"
)

func TestIndex(t *testing.T) {
        var tests = []struct {
                s   string
                sep string
                out int
        }{
                {"", "", 0},
                {"", "a", -1},
                {"fo", "foo", -1},
                {"foo", "foo", 0},
                {"oofofoofooo", "f", 2},
                // etc
        }
        for _, test := range tests {
                actual := strings.Index(test.s, test.sep)
                if actual != test.out {
                        t.Errorf("Index(%q,%q) = %v; want %v",
                             test.s, test.sep, actual, test.out)
                }
        }
}

结果如下:

$go test -v strings_test.go
=== RUN TestIndex
— PASS: TestIndex (0.00 seconds)
PASS
ok      command-line-arguments    0.007s
  • 3、T结构

*testing.T参数用于错误报告:

t.Errorf("got bar = %v, want %v", got, want)
t.Fatalf("Frobnicate(%v) returned error: %v", arg, err)
t.Logf("iteration %v", i)

也可以用于enable并行测试(parallet test):
t.Parallel()

控制一个测试是否运行:

if runtime.GOARCH == "arm" {
    t.Skip("this doesn't work on ARM")
}
  • 4、运行测试

我们用go test命令来运行特定包的测试。

默认执行当前路径下包的测试代码。

$ go test
PASS

$ go test -v
=== RUN TestIndex
— PASS: TestIndex (0.00 seconds)
PASS

要运行工程下的所有测试,我们执行如下命令:

$ go test github.com/nf/…

标准库的测试:
$ go test std

注:假设strings_test.go的当前目录为testgo,在testgo目录下执行go test都是OK的。但如果我们切换到testgo的上一级目录执行go test,我们会得到什么结果呢?

$go test testgo
can't load package: package testgo: cannot find package "testgo" in any of:
    /usr/local/go/src/pkg/testgo (from $GOROOT)
    /Users/tony/Test/GoToolsProjects/src/testgo (from $GOPATH)

提示找不到testgo这个包,go test后面接着的应该是一个包名,go test会在GOROOT和GOPATH下查找这个包并执行包的测试。

  • 5、测试覆盖率

go tool命令可以报告测试覆盖率统计。

我们在testgo下执行go test -cover,结果如下:

go build _/Users/tony/Test/Go/testgo: no buildable Go source files in /Users/tony/Test/Go/testgo
FAIL    _/Users/tony/Test/Go/testgo [build failed]

显然通过cover参数选项计算测试覆盖率不仅需要测试代码,还要有被测对象(一般是函数)的源码文件。

我们将目录切换到$GOROOT/src/pkg/strings下,执行go test -cover:

$go test -v -cover
=== RUN TestReader
— PASS: TestReader (0.00 seconds)
… …
=== RUN: ExampleTrimPrefix
— PASS: ExampleTrimPrefix (1.75us)
PASS
coverage: 96.9% of statements
ok      strings    0.612s

go test可以生成覆盖率的profile文件,这个文件可以被go tool cover工具解析。

在$GOROOT/src/pkg/strings下面执行:

$ go test -coverprofile=cover.out

会再当前目录下生成cover.out文件。

查看cover.out文件,有两种方法:

a) cover -func=cover.out

$sudo go tool cover -func=cover.out
strings/reader.go:24:    Len                66.7%
strings/reader.go:31:    Read                100.0%
strings/reader.go:44:    ReadAt                100.0%
strings/reader.go:59:    ReadByte            100.0%
strings/reader.go:69:    UnreadByte            100.0%
… …
strings/strings.go:638:    Replace                100.0%
strings/strings.go:674:    EqualFold            100.0%
total:            (statements)            96.9%

b) 可视化查看

执行go tool cover -html=cover.out命令,会在/tmp目录下生成目录coverxxxxxxx,比如/tmp/cover404256298。目录下有一个 coverage.html文件。用浏览器打开coverage.html,即可以可视化的查看代码的测试覆盖情况。

关于go tool的cover命令,我的go version go1.3 darwin/amd64默认并不自带,需要通过go get下载。

$sudo GOPATH=/Users/tony/Test/GoToolsProjects go get code.google.com/p/go.tools/cmd/cover

下载后,cover安装在$GOROOT/pkg/tool/darwin_amd64下面。

KMP算法与朴素匹配

查找算法中朴素匹配之于KMP就类似冒泡排序之于快速排序

 function KMPMatch($src, $par) {
    $K = array(0);
    $M = 0;
    for($i=1; $i<strlen($str); $i++) {
        if ($str[$i] == $str[$M]) {
            $K[$i] = $K[$i-1] + 1;
            $M ++;
        } else {
            $M = 0;
            $K[$i] = $K[$M];
        }
    }
    for($i=0,$j=0; $i<strlen($src); ) {
        if ($j == strlen($par)) return $i-$j;

        if ($par[$j] === $src[$i]) {
            $j++;
            $i++;
        } else {
            if ($j === 0 && $par[$j] != $src[$i]) {
                $i++;
            }
            $j = $K[$j-1 >= 0 ? $j -1 : 0];
        }
     }
     return false;
 }

 function normalSearch($src, $par) {
     for($i=0; $i< strlen($src); $i++) {
         $k = $i;
         $j = 0;
         while($i<strlen($src) && $j<strlen($par) && $par[$j] == $src[$k]) {
             $k++;$j++;
         }
         if ($j == strlen($par)) return $k - $j;
     }
     return false;
 }

匹配内容包含较多重复字符时KMP算法明显比朴素匹配要快.

PHP图的邻接矩阵表示以及几种简单遍历算法

在web开发中图这种数据结构的应用比树要少很多,但在一些业务中也常有出现,下面介绍几种图的寻径算法,并用PHP加以实现.

佛洛依德算法,主要是在顶点集内,按点与点相邻边的权重做遍历,如果两点不相连则权重无穷大,这样通过多次遍历可以得到点到点的最短路径,逻辑上最好理解,实现也较为简单,时间复杂度为O(n^3);

迪杰斯特拉算法,OSPF中实现最短路由所用到的经典算法,djisktra算法的本质是贪心算法,不断的遍历扩充顶点路径集合S,一旦发现更短的点到点路径就替换S中原有的最短路径,完成所有遍历后S便是所有顶点的最短路径集合了.迪杰斯特拉算法的时间复杂度为O(n^2);

克鲁斯卡尔算法,在图内构造最小生成树,达到图中所有顶点联通.从而得到最短路径.时间复杂度为O(N*logN);

<?php  
/** 
 * PHP 实现图邻接矩阵 
 */  

class MGraph{  
        private $vexs; //顶点数组  
        private $arc; //边邻接矩阵,即二维数组         
        private $arcData; //边的数组信息  
        private $direct; //图的类型(无向或有向)  
        private $hasList; //尝试遍历时存储遍历过的结点  
        private $queue; //广度优先遍历时存储孩子结点的队列,用数组模仿  
        private $infinity = 65535;//代表无穷,即两点无连接,建带权值的图时用,本示例不带权值   
        private $primVexs; //prim算法时保存顶点  
        private $primArc; //prim算法时保存边  
        private $krus;//kruscal算法时保存边的信息   

        public function MGraph($vexs, $arc, $direct = 0){  
                $this->vexs = $vexs;  
                $this->arcData = $arc;  
                $this->direct = $direct;  
                $this->initalizeArc();  
                $this->createArc();   
        }  

        private function initalizeArc(){  
                foreach($this->vexs as $value){  
                        foreach($this->vexs as $cValue){  
                                $this->arc[$value][$cValue] = ($value == $cValue ? 0 : $this->infinity);  
                        }  
                }  
        }  

        //创建图 $direct:0表示无向图,1表示有向图  
        private function createArc(){  
                foreach($this->arcData as $key=>$value){  
                        $strArr = str_split($key);  
                        $first = $strArr[0];  
                        $last = $strArr[1];  

                        $this->arc[$first][$last] = $value;  
                        if(!$this->direct){  
                                $this->arc[$last][$first] = $value;   
                        }  
                }  
        }  

        //floyd算法  
        public function floyd(){  
                $path = array();//路径数组  
                $distance = array();//距离数组  

                foreach($this->arc as $key=>$value){  
                        foreach($value as $k=>$v){  
                                $path[$key][$k] = $k;  
                                $distance[$key][$k] = $v;  
                        }  
                }  

                for($j = 0; $j < count($this->vexs); $j ++){  
                        for($i = 0; $i < count($this->vexs); $i ++){  
                                for($k = 0; $k < count($this->vexs); $k ++){  
                                        if($distance[$this->vexs[$i]][$this->vexs[$k]] > $distance[$this->vexs[$i]][$this->vexs[$j]] + $distance[$this->vexs[$j]][$this->vexs[$k]]){  
                                                $path[$this->vexs[$i]][$this->vexs[$k]] = $path[$this->vexs[$i]][$this->vexs[$j]];  
                                                $distance[$this->vexs[$i]][$this->vexs[$k]] = $distance[$this->vexs[$i]][$this->vexs[$j]] + $distance[$this->vexs[$j]][$this->vexs[$k]];  
                                        }  
                                }  
                        }  
                }  

                return array($path, $distance);  
        }  

        //djikstra算法  
        public function dijkstra(){  
                $final = array();  
                $pre = array();//要查找的结点的前一个结点数组  
                $weight = array();//权值和数组  
                foreach($this->arc[$this->vexs[0]] as $k=>$v){  
                        $final[$k] = 0;  
                        $pre[$k] = $this->vexs[0];  
                        $weight[$k] = $v;  
                }  

                $final[$this->vexs[0]] = 1;  

                for($i = 0; $i < count($this->vexs); $i ++){  
                        $key = 0;  
                        $min = $this->infinity;  

                        for($j = 1; $j < count($this->vexs); $j ++){  
                                $temp = $this->vexs[$j];  
                                if($final[$temp] != 1 && $weight[$temp] < $min){  
                                        $key = $temp;  
                                        $min = $weight[$temp];   
                                }  
                        }  

                        $final[$key] = 1;  

                        for($j = 0; $j < count($this->vexs); $j ++){  
                                $temp = $this->vexs[$j];  
                                if($final[$temp] != 1 && ($min + $this->arc[$key][$temp]) < $weight[$temp]){  
                                        $pre[$temp] = $key;  
                                        $weight[$temp] = $min + $this->arc[$key][$temp];  
                                }  
                        }  
                }  

                return $pre;  
        }  

        //kruscal算法  
        private function kruscal(){  
                $this->krus = array();  

                foreach($this->vexs as $value){  
                        $krus[$value] = 0;     
                }  

                foreach($this->arc as $key=>$value){  
                        $begin = $this->findRoot($key);  

                        foreach($value as $k=>$v){  
                                $end = $this->findRoot($k);  
                                if($begin != $end){  
                                        $this->krus[$begin] = $end;   
                                }  
                        }  
                }   
        }  

        //查找子树的尾结点  
        private function findRoot($node){  
                while($this->krus[$node] > 0){  
                        $node = $this->krus[$node];  
                }  

                return $node;  
        }  



        //prim算法,生成最小生成树  
        public function prim(){  
                $this->primVexs = array();  
                $this->primArc = array($this->vexs[0]=>0);  

                for($i = 1; $i < count($this->vexs); $i ++){  
                        $this->primArc[$this->vexs[$i]] = $this->arc[$this->vexs[0]][$this->vexs[$i]];  
                        $this->primVexs[$this->vexs[$i]] = $this->vexs[0];  
                }  

                for($i = 0; $i < count($this->vexs); $i ++){  
                        $min = $this->infinity;  
                        $key;  

                        foreach($this->vexs as $k=>$v){  
                                if($this->primArc[$v] != 0 && $this->primArc[$v] < $min){  
                                        $key = $v;  
                                        $min = $this->primArc[$v];  
                                }  
                        }  

                        $this->primArc[$key] = 0;  

                        foreach($this->arc[$key] as $k=>$v){  
                                if($this->primArc[$k] != 0 && $v < $this->primArc[$k]){  
                                        $this->primArc[$k] = $v;    
                                        $this->primVexs[$k] = $key;   
                                }  
                        }  
                }  

                return $this->primVexs;  
        }  

        //一般算法,生成最小生成树  
        public function bst(){  
                $this->primVexs = array($this->vexs[0]);  
                $this->primArc = array();  

                next($this->arc[key($this->arc)]);   
                $key = NULL;  
                $current = NULL;  

                while(count($this->primVexs) < count($this->vexs)){  
                        foreach($this->primVexs as $value){  
                                foreach($this->arc[$value] as $k=>$v){  
                                        if(!in_array($k, $this->primVexs) && $v != 0 && $v != $this->infinity){  
                                                if($key == NULL || $v < current($current)){  
                                                        $key = $k;  
                                                        $current = array($value . $k=>$v);  
                                                }  
                                        }  

                                }  
                        }  

                        $this->primVexs[] = $key;  
                        $this->primArc[key($current)] = current($current);  
                        $key = NULL;  
                        $current = NULL;  
                }  

                return array('vexs'=>$this->primVexs, 'arc'=>$this->primArc);  
        }  

        //一般遍历  
        public function reserve(){  
                $this->hasList = array();  

                foreach($this->arc as $key=>$value){  
                        if(!in_array($key, $this->hasList)){  
                                $this->hasList[] = $key;  
                        }  

                        foreach($value as $k=>$v){  
                                if($v == 1 && !in_array($k, $this->hasList)){  
                                        $this->hasList[] = $k;     
                                }  
                        }  
                }  

                foreach($this->vexs as $v){  
                        if(!in_array($v, $this->hasList))  
                                $this->hasList[] = $v;  
                }  

                return implode($this->hasList);  
        }  

        //广度优先遍历  
        public function bfs(){  
                $this->hasList = array();  
                $this->queue = array();  

                foreach($this->arc as $key=>$value){  
                        if(!in_array($key, $this->hasList)){  
                                $this->hasList[] = $key;  
                                $this->queue[] = $value;  

                                while(!empty($this->queue)){  
                                        $child = array_shift($this->queue);  

                                        foreach($child as $k=>$v){  
                                                if($v == 1 && !in_array($k, $this->hasList)){  
                                                        $this->hasList[] = $k;  
                                                        $this->queue[] = $this->arc[$k];     
                                                }  
                                        }  
                                }  
                        }  
                }  

                return implode($this->hasList);  

        }  

        //执行深度优先遍历  
        public function excuteDfs($key){  
                $this->hasList[] = $key;    

                foreach($this->arc[$key] as $k=>$v){  
                        if($v == 1 && !in_array($k, $this->hasList))  
                                $this->excuteDfs($k);     
                }  
        }  

        //深度优先遍历  
        public function dfs(){  
                $this->hasList = array();  

                foreach($this->vexs as $key){  
                        if(!in_array($key, $this->hasList))   
                                $this->excuteDfs($key);   
                }  

                return implode($this->hasList);  
        }  

        //返回图的二维数组表示  
        public function getArc(){  
                return $this->arc;  
        }  

        //返回结点个数  
        public function getVexCount(){  
                return count($this->vexs);  
        }  
}  


$a = array('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i');  
$b = array('ab'=>'10', 'af'=>'11', 'bg'=>'16', 'fg'=>'17', 'bc'=>'18', 'bi'=>'12', 'ci'=>'8', 'cd'=>'22', 'di'=>'21', 'dg'=>'24', 'gh'=>'19', 'dh'=>'16', 'de'=>'20', 'eh'=>'7','fe'=>'26');//键为边,值权值  

$test = new MGraph($a, $b);  
print_r($test->bst());

crontab 里 % 引发的问题

最近在写一个crontab的时候发现的一个问题,这里记录一下
计划执行一个带cookie抓取页面内容的小任务,其中cookie里有一个百分号%,
然后 查看/var/log/cron 发现执行内容并不正确,翻看手册才发现在这样一句

Percent-signs (%) in the command, unless escaped with backslash (\), will be changed into newline characters, and all data after the first % will be sent to the command as standard input.

%如果没有用\转义就会被当做另外一行,不管是否有 引号 都会这样.

[翻译]在phpstorm中配置xdebug

这是一篇翻译文章,原文请见 配置Phpstorm,Xdebug

PhpStorm 和 XDebug 是非常帅气的一对搭档

大部分时候缺少一个debugger工具会导致你无法高效的编写代码,我为一个定制化的wordpress网站工作,通过debugger深度挖掘其功能是必不可少的过程.

配置xdebug与phpstorm工作是非常简单的,但是当两个人同时尝试用相同的IP在同一个远程开发环境中对同一段代码进行debug的时候,这件事情就变得非常微妙,这个时候xdebug无法分别出到底是谁在对代码进行debug.

所以你可以看一下单用户和多用户在配置xdebug时的区别.我会在下面对两者都作出介绍.

单个用户配置phpstorm xdebug 步骤

这有一张单独用户的xdebug工作图
单独用户xdebug图

  • php.ini中做如下配置:
    php.ini

  • 在phpstorm中做如下配置

single-debug-port.png

  • 确保phpstorm是在端口监听状态
    red-to-green.png
  • 下面在你的代码的某处设一个断点
  • 现在你已经可以在你的浏览器中进行debug对话了.这里设置了一个cookie所以服务端的xdebug知道如何执行你的debug需求.
    bookmarklet1.png
  • 在你的浏览器中浏览到'断点'页面(比如你的wordpress主页),如果php+xdebug发现了一个断点,它会发送debug数据到你的IDE.

恭喜你,到现在为止单用户的xdebug配置已经完成了!

未完待续...

散列函数time33学习随笔

年底项目任务中,忙里偷闲更新一篇.
众所周知,PHP拥有一个万能的数据结构--Array.这货实在是太易用太强大了,导致PHP程序员在程序员界都混不下去了.使用PHP的Array几乎可以实现在大学数据结构课本里出现的所有数据结构.
实际上在PHP内部,Array是由Zend引擎中的Zend HashTable实现的.其实不光是Array,包括各种常量,变量,函数体,class等都是用它来组织的.
在PHP的源代码里找到zend_hash.c后不难发现,zend hashtable包含两个结构体,分别是bucket

typedef struct bucket {
ulong h;       /* Used for numeric indexing */
uint nKeyLength;     /* key 长度 */
void *pData;      /* 指向Bucket中保存的数据的指针 */
void *pDataPtr;     /* 指针数据 */
struct bucket *pListNext;   /* 指向HashTable桶列中下一个元素 */
struct bucket *pListLast;    /* 指向HashTable桶列中前一个元素 */
struct bucket *pNext;    /* 指向具有同一个hash值的桶列的后一个元素 */
struct bucket *pLast;    /* 指向具有同一个hash值的桶列的前一个元素 */
char arKey[1];      /* 必须是最后一个成员,key名称*/
} Bucket;

以及_hashtable

typedef struct _hashtable {
uint nTableSize;
uint nTableMask;
uint nNumOfElements;
ulong nNextFreeElement;
Bucket *pInternalPointer;
Bucket *pListHead;
Bucket *pListTail; 
Bucket **arBuckets;
dtor_func_t pDestructor;
zend_bool persistent;
unsigned char nApplyCount;
zend_bool bApplyProtection;
#if ZEND_DEBUG
int inconsistent;
#endif
} HashTable;

这篇博文的重点并不在这里,相信每一个从事PHP行业的职业PHPer都对这些烂熟于心了.今天主要学习一下PHP使用的DJBX33A哈希算法
DJBX33A (Daniel J. Bernstein, Times 33 with Addition)普遍叫做time33算法,这个算法被广泛运用与多个软件项目,它是已知的最好的哈希算法之一,在处理以字符串为键值的哈希时,有着极快的计算效率和很好哈希分布.
如果用映射关系来表达的话就是如下形式,很简单:

hash(i) = hash(i-1) * 33 + str[i]

以下是PHP内部使用的time33版本:

inline unsigned time33(char const*str, int len) 
{ 
     unsigned long hash = 5381; 
     /* variant with the hash unrolled eight times */ 
     for (; len >= 8; len -= 8) { 
         hash = ((hash << 5) + hash) + *str++; 
         hash = ((hash << 5) + hash) + *str++; 
         hash = ((hash << 5) + hash) + *str++; 
         hash = ((hash << 5) + hash) + *str++; 
        hash = ((hash << 5) + hash) + *str++; 
        hash = ((hash << 5) + hash) + *str++; 
        hash = ((hash << 5) + hash) + *str++; 
        hash = ((hash << 5) + hash) + *str++; 
    } 
    switch (len) { 
        case 7: hash = ((hash << 5) + hash) + *str++; /* fallthrough... */ 
        case 6: hash = ((hash << 5) + hash) + *str++; /* fallthrough... */ 
        case 5: hash = ((hash << 5) + hash) + *str++; /* fallthrough... */ 
        case 4: hash = ((hash << 5) + hash) + *str++; /* fallthrough... */ 
        case 3: hash = ((hash << 5) + hash) + *str++; /* fallthrough... */ 
        case 2: hash = ((hash << 5) + hash) + *str++; /* fallthrough... */ 
        case 1: hash = ((hash << 5) + hash) + *str++; break; 
        case 0: break; 
    } 
    return hash; 
} 

用位运算代替乘法,效率更高.待续..

抽奖程序中随机概率的测试

最近一个项目里关于抽奖活动的概率引发了一些争执,
讲一下整个抽奖流程:
一共有M种元素,用户集齐其中的N种即算中奖,M种元素获得的概率都不相同.然后用户每天有T次机会可以抽奖,其中满足条件T>M;另说明我不是做游戏的,对于这方面来说有些欠缺,只能摸着石头过河,一段代码来验证概率是否合理.

$arr = array(
    'h1' => 30,
    'h2' => 30,
    'h3' => 8,
    'h4' => 8,
    'h5' => 8,
    'h6' => 8,
    'h7' => 8,
    'h8' => 5,
    ...
);

$lucky = array();
foreach( $arr as $k=>$v )
{
    $lucky += array_fill( count($lucky),$v,$k );
}

$user = array();
$limit = array();
$j = 0;
//采样数量$k
for( $k =0; $k < 1000;$k++ )
{
    $i = 1;
    while(true)
    {
        $a = $lucky[mt_rand(0,99)];
        if( !in_array( $a, $user ) )
        {
            $user[] = $a;
        }
            //达到获奖条件N
        if( count($user) >N )
        {
            $user = array();
            break;
        }
        $i++;
    }

    //用户每天有T次机会
    if( $i <= T )
    {
        $j++;
    }

    $limit[] = $i;

}

//这里得到采样中达到获奖资格平均需要多少次抽奖
var_dump(array_sum( $limit )/1000);

//得到在$k中有多少人可以在抽奖资格内的中奖
echo $k.'人中有多少人第一天能中奖'.($j);

Git Client 保存密码

GIT的客户端越来越强大了.这是一个好事情.

可是对于我这种懒人来说,每次pull或者push都要输入账号密码,这个实在是太不能接受了.

好在有办法可以保存账号密码.这里做一个备忘.

windows下找到用户目录,新建 _netrc 文件

machine git.notech.cc
login user
password xxxxxx

Linux下同样可行,需要在~目录下新建 .netrc 文件,文件内容同上

GitLab5.0安装全过程(转)

GitLab5发布快一个月了,决定试用下,5.0最大的特性就是用GitLab-Shell取代了Gitolite,这大大降低了安装难度,不多本人在安装过程中还是越到了一些问题,所以记录下来供要安装GitLab5的朋友参考!

- 阅读剩余部分 -

官方wiki:Configuring PhpStorm IDE for Yii

Code completion

  1. Exclude yiilite.php from index:
    • File → Settings → IDE Settings → File Types.
    • yiilite.php to Ignore files and folders.
  2. Exclude not used directories, specify resources.
    • File → Settings → Project settings → Directories.
    • Mark framework/cli/viewsprotected/runtime and assets as excluded.
    • Mark website root as resource root.
  3. Specify path to your PHP.
    • File → Settings → Project settings → PHP → PHP Home.
  4. If your project uses common Yii framework folder you need to include it.
    • File → Settings → Project settings → PHP → PHP Home → Add.
    • Specify a path to framework directory.
  5. If you are writing unit tests you can include PHPUnit to get code completion:
    • File → Settings → Project settings → PHP → PHP Home → Add.
    • Specify a path to PHPUnit.
  • Complete code: Ctrl+Space.
  • Show method arguments: Ctrl+Q.

Yummy\'s time has gone

大概在现在这样的季节不应该写一些伤春悲秋的玩意,可是既然开了头,那就多啰嗦两句好了.

最近在下班的公交车上经常能看到一些身着校服的孩子,很明显是去参加了某某补习班后拖着疲惫身子赶回家时的样子,这让我不由多了一些感慨,明天是高考的日子,我在若干年前也曾经经历过这样一段紧张又令人难忘的时期,现在想来那段时光真的是美好且愉悦的,如果只需要踌躇于函数式的求导`细胞的有丝分裂过程等诸如此类问题的话...

说到这里,突然发现我离开学校到步入社会也有一年的时间了,这一年里得到了一些,但是好像失去了更多,我没有时间去回忆匆匆而过的美好时光,当我投身进这个大熔炉时我首先想到的是如何不被淘汰掉,于是疯狂地做无关兴趣只关乎生存的事情,曾几何时我也有些自命不凡的抱负和希冀,现在看来不得不接受现实的残酷,本来就是个俗人,做些俗的事情无可厚非,况且值得让我庆幸的是我现在养活自己的手段也是我自愿并且喜欢做的事. 然后美好的时光就这样匆匆流过。每当想起这些,我就觉得沮丧。但有很多事,真的不是我能改变的。也许这一年有过太多抱怨,太多摇摆,为了获得,不断地放弃。有时候早上醒来,已经不知道自己有什么目标,是什么,让自己活下去。 大家都认为一个码代码的应该拥有纯理性的思维,这样才能保证写出优质的代码的同时尽量少地为自己或者后来维护的人挖坑.但往往事情却无这样的绝对.

从来英雄如美人,不许人间见白头.

在这条路上还能走多久,我不知道.我甚至不敢想,连触及一下的念头都没有,何时已经如此怯懦,我也不知道... 幼稚往往是一个人的常态,我也只能这样的安慰我自己,从这个角度来看,我也算是一个复杂的动物,嘴上一句带过心里却一直重复.

清末河北人郭云深曾因犯下命案入狱二十多年.郭老在牢里被戴上脚铐,行走不便,并且每次只能迈开半步,因此常人练崩拳需要前跨一步,而郭老只能跨半步.后来郭老名扬四海,以“半步崩拳打天下”著称. 我从这个故事得到的启发是环境不是限制人的先决条件,比如黑煤窑里的挖煤工,他们人人都有一副壮硕的身体. 这个圈子也一样,你进来时稚气未脱,现如今已初尝人世百态,你会看到以前落榜的同学已经走入社会,你参加同学会时会发现曾经交集颇深的人们已经分别走上了不同的生活轨迹,有些混迹官场,有些浪荡江湖,有些新婚燕尔,有些已经为人父母.

放眼全是熟悉人,开口却皆是新鲜事...

这个世界上还存在没有故事的人么? Yummy原是我为我妈妈的西点屋起的名字,我甚至为它做了一些VI设计,但是最后的结果是我的妈妈并没有用它,这让我有一些失落. so, Yummy's time has gone~

一个php进程可以处理包含亿级数量的数组么?答案Yes

在之前很多人的认知中,php的原则是quick and dirty,我认为这有一定道理.无论从编码的设计思路还是其特殊的垃圾回收机制都证明着这个观点.

随着时间的推移,PHP的年纪越来越大,喷的人越来越多,但是丝毫没有影响PHP在web世界的霸主地位. 原因是多种多样的. 我认为无论何种编程语言都是为产品服务的,那么只要能稳定,合格的实现产品功能,就可以说这门语言是成功的.

在这个基础上PHP还拥有开发速度快,入门成本低等先天优势,那么风靡世界就是自然而然的事情了. 我很不理解某些自命不凡或者自命清高的程序员,任何职业都是要接地气的,尤其是在中国.实现产品功能是硬性条件,在这个基础上尽量控制开发成本已经开发时间,这是很浅显的道理.不需要多么优雅,我们伟大的party也是农民阶级建立并解放新中国的.简单直接才是硬道理.

好了,不扯一些别的东西了. 最近PHP的大事是5.5 release了,里面有一些有趣的东西. 今天介绍一下Generators这个东东,有一些技术博客将它翻译成生成器, 官方给出的介绍是这样的:Generators provide an easy way to implement simple iterators without the overhead or complexity of implementing a class that implements the Iterator interface.
我理解的意思就是一个简单实现的迭代器. 有了它,php能做的事情更多了.比如说:

function xrange($start, $end, $step = 1) {
    for ($i = $start; $i <= $end; $i += $step) {
        yield $i;
    }
}
foreach (xrange(1, 1000000) as $num) {
    echo $num, "\n";
}

 
上面这个xrange函数提供了和PHP的内建函数range一样的功能。但是不同的是range()函数返回的是一个包含属组值从1到100万的数组(注:请查看手册)。
而xrange函数返回的是依次输出这些值的一个迭代器,而且并不会真正以数组形式计算。 这种方法的优点是显而易见的。它可以让你在处理大数据集合的时候不用一次性的加载到内存中。甚至你可以处理无限大的数据流。 当然,也可以不同通过生成器来实现这个功能,而是可以通过继承Iterator接口实现。通过使用生成器实现起来会更方便,而不用再去实现iterator接口中的5个方法了。 要从生成器认识协同程序,理解它们内部是如何工作的非常重要:生成器是可中断的函数,在它里面,yield构成了中断点。

紧接着上面的例子,如果你调用xrange(1,1000000)的话,xrange()函数里代码没有真正地运行。相反,PHP只是返回了一个实现了迭代器接口的生成器类实例
你对某个对象调用迭代器方法一次,其中的代码运行一次。例如,如果你调用$range->rewind(),那么xrange()里的代码运行到控制流 第一次出现yield的地方。在这种情况下,这就意味着当$i=$start时yield $i才运行。传递给yield语句的值是使用$range->current()获取的。
为了继续执行生成器中的代码,你必须调用$range->next()方法。这将再次启动生成器,直到yield语句出现。因此,连续调用next()和current()方法 你将能从生成器里获得所有的值,直到某个点没有再出现yield语句。对xrange()来说,这种情形出现在$i超过$end时。在这中情况下, 控制流将到达函数的终点,因此将不执行任何代码。一旦这种情况发生,vaild()方法将返回假,这时迭代结束。 再举一个例子: 假如有一个巨大的文件,  

function getLinesFromFile($fileName) {
  if (!$fileHandle = fopen($fileName, 'r')) {
    return;
  }

  while (false !== $line = fgets($fileHandle)) {
    yield $line;
  }

  fclose($fileHandle);
}

我们通过简单的 生成器就可以用一个php进程处理整个文件,只是时间问题而已.

$filename = 'somefile.txt';
$gen = getLinesFromFile($filename);

foreach ($gen as $line) {
  echo $line;
}

引自一个老外的测试结果,还是很惊喜的.

0E4E064A-D25E-4A16-8332-6A5FF080D54D
PHP 5.5给我们的惊喜还不止于此.而且作为一门有一些历史的语言(想比较node,go等)保持高速的进步实属不易,现在官方需要做的是如何加速php世界的版本更新,这个尤为重要. 其实我更想看到的是php能够更加实用和具体的功能,比如: 函数重载. 错误异常中继而不是简单的输出.