近期打算去把搁置一年多的驾照去考了,听说最近北京驾照改革,拿本难度升级了不少,希望好运!
东方时尚的科目三考试路线总共分为A,B,C三段,A+B+C就是绕东方时尚校区的一个闭环路线。但是由于平时考试路线都不允许训练车辆驶入,因此科目三考前,每个学员顶多跑1-2圈,而我认为科三的考试最重要的就是熟悉线路,明白在哪儿需要变道,在哪儿是公交车站、学校需要减速,其余就是仔细听语音播报,不要慌乱即可。
既然我们在实际考试路线上的训练时间非常少,因此我们需要多去看看东方时尚APP提供的三段路线的考试视频,达到熟记路线的目的。然而东方时尚APP内嵌的考试视频我们无法直接下载,每次打开都需要耗费流量下载(每段视频都在100M以上,很费流量)因此我们需要特殊的技巧将视频下载下来,这样可以在去驾校的班车上复习路线,具体操作如下:

1. 我们需要使用手机端抓包软件获取视频的真实地址,我们使用
packet capture 这款抓包软件,

packet_capture
首先下载安装packet capture。
2. 首先关闭所有应用,然后打开packet capture

再打开东方时尚APP,点击视频tab,就会出现我们需要的视频展示页面,点击“科目三考试路线A”,直到开始播放视频。

3. 切回packet capture,它已经捕获这段时间内我们手机应用的所有网络请求。点进去,会出现具体的每个请求的信息。如下图所示:

我们逐个点击带东方时尚APP logo的包,直到看到有个类似视频地址的链接。如下图圈出部分:

至此,我们已经拿到了视频的真实地址,并且可以看出视频是托管在nuetv上,该视频肯定是私有视频,因此视频链接中带有apikey以及deviceId等参数。
我们在浏览器中打开这个链接,会下载下来一个.m3u8的文件,关于m3u8文件格式,可自行google,总之这个文件就是我们真正想要的视频的描述信息,我们可以用常用的视频播放器打开此文件,将会正常播放视频,只不过数据都需要在线加载。
接下来我们的任务变成通过这个m3u8文件下载到真实视频。通过google我找到一个视频播放器VLC,首先下载安装VLC。

用VLC打开我们下载的m3u8文件,VLC也会自动播放视频,我们需要点击视频左下角的方块按钮(图中已圈出),

之后我们在播放列表中能看到该文件,我们右键保存到想要的位置就可以了。

为了方便,我已经视频上传至了百度云,有需要的同学可以自行下载。
链接: https://pan.baidu.com/s/1ggFUGuf 密码: mazw

协程,又称微线程,纤程。英文名Coroutine

我们可以将协程理解为一个子程序/函数的特例。与子程序/函数不同的是,子程序调用总是一个入口,一次返回,调用顺序是明确的。而协程的调用和子程序不同。协程看上去也是子程序,但执行过程中,在子程序内部可中断,然后转而执行别的子程序,在适当的时候再返回来接着执行。

子程序与主程序是调用与被调用关系,而协程之间是平等的关系,先执行一个协程A,在适当的时候去执行另一个协程B,在适当的时候又返回协程A继续执行。协程在单线程中实现了类似多线程的效果,但因为协程始终属于一个线程,不同协程的执行只是一个线程在执行不同的“函数”而已,因此它省去了线程切换带来的开销,具有很高的并发和性能。

但协程是一个线程执行,如何利用多核CPU呢,答案就是协程+进程,每个核维持一个进程,在该进程中有一个线程来执行协程,这样就能充分利用多核以及协程的高效率,获得极大地性能。

在Python中,由于GIL(Global Interpreter Lock)的存在,导致在python中的多线程其实是伪多线程,同一时刻只有一个线程正在执行。因此在python中多线程往往(对于CPU密集型)还没有单线程高效,(当然可以用multiprocessing模块,利用多进程实现多核CPU并行),因此python的多线程对于CPU密集型工作其实是个鸡肋。多进程+协程才是python性能的大杀器。在IO密集型工作中,python的多线程能发挥得好一些,但还是没有协程高效。

回到本文实现的目标:做一个爬虫。爬虫属于IO密集型,那么如果我们不利用任何多线程或者协程技术,也就是使用同步来实现爬虫,那么对于每一次网络调用,CPU都会阻塞,直到网络调用response的到来。这就使CPU的大部分时间阻塞在等待网络IO上,效率及其低。而利用协程的话,每当一个协程进行网络调用时,CPU不用阻塞等待而是直接执行下一个协程,当网络调用返回后,将注册在事件循环中,在未来的某个时刻接着执行。这就是异步IO,能极大地提高性能。

Scrapy框架使用多线程来实现爬虫这种IO密集型的工作,也能取得不错的性能。但我们今天不打算利用线程池来实现高效            爬虫,而是使用协程来实现。Python 3.5以后已经直接支持async, await关键字,使得协程的实现变得很简单。

