花火

雪,稀疏撒在暗黑的画布上

光,渐渐出现

雪中光,光中雪,混杂,交融

雪渐浓,光依旧

霎时间,鲜红的“自杀”二字震撼人心。

如“花火”般绚烂绽放,定会像“花火”般壮烈谢幕。

 

海边

宁静

不会记住

那两声枪响

Python修饰器小应用——级数求和算法简化

假设我们遇到了

    \[\sum_{n=1}^{\infty} \frac{3n+5}{3^n}\]

这样一个东西,我们算出了结果,并且需要用python验算。

通过抽象,我们需要计算

    \[\sum_{n=1}^{\infty} f(x,n)\]

用普通的for语句比较麻烦,正巧python有一个叫做修饰器的东西可以简化运算,我们每次只需要把sigma内部的公式输入即可。

series_sum为一个修饰器,只用输入一次,之后我们只需要将我们的f(x,n)用series_sum函数修饰就好了,超级优美!

 

[Pikapika]科技文献的脉络梳理-网页展示的编写

基于Flask编写

既然后端数据处理使用了python,最开始的想法是通过python-flask写网页,也因此学习了flask,但是因为实际写后端的时候没有网,于是乎重新回到了自己比较熟悉的nodejs

基于Nodejs编写

网站demo:http://pikapika.mhy12345.xyz:3000

运用d3的数据图形化的库,展示词云与结构树,过程参见http://blog.mhy12345.xyz/2017/05/18/nodejs学习笔记/

词云

使用d3项目https://www.jasondavies.com/wordcloud/,由其中demo的browserify.js生成。

 

结构树

结构树https://bl.ocks.org/mbostock/4063570,直接把里面的js代码搬下来就好了。当然,需要各种修改以适应这里的情况,不过这些细节就不用说了。

 

Nodejs学习笔记

相关链接

Express

Express官网:http://www.expressjs.com.cn

DC3

DC3官网:https://d3js.org

DC3 tutorials:https://github.com/d3/d3/wiki/Tutorials

选择器原理:https://bost.ocks.org/mike/join/

D3 4.0 API:https://github.com/d3/d3/blob/master/API.md

browserify

官网:http://browserify.org

D3-cloud词云制作

d3-scale-category20 undefined:http://stackoverflow.com/questions/41178111/d3js-d3-scale-category10-not-working

Jade

教程1:http://www.w3cplus.com/html/how-to-use-jade.html

Nodejs 包

Child_process:http://nodejs.cn/api/child_process.html

[Pikapika]科技文献的脉络梳理-构建查询Wiki的数据结构

首先我们需要实现的是一个能够查询Wiki的数据结构,而有如下几种处理方式

  1. 直接的爬虫抓取及其优化
  2. 调用现成python库(基于wiki的api)
  3. 下载离线版wikipedia

直接使用爬虫抓取wikipedia

如果直接使用python的urllib库调用的话,由于网络延迟等问题,效率大概是3sec/search

这里粘贴一个爬取百度百科的代码,wiki可以肯定比百度百科慢,毕竟在墙外面……

 

接着考虑使用更加高效的爬取框架scrapy

代码架构比较复杂,但是搜索的速度可以提升至1sec/search,其原理大概是通过异步的方式解决网络延迟的问题,但是基础的长达3sec的网络延迟还是必定会存在的,不过对于我们的分析还是过于慢了

Python库实现wiki查询

python有一个叫做wikipedia的库,其核心是通过wikipedia的公开api实现查询。还是很慢……

离线Wiki数据查询

离线数据下载主页:https://en.wikipedia.org/wiki/Wikipedia:Database_download

具体来说我下载的离线数据在这里:https://dumps.wikimedia.org/other/static_html_dumps/current/zh/

其中html.lst文件列举了所有文件名,wikipedia-zh-html.tar.7z文件就是实际的数据集,解压后11G,最棒的是解压后发现居然已经帮我把trie树建出来了!

但是,问题来了,虽然在个人的mac上面文件名非常正常,但是把它弄到ubuntu下面就完全不可看,大概就是一堆问号的情况。事实上这只是ssh上去的显示问题,还是可以用程序访问的。

不过速度嘛……

[Pikapika]科技文献的脉络梳理-概述

离散大作业我和wxz希望能够做一个科技文献的脉络梳理的小程序,输入一篇科技文献(可以是html或者纯文本),通过关键词查询等方式实现文献脉络的整理。

其中我们计划的是通过pagerank算法,引入wiki外部语料库建模,提取出科技文献的脉络。

实际上,由于效率的问题,我们并没有使用wiki外部资料库,单纯使用了pagerank。

而demo的展示通过网页实现:http://pikapika.mhy12345.xyz:3000,不过我并不准备长时间维护这个网站,所以说上不去很正常……

人智大作业-四子棋实验报告

题目大意

带重力的四子棋(连成4个(横竖斜)胜利)

大致算法

预测:朴素搜索

通过判定一个必胜态的后继状态存在对手必败态,一个必败态后继状态必须全是对手必胜态。实现搜索算法,搜索深度可以达到6层左右。

朴素搜索只能对于短期一定必胜、必败的状态进行判断,故可用于

  1. 蒙特卡罗树新增一个节点时,如果该节点胜负短期可判,则不使用随机游走,而直接将固定胜率\败率100%返回
  2. 决策时跑预测防止出现一些蒙特卡洛故意走向一个必败态的情况

估值:随机下子

估计一个局面的情况可以通过随机下子的方式,双方随机在可能的位置等概率下子,判断最后谁胜,将随机下子次数增加可以非常“不准确”的估计出当前局面对谁有优势

决策:蒙特卡洛搜索树

对于上述算法,在短期无法判断局面的时候很难决策如何下子,因此使用信心上限树算法(UCT).

     $$I_j = X_j + \sqrt{\frac{2ln(n)}{T_j(n)}}$$

通过上面的式子得出决策树上每一个位置的信心上限[latex]I_j[\latex],其中n表示总的尝试次数,

    \[$T_j$\]

表示第j个状态(及其子状态)尝试次数。

显然,每次尝试I值最大的状态可以平衡所有状态的最小尝试次数以及对较优状态的多次尝试。

程序表现

与样例程序进行对抗,分数大约在30/200分左右。

一些细节

  1. 蒙特卡洛树的决策最好选择访问次数最多的而非期望权值最大的那一个,因为蒙特卡洛每次都会拓展期望权值L最大的那一个,并有一定概率使其变小。换句话说,蒙特卡洛的决策在某种意义下就是平衡L值得过程,所以L值并不能代表一个状态的优劣
  2. 比较神奇的是有些时候迭代次数较多的程序表现没有迭代次数较少的程序,可能是因为常数没有调好……
  3. 曾经尝试在随机游走的时候加入深度较小的特判,使得双方“稍微”有一点智能,但是发现这样会导致结果基本是平局
  4. 最开始程序使用new分配内存,然而Compete程序多次调用会出现segmentation fault,单独调用无误,改为预先分配就没有问题了。不知道是否和电脑的垃圾回收机制有关系。