大四了，以后做作业的次数也越来越少了。最近很多课程都到尾声了，都要交作业了，忙碌了两个星期，今天算是把这些课程的作业做好了。

我的大四的课程如下：

1. 《传感网与物联网》
2. 《数据挖掘》
3. 《算法与数据结构高级课程》
4. 《虚拟化与云计算》

不得不承认这些课程的名字太大了，搞的好像确实挺牛的。其实老师只是把书本过一遍而已，浅尝辄止，不会很深入。因为没必要，很多人都没去上课，包括我在内，我只是上了5节以内的课。以前确实对课内的知识不是很重视，不是说它不好，学校这么多年的课程安排肯定有它的意义，只是觉得自己学得东西有时候太泛了反而不是很好，毕竟自己要有自己的核心竞争力。

但是这次不知道是哪股劲，把我最讨厌的算法都很认真的用键盘把它敲出来，还有就是用的是我也不怎么喜欢的C语言(因为老师规定只能用C来编写程序)。不过可能是我本身的C语言环境配置得不是很好，导致比如一些常规的调试，断点调试都不能用，这样子的话就只能看结果来猜一下自己的代码出现的问题。

下面简单回顾下这两周做的成果吧

《传感网与物联网》

这个要做的是PPT，介绍你对物联网的了解，然后随机抽取人上讲台去介绍。很不幸，我中枪了，我也不知道为什么老师要选我。我介绍的是小米手环的物联网应用，确实这个是自己的PPT处女作，做的还是挺垃圾的。不过在收集整理资料的时候还是有收获的。还是比较更深一层了解了物联网，它是基于互联网之上的，很多企业都涉及到物联网。物物相连，让物体能"说话"，这个是我给它的一个定义。

具体的PPT可以看 小米手环之物联网。(温馨提示：这个需要翻墙才可以看到，对，我就是那么任性)

《算法与数据结构高级课程》

看到这个课程题目当时吓我一跳，完全不知道当初为什么会选这门课的！考核内容，考核内容就是你要在固定的章节中挑一些题目来做，总共有5道。我选了以下的5道，不过说真的就只有3道，因为一道没用到真正的数据结构，一道知道原理，但是因为时间比较赶，所以只能抄别人的(嘘！一般人我不告诉他)

• 1. 最接近的数(双向链表)

  问题描述：给一个n个元素的线性表A，对于每个数Ai，找到它之前的数中，和它最接近的数。即对于每一个i，计算
  Ci = min{| Ai - Aj ||1 <= j < i }规定 C1 = 0, A = {2, 6, 5, 10, 4, 7}, C = {0, 4, 1, 4, 1, 1}

  算法分析：先把A集合中的元素排序，构建双向链表。依次计算C6，C5，C4....
  计算Ci只需要比较左右两个元素，然后删除掉Ai。删除掉Ai主要原因是，举个例子A6是没出现在A5之前的。

  代码: 最接近的数(注意需要翻墙)

• 2. 序列和的前n小元素(二叉堆)

  问题描述：给出两个长度为n的有序表A和B，在A和B中各任取一个元素，可以得到n^2个和，求这些和中最小的n个

  算法分析：看成n个有序表
  A[0] + B[0] <= A[0] + B[1] <= A[0] + B[2] <= ... <= A[0] + B[n-1]
  A[1] + B[0] <= A[1] + B[1] <= A[1] + B[2] <= ... <= A[1] + B[n-1]
  A[n-1] + B[0] <= A[n-1] + B[1] <= ... <= A[n-1] + B[n-1]
  拿出每个有序表的首元素，用小顶堆维护。每次拿出最小元素，并放进对应的有序表的下一个元素。

  测试用例：A {1, 2, 5} B {2, 4, 7}
  输出的结果为 {3, 4, 5}

  代码: 序列和的前n小元素(注意需要翻墙)

