Intro

工厂的本质是啥？可不可以理解根据客户的需求工厂生产对应的产品。

实际应用

JDK中的Executors类。

元数据

要了解注解前提要了解有关元数据的一些概念。

元数据是关于数据的数据。在编程语言上下文中，元数据是添加到程序元素如方法、字段、类和包上的额外信息。对数据进行说明描述的数据。

一般来说，元数据可以用于创建文档，跟踪代码中的依赖性，执行编译时检查，代码分析。

什么是注解

注解Annotation就是java平台的元数据，该机制允许在Java代码中添加自定义注释，并允许通过反射（Reflection），以编程方式访问元数据注释。通过提供为程序元素（类、方法等）附加额外数据的标准方法，元数据功能具有简化和改进许多应用程序开发领域的潜在能力，其中包括配置管理、框架实现和代码生成。

Annotations are primarily used by code that is inspecting other code. They are often used for modifying (i.e. decorating or wrapping) existing classes at run-time to change their behavior.

Annotations are meta-meta-objects which can be used to describe other meta-objects. Meta-objects are classes, fields and methods. Asking an object for its meta-object (e.g. anObj.getClass() ) is called introspection. The introspection can go further and we can ask a meta-object what are its annotations (e.g. aClass.getAnnotations). Introspection and annotations belong to what is called reflection and meta-programming.

注解需要以某种方式解释才能有用。注解可是在开发时由IDE或编译器解释，也可以在运行时由框架解释。

工具是运用知识处理数据的手段。

JDK的命令行工具

jps：虚拟机进程状况工具

可以列出正在运行的虚拟机进程，并显示虚拟机执行主类（Main Class，main()函数所在的类）的名称，以及这些进程的本地虚拟机的唯一ID（LVMID，Local Virtual Machine Identifier）。

对于本地虚拟机进程来说，LVMID与操作系统的进程ID（PID，Process Identifier）是一致的。

​ The jps command supports a number of options that modify the output of the command. These options are subject to change or removal in the future.

​ -q Suppress the output of the class name, JAR file name, and arguments passed to the main method, producing only a list of local VM identifiers.

​ -m Output the arguments passed to the main method. The output may be null for embedded JVMs.

​ -l Output the full package name for the application’s main class or the full path name to the application’s JAR file.

​ -v Output the arguments passed to the JVM.

​ -V Output the arguments passed to the JVM through the flags file (the .hotspotrc file or the file specified by the -XX:Flags=argument).

​ -Joption Pass option to the java launcher called by javac. For example, -J-Xms48m sets the startup memory to 48 megabytes. It is a common convention for -J to pass options to the underlying VM executing applications written in Java.

简介

链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存在下一个的指针(Pointer)。

链表是一组数据项的集合，其中每个数据项都是一个节点的一部分，每个节点都包含指向下一个节点的链接。

由于不需要按照顺序存储，链表在插入的时候可以达到O(1)的复杂度。所以比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而顺序表相应的时间复杂度分别为O(logn)和O(1).

使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。

链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的访问往往要在不同的排列顺序中转换。而链表是一种自我指示数据类型，因为它包含指向另一个相同类型的数据的指针。链表允许插入和移除表上任意位置上的结点，但是不允许随机存取。

删除节点x后的下一节点使用的语句是：

1

x->next = x->next->next;

把节点t插入链表中节点x后的下一位置，我们使用语句：

1

t->next = x->next; x->next=t;

约瑟夫问题

假设有N个人决定选出一个领导人，方法如下：所有人排成一个圆圈，按顺序数数，每隔第M的人出局，此时，他两边的人靠拢重新形成圆圈。问题是找出哪一个人将会是最后剩下的那个人。所选出的领导人的号码是一个N和M的函数，我们称之为约瑟夫函数（Jesephus function）。更为一般地，我们希望知道所有人出局的顺序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

