Fisher–Yates shuffle 洗牌算法

发表于

简单来说 Fisher–Yates shuffle 算法是一个用来将一个有限集合生成一个随机排列的算法（数组随机排序）。这个算法生成的随机排列是等概率的。同时这个算法非常高效。

Fisher and Yates 的原始版

Fisher–Yates shuffle 的原始版本，最初描述在 1938 年的 Ronald Fisher 和 Frank Yates 写的书中，书名为《Statistical tables for biological, agricultural and medical research》。他们使用纸和笔去描述了这个算法，并使用了一个随机数表来提供随机数。它给出了 1 到 N 的数字的的随机排列，具体步骤如下：

写下从 1 到 N 的数字
取一个从 1 到剩下的数字（包括这个数字）的随机数 k
从低位开始，得到第 k 个数字（这个数字还没有被取出），把它写在独立的一个列表的最后一位
重复第 2 步，直到所有的数字都被取出
第 3 步写出的这个序列，现在就是原始数字的随机排列
已经证明如果第 2 步取出的数字是真随机的，那么最后得到的排序一定也是。

JavaScript 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * Fisher–Yates shuffle
 */
Array.prototype.shuffle = function() {
    var input = this;

    for (var i = input.length-1; i >=0; i--) {

        var randomIndex = Math.floor(Math.random()*(i+1));
        var itemAtIndex = input[randomIndex];

        input[randomIndex] = input[i];
        input[i] = itemAtIndex;
    }
    return input;
}

使用async库结合puppeteer并发爬取网易云音乐歌单(简易demo)

发表于
async是node的一个强大的异步第三方库,它包含许多功能方法,今天主要用其中的mapLimit方法来实现并行执行爬虫.mapLimit(coll,limit, iteratee, callbackopt)接收四个参数:
coll:是一个迭代器,代表要迭代的集合
limit:数字代表同时执行并行的限制
iteratee:迭代器方法,对于coll中的每一个item，迭代执行该异步函数。用(item, callback)调用，callback可选
callbackopt:所有iteratee 函数完成后或发生错误时触发的回调函数。用(err, results)调用。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
const puppeteer = require('puppeteer')
const cheerio = require('cheerio')
const mapLimit  = require('async/mapLimit')

const URL = 'https://music.163.com'
//标签集合
const type =['华语','欧美','日语','韩语','粤语','小语种']
async function start(type,callback){
	const browser = await puppeteer.launch({
		headless:true
	})
	const page = await browser.newPage()
	await page.goto(`${URL}/discover/playlist/?cat=${type}`)
	const $ = cheerio.load(await page.mainFrame().childFrames()[0].content())
	const list = $('#m-pl-container').find('li')
	let album = []
	Array.from(list).forEach(ele=>{
		let obj ={
			name:$(ele).find('.dec a').attr('title'),
			href:$(ele).find('.dec a').attr('href')
		}
		album.push(obj)
	})
	callback(null,album)
	await browser.close()
}

mapLimit(type,5,(type,callback)=>{
//设置并发数为 5
	start(type,callback)
},(err,result)=>{
	for(let index in result){
		console.log(result[index])
	}
})

result:

使用Puppeteer爬虫

发表于
Puppeteer是 GoogleChrome团队官方的无界面（Headless）Chrome工具，它是一个Node库，提供了一个高级的API来控制DevTool协议上的无头版 Chrome 。也可以配置为使用完整（非无头）的 Chrome。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
const puppeteer = require('puppeteer')
const cheerio = require('cheerio')
const fs = require('fs')
const assert = require('assert')

async function start() {
	const browser = await puppeteer.launch()
	const page = await browser.newPage()
	//过滤请求资源
//	await page.setRequestInterception(true)
//	page.on('request', interceptedRequest => {
//		if (interceptedRequest.url().endsWith('.png') ||
//			interceptedRequest.url().endsWith('.jpg') ||
//			interceptedRequest.url().endsWith('.gif'))
//			interceptedRequest.abort()
//		else
//			interceptedRequest.continue()
//	})
	await page.goto('http://jandan.net/ooxx')
	const $ = cheerio.load(await page.content())
	const $img = $('img')
	for (let index in $img) {
		try {
			const content = await getResourceContent(page, ($img[index].attribs.src))
			const contentBuffer = Buffer.from(content, 'base64')
			const fileName = $img[index].attribs.src.match(
				/^http(s)?:\/\/(.+)\/(.+)\/(.+\..+)/)[4]
			fs.writeFileSync(fileName, contentBuffer, 'base64')
		}
		catch (e) {}
	}
	await browser.close()
}

//获得资源树
async function getResourceTree(page) {
	var resource = await page._client.send('Page.getResourceTree')
	return resource.frameTree
}

//根据url frameId查找资源实例
async function getResourceContent(page, url) {
	const {content, base64Encoded} = await page._client.send(
		'Page.getResourceContent',
		{frameId: String(page.mainFrame()._id), url},
	)
	assert.strictEqual(base64Encoded, true)
	return content
}

start()