计算机

使用 partition by 查找并删除 MySQL 数据库中重复的行

在创建 MySQL 数据表的时候,经常会忘记给某个字段添加 unique 索引,但是等到想添加的时候又已经有了重复数据,这时候就需要删除重复数据。

准备数据

本文使用如下的数据作为演示:

CREATE TABLE contacts (
    id INT PRIMARY KEY AUTO_INCREMENT,
    first_name VARCHAR(50) NOT NULL,
    last_name VARCHAR(50) NOT NULL,
    email VARCHAR(255) NOT NULL
);

INSERT INTO contacts (first_name,last_name,email) 
VALUES ('Carine ','Schmitt','carine.schmitt@verizon.net'),
       ('Jean','King','jean.king@me.com'),
       ('Peter','Ferguson','peter.ferguson@google.com'),
       ('Janine ','Labrune','janine.labrune@aol.com'),
       ('Jonas ','Bergulfsen','jonas.bergulfsen@mac.com'),
       ('Janine ','Labrune','janine.labrune@aol.com'),
       ('Susan','Nelson','susan.nelson@comcast.net'),
       ('Zbyszek ','Piestrzeniewicz','zbyszek.piestrzeniewicz@att.net'),
       ('Roland','Keitel','roland.keitel@yahoo.com'),
       ('Julie','Murphy','julie.murphy@yahoo.com'),
       ('Kwai','Lee','kwai.lee@google.com'),
       ('Jean','King','jean.king@me.com'),
       ('Susan','Nelson','susan.nelson@comcast.net'),
       ('Roland','Keitel','roland.keitel@yahoo.com'),
       ('Roland','Keitel','roland.keitel@yahoo.com');

注意其中有一行重复了三次。输入完成后,数据如图所示:

file

查找重复的行

使用 group by 和 having

假设我们要通过 email 字段来查找重复值。通过使用 group by 和 having 子句可以查找到哪些行是重复的。

SELECT
    email,
    COUNT(email)
FROM
    contacts
GROUP BY email
HAVING COUNT(email) > 1;

file

Having 就类似于 Group by 之后的 where 子句。但是这个语句还是很难解决我们的问题,我们只知道发生重复的第一行了,而不知道哪些行是重复的。这时候可以使用 partition by 语句。

使用 partition by 找出所有的重复行

需要注意的是,partition by 只有在 MySQL 8.0 之后才支持,而现在常用的是 5.6 和 5.7 版本。

Partition 语句又叫做窗口聚合语句,也就是说他会把同一个值的行聚合成一个窗口,但是和 Group by 语句不同的是,窗口内的每一个行并没有被压缩成一行,具体说Partition by 的语法是:

window_function_name(expression) 
    OVER (
        [partition_defintion]
        [order_definition]
        [frame_definition]
    )

删除重复的行

删除的方法有很多种,这里介绍两种。

References

  1. https://www.mysqltutorial.org/mysql-window-functions/

Puppeteer 中如何绕过无头浏览器检测

执行以下代码:

# credits: https://intoli.com/blog/making-chrome-headless-undetectable/

import pyppeteer as pp

from futile2.http import get_random_desktop_ua