回想一下如果我们不使用协程+异步IO,我们将这么实现,代码基于python3.5:

from urllib import request
from urllib.error import HTTPError
import json

def crawl(url):
    try:
        res = request.urlopen(url)
    except HTTPError:
        return None
    return res.read() #返回字节流
if name == 'main':
    url = 'https://api.github.com/users/ayonel/followers?per_page=99&page=1'
    res_data = crawl(url)
    json_data = json.loads(res_data.decode()) # 字节流解码,并转为json
    print(json_data)

上面这段代码,利用python3内置的urllib模块,爬取github API, 返回的是笔者的github的粉丝(虽然没几个…)。

在上面代码中,程序将阻塞在这一行,直到网络调用返回结果。

 res = request.urlopen(url)

我们的协程+异步IO爬虫,就是解决这个问题,当发出网络请求,程序不用阻塞,CPU直接执行下一个协程。
在urllib中的request是基于同步实现的,我们需要aiohttp这个模块,用来发出异步的网络请求。另外,我还将爬取到的结果,存入了MongoDB,但是python中最常用的操作MongoDB的驱动pymongo也不是基于异步实现的,还好有motor,一个基于异步IO的python MongoDB驱动。

还是原来的需求,我们需要爬取github上一些用户的粉丝。爬取链接为:

https://api.github.com/users/{user}/followers?per_page=99&page={page}

上述这个URL返回一个用户的粉丝,并且每页最多返回99个,如果超过99个,则需要对page+1

先定义两个协程函数, fetch 以及 do_insert,分别用于异步爬取网页,以及异步插入MongoDB。

async def fetch(session, user, page):
    url = 'https://api.github.com/users/' + user + '/followers?per_page=99&page=' + str(page)
    with async_timeout.timeout(20):  # 默认超时时间20s
        async with session.get(url, headers={}) as response:
            if response.status == 200:
                return True, user, await response.read()  # True代表爬取成功
            else:
                return False, user, await response.read()   # False代表爬取失败

还有插入数据库函数:

async def do_insert(arg):
    await collection.insert_one(arg)  # collection是全局变量,代表你要插入的MongoDB的collection

上面这两个协程函数,是我们异步IO调用的关键函数,也是我们爬虫性能高效的关键所在。
有了协程函数,我们就需要定义一个主函数来执行,我们的主函数也是协程函数,另外还传入了你要爬取的用户集

async def main(loop, peopleSet):
    async with aiohttp.ClientSession(loop=loop) as session:
        for people in peopleSet:
            page = 1
            while True:  # 因为有些人不止有99个粉丝,所以遇到一页返回99个粉丝的,不能直接下一个人,还需要将page+1,去爬取该人的其他粉丝
                is_ok, user, data = await fetch(session, people, page)
                print(user)
                if is_ok:  #如果网络返回正常,status==200
                    if data[0] == 31 and data[1] == 139:  # 这儿是个坑,判断是不是gzip压缩过的字节流。原因见下文解释
                        print('gzip data returned!')
                        data = zlib.decompress(data, zlib.MAX_WBITS | 16)  # 解gzip字节流

                follower_list = []
                for follower in json.loads(data.decode()): # 将字节流解码为str,并转为json
                    follower_list.append(follower['login'])

                await do_insert({'user': user, 'follower': follower_list}) # 异步调用插入数据库
                if len(follower_list) == 99: # 如果返回99个粉丝,需要page+1
                    page += 1
                else: # 否则,直接break,爬取下一个人
                    break
            else: # 网络调用失败,直接break,爬取下一个人
                break

解释一下上面为什么要判断字节流是否是gzip压缩过的。Github API 有个坑,它有时会将响应内容压缩为gzip返回,我们用浏览器查看时没问题,因为浏览器会自动判断是否是gzip格式的字节流,如果是将会自动解压。而aiohttp返回的response.read()是原始的字节流,你不知道它有没有经过gzip压缩。按常理来说,如果你在你的请求头中不要设置Accept-Encoding字段,服务器应该认为该客户端不接受任何压缩过的内容,应该返回未压缩的字节流。但我强制指定请求头,不设置Accept-Encoding字段,Github API还是玄幻地随机返回gzip字节流。并且它的response的headers中永远显示其Content-Encoding = gzip,这儿应该是个bug吧。所以我不得不自行判断是否是gzip格式的,判断方法很简单,利用字节流的前两个字节:
前两个字节用于标识gzip文件,其中第一个字节ID1 = 31(0x1f,\037),第二个字节ID2 = 139(0x8b,\213),如果判断该字节流以这两个字节开头,那么可以初步认为这是gzip字节流。

我们还需要开启事件循环,才能达到异步IO的效果,完整程序见下文:

'''
Author: ayonel
Date:
Blog: https://ayonel.malash.net
GitHub: https://github.com/ayonel
E-mail: ayonel@qq.com
提取出所有pull中的人员,爬取其关注关系。
'''