• 3. 逆序对(树状数组)

  问题描述：设 A[1. ..n] 是一个包含n个不同数的数组。如果 i A[j]，则（i,j）称为A中的一个逆序对。现给出一个 长度为n的 数列，求该数列中的逆序对数(逆序数)

  算法分析：先将数据列离散化，使得数据紧密。通过树状数组的特性来操作数据集。每插入一个数，统计比它小的数的个数，对应的逆序个数为 i - getsum( discreted[i] ),这里的discreted数组为下面的 {5, 2, 1, 4, 3},i 指的是当前已经插入的数的个数，getsum(discreted[i])指的是比discreted[i](刚插入的值)小的个数。假设用tree这个数组还作为树状数组.

  1. 输入5, 调用update(5, 1),tree为{0, 0, 0, 0, 1},getsum(5) = 1,i = 1,所以对于5来说它的逆序对为0
  2. 再输入2, 调用update(2, 1), tree为{0, 1, 0, 0, 1},getsum(2) = 1,i = 2,所以对2来说它的逆序对为1
  3. 一直循环下去可以知道，1的逆序对为2, 4的逆序对为1, 3的逆序对为2
  4. 0 + 1 + 2 + 1 + 2 = 6, 所以加起来就是为6

  测试用例：{9, 1, 0, 5, 4}, 离散后的 {5, 2, 1, 4, 3}
  输出结果为 6

  代码: 逆序对(注意需要翻墙)

《虚拟化与云计算》

这个只能略了，随便弄了份报告就交了，因为它要实验的，但是我都没去上过，所以这个只能copy别人的。

《数据挖掘》

当时老师有给我们选择，你可以写程序和考试，那时候我就果断选些程序呀(因为我手头有一份，不过最后没用，因为是用java的)。因为后来我想了想如果是考试的话，我一定是应付任务去看书的，但是不一定有写程序那么好玩，我觉得大学一些课程用考试的形式让我把我之前临时抱佛脚读的东西都还给老师了。我倒不如自己写一些程序来巩固下我的前端知识，有了这个想法，我就不用我跟同学拿到的程序了。

我选择的题目是ID3决策树，是用数据生成一棵决策树，然后再用其他数据预测结果，来看预测结果与真实结果的差距。

1. 决策树的概念

是一种树型结构，包括了决策节点，分支和叶子节点三个部分。决策节点是信息增益最大的一个属性，分支是该属性对应的不同值，叶子节点表示的是一种可能的分类结果。具体可以参考蒋盛益老师的《数据挖掘原理与实践》P51

2. ID3算法

ID3是找出每一个样本集的信息增益最大的一个属性作为节点，并用它对应的不同值作为分支，并且递归下去，直到只有叶子节点(样本集同属于一个类别)。

其实很多都是套用公式的，还不是很清楚他们的原理是什么的。就只知道了信息熵越大，样本集就越混乱。

3. 具体实现

在刚开始做的时候，我就在想怎么把一个树渲染出来，之前想着用SVG、canvas，但是因为不是很熟，就没用了，而Ext的treepanel不适合这个场景。经过一番的搜索之后，我用了一个基于d3的库叫做mermaid.js，就像在写markdown语法那样子。还有就是一些数据，是需要用来展示的，我用了Ext的gridpanel，并在它的基础上修改了一些样式，使得界面更加绚丽多彩，而不是只有一种淡蓝色。整个项目是基于grunt的构建的，使用了browserify的模块化功能。具体代码可以看monkindey‘s decision tree

一些体会

1. 考试不如做东西出来

确实就像刚才我写的，考完试很多东西都还给了老师，分数就在那里，不增不减。但是你做东西的话，可能你在解决问题的道路上走了一遍。至少你提高你的动手能力，有理论知识没用的，等你动手的时候，你才知道你写的程序有这么多bug！特别是用C来写，各种指针bug。

2. 数据结构可以使问题变得更简单

确实看到了自己在算法、数据结构上的不足。可能在以往的编程中很少用到，所以之前学的排序、查找算法都忘了。在这里不得不佩服那些想出这些算法和数据结构的牛人。这次我站上巨人的肩膀上，我体会了下数据结构，确实该学。虽然我现在还不能学到活学活用，但是我至少体会了一番，不同的数据结构对应不同的解决方案，问题变得更简单了。

3. browserify体会

browserify让整个项目都可以用nodejs的模块化思想。确实在编写的时候思路很清晰，这个模块该暴露什么接口等等，但是也存在一些弊端，在调试的时候，你需要用grunt watch去监听你的js，因为browserify它是把你require的js文件打包成一个js,你只能用watch帮你自动打包，这样子的话，有时候改了段代码，要在浏览器上调试，但是watch有时候会延迟执行，导致看不出改了跟没改的一样，其实不是一样，只是watch还正在把之前的代码打包。