ARTS-week04

发表于 分类于 本文字数： 3.8k 阅读时长 ≈ 3 分钟

Algorithms

本周leetcode：Reverse Integer
int型数值范围： -2147483648～2147483647，最开始时并没考虑溢出问题，导致在Submit直接报错，原数转置以后可能会出现溢出的情况。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int reverse(int x) {
        int res = 0;
        const int re = 10;
        while(x != 0){
            if(res > INT_MAX/10 || res < INT_MIN/10 ){
                return 0;
            }
            res = res * re + x % re;
            x = x / 10;
        }
        return res;
    }
};

Review

本周阅读英文文章The Top 5 Magic Commands for Jupyter Notebooks

Jupyter notebook是一个Web的交互式工具。在日常工作学习中也有使用。文章中有提到的五大魔术命令，就不一一列举：

1. %time, %timeit, %%time

想知道代码需要运行多长时间，可以使用%%time进行基准测试。 

1
2
import numpy as np
from numpy.random import randint
1
2
def one_million_dice():
    return randint(low=1, high=7, size=1000000)
1
2
%time throws = one_million_dice()
%time mean = np.mean(throws)
# Output: Wall time: 13 ms
# Output: Wall time: 2 ms

1
2
%timeit throws = one_million_dice()
%timeit mean = np.mean(throws)
# Output: 13.9 ms ± 166 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
# Output: 1.6 ms ± 20.9 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

1
2
3
%%time
throws = one_million_dice()
mean = np.mean(throws)
# Output: Wall time: 16 ms

2. %load_ext autoreload

这个命令允许自动重载加载模块，不必在每次更改代码后重新加载内核，例子可查看： https://ipython.org/ipython-doc/3/config/extensions/autoreload.html

1
2
%load_ext autoreload
%autoreload 2
1
from foo import some_function
1
some_function()
# Output: Hello world

打开foo.py修改一行内容 

1
some_function()
# Output: Hello world
# Output: foo.py already modify

Technique

《Linux/Unix系统编程手册》
进程记账(process accounting)。打开进程记账功能后，内核会在每个进程终止时将一条记账信息写入系统级的进程记账文件。这条账单记录了包含内核为该进程所维护的多种信息，包括终止状态以及进程消耗的CPU时间。

特权进程可利用系统调用acct()来打开和关闭进程记账功能。应用程序很少这一系统调用。一般会将相应命令置于系统启动脚本中，在系统每次重启时开启进程记账功能。 

1
2
3
4
5
6
#define __BSD_SOURCE
#include <unistd.h>

int acct(const char *acctfile);

return 0 on success, or -1 on error

为了打开进程账单功能，需要在参数acctfile中指定一个现有常规文件的路径名。记账文件通用的路径名是/var/long/pacct或/usr/account/pacct.若想关闭进程记账功能，则指定acctfile为NULL即可。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#define _BSD_SOURCE
#include <unistd.h>
#include "tlpi_hdr.h"

int main(int argc, char *argv[])
{
    if (argc > 2 || (argc > 1 && strcmp(argv[1], "--help") == 0))
        usageErr("%s [file]\n", argv[0]);

    if (acct(argv[1]) == -1)
        errExit("acct");

    printf("Process accounting %s\n",
            (argv[1] == NULL) ? "disabled" : "enabled");
    exit(EXIT_SUCCESS);
}

由于向记账文件中写入信息可能会加速对磁盘空间的消耗，为了对进程记账行为加以控制，Linux系统提供了名为/proc/sys/kernel/acct的虚拟文件。此文件包含3个值，按顺序分别定义了如下参数：高水位、低水位和频率。这三个参数通常的默认值为4、2和30.如果开启进程记账特性且磁盘空间低于低水位百分比，将暂停记账。如果磁盘空间升至高水位百分比之上，则恢复记账。频率值则规定了两个检查空闲磁盘空间占比的间隔时间(以秒为单位)。