import itertools
import json
import aiohttp
import asyncio
import time
from motor.motor_asyncio import AsyncIOMotorClient
import zlib
import async_timeout

async_client = AsyncIOMotorClient('localhost', '27017') # 建立motor的client
db = async_client['follow'] # 指定要插入的数据库
collection = db['asyncfollow'] # 指定要插入的collection

#异步插入函数

async def do_insert(arg):
    await collection.insert_one(arg)

#异步爬取函数

async def fetch(session, user, page):
    url = 'https://api.github.com/users/' + user + '/follower?per_page=99&page=' + str(page)
    with async_timeout.timeout(20):  # 默认超时时间20s
        async with session.get(url, headers={}) as response:
            if response.status == 200:
                return True, user, await response.read()  # True代表爬取成功
            else:
                return False, user, await response.read()   # False代表爬取失败

#主函数

async def main(loop, peopleSet):
    async with aiohttp.ClientSession(loop=loop) as session:
        for people in peopleSet:
            page = 1
            while True:  # 因为有些人不止有99个粉丝,所以遇到一页返回99个粉丝的,不能直接下一个人,还需要将page+1,去爬取该人的其他粉丝
                is_ok, user, data = await fetch(session, people, page)
                print(user)
                if is_ok:  #如果网络返回正常,status==200
                    if data[0] == 31 and data[1] == 139:  # 这儿是个坑,判断是不是gzip压缩过的字节流。原因见下文解释
                        print('gzip data returned!')
                        data = zlib.decompress(data, zlib.MAX_WBITS | 16)  # 解gzip字节流

                follower_list = []
                for follower in json.loads(data.decode()): # 将字节流解码为str,并转为json
                    follower_list.append(follower['login'])

                await do_insert({'user': user, 'follower': follower_list}) # 异步调用插入数据库
                if len(follower_list) == 99: # 如果返回99个粉丝,需要page+1
                    page += 1
                else: # 否则,直接break,爬取下一个人
                    break
            else: # 网络调用失败,直接break,爬取下一个人
                break


if name == 'main': # 程序入口
    start = time.time() # 标记开始时间
    peopleSet = set() # 初始化需要爬取的用户集
    peopleSet.add('ayonel')
    peopleSet.add('malash')
    # 上面我只添加了2个人,实际我的peopleSet中有2万多人
    loop = asyncio.get_event_loop() # 开启事件循环
    try:
        loop.run_until_complete(main(loop, peopleSet)) # 开始执行main
    except Exception:
        pass
    finally:
        print('总耗时:' + str((time.time()-start)/60))

我另外还是实现了同步的urllib.request作为对比测试,实验显示,在我的异步爬虫爬取了9000+人的时间里,同步爬虫爬取了300人不到。性能差距是巨大滴…

上面完整代码给出的爬虫还能不能提高速度呢?答案是可以的!上述代码中其实把整个爬取任务封装成了一个大协程,这个大协程由许多个网络调用小协程以及数据库插入小协程构成。同时我们的所有aiohttp的请求复用了同一个aiohttp.ClientSession(),这样做的好处是我们的程序运行期间只有一个ClientSession对象,十分节约内存资源,如果我们对每个请求新开一个ClientSession的话,请求一多,内存直接就爆掉了。我实际了测试20000个请求,很快内存就会吃到10G,所以说对于ClientSession我们需要复用,那是不是所有请求都复用一个呢,就像上面完整代码中一样。当然不是,我们可以自己组织,比如500个请求复用一个ClientSession对象,或者200个请求复用一个ClientSession对象,在实际测试中,爬取效率会迅速提升,远远高于所有请求复用同一个ClientSession对象的情况。

aiohttp中还有connector(连接池),相信利用connector肯定还能更进一步提高爬取效率。

最后总结,协程+异步IO是提高并发的大杀器,python一直被诟病的性能问题,可以从这儿找回点自信,但是缺点也比较明显,只适合于IO密集型的工作,另外异步代码确实不如同步代码好理解,虽然3.5已经实现了async await关键字,但还是需要多coding才能加深理解。 听说tornado是个不错的东东,有时间可以看看。

这两天仔细研究了一下SVM的底层数学原理,感觉大学基础数学没好好学,现在看起来真的很吃力啊~~
整理了几篇关于SVM原理的文章,大家有兴趣可以看看。
1. jasper的SVM入门教程,总共有9篇,作者文笔了得,深入浅出,将很复杂抽象的概念都能讲解的特别清楚,非常值得一看。
2.July、pluskid的支持向量机通俗导论(理解SVM的三层境界),讲得十分详细,很多细节都做了推导。
3.勿在浮砂筑高台【机器学习详解】SVM解二分类,多分类,及后验概率输出以及【机器学习详解】SMO算法剖析

由于编辑公式很繁琐,我在纸上进行了推导。主要参考了勿在浮砂筑高台的推导过程!

 

