百度Spider如何在不超过抓取限额的情况下使得抓取的网页价_百度笔试题

REDStone

类似于01背包问题，用动态规划方案进行解答，设抓取极限为n，每个网页有自己的额度和价值，在额度不超过的情况下求得价值之和最大

发表于 2014-11-22 23:09:52 回复(2)

耗子的媛宝

令共有n个页面（0,1,2,3，...n-1）等待抓取，共抓取k个网页。

如果 n个页面的网页价值是有限的b种，b远远小于n，则可以采取hash table（key ——value）的方法。依次扫描n个页面，根据它的网页价值key，把它id存入hash当中。可以扫描完成后再取网页价值大的前k个，也可以边扫描边判断网页价值大的前几个所含的网页id个数是否已超过k，超过则停止，没超过则继续扫描。时间复杂度是 O(n),空间复杂度也是 O(n)(会有很多冲突，解决冲突)。

如果网页的价值是连续的数值，也可以先划定小的区间范围，以此小区间做hash。

或者采用堆排序，维护一个最小堆，让所有网页的价值依次和堆顶元素进行比较，比它大则入堆，调整堆，比它小则继续下一个。这时，时间复杂度：O(n *klogk), 空间复杂度 O(k)。

发表于 2015-08-11 11:02:32 回复(1)

xxxxxxxxx

如果爬取网页的流量消耗不一样，01背包问题

F(k,y)表示前k种网页，流量不超过y的情况下，能获得的最大价值

wk表示爬取编号为k的网页需要消耗的流量，vk表示编号为k的网页的价值

递推公式为：

F(k,y) = max{ F(k-1,y), F(k-1,y-wk) + vk}

F(0,y) = 0; 0=<y<=b

F(k,0) = 0; k>=0

F(k,y) = -∞; y < 0

时间复杂度为O(K,Y):K--网页种类，T流量限制

空间复杂度为O(K,Y):K--网页种类，T流量限制

编辑于 2015-08-22 15:59:25 回复(0)

牛客网课程助教3

假设每个网页有价值为wi.

wi的值为浮点数,通过堆实现.

wi为整数,则通过桶式排序记录每个价值对应的网页数量

发表于 2014-10-25 00:25:58 回复(0)

百度Spider如何在不超过抓取限额的情况下使得抓取的网页价

问题信息

热门推荐

相关试题