HIDE_SCRIPTS = dict(
    hide_webdriver="""
() => {
    Object.defineProperty(navigator, 'webdriver', {
      get: () => false,
    });
  }
""",
    hide_navigator="""
() => {
    // We can mock this in as much depth as we need for the test.
    window.navigator.chrome = {
      app: {
        isInstalled: false,
      },
      webstore: {
        onInstallStageChanged: {},
        onDownloadProgress: {},
      },
      runtime: {
        PlatformOs: {
          MAC: 'mac',
          WIN: 'win',
          ANDROID: 'android',
          CROS: 'cros',
          LINUX: 'linux',
          OPENBSD: 'openbsd',
        },
        PlatformArch: {
          ARM: 'arm',
          X86_32: 'x86-32',
          X86_64: 'x86-64',
        },
        PlatformNaclArch: {
          ARM: 'arm',
          X86_32: 'x86-32',
          X86_64: 'x86-64',
        },
        RequestUpdateCheckStatus: {
          THROTTLED: 'throttled',
          NO_UPDATE: 'no_update',
          UPDATE_AVAILABLE: 'update_available',
        },
        OnInstalledReason: {
          INSTALL: 'install',
          UPDATE: 'update',
          CHROME_UPDATE: 'chrome_update',
          SHARED_MODULE_UPDATE: 'shared_module_update',
        },
        OnRestartRequiredReason: {
          APP_UPDATE: 'app_update',
          OS_UPDATE: 'os_update',
          PERIODIC: 'periodic',
        },
      },
    };
  }
""",
    hide_permission="""
() => {
    const originalQuery = window.navigator.permissions.query;
    return window.navigator.permissions.query = (parameters) => (
      parameters.name === 'notifications' ?
        Promise.resolve({ state: Notification.permission }) :
        originalQuery(parameters)
    );
  }
""",
    hide_plugins_length="""
() => {
    // Overwrite the `plugins` property to use a custom getter.
    Object.defineProperty(navigator, 'plugins', {
      // This just needs to have `length > 0` for the current test,
      // but we could mock the plugins too if necessary.
      get: () => [1, 2, 3, 4, 5],
    });
  }
""",
    hide_language="""
() => {
    // Overwrite the `plugins` property to use a custom getter.
    Object.defineProperty(navigator, 'languages', {
      get: () => ['en-US', 'en'],
    });
  }
""",
    hide_webgl_renderer="""
() => {
    const getParameter = WebGLRenderingContext.getParameter;
    WebGLRenderingContext.prototype.getParameter = function(parameter) {
      // UNMASKED_VENDOR_WEBGL
      if (parameter === 37445) {
        return 'Intel Open Source Technology Center';
      }
      // UNMASKED_RENDERER_WEBGL
      if (parameter === 37446) {
        return 'Mesa DRI Intel(R) Ivybridge Mobile ';
      }

      return getParameter(parameter);
    };
}
""",
    hide_broken_image="""
() => {
    ['height', 'width'].forEach(property => {
      // store the existing descriptor
      const imageDescriptor = Object.getOwnPropertyDescriptor(HTMLImageElement.prototype, property);

      // redefine the property with a patched descriptor
      Object.defineProperty(HTMLImageElement.prototype, property, {
        ...imageDescriptor,
        get: function() {
          // return an arbitrary non-zero dimension if the image failed to load
          if (this.complete && this.naturalHeight == 0) {
            return 20;
          }
          // otherwise, return the actual dimension
          return imageDescriptor.get.apply(this);
        },
      });
  });
}
""",
    hide_modernizr="""
() => {
    // store the existing descriptor
    const elementDescriptor = Object.getOwnPropertyDescriptor(HTMLElement.prototype, 'offsetHeight');

    // redefine the property with a patched descriptor
    Object.defineProperty(HTMLDivElement.prototype, 'offsetHeight', {
      ...elementDescriptor,
      get: function() {
        if (this.id === 'modernizr') {
            return 1;
        }
        return elementDescriptor.get.apply(this);
      },
    });
}
""",
)

async def get_headless_page(*args, **kwargs):
    """
    生成一个无法检测的浏览器页面
    """
    browser = await pp.launch(*args, **kwargs)
    page = await browser.newPage()
    await page.setUserAgent(get_random_desktop_ua())
    for script in HIDE_SCRIPTS.values():
        await page.evaluateOnNewDocument(script)

    return page

为什么不使用 scrapy,而是从头编写爬虫系统?

时隔一年了,来回答下自己提的问题。个人不喜欢 scrapy 原因一言以蔽之:高不成,低不就,弊大于利
总的来说,需要使用代码来爬一些数据的大概分为两类人:

  1. 非程序员,需要爬一些数据来做毕业设计、市场调研等等,他们可能连 Python 都不是很熟;
  2. 程序员,需要设计大规模、分布式、高稳定性的爬虫系统,对他们来说,语言都无所谓的,更别说用不用框架了。

