蒙特卡洛方法:算不动的问题就扔骰子
前言
有些问题Deterministic的路子根本走不通,硬解是天文数字,但是拿随机数去"扔",反而能又快又好的逼近答案。这就是蒙特卡洛方法,高性能计算领域里最气质独特的一支。
从算圆周率说起
最经典的入门例子,往单位正方形里随机撒点,数一数落在四分之一圆里的比例,命中数 $m$ 与总样本数 $N$ 之比就是面积的估计,于是 $\hat{\pi} = \dfrac{4m}{N}$:
有些问题Deterministic的路子根本走不通,硬解是天文数字,但是拿随机数去"扔",反而能又快又好的逼近答案。这就是蒙特卡洛方法,高性能计算领域里最气质独特的一支。
最经典的入门例子,往单位正方形里随机撒点,数一数落在四分之一圆里的比例,命中数 $m$ 与总样本数 $N$ 之比就是面积的估计,于是 $\hat{\pi} = \dfrac{4m}{N}$:
起因是同事说同样三重循环算矩阵乘法,只是把循环变量的顺序换了一下,快了几十倍,一开始我是不信的,算法都没换哪来的几十倍。自己跑了一遍被啪啪打脸,顺手把背后的原理捋清楚了,故有此文备忘。
C语言里教科书式的矩阵乘法,N阶方阵要做 $2N^3$ 次浮点运算,一行注释都不用多加:
本篇文章纯粹为了向还不是很了解SeimiAgent的同学演示下SeimiAgent的部分能力,目标网站随意选的,并没有其他目的。
SeimiAgent是基于QtWebkit开发的可在服务器端后台运行的一个webkit服务,可以通过SeimiAgent提供的http接口向SeimiAgent发送一个load请求(需求加载的URL以及对这个页面接受的渲染时间或是使用什么代理等参数),通过SeimiAgent去加载并渲染想要处理的动态页面,然后将渲染好的页面直接返给调用方进行后续处理,所以运行的SeimiAgent服务是与语言无关的,任何一种语言或框架都可以通过SeimiAgent提供的标准http接口来获取服务。SeimiAgent的加载渲染环境都是通用浏览器级的,所以不用担心他对动态页面的处理能力。同时支持渲染生成页面快照(png)和PDF,亦支持自定义js脚本处理基本渲染后的页面,具体请参见官方使用说明。
为了更为直观的了解,可以先看下分享在优酷上视频,点击地址直达
下面会是图片版的详细介绍
最近关注SeimiCrawler整合Mybatis的朋友比较多,故仅以此文抛砖引玉。如果是不了解SeimiCrawler的朋友也可以通过此文简单了解下SeimiCrawler。
SeimiCrawler是一个敏捷的,独立部署的,支持分布式的Java爬虫框架,希望能在最大程度上降低新手开发一个可用性高且性能不差的爬虫系统的门槛,以及提升开发爬虫系统的开发效率。在SeimiCrawler的世界里,绝大多数人只需关心去写抓取的业务逻辑就够了,其余的Seimi帮你搞定。设计思想上SeimiCrawler受Python的爬虫框架Scrapy启发,同时融合了Java语言本身特点与Spring的特性,并希望在国内更方便且普遍的使用更有效率的XPath解析HTML,所以SeimiCrawler默认的HTML解析器是JsoupXpath(独立扩展项目,非jsoup自带),默认解析提取HTML数据工作均使用XPath来完成(当然,数据处理亦可以自行选择其他解析器)。并结合SeimiAgent彻底完美解决复杂动态页面渲染抓取问题。
在开发调试情况下,可以直接采用main函数来启动SeimiCrawler,但是为了便于工程化部署与分发,SeimiCrawler提供了专门的打包插件maven-seimicrawler-plugin用来对SeimiCrawler工程进行打包,打好的包可以直接在服务器上部署运行了。