现在博客正式从aws上迁移到malash的服务器上。嘻嘻,以后再也不用花钱啦~~
然后malash跟我强行装了“用两句Haskell实现快排”的逼。确实感觉到函数式编程无限的想象力。
Haskell如何写,具体忘了,下面是Python的实现,原理类似。

def sort(arr):
    if len(arr) == 0:
        return []
    x = arr.pop(0)
    return sort(filter(lambda a : a < x ,arr)) + [x] + sort(filter( lambda a : a > x, arr))

整个世界清净了,这确实是快排~~

下面是一个不怎么”函数式”的实现,代码还是很简单,并且很直观!

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) / 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quicksort(left) + middle + quicksort(right)

最近在看周志明的《深入理解Java虚拟机-JVM高级特性与最佳实战》,要学习JVM,最好还是自己先能编译一遍。书中给出了在Mac上编译openjdk7的教程,但距离今天太过久远,书中的方法并不能奏效。只能自己上网一点点来了。

最开始打算是在我的Mac上编译,我的OSX系统是macOS sierra(10.12.2),从此我算是开始了噩梦般的一天。各种网上有的,或者没有的Error简直把我折磨得要奔溃。期间光JDK都不知道装了多少个,现在想起来还是心累。正好我桌子底下还有一台机子装着ubuntu14.04,那索性就弃了Unix的坑,用Linux来编译吧。

总得来说在Linux上编译,还是十分顺利的,总共遇见了2个Error(Mac上光解决的都不止10个,后来实在是心累不想再耗下去了)出现的Error网上都有解决方法。下面就简单说一下步骤吧。

1.下载要将要编译的openjdk,我选择的版本是openjdk-7u40-fcs-src-b43-26_aug_2013.zip,下载地址为https://jdk7.java.net/source.html

2.因为JDK中有很多代码是Java自身实现的,所以还需要一个已经安装在本机上可用的JDK,叫做“Bootstrap JDK”。我所选用的Bootstarp JDK是JDK1.6.0_45

java version "1.6.0_45"
Java(TM) SE Runtime Environment (build 1.6.0_45-b06)
Java HotSpot(TM) Server VM (build 20.45-b01, mixed mode)

3.安装编译前的依赖环境

安装gccg++make等  
sudo apt-get install build-essential      
安装ant 1.7以上  
sudo apt-get install ant  
安装XRender  
sudo apt-get install libxrender-dev  
sudo apt-get install xorg-dev  
安装alsa  
sudo apt-get install libasound2-dev
Cups  
sudo apt-get install libcups2-dev  
安装零碎的工具包  
sudo apt-get install gawk zip libxtst-dev libxi-dev libxt-dev

4.配置编译脚本
将你的openjdk解压后,并进入该文件夹。比如我的是在/home/ubuntu/openjdk下。
新建一个build.sh,并添加如下内容:

export LANG=C
#将一下两项设置为你的BootstrapJDK安装目录
export ALT_BOOTDIR=/usr/java/jdk1.6.0_45
export ALT_JDK_IMPORT_PATH=/usr/java/jdk1.6.0_45
#允许自动下载依赖包
export ALLOW_DOWNLOADS=true

#使用预编译头文件,以提升便以速度
export USE_PRECOMPILED_HEADER=true

#要编译的内容,我只选择了LANGTOOLS、HOTSPOT以及JDK
export BUILD_LANGTOOLS=true
export BUILD_JAXP=false
export BUILD_JAXWS=false
export BUILD_CORBA=false
export BUILD_HOSTPOT=true
export BUILD_JDK=true

#要编译的版本
export SKIP_DEBUG_BUILD=false
export SKIP_FASTDEBUG_BUILD=true
export DEBUG_NAME=debug

#避免javaws和浏览器Java插件等的build
BUILD_DEPLOY=false

#不build安装包
BUILD_INSTALL=false

#设置存放编译结果的目录
export ALT_OUTPUTDIR=/home/ubuntu/openjdk/openjdk/build

unset CLASSPATH
unset JAVA_HOME
make sanity
DEBUG_BINARIES=true make 2>&1 | tee $ALT_OUTPUTDIR/build.log

5.开始编译
在openjdk目录下,运行build.sh

chmod +x build.sh
./build.sh

由于我的机子比较旧,编译用了将近25分钟。最后如果出现如下图所示,祝贺你,终于成功了。
编译

进入生成build/j2re-image/bin下,执行

./java -version

输出的java版本信息将是带着你的机器用户名,我用的是root用户,所以输出了:

openjdk version "1.7.0-internal-debug"
OpenJDK Runtime Environment (build 1.7.0-internal-debug-root_2017_01_05_07_34-b00)
OpenJDK Server VM (build 24.0-b56-jvmg, mixed mode)

总算是迈出了真正的第一步。不得不佩服那些大牛超常的智慧,一个JDK我们编译都感到如此庞大复杂,他们居然用一行行代码敲出来!!orz—-
PS:linux上确实要好编译,我在ubuntu16.04 64位上也很快顺利完成了。
linux 64