为什么不适合初学者?

对于初学者来说用不上 scrapy 的原因很简单:

  1. scrapy 太复杂了;
  2. scrapy 采用异步模式带来的高性能和在反爬面前实际上没有任何卵用;
  3. scrapy 项目冗余的代码结构对初学者完全是过度设计。

对于一个任何一个已经入门的程序员来说,Python 都算不上一个很复杂的语言,除了不用大括号可能让一些人感觉有些不适应之外,基本上看看语法上手就能写了。但是恰恰是因为我们都是老司机了,所以不能体会到使用一门编程语言对于外行来说可能『比登天还难』。如果不用 scrapy,可能我只需要这样:

# 以下代码未经测试,可能有些许 bug
import requests

def main():
    for i in range(100):
        rsp = requests.get(f"http://www.example.com/{i}.html")
        with open("example-{i}.html", "w") as f:
            print(f"saving {i}")
            f.write(rsp.text)

if __name__ == "__main__":
    main()

就写好了一个简单的爬虫。而使用 scrapy 呢,大概需要这样吧:

# 以下代码未经测试,可能有些许 bug
import scrapy

class QuotesSpider(scrapy.Spider):
    name = 'quotes'

    def start_requests(self):
        for i in range(100):
            yield scrapy.Request(url=f"http://www.example.com/{i}.html", callback=self.parse)

    def parse(self, response):
        page = response.url.split('/')[-2]
        with open('example-%s.html' % page, 'wb') as f:
            f.write(response.body)
        self.log('Save file %s' % page)

先不说代码增长了不少,初学者会问到这些问题:“什么是 class?为什么类还有参数?啊,什么是继承?yield 又是什么鬼,那个 scrapy.Request 又是啥?”这些都是心智负担。那么 scrapy 这些心智负担又给我们带来了什么好处呢?好处是性能和相对来说比较统一的代码结构,但是其实这两个对初学者并没有什么卵用啊……

scrapy 采用了 twisted 作为基础,实现了基于协程的高并发。协程看着虽然挺好,但是对于非程序员来说,他们往往就想对一个站点做定向爬取,你说你蹭蹭蹭把并发涨上去了,无非两个后果:

  1. 对方承受不住你爬,挂掉了,你拿不到数据;
  2. 对方把你封禁了,疯狂弹验证码,你拿不到数据。

所以,对于非程序员做的一些定向爬取来说,速度是没有意义的,甚至往往是越慢越好。scrapy out。

那么相对来说比较统一的代码结构有什么卵用吗?答案依然是没有。我们知道在 web 开发领域基本上稍微有点规模的项目还是要使用框架的,哪怕是 flask 这种微框架。在 web 开发领域,有经典的 MVC 模式,我们需要 路由、模板、ORM 这些固定的组件,所以主循环是由框架和 web server 来控制的。而对于爬虫呢?其实没有什么固定的模式,scrapy 也仅仅是定义了几个钩子函数而已,反倒我们没有了主循环,在编写一些特定逻辑的时候非常受到掣肘。

另外 scrapy 提供的一些其他功能,比如说抓取的队列或者去重等等,个人感觉有过度封装的味道,而且也都是在内存里,在反爬导致爬虫挂掉这种故障面前没有什么卵用,不二次开发的话还是得重爬。对于小白来说,也不用想 redis 这些幺蛾子,其实可以用 Google 最开始使用的一个很简单的方法,就把每个新抓到的 url 写到一个 txt 文件就好了,爬虫每次重启的时候首先读取这个 txt 就好了,网上乱七八糟的教程大多是炫技的。

为什么不适合大型爬虫系统?

