Posts

测试 如何知道自己的程序是否真的在工作？在现实世界中，程序员相信他们的代码，因为代码通过了他们自己编写的测试。常用的测试有 Ad Hoc Testing， Unit test 和 Integration Testing。 Ad Hoc Testing，是指没有计划和记录的软件测试，除非发现缺陷，不然一般只运行一次。 Unit test 程序可分解为单元（或程序中可测试的最小部分），Unit test 严格测试代码的每个单元，最终确保项目正确运行。 Unit test 好处： Unit test 保证良好的代码结构（每个 method “只打一份工”），帮助我们较好地解析任务， 允许我们考虑每个方法的所有边界情况，并单独测试它们。 让我们每次只专注于一个单元，进行测试，debug，对准确度有信心后，再进行下一个单元的开发。相比于一次性写完所有代码，再测试debug，Unit test 减少了 debugging 时间。 坏处： 测试也要花时间 测试本身也是有可能出错的，测试可能不全面，不规范，或者有bug 有些单元是依赖于其他单元的 Unit testing 无法保证各个模块的交互，无法保证整个系统作为一个整体是否正常工作。 JUnit JUnit是一个给Java做测试的框架，由Erich Gamma（Design Patterns）和Kent Beck（eXtreme Programming）编写。 JUnit使用Java的 reflection 功能（Java程序可以检查自己的代码）和注释。 JUnit允许我们： 定义并执行测试和测试套件 使用测试作为规范的有效手段 使用测试来支持重构 将修改的代码集成到构建中 JUnit可用于多个IDE，例如BlueJ，JBuilder和Eclipse在一定程度上具有JUnit集成。 import org.junit.Test; import static org.junit.Assert.*; @Test public void testMethod() { assertEquals(<expected>, <actual>); } assertEquals测试一个变量的实际值是否等于它的期望值。 JUnit test 各个测试方法，必须是非静态的（JUnit的设计人员设计规定的）。 ...

Java 提供了 ArrayList, ArrayDeque 和 LinkedList 几个API. 队列 queue, 通俗的含义, 就是不能插队, 只能在末尾插入. 双端队列 Double Ended Queue (Deque) 是具有动态大小的序列容器，可以在两端（前端或后端）扩展或收缩 –http://www.cplusplus.com/reference/deque/deque/ CS61b的project 1a需要实现两种双端队列（array based 和 linkedklist based）. 不同的API, 在考虑什么时候应该用哪个时, 我们需要考虑它们的性能差异: 搜索/定位：与LinkedList相比，ArrayList搜索更快。 ArrayList的get(int index)性能是O(1)的，而LinkedList的性能是O(n)。因为ArrayList基于array数据结构，可以直接用 array index 定位元素。 删除/插入：LinkedList 操作性能是O(1)，而ArrayList的性能从O(n)（删除/插入第一个元素）到O(n)（最后一个元素）都有可能。因为LinkedList的每个元素都包含两个指向其相邻前后元素的指针（地址），因此仅需要改变，被删节点的prev和next指针位置。而在ArrayList中，需要移动剩余元素，来重新填充array空间。 内存开销：LinkedList的每个元素都有更多的内存开销(额外的指针), 而ArrayLists没有这个开销。但是，ArrayLists需要占用初始容量。一般ArrayList的默认初始容量非常小（Java 1.4 - 1.8使用10）。但是，往ArrayLists添加元素时， 它可能会适当地增大容量，所以如果添加了很多元素，则必须不断调整数组的大小，那样也可能会导致元素频繁挪动位置。 综上所述： 如果在应用中需要频繁插入和删除，那么选择LinkedList。 假如一开始，就知道后面要添加大量元素，那就使用较高的初始容量来构造ArrayList。 大部分用例中, 相比LinkedList, 人们更偏爱ArrayList以及ArrayDeque。如果你不确定应该选哪个, 那么就直接考虑ArrayList吧(参考 https://stackoverflow.com/questions/322715/when-to-use-linkedlist-over-arraylist).