题目描述:
如果两个字符串中的字符一样,出现次数也一样,只是出现的顺序的顺序不一样,则认为这两个字符串是兄弟字符串,或称变位词。例如”bad”和”adb”即为兄弟字符串。现提供一个字符串,请问如何在字典中迅速找到它的兄弟字符串。例如待查找的字符串是”apple”,字典是{“appl”,”paal”,”aplep”,”bb”,”leapp”,”hello”},则输出的单词应为:”aplep”, “leapp”。

题目描述:《编程之法》、《编程珠玑》
原理比较简单,但是要完整地实现起来,需要很多基础的小算法,如排序,搜索等。应该,用这个题顺便来练习一下基本算法,还是挺有意义的。

解题思路:首先用快排对整个字典排序,排序的比较标准是每个单词内部先排好序之后的签名,比如”apple”—>”aelpp”,”dddap”—>”adddp”;再用排序之后的字典二分搜索目标单词,找到签名一样的单词,则分别向上,向下找到同样签名的单词,并输出;

代码:

//
// Created by ayonel on 2016/12/27.
//

/**
 * 如果两个字符串中的字符一样,出现次数也一样,只是出现的顺序的顺序不一样,则认为这两个字符串是兄弟字符串。
 * 例如"bad"和"adb"即为兄弟字符串。现提供一个字符串,请问如何在字典中迅速找到它的兄弟字符串
 *
 * 例如待查找的字符串是"apple",字典是{"appl","paal","aplep","bb","leapp","hello"}
 * 则输出的单词应为:"aplep", "leapp"
 *
 * 首先用快排对整个字典排序,排序的比较标准是每个单词内部先排好序之后的签名,比如"apple"--->"aelpp","dddap"--->"adddp";
 * 再用排序之后的字典二分搜索目标单词,找到签名一样的单词,则分别向上,向下找同样签名的单词,并输出;
 * */


#include <stdio.h>
#include <string.h>
#define MAX_LEN 20 // 假定每个单词的最大字符数是20
#define WORD_COUNT 6
char set[][WORD_COUNT] = {"appl","paal","aplep","bb","leapp","hello"};


// 通过对单词插入排序,获取签名,不要直接传入原数组中的单词,应该传入单词的副本,反正覆盖原数组
char* sign(char *result) {
    int j = 0;
    int i = 1;
    char tmp = ' ';
    //插入排序
    while (result[i] != '\0') {
        tmp = result[i];
        for(j = i; j > 0 && result[j-1] > tmp; j--) {
            result[j] = result[j-1];
        }
        result[j] = tmp;
        i++;
    }
    return result;
}

//比较两个单词的签名大小
int compare_by_sign(char *a, char *b) {
    char sort_a[MAX_LEN];
    char sort_b[MAX_LEN];
    strcpy(sort_a, a);
    strcpy(sort_b, b);

    return strcmp(sign(sort_a), sign(sort_b));
}

//比较两个单词大小
int compare(char *a, char *b) {
    return strcmp(a, b);
}

//交换原数组中下标为i和j的单词位置
void swap(int i, int j){
    if (i == j)
        return;
    char tmp[MAX_LEN];
    strcpy(tmp, set[i]);
    strcpy(set[i], set[j]);
    strcpy(set[j], tmp);
}

// 对原数组按照签名大小,进行快排
void qsort(int l, int u) {
    if (l > u)
        return;
    int m = l;

    for(int i = l+1; i <= u; i++) {
        if(compare_by_sign(set[i], set[l]) < 0){
            swap(i,++m);
        }
    }
    swap(m,l);

    qsort(l, m-1);
    qsort(m+1, u);
}

//在排序好的数组中二分查找签名相同的单词,并输出
void bsearch(int l, int u, char *word_sign, int *is_found) {
    int mid = (u - l) / 2;
    if (l > u) {
        return;
    }
    char mid_sign[MAX_LEN];
    strcpy(mid_sign, set[mid]);
    sign(mid_sign);
    int com_result = compare(mid_sign, word_sign);
    if (com_result > 0)
        bsearch(l, mid-1, word_sign, is_found);
    if (com_result < 0)
        bsearch(mid+1, u, word_sign, is_found);
    if (com_result == 0){
        //找到了,开始向下以及向上寻找相同签名的词
        int flag = mid;
        printf("found brother word:\n%s\n",set[mid]);
        *is_found = 1;
        mid--;
        flag++;
        //向上找
        while(mid > 0){
            if(compare(sign(set[mid]), word_sign) == 0)
                printf("%s\n",set[mid]);
            else
                break;
            mid--;
        }
        //向下找
        while(flag < WORD_COUNT) {
            if(compare(sign(set[flag]), word_sign) == 0)
                printf("%s\n",set[flag]);
            else
                break;
            flag++;
        }
    }
}