前面说到,scrapy 基于 twisted。twisted 是 Python 的一个异步框架,最大的问题就是太难懂了,而且现在官方应支持了 asyncio,所以 twisted 的未来堪忧,甚至比起 twisted 来说,我更愿意投入时间到 curio 这样新兴的有潜力的异步框架。第二点就是 scrapy 控制了主循环,所以二次开发相当于只能在他的框架内做一些修修补补,并且还要兼容 twisted。

既然要开发大型爬虫系统,那么其中很重要的一部分就是爬虫的调度了。一种比较简单的模式是 scheduler 作为 master,全局调度。另一种模式没有 master,所有的爬虫 worker 都是对等的。在实际生产中显然是第一种用的更多。

显然 scheduler 这部分是不能再用一个爬虫框架来实现的,连主循环都没有怎么写逻辑呢?我们可能还要实现增量爬取,或者消费业务方发来的爬取请求等各种业务,这块显然是在 scheduler 里面的,那么这个爬虫系统无非是 scheduler 分发任务给各个 worker 来抓取。worker 还可以使用 scrapy 实现,但是呢,这个 worker 其实已经弱化为一层薄薄的 downloader 了,那我要他干嘛呢?scrapy 的核心逻辑也不过是个深度或者广度优先的遍历而已,少一个依赖不好么……

总结一下,爬虫的工作量要么在反爬,要么在调度等业务逻辑,本身只是一个 requests.get 而已,scrapy 提供的种种抽象对于初学者太复杂,大型系统又用不上,所以个人不推荐使用包括但不限于 scrapy 在内的所有爬虫框架

建议所有认为学习框架会使自己变强的人读读:Stop learning frameworks 和 评论,中文翻译

以上仅代表个人观点,欢迎讨论,不要人身攻击。

如何在 URL 中表示数组

我们知道 URL 后面的 query string 实际上是一个字典的形式。URL 的任何一个规范中都没有定义如何在 query 中传递数组,但是这个需求也是实际存在的,于是就诞生各种奇葩的形式,本文做一个总结。

常见的形式

http://www.baidu.com/search?q=url&tag=foo

这是一个正常的 URL,这里解析出来应该是一个字典 {"q": "url", "foo": "bar"}。但是 Python 会强行解析成数组 {"q": ["url"], "tag": ["foo"]}。

使用 URL 表示数组有以下几种常见形式:

http://www.baidu.com/search?q=url&tag=foo&tag=bar

重复键表示数组,Python/Node 中可以正确解析成数组,Java 只读取第一个值,PHP 只读取最后一个值。

http://www.baidu.com/search?q=url&tag[]=foo&tag[]=bar

键后增加[]并重复表示数组。PHP/Node 可以解析为 tag=[foo, bar]。Python 会解析成

PHP 的 http_build_query 会生成这种格式。

In [6]: from urllib.parse import parse_qs

In [7]: parse_qs("tag=foo&tag=bar")
Out[7]: {'tag': ['foo', 'bar']}

In [8]: parse_qs("tag[]=foo&tag[]=bar")
Out[8]: {'tag[]': ['foo', 'bar']}

In [9]: parse_qs("tag=foo")
Out[9]: {'tag': ['foo']}

http://www.baidu.com/search?q=url&tag[0]=foo&tag[1]=bar

使用数组形式表示。貌似没有原因能够处理,但是用的还挺多的。

http://www.baidu.com/search?q=url&tag=foo,bar

使用逗号分隔。貌似没有语言默认会处理这种,需要自己手工处理。但是我最喜欢这种。

一个更奇葩的例子

https://www.doi.gov/careers/explore-careers?f[0]=bureaus:20&f[1]=competencies:1638&f[2]=competencies:1642&f[3]=competencies:1648&f[4]=competencies:1656&f[5]=competencies:1661&f[6]=gs_levels:17&f[7]=gs_levels:158

总之,在不同的语言中,乃至于不同的 web 框架中对以上形式有不同的解析,非常混乱。

