每周学点大数据 | No.10何谓大数据算法

No.10期

何谓大数据算法

Mr. 王：下面我们就来谈谈大数据算法与一般算法的区别和联系。

小可：好。

Mr. 王：前面我们讲了如何评价一个算法，在相对比较小的数据规模下，我们往往可以接受多项式时间算法。但是当数据量很大时，很多小数据量上我们能够在可以接受的时间内解决问题的方法，也都变得不再可以接受。虽然有些算法是多项式算法，但是它的高阶项指数却是非常大的，导致当数据规模大起来时，它的增长速度会变得非常快。对于较大的数据量，资源约束和时间约束都变得相对很苛刻，我们要对可以接受的时间界限进行重新思考。

小可：那在大数据上比较好的算法是什么样的呢？

Mr. 王：大数据算法是在给定的资源约束下，以大数据为输入，在给定的时间约束内可以生成满足给定约束结果的算法。

对于大数据而言，访问全部数据是很费时的，所以大数据算法有时需要采取读取部分数据的办法，也就是设计时间亚线性算法。而且数据往往在内存中也存不下，数据要存储在磁盘上，所以要考虑设计外存算法；或者是采取读取部分数据的办法，设计空间亚线性算法。

小可：亚线性算法有一种抽样的感觉，不访问全部数据，而是尝试选择部分数据来代表全部数据。

Mr. 王：没错。如果单台计算机不能保存所有的数据，或者一台计算机的计算资源不足以在给定的时间内解决问题，则还要引入多台计算机进行并行处理，让它们的CPU、内存、磁盘都参与到问题的解决之中，这时候还要设计并行算法。甚至当计算机的能力不足以对某些问题进行处理，或者对某些问题的处理不够好，而这些问题的某一部分恰好是人类非常擅长做的工作时，还可以引入人工参与到问题的解决之中。

小可：引入人工来帮忙，这倒真是神奇啊！我还以为计算机算法都是一定要计算机来执行的呢，大数据算法还可以不是完全由计算机执行的啊？

Mr. 王：嗯，不仅如此，大数据算法还可以不是内存算法，很多时候需要磁盘参与到海量数据的存储之中；可以不是精确算法，很多时候得出精确解的代价过大，大数据算法就以得出一个足够让我们满意的近似解来谋求更高的计算效率；可以不是串行算法，在很多常见的大数据问题求解中，引入多台计算机参与到其中，发挥它们的各种计算资源的使用以提升问题的解决速度；甚至可以不是仅仅由计算机来执行的算法，在某些特定的情况下，有很多问题由人工来解决会比由机器来解决更容易、更准确或者更高效一些。从这些方面来看，大数据算法的设计和分析与传统的经典算法有着很大的区别。

另外，在大数据算法中常用的算法设计技术有：精确算法设计方法、并行算法、近似算法、随机算法、在线算法/ 数据流算法、外存算法、面向新型体系结构的算法、现代优化算法等。在大数据算法设计之后，与经典算法一样，依然要对算法进行分析。但在分析大数据算法时，我们需要研究的也不仅仅限于时间、空间复杂度的分析和优化。对于一些不能得出精确解的算法，还要对结果质量进行分析，看看在我们可以接受的时间范围内得出的近似结论是不是足够达到要求；对于要借助磁盘存储的算法，还要考虑磁盘的IO 复杂性。有时候大数据算法会运行在比如无线传感器节点这样的对电池电力有较强限制的终端上，我们还要分析算法运行消耗的能量是不是很大，这时还要进行能量复杂度分析；如果我们使用的是一个分布式系统，整个系统架构在网络上，要依靠各个节点的频繁通信来实现，那么还要考虑系统的通信复杂度。这些特点也使得大数据算法的分析变得相对复杂一些。

这些概念现在听起来也是一头雾水吧？

小可：嗯，的确。

Mr. 王：在以后的课程中，我会把大数据算法所涉及的内容讲解给你。以后我会给你讲讲大数据算法中的亚线性算法、外存算法、并行算法、众包算法，这些都是大数据算法中的核心算法。时间不早了，我们先下课吧。

小可：那太好了。那就明天再见了，老师。

内容来源：灯塔大数据