十大经典排序算法

0、算法概述0.1 算法分类十种常见排序算法可以分为两大类: 比较类排序:通过比较来决定元素间的相对次序,由于其时间复杂度不能突破O(nlogn),因此也称为非线性时间比较类排序。 非比较类排序:不通过比较来决定元素间的相对次序,它可以突破基于比较排序的时间下界,以线性时间运行,因此也称为线性时间非比较类排序。 0.2 算法复杂度 排序方法 时间复杂度(平均) 时间复杂...

Read more

蓄水池抽样算法(Reservoir Sampling)

一、问题给定一个数据流,数据流长度N很大,且N直到处理完所有数据之前都不可知,请问如何在只遍历一遍数据(O(N))的情况下,能够随机选取出m个不重复的数据。这个场景强调了3件事: 数据流长度N很大且不可知,所以不能一次性存入内存。时间复杂度为O(N)。随机选取m个数,每个数被选中的概率为m/N。 第1点限制了不能直接取N内的m个随机数,然后按索引取出数据。第2点限制了不能先遍历一遍,然后分块存...

Read more

使用Nginx过滤网络爬虫

现在的网络爬虫越来越多,有很多爬虫都是初学者写的,和搜索引擎的爬虫不一样,他们不懂如何控制速度,结果往往大量消耗服务器资源,导致带宽白白浪费了。 其实Nginx可以非常容易地根据User-Agent过滤请求,我们只需要在需要URL入口位置通过一个简单的正则表达式就可以过滤不符合要求的爬虫请求: ... location / { if ($http_user_...

Read more

当我们在谈论高并发的时候究竟在谈什么?

什么是高并发?高并发是互联网分布式系统架构的性能指标之一,它通常是指单位时间内系统能够同时处理的请求数,简单点说,就是QPS(Queries per second)。那么我们在谈论高并发的时候,究竟在谈些什么东西呢? 高并发究竟是什么?这里先给出结论:高并发的基本表现为单位时间内系统能够同时处理的请求数,高并发的核心是对CPU资源的有效压榨。 举个例子,如果我们开发了一个叫做MD5穷举的应用,...

Read more