参考资料

  1. https://stackoverflow.com/questions/6243051/how-to-pass-an-array-within-a-query-string
  2. https://stackoverflow.com/questions/11889997/how-to-send-an-array-in-url-request/11890080
  3. https://stackoverflow.com/questions/1763508/passing-arrays-as-url-parameter
  4. https://stackoverflow.com/questions/1746507/authoritative-position-of-duplicate-http-get-query-keys

Python metaclass 的原理和应用

元编程(meta programming)是一项很神奇的能力,可以通过代码在运行时动态生成代码。元类(meta classes)是 Python 提供的一种元编程的能力。在 Python 中,类也是一种对象,那么类这种对象就是元类的实例,所以我们可以在运行时通过实例化元类动态生成类。

使用 type “函数”

首先我们来了解一下 type,type 可以作为函数使用,用来获得对象的类型:

>>> class Foo:
...     pass
>>> obj = Foo()
>>> obj.__class__
<class '__main__.Foo'>
>>> type(obj)
<class '__main__.Foo'>
>>> obj.__class__ is type(obj)
True

实际上 type 并不是一个函数,而是一个类,我们可以使用 type(type) 来确定一下:

>>> type(type)
<class 'type'>

type 实际上不只是类,而是一个“元类”。我们接下来要可以看到,所有的元类都需要继承自 type。type 是所以类的元类,所以在上面的例子中 x 是 Foo 的实例,Foo 是 type 的实例,type 又是他自己的实例。

file

使用 type 动态创建类

如果传递给 type 的参数是三个的时候,type 的语义就不再是返回给定参数的类,而是实例化生成一个新的类。

type(name: str, bases: tuple, namespace: dict)

第一个参数是新生成的类的名字;第二个参数是新生成的类的基类列表;第三个参数是要个这个类绑定的属性的列表,比如说这个类的一些方法。实际上 class Foo 这种语法只是使用 type 生成类的语法糖而已。

最简单的一个例子,比如我们要创建 Foo[0..9] 这些类,可以这样做:

classes = []
for i in range(10):
    cls = type("Foo%s" % i, tuple(), {})
    classes.append(cls)

# 就像使用普通类一样初始化 Foo0

foo0  = clssses[0]()

如果要实现类的方法,一定要记得同样是要使用 self 变量的。在 Python 中 self 只是一个约定俗称的变量,而不是关键字。

def __init__(self, name):
    self.name = name

def print_name(self):
    print(self.name)

Duck = type("Duck", tuple(), {"__init__": __init__, "print_name": print_name})

duck = Duck("Donald")

duck.print_name()
# Donald

创建自己的元类

首先我们来回顾一下 Python 中类的初始化过程:

foo = Foo()

当这条语句运行的时候,Python 会依次调用 __new____init__ 方法。其中 __new__ 方法在 __init__ 之前调用,并返回已经创建好的新对象,而 __init__ 函数是没有返回结果的。一般情况下,我们都会覆盖 __init__ 方法来对新创建的对象做一些初始化操作。

现在回归到元类上,进入烧脑部分。前面我们说过元类的实例化就是类,所以大致相当于:

Foo = MetaFoo(name, bases, attrs)  # MetaFoo 默认情况下是 type
foo = Foo()

默认情况下,所有类的元类是 type,也就是在这个类是通过 type 来创建的,这和前面说的通过 type 来动态创建类也是一致的。

那么怎样定义一个 MetaFoo 呢?只需要继承自 type 就行了。因为元类的实例化就是类的创建过程,所以在元类中,我们可以修改 __new__ 来在 __init__ 之前对新创建的类做一些操作。

>>> class MetaFoo(type):
...     def __new__(cls, name, bases, namespace):
...         x = super().__new__(cls, name, bases, namespace)  # super实际上就是 type
...         x.bar = 100  # 为这个类增加一个属性
...         return x
...

>>> Foo = MetaFoo("Foo", tuple(), {})  # MetaFoo 在这里就相当于 type 了,可以动态创建类
>>> Foo.bar
100
>>> foo = Foo()
>>> foo.bar
100

