上周四下午的VIP试听课是由芒果给大家介绍的MySQL的一些基础知识，在这里芒果给大家分享其中的一部分内容——对数据库三大范式做个小介绍： 范式（数据库的设计范式）是符合某一种级别的关系模式的集合。...构造数据库必须遵循一定的规则，在关系数据库中，这种规则就是范式。关系数据库中的关系必须满足一定的要求，即满足不同的范式。范式，对于软件的性能、数据库的维护都是我们软件从业人员必须掌握的内容。...一般说来，数据库只需满足第三范式（3NF）就行了，所以在这里我也就跟大家介绍这三大范式。...实际上，第一范式是所有关系型数据库的最基本要求。...，然后第二范式需要确保数据库表中的每一列都和主键相关，而不能只与主键的某一部分相关（主要针对联合主键而言）。
No.7期 大数据规模的算法分析 Mr....王：这样的时间界限记为O(1)，我们称之为常数时间算法，这样的算法一般来说是最快的，因为它与输入规模完全无关，不论输入规模n多么大，我们都可以用一个与输入规模n无关的常数时间得出结论，相比于巨大的n来说...另外，与大O记号类似，常用的记号还有Θ，Θ(g(n)) 表示函数f(n)构成的集合，存在n0，c1，c2。当n≥n0时，0≤c1g(n)≤f(n)≤c2g(n)。...它们与大O记号和Ω记号类似，只是在大小关系上不包含等于。 小可：嗯，听到这里，我理解了如何进行算法的分析和几种记号表示的含义了。 Mr....内容来源：灯塔大数据
通过对基础磁盘算法的学习，我们可以很容易地想到，之所以需要设计外存的图算法，是因为如果内存无法存储全部的数据的话，我们就要尝试将数据存放在外存中；图也是一样的，当需要表示的图很大时，内存无法存下全部的图节点或者边时...，我们就要尝试将数据保存在外存中，仅当需要对图的某一部分进行处理时，才加载到内存中来。...是对一张表里面的数据进行排序吗？用前面的归并排序法可以解决吗？ Mr. 王：这里的排序和前面的不太一样，我们称前面的排序为“sort”，称现在要讲的这种排序为“ranking”。...小可：嗯，这么大的I/O 数肯定会导致程序运行的速度特别慢，用户肯定无法接受。 Mr. 王：现在看来，表排序这个问题并没有那么简单了吧。所以我们需要想一个面向外存的办法来解决这个问题。...内容来源：灯塔大数据
No.2期 大数据的特点、应用和算法 一、大数据的特点和应用 Mr. 王：大数据具有较大的数据量，和一般的数据相比，其具有如下一些特点。...在数据量上，大数据是通过各种设备产生的海量数据，其数据规模极为庞大，远大于目前互联网上的信息流量，PB 级别将是大数据的常态。...在多样性上，大数据种类繁多，在编码方式、数据格式、应用特征等多个方面存在差异性，多信息源并发形成大量的异构数据。...在价值上，数据持续到达，并且只有在特定时间和空间中才有意义。 Mr. 王：我们分析大数据、研究大数据，是希望能够利用它们获得我们需要的知识。...我们可以利用大数据进行： 预测 推荐 商业情报分析 科学研究 等发现大数据中的价值，使用大数据、利用大数据的过程。由此可知，对大数据的研究还是非常重要而有意义的。
王：其实社交网络上的这些信息就是一种典型的大数据。 小可惊讶地说：原来这就已经是大数据了？我一直以为大数据都在实验室里面呢。 Mr. 王：此言差矣，其实大数据就在我们身边。...站在社交网络之外看待它，就会发现里面有很多且杂乱无章的信息和内容，同时其规模非常大。 这就是大数据的一个典型例子。 小可恍然大悟地说道：哦，原来这就是大数据啊，那其实我每天都在接触大数据啊。 Mr....王笑道：的确，大数据就在我们每个人的身边，随着信息时代的到来，我们每个人每天接触到的数据量都是非常大的。但你在查看这些消息的时候，有没有看到除字面内容以外的东西呢？...而这么大的数据，不仅计算机的内存装不下，而且一般计算机的硬盘都已经存不下了。即使是扫描一遍，在上面发现一个小序列都需要一些时间，在这些数据上面做分析将是一件更困难的事情。这也是一种大数据。...这些仪器不停地记录下的数据，都涉及如何存储、如何分析研究的问题，这些都是大数据。 ? 生活中的大数据 小可：嗯。 Mr. 王：那我们就给大数据下个定义吧。
当我们要在机群上执行真正的大数据并行计算时，需要使用完全分布式模式才能让并行计算顺利完成。也只有在完全分布式模式下，才能真正地发挥并行计算的效果。 小可：那什么是伪分布式呢？ Mr....更多精彩内容，敬请关注灯塔大数据，每周五不见不散呦！ 文章作者：王宏志 文章编辑：秦革
join 操作在数据库中还是非常常见的。 小可：这个 join 指的是笛卡儿积操作吗？ Mr. 王：还不一样，但是我们要从笛卡儿积说起。 先来回顾一下笛卡儿积操作。...在数据库中，数据的基本单位就是元组。比如在学生成绩的数据库中，表头是学号、学生姓名和成绩，那么元组就是、这样的。...王：在数据库系统的各种操作中，连接开销非常大，所需要的 CPU 资源和内存资源，甚至是保存中间结果的磁盘资源都是非常多的，于是我们产生了一个很自然的想法，就是做并行连接操作。...然后 Reducer 会从 Mapper 中读取桶，这些桶是落在同一个区间内的数据，接下来进行归并，相当于把两个表分别进行了一次归并排序。...内容来源：灯塔大数据
王：优先队列满足这样一个条件 ：优先队列中每个节点都有一个值，以任意顺序入优先队列的节点，会以值从小到大的顺序出队列。...优先队列的内部是一个堆，今天我们先不谈其内部实现，你只要知道优先队列的出队列顺序，与其值的大小有关，值小的先出队列，值大的后出队列，而不是入队列时的顺序就可以了。 Mr....，注意优先队列中的点，它们会按照第一个数据域“终节点的拓扑编号”进行排序，以便最后按照从小到大的顺序出队列。虽然(6,1,0) 是先入队列的，但是4 的值比它们小，所以(4,2,1)要排在前面。...由于这个数据量非常大，我们不得不把优先队列放在外存中。...内容来源：灯塔大数据
内容来源：灯塔大数据
在传统的关系型数据库查询中，自然连接或者等值连接都可以严格地通过判等进行连接，而当执行相似的或者模糊判等操作时，它的计算时间一定会比精确比较更慢。于是我们定义了以下问题。...问题：一对来自两个数据集的记录，如果它们的相似性超过一定的程度，那么它们应该被连接，相似度可以根据特定应用来定义。 现在你能不能试着对这个问题给出一个朴素的解法呢？...它的中转数据也是很大的，有 K(R+S)个。所以这个方法虽然正确，但是太耗时了。 在实际的计算中，我们可以根据表中记录所具有的一定性质，来使用一些更加聪明的办法，使问题的求解变得更加高效。...内容来源：灯塔大数据
王：外排序是相对内排序而言的，当要排序的数据量无法被全部装进内存时，我们就需要用到外排序，此时有大量的数据被存在硬盘里，无法直接进行操作，必须先以块为单位读进内存中。...对于一个比较大、复杂的问题，我们很难一下子将其解决，这时就尝试采用将大的问题逐渐划分为小的问题，这些小的问题叫作子问题，对于子问题，求解起来往往会变得容易一些。...根据排序的问题定义，按照从小到大的顺序排列，所以第一次我们希望能够找出序列中最小的那个数。...在现实生活中，需要排序的数据量有时候是很大的，当内存中无法容纳这么大的数据量时，我们就要尝试将这些数据存储在磁盘上，利用内存作为数据的暂存地进行排序。 小可：那么在外排序中，归并排序又该怎么做呢？...内容来源：灯塔大数据
接下来我们来讨论另一种磁盘中的大数据算法策略，叫作时间前向处理方法。在这种策略中，我会讲解求解最大独立集的方法。先介绍一个时间前向独立集的其他例子。 ? 这是一个DAG。...在课程网络图中，也经常会出现一些比较复杂的情况，比如两门课程同时是第三门课程的前置课程，如“ C 语言程序设计”和“计算机数学基础”这两门课程，都是“数据结构与算法”这门课程的前置课程。...比如学过了“计算机数学基础”和“ C 语言程序设计”，就可以学习“数据结构与算法”了，所以我们可以将加入了拓扑序列的那些节点的出度删除，然后这个节点也就没用了，同样删掉。...内容来源：灯塔大数据
No.10期 何谓大数据算法 Mr. 王：下面我们就来谈谈大数据算法与一般算法的区别和联系。 小可：好。 Mr....虽然有些算法是多项式算法，但是它的高阶项指数却是非常大的，导致当数据规模大起来时，它的增长速度会变得非常快。...对于大数据而言，访问全部数据是很费时的，所以大数据算法有时需要采取读取部分数据的办法，也就是设计时间亚线性算法。...而且数据往往在内存中也存不下，数据要存储在磁盘上，所以要考虑设计外存算法；或者是采取读取部分数据的办法，设计空间亚线性算法。...小可：亚线性算法有一种抽样的感觉，不访问全部数据，而是尝试选择部分数据来代表全部数据。 Mr. 王：没错。
在效用矩阵中，每一行是一个用户，每一列是一个项目，每一个数据记录着某个用户x ∈ X 对某个项目s ∈ S 的一个评分。比如下图：基于效用矩阵，我们提出效用函数的概念。...在实际应用中，就涉及如何去收集这个效 用矩阵 中数据的问题。 （2）根据已知的评分推断未知的评分。这是使用效用矩阵的关键，当效用矩阵中的数据已 经收集好之后，我们如何利用效用矩阵进行用户推荐。...一些新推出的项目是没有评分的，它们刚刚出现在平台上，用户还没来得及对它们进行评分；相应的，平台对于新用户的喜好也是认识不足的，因为平台中没有任何关于新用户的历史数据。这也是两个比较棘手的问题。...更多精彩内容，敬请关注灯塔大数据，每周五不见不散呦！ 文章作者：王宏志 文章编辑：秦革
此时MapReduce 平台会将键值相同的数据项目洗混到一起，最后将每个键值的数据交给一个 Reducer 去处理。...由于它进行的是一个合并操作，所以可以将具有相同键值的记录合并为一个，一大好处是减小了各台计算机之间的网络流量。...其次是“数据分布”，进行将过程移动到数据的工作。“同步”完成聚集、排序、打乱中间数据的工作。 当然不能忘了“错误处理”的工作，由于参加并行运算的计算机是很多的，中间会涉及大量的网络通信。...在使用并行系统时，由于涉及很多计算机之间的通信，而通信往往是多机系统的效率瓶颈之一所以我们应尽可能多地让数据在本地计算、本地合并、传输结果，而不是将未经处理的数据一一发送出去。...内容来源：灯塔大数据
小可：嗯，一共有24 个数据项，内存能装下8 个数据项，一个磁盘块包含2 个数据项。 也就是说，内存可以装下4 个磁盘块。 我们就以1 ～ 24 这组数字为例吧。...首先考虑：对整个数据集合进行一次浏览或者说扫描需要多少次I/O ？将内存用数据填满又需要多少次I/O ？ 小可：扫描对于磁盘而言是I/O 线性的，所以是N/B。...首先选出一个分界点，通过算法操作使得数组中左边的数都比它小，右边的数都比它大，然后对左边、右边分别执行这个步骤，不断地递归执行下去，就可以实现整个数组的排序了。...小可看了看写在纸上的数据，说：现在每一组都已经能够放入内存中了。所以对每一块用内存排序，就可以实现对整个数组的排序了。 Mr....内容来源：灯塔大数据
当我们要处理的数据量达到一定规模时，每个机架中会有几十台计算机参与到并行计算之中。 ?...更多精彩内容，敬请关注灯塔大数据，每周五不见不散呦！ 文章作者：王宏志 文章编辑：天天
但是有一个原则，那就是所有的边都要从ID 小的节点指向ID 大的节点。 有了DAG，我们就可以按照前面介绍的时间前向方法进行处理了。 对于这个图而言，首先我们访问序号最小的1 号节点。...这就是说，E 和 V 几乎是一样大的。所以应该是 O(sort(N))。 Mr. 王：没错。至于最大独立集至少有N/3 个节点，是因为在链表中，我们每选择一个节点，就会放弃其相邻的两个节点。...更多精彩内容，敬请关注灯塔大数据，每周五不见不散呦！ 内容来源：灯塔大数据
我们不得不设计磁盘算法，重要原因就是内存存不下特别大的图。 所以一些基本的考虑就是，我们能不能试着把图变得小一点，使之能被放进内存中。...王：我们来看这样一个问题：判定一个特别大的图的连通性。显然这个大图会被存储在外存中。 Mr. 王：首先我们试着给出一个半外存算法。 小可：这个“半外存”怎么解释呢？ Mr....小可：不过在实际情况中，也会有很多 |V|>M 的情况，对于那些真的大到连顶点都不能全放进内存中的图怎么办呢？ Mr. 王：嗯，接下来我们就谈一谈对一般情况怎么处理。...王：没错，比如新的顶点 A 和 B 之间的边，外存中保存的数据中并没有 A 和 B 顶点间的边，只有 ef 和 dc这样的边，所以还要有机制来记住 e、 f 这两个顶点之间的边，在下一轮迭代中，是 A、...内容来源：灯塔大数据
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
即时通信 IM
ICP备案
对象存储
实时音视频