双向链表 Doubly Linked List 前面介绍过的单向链表有几个缺点. 第一个就是它的addLast操作非常慢。单向链表只有一个变量保存列表头的地址, 以及每个节点对后面节点的单向引用(链接). 对于很长的列表，addLast方法必须遍历整个列表, 直到找到列表末尾才能执行插入操作. 最直观的优化方案就是加个’车尾’ 这样我们就可以直接通过last.next引用末尾位置. 不过另一个问题并没有解决, 就是删除列表最后一项removeLast这个操作还是很慢。因为在目前的结构设计下, 我们需要先找到倒数第二项，然后将其下一个指针设置为null。而要找到倒数第二节点, 我们就得先找到倒数第三个节点…… 以此类推。也就是说，对于删除末尾的操作，还是要几乎遍历整个列表。 反方向的链接 基于前面单向链表构建双向链表, 一个比较有效的方法是额外为每个节点添加一个指向前面节点的链接 - 指针. public class OneNode { public OneNode prev; //指向前 public int item; public OneNode next; //指向后 } 增加这些额外的指针会导致额外的代码复杂度, 以及额外的内存开销, 这就是追求时间效率的代价. Sentinel 与尾节点 双向链表的一个设计初衷，就是为了解决单向链表针对列表末尾位置的操作效率不高的问题，除了sentinel和反方向的链接还不够，我们还需要一个节点（指针）能够直接帮我们定位到列表末端。可以考虑添加一个的尾节点last 这样的列表就可以支持O(1)复杂度的addLast,getLast 和 removeLast操作了。 循环双端队列 Circular double ended queue 上面的尾节点设计虽然没什么错误，但有点瑕疵：最后一个尾节点指针有时指向前哨节点，有时指向一个真正的节点。更好的方法是使双向链表首尾相连, 构成一个循环，即前后节点共享唯一的一个前哨节点。 这样的设计相对更整洁，更美观(主观上的), sentinel的prev就指向列表最后一个节点, sentinel的next指向列表第一个节点. ...

链表 Linked List 前面有介绍以array为基础搭建的列表，支持自动扩容, 各种插入，删除速度都很快. 这里再介绍另一种方案, 链表, 也可以实现列表自动扩容. 带链接的节点 链表的核心组成是带链接的节点, 每个节点就像火车车厢, 有钩子连接下一节车厢. 以int节点为例: public class IntNode { public int item; public IntNode next; public IntNode(int i, IntNode n) { item = i; next = n; } } next就是这个链接, 每一个节点就是其上一个节点的next. 使用嵌套类 这个节点作为一个相对独立的数据结构, 我们更希望让他单独作为一个类来维护. 再另外创建一个名为LinkedList的class与用户进行交互. 这样还有另一个好处就是提供一个命名为LinkedList的类给用户交互，用户更直观地知道自己是在调用链表。如果直接与node类交互，用户可能会困扰. 但同时考虑到这个node类只有LinkedList会调用，所以我们可以把node类嵌套进LinkedList中。 public class LinkedList<XXX> { private class OneNode { public XXX item; public OneNode next; public OneNode(XXX i, OneNode n) { item = i; next = n; } } private OneNode first; private int size; public LinkedList(XXX x) { first = new OneNode(x, null); size = 1; } //下面是各种方法... } 以上定义使用了泛型。声明OneNode实例first为私有变量, 是为了防止用户错误地摆弄链接指向，private和public的使用参考. ...

我学习CS历程，也包含基础知识的总结以及编程实现的整理。 每一阶段里面, 都有很多个性化选项, 仅供参考 入门 CS入门 学习编写(至少)一种面向对象编程语言(C ++，Java®，Python®) 测试你的代码 夯实基础 你可以跳过这些而直接进入下面的进阶实践环节，并根据自己需要查漏补缺。 但是这些都是非常重要的基础，任何时候，只要有时间，就可以去学习了解。 逻辑推理和离散数学 熟悉计算机操作系统 学习计算机网络 掌握数据库 了解编译器和优化 了解计算理论 学习其他编程语言 进阶与实践 深入了解算法和数据结构 分布式，并行和大数据 安卓开发 iOS开发 网页开发 加密与区块链 参与项目 English template 英文模板 CS入门 现在的入门课基本都是用Python语言。 计算机科学导论，优达学城 CS50x 哈佛，语言包括C，Python，SQL和JavaScript加CSS和HTML CMU 15213: Introduction to Computer Systems (ICS) 面向对象编程语言 一般而言，建议先学Java 或 Python，再学C++。 这三种语言都基本掌握后，再根据自身的职业需求，选择其中一个语言（或者其他语言）进一步深入练习。 面向初学者程序员的在线资源： 编程方法学，斯坦福CS106A，Java 伯克利大学CS 61A计算机程序的结构与解读，Python Java编程简介，MIT Google Python Class 面向有经验的程序员的在线资源： 数据结构，伯克利大学 CS 61B，Java 计算机程序设计，Udacity，Python 抽象编程，斯坦福 CS106B，C ++, 最新作业 http://web.stanford.edu/class/cs106b/ 《数据结构与算法分析:C++描述》, Mark A. Weiss 测试你的代码 了解如何捕获错误，创建测试和破解软件. ...

记录学习AI的学习笔记，内容包含基础知识的总结以及编程实现的整理。 English template 英文模板 机器学习 Coursera Machine Learning， 吴恩达的简化版机器学习 Machine Learning, 吴恩达的机器学习课程 这个比较深入 Deep Learning, 吴恩达的深度学习课程 Neural Networks for Machine Learning, Hinton的神经网络课程 深度学习 Deep learning, Coursera Machine Learning Practical: DNN, CNN, RNN 每个lab的答案在下一个lab 分支，即lab1的答案可以在lab2 branch里面看到。这个代码全部用Python class，比coursera的难度高点。 自然语言处理 自然语言处理, 斯坦福 加速自然语言处理, 爱丁堡大学 深度学习处理自然语言，斯坦福 计算机视觉 图像识别：卷积神经网络，李飞飞，斯坦福 机器人 机器人入门，斯坦福

列表 List 前面说到Java的数组无法更改长度，那么也就无法实现插入或者删除数组成员。Java提供了功能更丰富的数据结构 - 列表（list）。所谓列表，即有序的集合（序列），用户可以精确地控制每个元素插入到列表中的哪个位置。用户可以通过整数索引（列表中的位置）来访问元素，并搜索列表中的元素（详细可进一步参考oracle官网）。 这里我们尝试以java的array为基础实现一个列表，目标是实现自动扩容 (Java中的ArrayList不仅仅有自动扩容, 也继承了[List]的其他功能)。在探索的过程中, 可以顺带学习很多相关的内容. 使用自上而下的设计思想搭建一个框架: 先写出最基础的部分, 也就是一个构造器，前面学过了整数数组，我们直接拿来用 /** Array based list. */ // index 0 1 2 3 4 5 6 7 // items: [6 9 -1 2 0 0 0 0 ...] // size: 5 public class AList { private int[] items; private int size; /** 构造一个初始容量100的数组，初始有效数据成员为0. */ public AList() { items = new int[100]; size = 0; } /** 下面添加其他方法 */ } 然后思考我们需要什么功能，把功能需求转化为实例方法instance method的形式，先把方法的外壳描绘出来，注释上该方法的功能（目的），输入值，返回值是什么之类的。具体的功能实现可以先空着，之后一步步丰富。 ...

数组（Array） 数组是一种特殊的对象，有一个固定的数组长度参数N，由一连串（N个）连续的带编号的内存块组成，每个都是相同的类型(不像Python可以包含不同类型)，索引从0到N-1编号。A[i]获得数组A的第i个元素。这与普通的类实例不同，类实例有具体变量名命名的内存块。 数组实例化，包含对象的数组 Array Instantiation, Arrays of Objects 要创建最简单的整数数组, 有三种方式: x = new int [3]; //创建一个指定长度的数组，并用默认值（0）填充每个内存块。 y = new int [] {1，2，3，4，5}; //创建一个合适大小的数组，以容纳指定的初始值 int [] z = {9，10，11，12，13}; //省略了new，只能结合变量声明使用。 创建一组实例化对象: public class DogArrayDemo { public static void main(String[] args) { /* Create an array of two dogs. */ Dog[] dogs = new Dog[2]; dogs[0] = new Dog(8); dogs[1] = new Dog(20); /* Yipping will result, since dogs[0] has weight 8. */ dogs[0].makeNoise(); } } 注意到new有两种不同的使用方式：一种是创建一个可以容纳两个Dog对象的数组，另外两个创建各个实际的Dog实例。 ...

数据类型 数据类型是程序设计语言描述事物、对象的方法。Java数据类型分为基本类型（内置类型）和引用类型(扩展类型）两大类。基本类型就是Java语言本身提供的基本数据类型，比如，整型数，浮点数，字符，布尔值等等。而引用类型则是Java语言根据基本类型扩展出的其他类型，Java要求所有的引用扩展类型都必须包括在类定义里面，这就是Java为什么是面向对象编程语言的原因… 上面的定义有点抽象，要理解数据类型，需要先理解一个问题: 神秘的海象问题 尝试预测下面的代码运行时会发生什么。b的变化是否会影响a？提示：类似Python。 Walrus a = new Walrus(1000, 8.3); Walrus b; b = a; b.weight = 5; System.out.println(a); System.out.println(b); 同样尝试预测下面的代码运行时会发生什么。x的改变是否影响y？ int x = 5; int y; y = x; x = 2; System.out.println("x is: " + x); System.out.println("y is: " + y); 答案是b的变化会影响a, 但x的改变不影响y，具体见可视化过程. 这里的差别虽然微妙, 但其背后的原理对于数据结构的效率来说是非常重要的，对这个问题的深入理解也将引导我们写出更安全，更可靠的代码。 基本类型 Primative Types 计算机中的所有信息都以一系列1和0的形式存储在内存中，这些二进制的0和1就是比特位（bits）。比如72和“H”在内存一般以01001000的形式存储，对他们的形式是一样的。一个引申问题就是：Java代码如何解释01001000，怎么知道应该解释为72还是“H”？ 通过类型types，预先定义好类型即可, 以下代码 char x = 'H'; int y = x; System.out.println(x); System.out.println(y); 会分别得到“H”和72. 在这种情况下，x和y变量都包含几乎相同的bits，但是Java解释器在输出时对它们进行了不同的处理。 Java有8种基本类型：byte，short，int，long，float，double，boolean和char。 ...

嵌套类 我们经常需要在某个类A中使用另一个类B，如果设计时我们知道类B只有在类A中有被使用的可能性, 那么我们可以把类B定义在类A中, 作为类A的嵌套类, 类A就称之为外部类. 这样做可以隐藏类名，减少全局的标识符，从而限制用户能否使用该类建立对象。这样可以提高类的抽象能力，并且强调了两个类(外围类和嵌套类)之间的主从关系。 A nested class is any class whose declaration occurs within the body of another class or interface. A top level class is a class that is not a nested class. 嵌套类分为两类：静态和非静态。声明为static的嵌套类简称为静态嵌套类。非静态嵌套类称为内部类(inner class)。 class OuterClass { ... static class StaticNestedClass { ... } class InnerClass { ... } } 作为OuterClass的成员，嵌套类可以声明为private，public，protected或package private。外部类只能声明为public或package private。更多详情参考官网. 内部类 内部类可以直接访问外部类的方法和变量(即使是private的也可以)。如果从外部类程序代码中初始化内部类, 此内部对象会绑在该外部对象上. 一个内部类的实例作为成员存在于所属外部类的实例中。 public class Outer { private int outVar; class Inner { public int inVar; void go() { outVar += inVar; } } Inner myInner = new Inner(); public void do() { myInner.go(); } } public static void main(String[] args) { Outer O = new Outer(); Outer.Inner I = O.new Inner(); } 也可以从外部类之外的程序来初始化外部类的内部实例, 语法比较特殊 ...