在这里我们创建了 MetaFoo 这个元类,他会给新创建的类增加一个叫做 bar 的属性。

在实际的代码中,我们一般还是不会直接动态生成类的,还是调用 class Foo 语法来生成类比较常见一点,这时候可以指定 metaclass 参数就好了。可以通过 Foo(metaclass=MetaFoo) 这种方式来指定元类。

class Foo(metaclass=MetaFoo):
    pass

这种定义和上面的元类用法效果完全是一致的。

一个现实世界的元类例子

在 django.models 或者 peewee 等 ORM 中,我们一般使用类的成员变量来定义字段,这里就用到了元类。

class Field:
    pass

class IntegerField(Field):
    pass

class CharField(Field):
    pass

class MetaModel(type):
    def __new__(meta, name, bases, attrs):
        # 这里最神奇的是:用户定义的类中的 bases 和 attrs 都会作为参数传递进来
        fields = {}
        for key, value in attrs.items():
            if isinstance(value, Field):
                value.name = '%s.%s' % (name, key)
                fields[key] = value
        for base in bases:
            if hasattr(base, '_fields'):
                fields.update(base._fields)
        attrs['_fields'] = fields
        return type.__new__(meta, name, bases, attrs)

class Model(metaclass=MetaModel):
    pass

这样用户使用的时候就可以这样定义:

>>> class A(Model):
...     foo = IntegerField()
...
>>> class B(A):
...     bar = CharField()
...
>>> B._fields
{'foo': Integer('A.foo'), 'bar': String('B.bar')}

程序在执行的时候就可以直接访问 X._fields,而不用每次都通过反射遍历一次,从而提高效率以及做一些验证。

不过,其实这个完全可以通过装饰器来实现:

def model(cls):
    fields = {}
    for key, value in vars(cls).items():
        if isinstance(value, Field):
            value.name = '%s.%s' % (cls.__name__, key)
            fields[key] = value
    for base in cls.__bases__:
        if hasattr(base, '_fields'):
            fields.update(base._fields)
    cls._fields = fields
    return cls

@model
class A():
    foo = IntegerField()

class B(A):
    bar = CharField()

但是用装饰器的话,就失去了一些类型继承的语义信息。

总结与思考

Python 中的元编程还是一种很强大的特性,但是也比较复杂,有时候很难以理解。实际上,过分的动态特性也导致了 Python 的解释器和静态分析、自动补全等很难优化,因为有好多信息必须到运行时才能知道。

实际上近些年新开发的语言越来越多地加入了静态类型的特性,比如 swift, rust, go 等。就连 Python 本身也增加了 type hinting 的功能,很遗憾的是,这个功能不是强制性的,所以也很难用来提升性能。

元类这块应该是我在 Python 语言方面了解的最后一大块知识了。接下来除了写业务代码不会再深究 Python 了,研究 Golang 去了~

Au revoir, Python!

参考

  1. https://realpython.com/python-metaclasses/
  2. https://stackoverflow.com/questions/392160/what-are-some-concrete-use-cases-for-metaclasses
  3. https://blog.ionelmc.ro/2015/02/09/understanding-python-metaclasses/
  4. https://stackoverflow.com/questions/2608708/what-is-the-difference-between-type-and-type-new-in-python

给 Python 程序员的 Go 语言教程

楔子

最近读到一亩三分地上一篇讲 Facebook 架构和国内对比的文章,感觉自己真是井底之蛙。头脑中一些架构方面的概念和 Status of the Art 的理念还相去甚远,迫切想要进一步了解一些先进知识。比如说,以前觉得 git flow 这个概念还挺不错的,实践了半年,发现 develop 分支完全是多余的;以前觉得每个项目分一个仓库方便管理,现在觉得 monorepo 似乎更好一点。另外就是对“互联网时代的 C 语言” Golang 有点想了解一下。