#include <stdlib.h>
typedef struct node* link;
struct node {int item; link next;};
main(int argc, char *argv[])
{
    int i, N = atoi(argv[1]), M = atoi(argv[2]);
    link t = malloc(sizeof *t), x=t;
    t->item = 1; t->next = t;
    for (i = 2; i <= N; i++)
    {
        x = (x->next = malloc(sizeof *x));
        x->item = i; x->next = t;
    }
    while (x != x->next)
    {
        for (i = 1; i < M; i++) x = x->next;
        x->next = x->next->next;N--;
    }
    printf("%d\n", x->item);
}

链表有很多种不同的类型：单向链表，双向链表以及循环链表。

Intro

A context switch (also sometimes referred to as a process switch or a task switch) is the switching of the CPU (central processing unit) from one process or thread to another.

Context switch过高会导致CPU像个搬运工，频繁在寄存器和运行队列之间奔波，更多的时间花在了线程切换，而不是真正工作的线程上。直接的消耗包括CPU寄存器需要保存和加载，系统调度器的代码需要执行。间接消耗在于多核cache之间的共享数据。

A process (also sometimes referred to as a task) is an executing (i.e., running) instance of a program. In Linux, threads are lightweight processes that can run in parallel and share an address space (i.e., a range of memory locations) and other resources with their parent processes (i.e., the processes that created them).

A context is the contents of a CPU’s registers and program counter at any point in time. A register is a small amount of very fast memory inside of a CPU (as opposed to the slower RAM main memory outside of the CPU) that is used to speed the execution of computer programs by providing quick access to commonly used values, generally those in the midst of a calculation. A program counter is a specialized register that indicates the position of the CPU in its instruction sequence and which holds either the address of the instruction being executed or the address of the next instruction to be executed, depending on the specific system.

编写高校程序需要几类活动：第一，我们必须选择一组合适的算法和数据结构。第二，我们必须编写出编译器能够有效优化以转换成高效可执行代码的源代码。第三、针对处理运算量特别大的计算，将一个任务分成多个部分，这些部分可以在多核和多处理器的某种组合上并行地计算。

程序优化步骤：

• 消除不必要的内容，让代码尽可能有效地执行它期望的工作。这包括消除不必要的函数调用、条件测试和存储器引用。这些优化不依赖于目标机器的任何具体属性
• 利用处理器提供的指令级并行（instruction-level parallelism）能力，同时执行多条指令。

优化编译器的能力和局限性

• 两个指针可能指向同一个存储器位置的情况称为存储器别名使用（memory aliasing）
• 函数调用

表示程序性能

度量标准每元素的周期数（Cycles Per Element, CPE）作为一种表示程序性能并指导我们改进代码的方法。
处理器活动的顺序是由时钟控制的，时钟提供了某个频率的规律信号，通常用千兆赫兹（GHz）,即十亿周期每秒来表示。

什么是最小乘方拟合？

对于一个数据点$$（x_1,y_1）…(x_n,y_n)$$的集合，我们常常试图画一条线，它能最接近于这些数据代表的X-Y趋势。使得最小二乘方拟合，寻找一条形如y=mx+b的线，使得下面的这个误差度量最小：

$$E(m, b) = \Sigma(mx_i+b-y_i)^{2}$$

将E(m,b)分别对m和b求导，把两个导数函数设置为0，进行推导就能得出计算m和b的算法。

程序示例

消除循环的低效率

• 代码移动（code motion）这类优化包括识别要执行多次但是计算结果不会改变的计算。因此可以将计算移动到代码前面不会被多次求值的部分。

隐藏的渐近低效率（asymptotic inefficiency）
例子循环使用strlen判断字符串长度的问题。

管理网络中跨多台计算机存储的文件系统称为分布式文件系统（distributed filesystem）。Hadoop有一个称为HDFS的分布式系统，即Hadoop Distributed Filesystem。

HDFS的设计

HDFS以流式数据访问模式来存储超大文件，运行于商用硬件集群上。

• 超大文件
• 流式数据访问 HDFS的构建思路是这样的：一次写入、多次读取是最高效的访问模式。
• 商用硬件
• 低时间延迟的数据访问
• 大量的小文件
• 多用户写入，任意修改文件

HDFS的概念

初识Hadoop

『大数据胜于好算法。』