int main() {
    qsort(0, WORD_COUNT-1); //对原数组排序
    char des[] = "apple"; //待查找单词
    char *word_sign;
    word_sign = sign(des); //待查找单词的签名
    printf("sign is: %s\n", word_sign);

    int is_found = 0; //标记是否找到
    bsearch(0, WORD_COUNT, sign(des), &is_found); //二分查找
    if (is_found == 0) { //未找到
        printf("%s\n", "can not found brother word!!");
    }
}

输出为:

sign is: aelpp
found brother word:
leapp
aelpp

问题描述:输入具有n个浮点数的向量x,输出向量x中任何连续子向量中的最大和。例如:
如果x={1,2,3},则output=6
如果x={1,-2,3},则output=3
如果x={31,-41,59,26,-53,58,97,-93,-23,84},则output=187
当所有输入为负数时,最大连续子向量为空向量,输出为0

问题来源:《编程珠玑 第2版》第8章

对于该问题,平方算法书中给出了两种,都比较直观。

作者提出了一种O(nlogn)的算法,主要利用分治和递归。将原向量从中间分开,分为左向量和右向量。递归寻找左向量,右向量,以及以分开点为起点的向左最大向量+向右最大向量。
书中也给出了算法。如下:

#include <stdlib.h>
int x[10] = {31,-41,59,26,-53,58,97,-93,-23,84};
float max(float x, float y) {
    return x >= y? x : y;
}

float max3(float x, float y, float z) {
    int larger = max(x, y);
    return max(larger, z);
}
//核心算法
float maxsum3(int l, int u) {
    if (l > u)
        return 0;
    if (l == u)
        return max(0, x[1]);
    int m = (l + u) / 2;
    //找出以m为起点的向左的最大子向量
    float lmax  = 0;
    float sum = 0;
    for (int i = m; i >= 1; i--) {
        sum += x[i];
        lmax = max(lmax, sum);
    }
    //找出以m为起点的向右的最大子向量
    float rmax = 0;
    sum = 0;
    for(int i = m + 1; i < u; i++) {
        sum += x[i];
        rmax = max(rmax, sum);
    }
    //lmax+rmax 就是经过m的最大子向量
    return max3(lmax+rmax, maxsum3(l, m), maxsum3(m+1, u));
}
int main(){
    printf("%f", maxsum3_l(0,9));
}

书中又给出了一个线性扫描算法,时间复杂度为O(n),程序的关键就是对maxendinghere变量,在每一次for循环中对其赋值之前,其是结束位置为i-1的最大子向量的和。赋值后其实结束位置为i的最大子向量的和;若加上x[i]之后结果依然为正,则该赋值语句将maxendinghere增大x[i];若加上x[i]之后结果为负,则该赋值语句将maxendinghere置为0(因为结束为止为i的最大子向量现在为空向量)
代码如下:

#include <stdlib.h>
int x[10] = {31,-41,59,26,-53,58,97,-93,-23,84};
float maxsum4(int n){
    float maxsofar = 0;
    float maxendinghere = 0;
    for (int i = 0; i < n; ++i) {
        maxendinghere = max(maxendinghere+x[i], 0);
        maxsofar = max(maxsofar, maxendinghere);
    }
    return maxsofar;
}

int main(){
    printf("%f", maxsum4(10));

}

可以证明不会存在快于O(n)的算法。在课后题中作者提出改进原来O(nlogn)的递归算法,使其在最坏情况下的复杂度为O(n),主要核心思想是从m向左以及向右找最大子向量时,要记下最大子向量的结束位置,下一轮递归寻找时,直接从上一次记下的结束位置开始,分别向左和向右找。代码如下:

#include <stdlib.h>
int x[10] = {31,-41,59,26,-53,58,97,-93,-23,84};
float max(float x, float y) {
    return x >= y? x : y;
}

float max3(float x, float y, float z) {
    int larger = max(x, y);
    return max(larger, z);
}
float maxsum3_l(int l, int u) {
    if (l > u)
        return 0;
    if (l == u)
        return max(0, x[l]);
    int m = (l + u) / 2;

    float lmax  = 0;
    float sum = 0;
    int last_l = m;  //向左找时最大子向量的结束位置
    for (int i = m; i >= 0; i--) {
        sum += x[i];
        if (lmax<=sum) {
            lmax = sum;
            last_l--;
        }
    }

    int last_r = m+1; //向右找时最大子向量的结束位置
    float rmax = 0;
    sum = 0;
    for(int i = m + 1; i <= u; i++) {
        sum += x[i];
        if (rmax<sum) {
            rmax = sum;
            last_r++;
        }
    }
    return max3(lmax+rmax, maxsum3_l(l, last_l-1), maxsum3_l(last_r, u)); //直接从结束位置向左及向右找
}
int main(){
    printf("%f", maxsum3_l(0,9));
}

上述程序的输出应该均为187.000000