一年前休假的时候看了几眼 Golang,感觉还不错,但是想实际写点什么的时候发现 GOPATH 这个设计真是奇葩至极。而现在我的思想已经完全倒向 Monorepo 了,那么 GOPATH 也就看起来很可爱了,Golang 看起来也就很可爱了,也就决定再翻翻 Go 语言的书吧,以后说不定会写点儿什么呢。

忘了在哪里看过一句话:人的知识像一个网络,新学到的知识只有和已有的知识关联起来才能真正记得住、记得牢,否则的话像是一个孤岛的新知识很快就会被忘记了,于是就有了本文。

需要注意的是,本文并不是一个简单的语法对比,倘若只是语法的话,直接把代码一列其实就差不多了。除去语法之外,本文还在设计理念上做了一些对比。以下为目录。(没有链接的表示还没有写,敬请期待)

目录

  1. 语法基础
    1. 类型与变量
    2. 数据结构与控制语句
    3. 函数定义
    4. 面向对象
    5. 错误处理
    6. 包管理
  2. 并发与网络
    1. 并发机制
    2. Http 请求
  3. 常用标准库
    1. 时间解析
    2. 文件 IO
    3. 正则表达式
    4. 数学函数
    5. 定时机制

写这些文章的另一个目的就是对 Python 中相关的知识做个梳理,以便以后再学习新的语言(比如 rust, clojure)能够更有条理。

Ref

  1. Python slice notation. https://stackoverflow.com/questions/509211/understanding-slice-notation/50929x
  2. How to get type of go. https://stackoverflow.com/questions/20170275/how-to-find-a-type-of-an-object-in-go
  3. Golang online repo. https://repl.it/languages/go
  4. A tour of go. https://tour.golang.org/moretypes/6
  5. golang vs python. http://govspy.peterbe.com/#lists
  6. https://www.353.solutions/py2go/index.html

LeetCode 1236/1242 设计一个(多线程)爬虫解法

单线程题目 LeetCode-1236

具体题目就不说了,直接去 LeetCode 上看就好了。1236 要求使用单线程即可,考察的主要是图的遍历。只要注意到对于新发现的节点需要考虑是否已经访问过就好了。在实际生产中,肯定也是要用广度优先,深度优先基本就会陷进一个网站出不来了。

from urllib.parse import urlsplit

class Solution:
    def crawl(self, startUrl: str, htmlParser: 'HtmlParser') -> List[str]:
        domain = urlsplit(startUrl).netloc
        q = [startUrl]
        visited = set([startUrl])
        while q:
            newUrls = []
            for url in q:
                urls = htmlParser.getUrls(url)
                for newUrl in urls:
                    u = urlsplit(newUrl)
                    if u.netloc != domain:
                        continue
                    if newUrl in visited:
                        continue
                    visited.add(newUrl)
                    newUrls.append(newUrl)
            q = newUrls
        return list(visited)

多线程题目 LeetCode-1242

1242 题要求使用多线程来实现。在现实生活中,爬虫作为一个 IO 密集型的任务,使用多线程是一项必须的优化。

在上述的单线程版本中,我们使用了 visited 这个数组来存放已经访问过的节点,如果我们采用多线程的话,并且在每个线程中并发判断某个 URL 是否被访问过,那么势必需要给这个变量加一个锁。而我们知道,在多线程程序中,加锁往往造成性能损失最大,最容易引起潜在的 bug。那么有没有一种办法可以不用显式加锁呢?

其实也很简单,我们只要把需要把并发访问的部分放到一个线程里就好了。这个想法是最近阅读 The Go Programming Language 得到的启发。全部代码如下:

import threading
import queue
from urllib.parse import urlsplit