Share

本周阅读《HTTP权威指南》Web机器人一章。

一、大规模Web爬虫对其访问过的地址进行管理时使用的一些技术：

1)树和散列表
复杂的机器人可能会用搜索树或散列表来记录已访问的URL。这些是加速URL查找的软件数据结构。

2)有损的存在位图
为了减小空间，一些大型爬虫会使用有损数据结构，比如存在位数组(presence bit array)。用一个散列函数将每个URL都转换成一个定长的数字，这个数字在数组中有个相关的“存在位”。爬行过一个URL时，就将相应的“存在位”置位。如果存在位已经置位了，爬虫就认为已经爬行过那个URL了。

3)检查点
一定要将已访问URL列表保存到硬盘上，以防机器人程序崩溃。

4)分类
有些大型Web机器人会使用机器人“集群”，每个独立的计算机是一个机器人，以汇接方式工作。为每个机器人分配一个特定的URL“片”，由其负责爬行。这些机器人配合工作，爬行整个Web。机器人个体之间可能需要相互通信，来回传送URL，以覆盖出故障的对等实体的爬行范围，或协调其工作。

二、避免循环和重复

1)规范化 URL
将URL转换为标准形式以避免语法上的别名

2)广度优先的爬行
每次爬虫都有大量潜在的URL要去爬行。以广度优先的方式来调度 URL去访问Web站点，就可以将环路的影响最小化。即使碰到了机器人陷阱，也可以在回到环路中获取的下一个页面之前，从其他Web站点中获取成百上千的页面。如果采用深度优先方式，一头扎到单个站点中去，就可能会跳入环路，永远无法访问其他站点。

3)节流
限制一段时间内机器人可以从一个 Web 站点获取的页面数量。如果机器人跳进了一个环路，试图不断地访问某个站点的别名，也可以通过节流来限制重复的页面总数和对服务器的访问总数。

4)限制URL的大小
机器人可能会拒绝爬行超出特定长度（通常是 1KB）的URL。如果环路使URL的长度增加，长度限制就会最终终止这个环路。有些Web服务器在使用长URL时会失败，因此，被URL增长环路困住的机器人会使某些Web服务器崩溃。这会让网管错误地将机器人当成发起拒绝服务攻击的攻击者。

5)URL/站点黑名单
维护一个与机器人环路和陷阱相对应的已知站点及URL列表，然后像躲避瘟疫一样避开它们。发现新问题时，就将其加入黑名单。这就要求有人工进行干预。但现在很多大型爬虫产品都有某种形式的黑名单，用于避开某些存在固有问题或者有恶意的站点。还可以用黑名单来避开那些对爬行大惊小怪的站点。

6)模式检测
文件系统的符号连接和类似的错误配置所造成的环路会遵循某种模式；比如，URL会随着组件的复制逐渐增加。有些机器人会将具有重复组件的URL当作潜在的环路，拒绝爬行带有多于两或三个重复组件的 URL。

7)内容指纹
一些更复杂的Web爬虫会使用指纹这种更直接的方式来检测重复。使用内容指纹的机器人会获取页面内容中的字节，并计算出一个校验和(checksum)。这个校验和是页面内容的压缩表示形式。如果机器人获取了一个页面，而此页面的校验和它曾经见过，它就不会再去爬行这个页面的链接了——如果机器人以前见过页面的内容，它就已经爬行过页面上的链接了。必须对校验和函数进行选择，以求两个不同页面拥有相同校验和的几率非常低。MD5这样的报文摘要函数就常被用于指纹计算。

有些Web服务器会在传输过程中对页面进行动态的修改，所以有时机器人会在校验和的计算中忽略Web页面内容中的某些部分，比如那些嵌入的链接。而且，无论定制了什么页面内容的动态服务器端包含（比如添加日期、访问计数等）都可能会阻碍重复检测。

8)人工监视