1)首先,能够获得大家一致认可的是,不论一个servlet保存多长时间,它的生存周期肯定会短于容器的生存期,servlet实例在容器被移除之前被销毁,即所谓的“皮之不存,毛何附焉”;
(2)servlet生存期的定义,包括加载、实例化、初始化、处理客户端请求以及如何被移除。这个生存期由javax.servlet.Servlet接口的init,service和destroy方法表达。
(3)重点是:servlet采用的是单实例,多线程模式,即在同一时刻,容器中只存在某servlet的一个实例;同时,多请求(用户)会获得多个线程来运行同一个实例;
(4)在容器生命周期内,不同时间段会生存servlet的不同实例,可以理解为:A servlet在“时间段一”存在实例A.1,在“时间段二”会存在实例A.2;容器可以根据需要对长时间没有被请求的servlet实例销毁,在必要的时候再生成。

servlet在服务器中只有一个实例,每个请求会获得一个线程运行这个实例(这也是为什么对于一些操作步骤要synchronize,因为线程的轮换执行可能会对同一个servlet的共享的数据造成混乱)

servlet是首次加载后,生成了相关对象保存在web容器中,该对象是灌注整个web容器的始终,直到web容器关闭。可以参考servlet的生命周期,该对象被实例化后保存在web容器中,当有请求时web容器先截获,然后web容器开启一条线程去servlet的map集合里根据request报头寻找相关的servlet处理请求,该线程是一直处理该request,直到处理结束,响应请求。该线程结束,但是servlet对象是不会被销毁的,他还是保留在web容器中。多个请求同一servlet时就是开启多条线程响应请求。

scipy是python下的一个数值计算工具包,sklearn依赖于这个包。当我调用sklearn的CountVectorizer时,提示没有发现包scipy,直接安装又总是失败。
问题就在于 scipy的安装需要依赖很多别的包,在windows这个蛋疼的平台下极有可能安装失败。并且在windows上scipy的安装依赖于mkl+numpy这个包。这个包官方并没有提供,而在http://www.lfd.uci.edu/~gohlke/pythonlibs/#scipy这里面有提供。

我的python是3.5,64位。 所以我选择numpy-1.12.0b1+mkl-cp35-cp35m-win_amd64.whl和scipy-0.18.1-cp35-cp35m-win_amd64.whl这两个文件。cp35代表python3.5,其他版本要选择其他对应的文件。下载好之后先用pip 安装numpy+mkl:

pip install numpy-1.12.0b1+mkl-cp35-cp35m-win_amd64.whl

再安装scipy:

pip install scipy-0.18.1-cp35-cp35m-win_amd64.whl

大功告成。
pip
不过这个网址“http://www.lfd.uci.edu/~gohlke/pythonlibs/”是在国外,下载起来速度简直是龟速。我把我安装的这个两个文件已经上传到百度云了。另外还有32位的,有需要的同学可以自行下载。
分享链接:http://pan.baidu.com/s/1miloOe0 密码:edo4

在文本分类中有这样一个场景,当我们已经分好词,并构造出词频向量后,这个向量会很大,经常会多达几万维,甚至十几万维。这种规模的模型如果要用SVM等较高级的机器学习进行训练的话,那简直是慢的要死,深度学习就再别谈了。为了较少向量维度,我们可以采用一些方法,比如在词向量中过滤掉词频小于N的词,这个N可以自己定,但一般取值比较小。采用这种方法能有效降低向量维度,但是还是不够。我们不能为了降低向量维度到一定的程度而不断地增大N值,因为这种过滤掉低频次的方法,对向量维度的减少是随着N的增大而逐步降低的,比如说:将N=1,你可以过滤掉10000个单词;接着N=2,你过滤掉了15000个单词;N=3,过滤掉16000个单词;N=4,过滤掉了16800个单词。所以这种方法适用于粗糙地降维。我们可以在原始数据集上利用这种方法先过滤一波词。然后再想别的方法。

那么怎样才能将向量的维度降到我们想要的大小,而不会对整个系统的信息产生重大影响呢?这个问题就是特征选择的问题。
特征选择有2个很明显的优点:
1. 减少特征数量、降维,使模型泛化能力更强,减少过拟合
2. 增强对特征和特征值之间的理解

一般对于文本分类有两种最常用的信息选择方法。一个是卡方检验,另一个是信息增益。但凡是特征选择,总是在将特征的重要程度量化之后再进行选择,而如何量化特征的重要性,就成了各种方法间最大的不同。开方检验中使用特征与类别间的关联性来进行这个量化,关联性越强,特征得分越高,该特征越应该被保留。

在信息增益中,重要性的衡量标准就是看特征能够为分类系统带来多少信息,带来的信息越多,该特征越重要。本文只针对信息增益,卡方检验请自行谷歌度娘。

关于信息增益,大牛Jasper有一篇十分精彩的博文来进行介绍,其计算方法Jasper已经说得十分清楚了。建议你看完这篇文章,再来继续阅读本文。

信息增益最后的推导公式为
我们现在要用python来实现信息增益的计算。
假设我们有4篇文档,每篇文档都已经分好词了:

文档1: 鲜花 体育
文档2: 太阳 大象 体育
文档3:  大象