class Solution:
    def crawl(self, startUrl: str, htmlParser: 'HtmlParser') -> List[str]:
        domain = urlsplit(startUrl).netloc
        requestQueue = queue.Queue()
        resultQueue = queue.Queue()
        requestQueue.put(startUrl)
        for _ in range(5):
            t = threading.Thread(target=self._crawl, 
                args=(domain, htmlParser, requestQueue, resultQueue))
            t.daemon = True
            t.start()
        running = 1
        visited = set([startUrl])
        while running > 0:
            urls = resultQueue.get()
            for url in urls:
                if url in visited:
                    continue
                visited.add(url)
                requestQueue.put(url)
                running += 1
            running -= 1
        return list(visited)

    def _crawl(self, domain, htmlParser, requestQueue, resultQueue):
        while True:
            url = requestQueue.get()
            urls = htmlParser.getUrls(url)
            newUrls = []
            for url in urls:
                u = urlsplit(url)
                if u.netloc == domain:
                    newUrls.append(url)
            resultQueue.put(newUrls)

在上面的代码中,我们开启了 5 个线程并发请求,每个 worker 线程都做同样的事情:

  1. 从 requestQueue 中读取一个待访问的 url;
  2. 执行一个很耗时的网络请求:htmlParser.getUrls
  3. 然后把获取到的新的 url 处理后放到 resultQueue 中。

而在主线程中:

  1. 从 resultQueue 中读取一个访问的结果
  2. 判断每个 URL 是否已经被访问过
  3. 并分发到 requestQueue 中。

我们可以看到在上述的过程中并没有显式使用锁(当然 queue 本身是带锁的)。原因就在于,我们把对于需要并发访问的结构限制在了一个线程中。

在 IPython 中自动重新导入包

在使用 IPython 交互性测试编写的函数的时候,可以打开自动重新导入包的功能,这样每次保存后就可以直接测试了。

In [1]: %load_ext autoreload

In [2]: %autoreload 2

其中三个数字的含义是:

  • %autoreload 0 – 关闭自动重新导入
  • %autoreload 1 – 只在 import 语句重新导入
  • %autoreload 2 – 调用的时候自动重新导入

如果想要在 IPython 中自动启用

$ ipython profile create
$ vim ~/.ipython/profile_default/ipython_config.py
c.InteractiveShellApp.extensions = ['autoreload']
c.InteractiveShellApp.exec_lines = ['%autoreload 2']

Go 语言 Map 实战

相比 Rust 中尚未实现 IndexMut 的 Hash 类型来说,Go 中的 Map 实现度可以说是非常高了。

基本用法

Map 的类型是 map[KeyType]ValueType 的。也就是由 Key 类型和 Value 类型同时决定的。声明一个 Map:

var m map[string]int

不过一般很少有人这样写,还是生命并赋值比较常见,还是使用我们的 make 函数:

m = make(map[string]int)
commits := map[string]int{
    "rsc": 3711,
    "r":   2138,
    "gri": 1908,
    "adg": 912,
}

基本上除了 slice,map 和 function 以外,都可以做 map 的键。

赋值

m["route"] = 66

获取值

i := m["route"]  // 如果 route 不存在,那么获取的就是对应的零值
j := m["non-exist"]

删除值

delete(m, "route")  // 如果不存在的话,也不会抛出异常。这里和 Python 不一样

判断是否存在

i, ok := m["route"]

遍历

for key, value := range m {
    fmt.Println("Key:", key, "Value:", value)
}

并发性

map 不是线程安全的。

使用 ssh 反向隧道登录没有 IP 的服务器

假设我们家里的服务器叫做 homeserver,没有公网 IP。然后我们有一台服务器叫做 relayserver,拥有公网 IP。

在家里执行

homeserver~$ ssh -fN -R 10022:localhost:22 relayserver_user@1.1.1.1

在服务器上就可以登陆啦

relayserver~$ ssh -p 10022 homeserver_user@localhost

然而这样链接还是很不稳定的,我们还是需要一个稳定的链接,这时候就可以使用 autossh 了,它会保持链接的稳定,自动重新连接。

autossh -M 20000 -f -N your_public_server -R 1234:localhost:22 -C

参考

  1. http://xmodulo.com/access-linux-server-behind-nat-reverse-ssh-tunnel.html
  2. https://superuser.com/questions/37738/how-to-reliably-keep-an-ssh-tunnel-open