为什么不能用数据库来对大量硬盘上的大规模数据进行批量分析呢？我们为什么需要MapReduce?

这两个问题的答案来自于计算机硬盘的另一个发展趋势：寻址时间的提升远远不敌于传输速率的提升。寻址是将磁头移动到特定硬盘位置进行读写操作的过程。它是导致硬盘操作延迟的主要原因，而传输速率取决于硬盘的带宽。

如果数据访问模式中包含大量的硬盘寻址，那么读取大量数据集就必然会花更长的时间。另一方面，如果数据库系统只更新一小部分记录，那么传统的B树就更有优势。但数据库系统如果有大量数据更新时，B树的效率就明显落后于MapReduce，因为需要使用”排序/合并”（sort/merge）来重建数据库。

MapReduce比较适合以批处理方式处理需要分析整个数据集的问题，尤其是动态分析。RDBMS适用于点查询和更新，数据集被索引之后，数据库系统能够提供低延迟的数据检索和快速的少量数据更新。MapReduce适合一次写入、多次读取数据的应用，关系型数据库则更适合持续更新的数据集。

基于两种相关的机器语言：Intel IA32 和 x86-64。

32位机器只能使用大概 4GB (2^32字节) 的随机访问存储器（即内存），而目前64位机器能够使用多达 256TB（2^48字节）的内存空间。

Intel 处理器系列俗称 x86, 经历了一个长期的、不断进化的发展过程。

Linux 使用了平坦寻址方式（flat addressing）。

对于机器级编程来说，其中两种抽象尤为重要。第一种是机器级程序的格式和行为，定义为指令集体系结构（Instrucion set architecture，ISA），它定义了处理器状态、指令的格式，以及每条指令对状态的影响。第二种抽象是，机器级程序使用的存储器地址是虚拟地址，提供的存储器模型是一个非常大的字节数组。

IA32 机器代码和原始的C代码差别非常大。一些通常对C语言程序猿隐蔽的处理器状态是可见的：

• 程序计数器（在 IA32 中，通常称为“PC”，用%eip表示）指示将要执行的下一条指令在存储器中的地址。
• 整数寄存器文件包含8个命名的位置，分别存储32位的值。这些寄存器可以存储地址（对英语C语言的指针）或整数数据。有的寄存器被用来记录某些重要的程序状态，而其他的寄存器则用来保存临时数据，例如过程的局部变量和函数的返回值。
• 条件码寄存去保存着最近执行的算数或逻辑指令的状态信息。它们用来实现控制或数据流中的变化，比如说用来实现if和while语句。
• 一组浮点寄存器存放浮点数据。

程序存储器（program momery）包含：程序的可执行机器代码，操作系统需要的一些信息，用来管理过程调用和返回的运行时栈，以及用户分配的存储器块（比如malloc库函数分配的）。

三种最重要的数字表示：

1. 无符号（unsigned）编码基于传统的二进制表示法，表示大于或者等于0的数字。

2. 补码（two’s-complement）编码是表示有符号整数的最常见的方式，有符号整数就是可以为正或者为负的数字。

3. 浮点数（floating-point）编码是表示实数的科学记数法的以二为基数的版本。

计算机的表示法是用有限数量的位来对一个数字编码，因此，当结果太大以致不能表示时，某些运算就会溢出（overflow）。

在C语言中，以0x或者0X开头的数字常量被认为是十六进制的值。

十进制和十六进制表示之间的转换需要使用乘法或者除法来处理一般情况。将一个十进制数x转换为十六进制，可以反复地用16除x，得到一个商q和一个余数r，也就是x=qx16+r。然后，我们用十六进制数字表示的r作为最低位数字，并且通过对q反复进行这个过程得到剩下的数字。

反过来，将一个十六进制数字转换为十进制数字，我们用相应的16的幂乘以每个十六进制数字。

1
2
3
4
5
6

#!/usr/bin/env perl
#Convert list of decimal numbers into hex

for($i = 0; $i < @ARGV; $i++){
	printf("%d\t=0x%x\n", $ARGV[$i], $ARGV[$i]);
}