假设我们词的索引是:

[鲜花,太阳,大象,体育]

那么我们的文档构造好的词频向量分别是:

文档1:[1,0,0,1]:
文档2:[0,1,1,1]
文档3:[0,0,1,0]

假设3篇文档的分类分别是:文档1和文档2属于“0”类,文档3属于“1”类。

那么我们程序的输入就是X,y:
X代表词频向量组成的矩阵

[[1,0,0,1],
 [0,1,1,1],
 [0,0,1,0]]

y代表标签向量

[0,0,1]

我们利用numpy包中的矩阵来包装X,因为它可以提供许多方便的高级函数。
下面就贴上代码,代码里有注释,有兴趣的同学可以好好研究一下,如果你想拿来直接用的话,也是没问题的。代码的效率应该还是可以的,其中有一个比较巧妙的矩阵的转秩。
可以好好理解一下:

#coding: utf-8
import numpy as np
'''
    计算信息增益
    powerd by ayonel
'''

class InformationGain:
    def __init__(self, X, y):
        self.X = X
        self.y = y
        self.totalSampleCount = X.shape[0]      # 样本总数
        self.totalSystemEntropy = 0             # 系统总熵
        self.totalClassCountDict = {}           # 存储每个类别的样本数量是多少
        self.nonzeroPosition = X.T.nonzero()    # 将X转置之后输出非零值的位置
        self.igResult = []                      # 保存结果的list
        self.wordExistSampleCount = 0
        self.wordExistClassCountDict = {}
        self.iter()


    # 将结果列表排序输出
    def get_result(self):
        return self.igResult

    # 计算系统总熵
    def cal_total_system_entropy(self):
        # 计算每个类别各有多少个
        for label in self.y:
            if label not in self.totalClassCountDict:
                self.totalClassCountDict[label] = 1
            else:
                self.totalClassCountDict[label] += 1
        for cls in self.totalClassCountDict:
            probs = self.totalClassCountDict[cls] / float(self.totalSampleCount)
            self.totalSystemEntropy -= probs * np.log(probs)


    # 遍历nonzeroPosition时,逐步计算出每个word的信息增益
    def iter(self):
        self.cal_total_system_entropy()

        pre = 0
        for i in range(len(self.nonzeroPosition[0])):
            if i != 0 and self.nonzeroPosition[0][i] != pre:
                for notappear in range(pre+1, self.nonzeroPosition[0][i]):  # 如果一个词在整个样本集中都未出现,则直接赋为0
                    self.igResult.append(0.0)
                ig = self.cal_information_gain()
                self.igResult.append(ig)
                self.wordExistSampleCount = 0
                self.wordExistClassCountDict = {}
                pre = self.nonzeroPosition[0][i]
            self.wordExistSampleCount += 1
            yclass = self.y[self.nonzeroPosition[1][i]]  # 求得当前样本的标签
            if yclass not in self.wordExistClassCountDict:
                self.wordExistClassCountDict[yclass] = 1
            else:
                self.wordExistClassCountDict[yclass] += 1
        # 计算最后一个单词的ig
        ig = self.cal_information_gain()
        self.igResult.append(ig)

    # 计算ig的主要函数
    def cal_information_gain(self):
        x_exist_entropy = 0
        x_nonexist_entropy = 0

        for cls in self.wordExistClassCountDict:
            probs = self.wordExistClassCountDict[cls] / float(self.wordExistSampleCount)
            x_exist_entropy -= probs * np.log(probs)

            probs = (self.totalClassCountDict[cls] - self.wordExistClassCountDict[cls]) / float(self.totalSampleCount - self.wordExistSampleCount)
            if probs == 0: #该单词在每条样本中都出现了,虽然该几率很小
                x_nonexist_entropy = 0
            else:
                x_nonexist_entropy -= probs*np.log(probs)

        for cls in self.totalClassCountDict:
            if cls not in self.wordExistClassCountDict:
                probs = self.totalClassCountDict[cls] / float(self.totalSampleCount - self.wordExistSampleCount)
                x_nonexist_entropy -= probs*np.log(probs)

        # 合并两项,计算出ig
        ig = self.totalSystemEntropy - ((self.wordExistSampleCount/float(self.totalSampleCount))*x_exist_entropy +
                                        ((self.totalSampleCount-self.wordExistSampleCount)/float(self.totalSampleCount)*x_nonexist_entropy))
        return ig
if __name__ == '__main__':
    X = np.array([[1,0,0,1],[0,1,1,1],[0,0,1,0]])
    y = [0,0,1]
    ig = InformationGain(X, y)
    print(ig.get_result())

以上程序运行结果:

[0.17441604792151594, 0.17441604792151594, 0.17441604792151594, 0.63651416829481278]

上面的结果代表着
鲜花的信息增益:0.17441604792151594
太阳的信息增益:0.17441604792151594
大象的信息增益:0.17441604792151594
体育的信息增益:0.63651416829481278