第1章  引言 1
1.1  异构并行计算 2
1.2  现代GPU的体系结构 6
1.3  为什么需要更高的速度和并行化 8
1.4  应用程序的加速 9
1.5  并行编程语言和模型 11
1.6  本书的总体目标 12
1.7  本书的组织结构 13
参考文献 16
第2章  GPU计算的发展历程 19
2.1  图形流水线的发展 19
2.1.1  固定功能的图形流水线时代 20
2.1.2  可编程实时图形流水线的发展 23
2.1.3  图形与计算结合的处理器 25
2.2  GPGPU：一个中间步骤 27
2.3  GPU计算 28
2.3.1  可扩展的GPU 29
2.3.2  发展近况 29
2.3.3  未来发展趋势 30
参考文献与课外阅读 30
第3章  CUDA简介 35
3.1  数据并行性 36
3.2  CUDA的程序结构 37
3.3  向量加法kernel函数 39
3.4  设备全局存储器与数据传输 41
3.5  kernel函数与线程 46
3.6  小结 50
3.6.1  函数声明 50
3.6.2  启动kernel函数 50
3.6.3  预定义变量 51
3.6.4  运行时API 51
3.7  习题 51
参考文献 53
第4章  数据并行执行模型 55
4.1  CUDA的线程组织 56
4.2  线程与多维数据的映射 59
4.3  矩阵乘法——一个更加复杂的kernel函数 65
4.4  线程同步和透明的可扩展性 70
4.5  线程块的资源分配 73
4.6  查询设备属性 74
4.7  线程调度和容许时延 75
4.8  小结 78
4.9  习题 79
第5章  CUDA存储器 81
5.1  存储器访问效率的重要性 82
5.2  CUDA设备存储器的类型 83
5.3  减少全局存储器流量的一种策略 89
5.4  分块矩阵乘法的kernel函数 93
5.5  存储器——限制并行性的一个因素 98
5.6  小结 100
5.7  习题 101
第6章  性能优化 103
6.1  WARP和线程执行 104
6.2  全局存储器的带宽 111
6.3  执行资源的动态划分 118
6.4  指令混合和线程粒度 120
6.5  小结 121
6.6  习题 121
参考文献 124
第7章  浮点运算 127
7.1  浮点格式 128
7.1.1  M的规范化表示 128
7.1.2  E的余码表示 129
7.2  能表示的数 130
7.3  特殊的位模式与IEEE格式中的精度 134
7.4  算术运算的准确度和舍入 135
7.5  算法的优化 136
7.6  数值稳定性 137
7.7  小结 141
7.8  习题 141
参考文献 142
第8章  并行模式：卷积 143
8.1  背景 144
8.2  一个基本算法：一维并行卷积 148
8.3  常数存储器和高速缓存 149
8.4  使用光环元素的分块一维卷积 153
8.5  一个更简单的分块一维卷积——通用高速缓存 158
8.6  小结 160
8.7  习题 161
第9章  并行模式：前缀和 163
9.1  背景 164
9.2  简单并行扫描 165
9.3  考虑工作效率 169
9.4  工作高效的并行扫描 170
9.5  任意输入长度的并行扫描 174
9.6  小结 177
9.7  习题 177
参考文献 178
第10章  并行模式：稀疏矩阵-向量乘法 179
10.1  背景 180
10.2  使用CSR格式的并行SpMV 183
10.3  填充与转置 184
10.4  用混合方法来控制填充 186
10.5  通过排序和划分来规则化 189
10.6  小结 191
10.7  习题 191
参考文献 192
第11章  应用案例研究：高级MRI重构 193
11.1  应用背景 194
11.2  迭代重构 197
11.3  计算FHD 198
11.4  最终评估 214
11.5  习题 217
参考文献 218
第12章  应用案例研究：分子可视化和分析 219
12.1  应用背景 220
12.2  kernel函数简单的实现方案 221
12.3  线程粒度调节 225
12.4  存储器合并 227
12.5  小结 230
12.6  习题 231
参考文献 232
第13章  并行编程和计算思想 233
13.1  并行计算的目标 234
13.2  问题分解 235
13.3  算法选择 238
13.4  计算思想 243
13.5  小结 244
13.6  习题 244
参考文献 244
第14章  OpenCL简介 245
14.1  背景 246
14.2  数据并行性模型 247
14.3  设备的体系结构 249
14.4  kernel函数 250
14.5  设备管理和启动kernel 251
14.6  OpenCL中的静电势图谱 254
14.7  小结 258
14.8  习题 258
参考文献 259
第15章  OpenACC并行编程 261
15.1  OpenACC与CUDA C的比较 261
15.2  执行模型 263
15.3  存储器模型 265
15.4  基本的OpenACC程序 266
15.4.1  并行构造 266
15.4.2  循环构造 267
15.4.3  kernels构造 272
15.4.4  数据管理 275
15.4.5  数据构造 276
15.4.6  异步计算和数据传输 278
15.5  OpenACC的发展方向 279
15.6  习题 280
第16章  Thrust：一个面向效率的CUDA编程库 281
16.1  背景简介 282
16.2  动机 284
16.3  Thrust的基本特性 284
16.3.1  迭代器和内存空间 286
16.3.2  互操作性 286
16.4  泛型编程 288
16.5  抽象的益处 290
16.5.1  编程效率 290
16.5.2  鲁棒性 291
16.5.3  真实性能 291
16.6  最佳范例 293
16.6.1  融合 293
16.6.2  数组结构体 294
16.6.3  隐式范围 296
16.7  习题 297
参考文献 298
第17章  CUDA FORTRAN 299
17.1  CUDA FORTRAN和CUDA C的区别 300
17.2  第一个CUDA FORTRAN程序 301
17.3  CUDA FORTRAN中的多维数组 303
17.4  用通用接口重载主机/设备端例程 304
17.5  通过iso_c_binding调用CUDA C 307
17.6  kernel循环指令和归约操作 309
17.7  动态共享存储器 310
17.8  异步数据传输 311
17.9  编译和性能剖析 316
17.10  在CUDA FORTRAN中调用Thrust 317
17.11  习题 321
第18章  C++ AMP简介 323
18.1  C++ AMP核心特性 324
18.2  C++ AMP执行模式详解 329
18.2.1  显式和隐式的数据复制 330
18.2.2  异步操作 331
18.2.3  本节小结 333
18.3  加速器管理 333
18.4  分块执行 335
18.5  C++ AMP图形特性 338
18.6  小结 340
18.7  习题 341
第19章  异构集群编程 343
19.1  背景简介 344
19.2  运行示例 344
19.3  MPI基础 346
19.4  MPI点对点通信模型 348
19.5  重叠计算和通信 355
19.6  MPI集合通信模型 362
19.7  小结 363
19.8  习题 363
参考文献 364
第20章  CUDA动态并行 365
20.1  背景 366
20.2  动态并行简介 367
20.3  重要细节 368
20.3.1  启动环境变量设置 369
20.3.2  API错误和启动失败 369
20.3.3  事件 369
20.3.4  流 369
20.3.5  同步范围 370
20.4  内存可见性 371
20.4.1  全局内存 371
20.4.2  零拷贝内存 371
20.4.3  常量内存 371
20.4.4  局部内存 371
20.4.5  共享内存 372
20.4.6  纹理内存 372
20.5  一个简单示例 373
20.6  运行时限制 376
20.6.1  内存占用 376
20.6.2  嵌套深度 376
20.6.3  内存分配和生存周期 376
20.6.4  ECC错误 377
20.6.5  流 377
20.6.6  事件 377
20.6.7  启动池 377
20.7  一个更复杂的示例 378
20.7.1  线性贝塞尔曲线 378
20.7.2  二次贝塞尔曲线 378
20.7.3  贝塞尔曲线计算(非动态并行版本) 378
20.7.4  贝塞尔曲线计算(使用动态并行) 381
20.8  小结 384
参考文献 384
第21章  结论与展望 385
21.1  重点回顾 385
21.2  存储器模型的演变 386
21.2.1  大型虚拟和物理地址空间 386
21.2.2  统一的设备存储空间 388
21.2.3  可配置的缓存和暂时存储器 388
21.2.4  提高原子操作的速度 389
21.2.5  提高全局内存的访问速度 389
21.3  kernel函数执行控制过程的演变 389
21.3.1  kernel函数内部的函数调用 389
21.3.2  kernel函数中的异常处理 390
21.3.3  多个kernel函数的同步执行 390
21.3.4  可中断的kernel函数 391
21.4  内核的性能 391
21.4.1  双精度的速度 391
21.4.2  更好的控制流效率 392
21.5  编程环境 392
21.6  美好前景 392
参考文献 393
附录A  矩阵乘法主机版的源代码 395
附录B  GPU的计算能力 407

第1章 绪论 1
1.1 大数据处理 1
1.1.1 数据的价值 2
1.1.2 受众较少 2
1.1.3 一种不同的方法 4
1.1.4 Hadoop 7
1.2 基于Amazon Web Services的云计算 12
1.2.1 云太多了 12
1.2.2 第三种方法 12
1.2.3 不同类型的成本 12
1.2.4 AWS：Amazon的弹性架构 13
1.2.5 本书内容 14
1.3 小结 15
第2章 安装并运行Hadoop 16
2.1 基于本地Ubuntu主机的Hadoop系统 16
2.2 实践环节：检查是否已安装JDK 17
2.3 实践环节：下载Hadoop 18
2.4 实践环节：安装SSH 19
2.5 实践环节：使用Hadoop计算圆周率 20
2.6 实践环节：配置伪分布式模式 22
2.7 实践环节：修改HDFS的根目录 24
2.8 实践环节：格式化NameNode 25
2.9 实践环节：启动Hadoop 26
2.10 实践环节：使用HDFS 27
2.11 实践环节：MapReduce的经典入门程序——字数统计 28
2.12 使用弹性MapReduce 33
2.13 实践环节：使用管理控制台在EMR运行WordCount 34
2.13.1 使用EMR的其他方式 41
2.13.2 AWS生态系统 42
2.14 本地Hadoop与EMRHadoop的对比 42
2.15 小结 43
第3章 理解MapReduce 44
3.1 键值对 44
3.1.1 具体含义 44
3.1.2 为什么采用键／值数据 45
3.1.3 MapReduce作为一系列键／值变换 46
3.2 MapReduce的HadoopJavaAPI 47
3.3 编写MapReduce程序 50
3.4 实践环节：设置classpath 50
3.5 实践环节：实现WordCount 51
3.6 实践环节：构建JAR文件 53
3.7 实践环节：在本地Hadoop集群运行WordCount 54
3.8 实践环节：在EMR上运行WordCount 54
3.8.1 0.20之前版本的JavaMapReduceAPI 56
3.8.2 Hadoop提供的mapper和reducer实现 57
3.9 实践环节：WordCount的简易方法 58
3.10 查看WordCount的运行全貌 59
3.10.1 启动 59
3.10.2 将输入分块 59
3.10.3 任务分配 60
3.10.4 任务启动 60
3.10.5 不断监视JobTracker 60
3.10.6 mapper的输入 61
3.10.7 mapper的执行 61
3.10.8 mapper的输出和reducer的输入 61
3.10.9 分块 62
3.10.10 可选分块函数 62
3.10.11 reducer类的输入 62
3.10.12 reducer类的执行 63
3.10.13 reducer类的输出 63
3.10.14 关机 63
3.10.15 这就是MapReduce的全部 64
3.10.16 也许缺了combiner 64
3.11 实践环节：使用combiner编写WordCount 64
3.12 实践环节：更正使用combiner的WordCount 65
3.13 Hadoop专有数据类型 67
3.13.1 Writable和Writable—Comparable接口 67
3.13.2 wrapper类介绍 68
3.14 实践环节：使用Writable包装类 69
3.15 输入／输出 71
3.15.1 文件、split和记录 71
3.15.2 InputFormat和RecordReader 71
3.15.3 Hadoop提供的InputFormat 72
3.15.4 Hadoop提供的RecordReader 73
3.15.5 OutputFormat和Record—Writer 73
3.15.6 Hadoop提供的OutputFormat 73
3.15.7 别忘了Sequencefiles 74
3.16 小结 74
第4章 开发MapReduce程序 75
4.1 使用非Java语言操作Hadoop 75
4.1.1 HadoopStreaming工作原理 76
4.1.2 使用HadoopStreaming的原因 76
4.2 实践环节：使用Streaming实现Word—Count 76
4.3 分析大数据集 79
4.3.1 获取UFO目击事件数据集 79
4.3.2 了解数据集 80
4.4 实践环节：统计汇总UFO数据 80
4.5 实践环节：统计形状数据 82
4.6 实践环节：找出目击事件的持续时间与UFO形状的关系 84
4.7 实践环节：在命令行中执行形状／时间分析 87
4.8 实践环节：使用ChainMapper进行字段验证／分析 88
4.9 实践环节：使用DistributedCache改进地点输出 93
4.10 计数器、状态和其他输出 96
4.11 实践环节：创建计数器、任务状态和写入日志 96
4.12 小结 102
第5章 高级MapReduce技术 103
5.1 初级、高级还是中级 103
5.2 多数据源联结 103
5.2.1 不适合执行联结操作的情况 104
5.2.2 map端联结与reduce端联结的对比 104
5.2.3 匹配账户与销售信息 105
5.3 实践环节：使用MultipleInputs实现reduce端联结 105
5.3.1 实现map端联结 109
5.3.2 是否进行联结 112
5.4 图算法 112
5.4.1 Graph101 112
5.4.2 图和MapReduce 112
5.4.3 图的表示方法 113
5.5 实践环节：图的表示 114
5.6 实践环节：创建源代码 115
5.7 实践环节：第一次运行作业 119
5.8 实践环节：第二次运行作业 120
5.9 实践环节：第三次运行作业 121
5.10 实践环节：第四次也是最后一次运行作业 122
5.10.1 运行多个作业 124
5.10.2 关于图的终极思考 124
5.11 使用语言无关的数据结构 124
5.11.1 候选技术 124
5.11.2 Avro简介 125
5.12 实践环节：获取并安装Avro 125
5.13 实践环节：定义模式 126
5.14 实践环节：使用Ruby创建Avro源数据 127
5.15 实践环节：使用Java语言编程操作Avro数据 128
5.16 实践环节：在MapReduce中统计UFO形状 130
5.17 实践环节：使用Ruby检查输出数据 134
5.18 实践环节：使用Java检查输出数据 135
5.19 小结 137
第6章 故障处理 138
6.1 故障 138
6.1.1 拥抱故障 138
6.1.2 至少不怕出现故障 139
6.1.3 严禁模仿 139
6.1.4 故障类型 139
6.1.5 Hadoop节点故障 139
6.2 实践环节：杀死DataNode进程 141
6.3 实践环节：复制因子的作用 144
6.4 实践环节：故意造成数据块丢失 146
6.5 实践环节：杀死TaskTracker进程 149
6.6 实践环节：杀死JobTracker 153
6.7 实践环节：杀死NameNode进程 154
6.8 实践环节：引发任务故障 160
6.9 数据原因造成的任务故障 163
6.10 实践环节：使用skip模式处理异常数据 164
6.11 小结 169
第7章 系统运行与维护 170
7.1 关于EMR的说明 170
7.2 Hadoop配置属性 171
7.3 实践环节：浏览默认属性 171
7.3.1 附加的属性元素 172
7.3.2 默认存储位置 172
7.3.3 设置Hadoop属性的几种方式 173
7.4 集群设置 174
7.4.1 为集群配备多少台主机 174
7.4.2 特殊节点的需求 176
7.4.3 不同类型的存储系统 177
7.4.4 Hadoop的网络配置 178
7.5 实践环节：查看默认的机柜配置 180
7.6 实践环节：报告每台主机所在机柜 180
7.7 集群访问控制 183
7.8 实践环节：展示Hadoop的默认安全机制 183
7.9 管理NameNode 187
7.10 实践环节：为fsimage文件新增一个存储路径 188
7.11 实践环节：迁移到新的NameNode主机 190
7.12 管理HDFS 192
7.12.1 数据写入位置 192
7.12.2 使用平衡器 193
7.13 MapReduce管理 193
7.13.1 通过命令行管理作业 193
7.13.2 作业优先级和作业调度 194
7.14 实践环节：修改作业优先级并结束作业运行 194
7.15 扩展集群规模 197
7.15.1 提升本地Hadoop集群的计算能力 197
7.15.2 提升EMR作业流的计算能力 198
7.16 小结 198
第8章 Hive：数据的关系视图 200
8.1 Hive概述 200
8.1.1 为什么使用Hive 200
8.1.2 感谢Facebook 201
8.2 设置Hive 201
8.2.1 准备工作 201
8.2.2 下载Hive 202
8.3 实践环节：安装Hive 202
8.4 使用Hive 203
8.5 实践环节：创建UFO数据表 204
8.6 实践环节：在表中插入数据 206
8.7 实践环节：验证表 208
8.8 实践环节：用正确的列分隔符重定义表 210
8.9 实践环节：基于现有文件创建表 212
8.10 实践环节：执行联结操作 214
8.11 实践环节：使用视图 216
8.12 实践环节：导出查询结果 219
8.13 实践环节：制作UFO目击事件分区表 221
8.13.1 分桶、归并和排序 224
8.13.2 用户自定义函数 225
8.14 实践环节：新增用户自定义函数 225
8.14.1 是否进行预处理 228
8.14.2 Hive和Pig的对比 229
8.14.3 未提到的内容 229
8.15 基于AmazonWebServices的Hive 230
8.16 实践环节：在EMR上分析UFO数据 230
8.16.1 在开发过程中使用交互式作业流 235
8.16.2 与其他AWS产品的集成 236
8.17 小结 236
第9章 与关系数据库协同工作 238
9.1 常见数据路径 238
9.1.1 Hadoop用于存储档案 238
9.1.2 使用Hadoop进行数据预处理 239
9.1.3 使用Hadoop作为数据输入工具 239
9.1.4 数据循环 240
9.2 配置MySQL 240
9.3 实践环节：安装并设置MySQL 240
9.4 实践环节：配置MySQL允许远程连接 243
9.5 实践环节：建立员工数据库 245
9.6 把数据导入Hadoop 246
9.6.1 使用MySQL工具手工导入 246
9.6.2 在mapper中访问数据库 246
9.6.3 更好的方法：使用Sqoop 247
9.7 实践环节：下载并配置Sqoop 247
9.8 实践环节：把MySQL的数据导入HDFS 249
9.9 实践环节：把MySQL数据导出到Hive 253
9.10 实践环节：有选择性的导入数据 255
9.11 实践环节：使用数据类型映射 257
9.12 实践环节：通过原始查询导入数据 258
9.13 从Hadoop导出数据 261
9.13.1 在reducer中把数据写入关系数据库 261
9.13.2 利用reducer输出SQL数据文件 262
9.13.3 仍是最好的方法 262
9.14 实践环节：把Hadoop数据导入MySQL 262
9.15 实践环节：把Hive数据导入MySQL 265
9.16 实践环节：改进mapper并重新运行数据导出命令 267
9.17 在AWS上使用Sqoop 269
9.18 小结 270
第10章 使用Flume收集数据 271
10.1 关于AWS的说明 271
10.2 无处不在的数据 271
10.2.1 数据类别 272
10.2.2 把网络流量导入Hadoop 272
10.3 实践环节：把网络服务器数据导入Hadoop 272
10.3.1 把文件导入Hadoop 273
10.3.2 潜在的问题 273
10.4 ApacheFlume简介 274
10.5 实践环节：安装并配置Flume 275
10.6 实践环节：把网络流量存入日志文件 277
10.7 实践环节：把日志输出到控制台 279
10.8 实践环节：把命令的执行结果写入平面文件 281
10.9 实践环节：把远程文件数据写入本地平面文件 283
10.9.1 信源、信宿和信道 284
10.9.2 Flume配置文件 286
10.9.3 一切都以事件为核心 287
10.10 实践环节：把网络数据写入HDFS 287
10.11 实践环节：加入时间戳 289
10.12 实践环节：多层Flume网络 292
10.13 实践环节：把事件写入多个信宿 294
10.13.1 选择器的类型 295
10.13.2 信宿故障处理 295
10.13.3 使用简单元件搭建复杂系统 296
10.14 更高的视角 297
10.14.1 数据的生命周期 297
10.14.2 集结数据 297
10.14.3 调度 297
10.15 小结 298
第11章 展望未来 299
11.1 全书回顾 299
11.2 即将到来的Hadoop变革 300
11.3 其他版本的Hadoop软件包 300
11.4 其他Apache项目 303
11.4.1 HBase 303
11.4.2 Oozie 303
11.4.3 Whir 304
11.4.4 Mahout 304
11.4.5 MRUnit 305
11.5 其他程序设计模式 305
11.5.1 Pig 305
11.5.2 Cascading 305
11.6 AWS资源 306
11.6.1 在EMR上使用HBase 306
11.6.2 SimpleDB 306
11.6.3 DynamoDB 306
11.7 获取信息的渠道 307
11.7.1 源代码 307
11.7.2 邮件列表和论坛 307
11.7.3 LinkedIn群组 307
11.7.4 Hadoop用户群 307
11.7.5 会议 308
11.8 小结 308
随堂测验答案 309

推荐序1 iii
推荐序2 v
译序 vii
序言 xvii
前言 xix
致谢 xxi
第一部分  基础 1
第1章  导论 3
1.1 典型游戏团队的结构 4
1.2 游戏是什么 7
1.3 游戏引擎是什么 10
1.4 不同游戏类型中的引擎差异 11
1.5 游戏引擎概观 22
1.6 运行时引擎架构 27
1.7 工具及资产管道 46
第2章  专业工具 53
2.1 版本控制 53
2.2 微软Visual Studio 61
2.3 剖析工具 78
2.4 内存泄漏和损坏检测 79
2.5 其他工具 80
第3章  游戏软件工程基础 83
3.1 重温C++及最佳实践 83
3.2 C/C++的数据、代码及内存 90
3.3 捕捉及处理错误 118
第4章  游戏所需的三维数学 125
4.1 在二维中解决三维问题 125
4.2 点和矢量 125
4.3 矩阵 139
4.4 四元数 156
4.5 比较各种旋转表达方式 164
4.6 其他数学对象 168
4.7 硬件加速的SIMD运算 173
4.8 产生随机数 180
第二部分  低阶引擎系统 183
第5章  游戏支持系统 185
5.1 子系统的启动和终止 185
5.2 内存管理 193
5.3 容器 208
5.4 字符串 225
5.5 引擎配置 234
第6章  资源及文件系统 241
6.1 文件系统 241
6.2 资源管理器 251
第7章  游戏循环及实时模拟 277
7.1 渲染循环 277
7.2 游戏循环 278
7.3 游戏循环的架构风格 280
7.4 抽象时间线 283
7.5 测量及处理时间 285
7.6 多处理器的游戏循环 296
7.7 网络多人游戏循环 304
第8章  人体学接口设备（HID） 309
8.1 各种人体学接口设备 309
8.2 人体学接口设备的接口技术 311
8.3 输入类型 312
8.4 输出类型 316
8.5 游戏引擎的人体学接口设备系统 318
8.6 人体学接口设备使用实践 332
第9章  调试及开发工具 333
9.1 日志及跟踪 333
9.2 调试用的绘图功能 337
9.3 游戏内置菜单 344
9.4 游戏内置主控台 347
9.5 调试用摄像机和游戏暂停 348
9.6 作弊 348
9.7 屏幕截图及录像 349
9.8 游戏内置性能剖析 349
9.9 游戏内置的内存统计和泄漏检测 356
第三部分  图形及动画 359
第10章  渲染引擎 361
10.1 采用深度缓冲的三角形光栅化基础 361
10.2 渲染管道 404
10.3 高级光照及全局光照 426
10.4 视觉效果和覆盖层 438
10.5 延伸阅读 446
第11章  动画系统 447
11.1 角色动画的类型 447
11.2 骨骼 452
11.3 姿势 454
11.4 动画片段 459
11.5 蒙皮及生成矩阵调色板 471
11.6 动画混合 476
11.7 后期处理 493
11.8 压缩技术 496
11.9 动画系统架构 501
11.10 动画管道 502
11.11 动作状态机 515
11.12 动画控制器 535
第12章  碰撞及刚体动力学 537
12.1 你想在游戏中加入物理吗 537
12.2 碰撞/物理中间件 542
12.3 碰撞检测系统 544
12.4 刚体动力学 569
12.5 整合物理引擎至游戏 601
12.6 展望：高级物理功能 616
第四部分  游戏性 617
第13章  游戏性系统简介 619
13.1 剖析游戏世界 619
13.2 实现动态元素：游戏对象 623
13.3 数据驱动游戏引擎 626
13.4 游戏世界编辑器 627
第14章  运行时游戏性基础系统 637
14.1 游戏性基础系统的组件 637
14.2 各种运行时对象模型架构 640
14.3 世界组块的数据格式 657
14.4 游戏世界的加载和串流 663
14.5 对象引用与世界查询 670
14.6 实时更新游戏对象 676
14.7 事件与消息泵 690
14.8 脚本 707
14.9 高层次的游戏流程 726
第五部分  总结 727
第15章  还有更多内容吗 729
15.1 一些未谈及的引擎系统 729
15.2 游戏性系统 730
参考文献 733
中文索引 737
英文索引 755

第一版读者赞誉
第二版出版说明
第一版序言
第二版序言
第二版前言
第1章 文字和语言 vs 数字和信息 1
1 信息
2 文字和数字
3 文字和语言背后的数学
4 小结
第2章 自然语言处理——从规则到统计 15
1 机器智能
2 从规则到统计
3 小结
第3章 统计语言模型 27
1 用数学的方法描述语言规律
2 延伸阅读：统计语言模型的工程诀窍
3 小结
第4章 谈谈分词 41
1 中文分词方法的演变
2 延伸阅读：如何衡量分词的结果
3 小结
第5章 隐含马尔可夫模型 50
1 通信模型
2 隐含马尔可夫模型
3 延伸阅读：隐含马尔可夫模型的训练
4 小结
第6章 信息的度量和作用 60
1 信息熵
2 信息的作用
3 互信息
4 延伸阅读：相对熵
5 小结
第7章 贾里尼克和现代语言处理 72
1 早年生活
2 从水门事件到莫妮卡·莱温斯基
3 一位老人的奇迹
第8章 简单之美——布尔代数和搜索引擎 82
1 布尔代数
2 索引
3 小结
第9章 图论和网络爬虫 89
1 图论
2 网络爬虫
3 延伸阅读：图论的两点补充说明
4 小结
第10章 PageRank——Google的民主表决式网页排名技术 98
1 PageRank 算法的原理
2 延伸阅读：PageRank的计算方法
3 小结
第11章 如何确定网页和查询的相关性 104
1 搜索关键词权重的科学度量TF—IDF
2 延伸阅读：TF—IDF的信息论依据
3 小结
第12章 有限状态机和动态规划——地图与本地搜索的核心技术 111
1 地址分析和有限状态机
2 全球导航和动态规划
3 延伸阅读：有限状态传感器
4 小结
第13章 Google AK—47的设计者——阿米特·辛格博士 121
第14章 余弦定理和新闻的分类 127
1 新闻的特征向量
2 向量距离的度量
3 延伸阅读：计算向量余弦的技巧
4 小结
第15章 矩阵运算和文本处理中的两个分类问题 136
1 文本和词汇的矩阵
2 延伸阅读：奇异值分解的方法和应用场景
3 小结
第16章 信息指纹及其应用 142
1 信息指纹
2 信息指纹的用途
3 延伸阅读：信息指纹的重复性和相似哈希
4 小结
第17章 由电视剧《暗算》所想到的——谈谈密码学的数学原理 153
1 密码学的自发时代
2 信息论时代的密码学
3 小结
第18章 闪光的不一定是金子——谈谈搜索引擎反作弊问题和搜索结果的权威性问题 162
1 搜索引擎的反作弊
2 搜索结果的权威性
3 小结
第19章 谈谈数学模型的重要性 171
第20章 不要把鸡蛋放到一个篮子里——谈谈最大熵模型 177
1 最大熵原理和最大熵模型
2 延伸阅读：最大熵模型的训练
3 小结
第21章 拼音输入法的数学原理 186
1 输入法与编码
2 输入一个汉字需要敲多少个键——谈谈香农第一定理
3 拼音转汉字的算法
4 延伸阅读：个性化的语言模型
5 小结
第22章 自然语言处理的教父马库斯和他的优秀弟子们 197
1 教父马库斯
2 从宾夕法尼亚大学走出的精英们
第23章 布隆过滤器 204
1 布隆过滤器的原理
2 延伸阅读：布隆过滤器的误识别问题
3 小结
第24章 马尔可夫链的扩展——贝叶斯网络 209
1 贝叶斯网络
2 贝叶斯网络在词分类中的应用
3 延伸阅读：贝叶斯网络的训练
4 小结
第25章 条件随机场、文法分析及其他 217
1 文法分析——计算机算法的演变
2 条件随机场
3 条件随机场在其他领域的应用
4 小结
第26章 维特比和他的维特比算法 227
1 维特比算法
2 CDMA技术——3G移动通信的基础
3 小结
第27章 上帝的算法——期望最大化算法 238
1 文本的自收敛分类
2 延伸阅读：期望最大化和收敛的必然性
3 小结
第28章 逻辑回归和搜索广告 244
1 搜索广告的发展
2 逻辑回归模型
3 小结
第29章 各个击破算法和Google云计算的基础 249
1 分治算法的原理
2 从分治算法到MapReduce
3 小结
第30章 Google大脑和人工神经网络 254
1 人工神经网络
2 训练人工神经网络
3 人工神经网络与贝叶斯网络的关系
4 延伸阅读：Google大脑
5 小结
第31章 大数据的威力——谈谈数据的重要性 273
1 数据的重要性
2 数据的统计和信息技术
3 为什么需要大数据
4 小结
附录 计算复杂度 295
第二版后记 299
索引 302

写在前面i
译者的话iii
前言v
第1章迭代（Iteration） 1
第2章斐波那契数（Fibonacci Numbers） 15
第3章日历与时钟（Calendars and Clocks） 29
第4章矩阵（Matrices） 39
第5章线性方程组（Linear Equations） 53
第6章蕨型叶分形（Fractal Fern） 63
第7章谷歌的网页排名值（Google PageRank） 71
第8章指数函数（Exponential Function） 85
第9章T 形积木（T Puzzle） 99
第10章幻方问题（Magic Squares） 107
第11章井字棋的魅力（TicTacToe Magic） 123
第12章生命游戏（Game of Life） 131
第13章曼德勃罗集（Mandelbrot Set） 141
第14章数独（Sudoku） 159
第15章常微分方程（Ordinary Differential Equations） 173
第16章捕食者与猎物模型（Predator–Prey Model） 185
第17章轨道（Orbits） 191
第18章浅水方程（Shallow Water Equations） 207
第19章摩尔斯电码（Morse Code） 211
第20章音乐（Music） 227

第1章
演示初心／1
1.1 为什么要做PPT？／2
1.2 PPT的四堂理论课／4
1.3 如何成为PPT高手／7
第2章
制图概要／9
2.1 急速熟悉PowerPoint2010／10
2.2 PowerPoint的五个制图功能／15
2.3 PPT的三大制图技巧／27
2.4 PPT图示制作基础／34
第3章
字体气质／38
3.1 文字的缺点及优点／39
3.2 文字的三要素／39
3.3 字体的选择／45
第4章
图像力量／55
4.1 图片的作用／56
4.2 图片的用法／57
4.3 图片选择的雷区／60
4.4 苹果公司怎样用图片／66
4.5 图片的格式分类／69
4.6 图片的搜索／71
4.7 图片的基本处理／73
4.8 图片的高阶处理／76
4.9 多图安排的注意事项／78
4.10图文混排／79
目录0528.indd82015／6／412：16：06
第5章
图表魔术／82
5.1 表格和图表的四个基本要求／83
5.2 表格的设计／86
5.3 图表的基本构成／89
5.4 选择正确的图表／90
5.5 图表的制作／94
5.6 几种经典图表／98
5.7 图表的美化／101
5.8 图表的真相／104
5.9 启发图表制作的5个站点／107
第6章
图示表达／109
6.1 图示制作的三大误区／110
6.2 基本关系的图示化／112
6.3 复杂关系的图示化／125
6.4 图示的美化／126
第7章
解密动画／130
7.1 动画的作用／131
7.2 动画的要求／131
7.3 动画的三种类型／132
7.4 动画的基本设置／132
7.5 基本动画解析／136
7.6 动画的扩展／140
7.7 辅助动画技巧／147
7.8 页面切换动画／151
7.9 音频与视频／154
第8章
排版语言／158
8.1 要事第一／159
8.2 选择版式／160
8.3 组织信息／163
8.4 锦上添花／172
8.5 化静为动／178
8.6 视线操控／181
8.7 统一风格／184
第9章
色彩感觉／187
9.1 定义颜色／188
9.2 色彩的感受／189
9.3 色彩的性格／191
9.4 色轮／195
9.5 配色方法／198
9.6 配色的捷径／202
第10章
模板速成／204
10.1 模板的构成／205
10.2 创建模板／206
10.3 封面设计／207
10.4 内容页设计／212
10.5 导航系统／215
第11章
保存发布／219
11.1 文件的格式／220
11.2 兼容性问题／221
11.3 演示文稿的保护／222
11.4 使用“演示者”视图／223
11.5 遥控演示PPT／224
11.6 录制幻灯片演示／225
附录A PowerPoint快捷键大全／227
附录B 字体的分类／228
附录C 图表／230
附录D 图示汇总／233
附录E PowerPoint2003／2010动画对照表／236
附录F 达人们都是怎么找图的／237
附录G PPT原创博客推荐／239
附录H 其他一些应该知道的网站／241
鸣谢／242

《梦断代码》
第0章 软件时间 / 1
第1章 死定了[2003年7月] / 11
第2章 agenda之魂[1968年～2001年] / 31
第3章 原型与python[2001年～2002年11月] / 53
第4章 乐高王国[2002年11月～2003年8月] / 77
第5章 管束奇客和狗[2003年4月～8月] / 107
第6章 搞掂设计方案[2003年7月～11月] / 133
第7章 细节视图[2004年1月～5月] / 161
第8章 白板上的即时贴[2004年6月～10月] / 191
第9章 方法 / 217
第10章 工程师和艺术家 / 249
第11章 通往狗食版之路[2004年11月～2005年11月] / 285
尾声 长赌 [2005年～2029年及以后] / 317
译后记 / 327
附录a 专有名词对译表 / 330

第1章 0的故事——无即是有
本章学习内容
小学一年级的回忆
10进制计数法
什么是10进制计数法
分解2503
2进制计数法
什么是2进制计数法
分解1100
基数转换
计算机中为什么采用2进制计数法
按位计数法
什么是按位计数法
不使用按位计数法的罗马数字
指数法则
10的0次方是什么
10—1是什么
规则的扩展
对20进行思考
2—1是什么
0所起的作用
0的作用：占位
0的作用：统一标准，简化规则
日常生活中的0
人类的极限和构造的发现
重温历史进程
为了超越人类的极限
本章小结
第2章 逻辑——真与假的二元世界
本章学习内容
为何逻辑如此重要
逻辑是消除歧义的工具
致对逻辑持否定意见的读者
乘车费用问题——兼顾完整性和排他性
车费规则
命题及其真假
有没有“遗漏”
有没有“重复”
画一根数轴辅助思考
注意边界值
兼顾完整性和排他性
使用if语句分解问题
逻辑的基本是两个分支
建立复杂命题
逻辑非——不是A
逻辑与——A并且B
逻辑或——A或者B
异或——A或者B（但不都满足）
相等——A和B等
蕴涵——若A则B
囊括所有了吗
德•摩根定律
德•摩根定律是什么
对偶性
卡诺图
二灯游戏
首先借助逻辑表达式进行思考
学习使用卡诺图
三灯游戏
包含未定义的逻辑
带条件的逻辑与（&&）
带条件的逻辑或（||）
三值逻辑中的否定（！）
三值逻辑的德？摩根定律
囊括所有了吗
本章小结
第3章 余数——周期性和分组
本章学习内容
星期数的思考题（1）
思考题（100天以后是星期几）
思考题答案
运用余数思考
余数的力量——将较大的数字除一次就能分组
星期数的思考题（2）
思考题（10100天以后是星期几）
提示：可以直接计算吗
思考题答案
发现规律
直观地把握规律
乘方的思考题
思考题（1234567987654321）
提示：通过试算找出规律
思考题答案
回顾：规律和余数的关系
通过黑白棋通信
思考题
提示
思考题答案
奇偶校验
奇偶校验位将数字分为两个集合
寻找恋人的思考题
思考题（寻找恋人）
提示：先试算较小的数
思考题答案
回顾
铺设草席的思考题
思考题（在房间里铺设草席）
提示：先计算一下草席数
思考题答案
回顾
一笔画的思考题
思考题（哥尼斯堡七桥问题）
提示：试算一下
提示：考虑简化一下
提示：考虑入口和出口
思考题答案
奇偶校验
本章小结
第4章 数学归纳法——如何征服无穷数列
本章学习内容
高斯求和
思考题（存钱罐里的钱）
思考一下
小高斯的解答
讨论一下小高斯的解答
归纳
数学归纳法——如何征服无穷数列
0以上的整数的断言
高斯的断言
什么是数学归纳法
试着征服无穷数列
用数学归纳法证明高斯的断言
求出奇数的和——数学归纳法实例
奇数的和
通过数学归纳法证明
图形化说明
黑白棋思考题——错误的数学归纳法
思考题（黑白棋子的颜色）
提示：不要为图所惑
思考题答案
编程和数学归纳法
通过循环表示数学归纳法
循环不变式
本章小结
第5章 排列组合——解决计数问题的方法
本章学习内容
计数——与整数的对应关系
何谓计数
注意“遗漏”和“重复”
植树问题——不要忘记0
植树问题思考题
加法法则
加法法则
乘法法则
乘法法则
置换
置换
归纳一下
思考题（扑克牌的摆法）
排列
排列
归纳一下
树形图——能够认清本质吗
组合
组合
归纳一下
置换、排列、组合的关系
思考题练习
重复组合
也要善于运用逻辑
本章小结
第6章 递归——自己定义自己
本章学习内容
汉诺塔
思考题（汉诺塔）
提示：先从小汉诺塔着手
思考题答案
求出解析式
解出汉诺塔的程序
找出递归结构
再谈阶乘
阶乘的递归定义
思考题（和的定义）
递归和归纳
斐波那契数列
思考题（不断繁殖的动物）
斐波那契数列
帕斯卡三角形
什么是帕斯卡三角形
递归定义组合数
组合的数学理论解释
递归图形
以递归形式画树
实际作图
谢尔平斯基三角形
本章小结
第7章 指数爆炸——如何解决复杂问题
本章学习内容
什么是指数爆炸
思考题（折纸问题）
指数爆炸
倍数游戏——指数爆炸引发的难题
程序的设置选项
不能认为是“有限的”就不假思索
二分法查找——利用指数爆炸进行查找
寻找犯人的思考题
提示：先思考人数较少的情况
思考题答案
找出递归结构以及递推公式
二分法查找和指数爆炸
对数——掌握指数爆炸的工具
什么是对数
对数和乘方的关系
以2为底的对数
以2为底的对数练习
对数图表
指数法则和对数
对数和计算尺
密码——利用指数爆炸加密
暴力破解法
字长和安全性的关系
如何处理指数爆炸
理解问题空间的大小
四种处理方法
本章小结
第8章 不可解问题——不可解的数、无法编写的程序
本章学习内容
反证法
什么是反证法
质数思考题
反证法的注意事项
可数
什么是可数
可数集合的例子
有没有不可数的集合
对角论证法
所有整数数列的集合是不可数的
所有实数的集合是不可数的
所有函数的集合也是不可数的
不可解问题
什么是不可解问题
存在不可解问题
思考题
停机问题
停机
处理程序的程序
什么是停机问题
停机问题的证明
写给尚未理解的读者
不可解问题有很多
本章小结
第9章 什么是程序员的数学——总结篇
本章学习内容
何为解决问题
认清模式，进行抽象化
由不擅长催生出的智慧
幻想法则
程序员的数学

第1章Google软件测试介绍
1.1质量不等于测试
1.2角色
1.2.1软件开发工程师（SWE）
1.2.2软件测试开发工程师（SET）
1.2.3测试工程师（TE）
1.3组织结构
1.4爬、走、跑
1.5测试类型
第2章软件测试开发工程师
2.1SET的工作
2.1.1开发和测试流程
2.1.2SET究竟是谁
2.1.3项目的早期阶段
2.1.4团队结构
2.1.5设计文档
2.1.6接口与协议
2.1.7自动化计划
2.1.8可测试性
2.1.9SET的工作流程：一个实例
2.1.10测试执行
2.1.11测试大小的定义
2.1.12测试规模在共享测试平台中的使用
2.1.13测试规模的益处
2.1.14测试运行要求
2.2测试认证
2.3SET的招聘
2.4与工具开发工程师TedMao的访谈
2.5与WebDriver的创建者SimonStewart的对话
第3章测试工程师
3.1一种面向用户的测试角色
3.2测试工程师的工作
3.2.1测试计划
3.2.2风险
3.2.3测试用例的生命周期
3.2.4bug的生命周期
3.2.5TE的招聘
3.2.6Google的测试领导和管理工作
3.2.7维护模式的测试（MaintenanceModeTesting）
3.2.8质量机器人（QualityBot）实验
3.2.9BITE实验
3.2.10GoogleTestAnalytics
3.2.11零成本测试流程
3.2.12外部供应商
3.3与GoogleDocs测试工程师林赛·韦伯斯特（LindsayWebster）的访谈
3.4与YouTube测试工程师安普·周（AppleChow）的访谈
第4章测试工程经理
4.1测试工程经理的工作
4.2获得项目和人员
4.3影响力
4.4Gmail测试工程经理AnkitMehta的访谈
4.5Android测试工程经理HungDang的访谈
4.6Chrome测试工程经理JoelHynoski的访谈
4.7测试总监
4.8搜索和地理信息测试总监SheltonMar的访谈
4.9工程工具总监AshishKumar的访谈
4.10印度Google测试总监SujaySahni访谈
4.11工程经理BradGreen访谈
4.12JamesWhittaker访谈
第5章Google软件测试改进
5.1Google流程中的致命缺陷
5.2SET的未来
5.3TE的未来
5.4测试总监和经理的未来
5.5未来的测试基础设施
5.6结论
附录AChromeOS测试计划
A.1测试主题概述
A.2风险分析
A.3每次构建版本的基线测试
A.4最新可测试版本（LastKnownGood，LKG）的每日测试
A.5发布版本测试
A.6手工测试与自动化测试
A.7开发和测试的质量关注点
A.8发布通道
A.9用户输入
A.10测试用例库
A.11测试仪表盘
A.12虚拟化
A.13性能
A.14压力、长时运行和稳定性测试
A.15测试执行框架（Autotest）
A.16OEM厂商
A.17硬件实验田
A.18端到端测试自动化集群
A.19测试浏览器的应用管理器
A.20浏览器的可测试性
A.21硬件
A.22时间线
A.23主要的测试驱动力
A.24相关文档
附录BChrome的漫游测试
B.1购物漫游
B.2学生漫游
B.3国际长途电话漫游
B.4地标漫游
B.5通宵漫游
B.6公务漫游测试
B.7危险地带漫游
B.8个性化漫游
附录C有关工具和代码的博客文章
C.1使用BITE从bug和冗余的工作中解脱出来
C.2发布QualityBot
C.3RPF：Google的录制回放框架
C.4Google测试分析系统（GoogleTestAnalytics）——现在开源了
附录D术语表

第一部分 HTTP：Web的基础
第1章 HTTP概述
1.1 HTTP——因特网的多媒体信使
1.2 Web客户端和服务器
1.3资源
1.3.1媒体类型
1.3.2 UIU
1.3.3 URL
1.3.4 URN
1.4事务
1.4.1 方法
1.4.2状态码
1.4.3 Web页面中可以包含多个对象
1.5报文
1.6连接
1.6.1 TCMP
1.6.2连接、IP地址及端口号
1.6.3 一个使用Telnet的实例
1.7协议版本
1.8 Web的结构组件
1.8.1 代理
1.8.2缓存
1.8.3 网关
1.8.4隧道
1.8.5 Agent代理
1.9起始部分的结束语
1.10更多信息
1.10.1 HTTP协议信息
1.10.2历史透视
1.10.3其他万维网信息
第2章URL与资源
2.1浏览因特网资源
2.2 URL的语法
2.2.1方案——使用什么协议
2.2.2主机与端口
2.2.3 用户名和密码
2.2.4路径
2.2.5 参数
2.2.6查询字符串
2.2.7片段
2.3 URL快捷方式
2.3.1相对UPL
2.3.2 自动扩展URL
2.4各种令人头疼的字符
2.4.1 URL字符集
2.4.2编码机制
2.4.3字符限制
2.4.4另外一点说明
2.5方案的世界
2.6未来展望
2.7更多信息
第3章HTTP报文
3.1报文流
3.1.1报文流入源端服务器
3.1.2报文向下游流动
3.2报文的组成部分
3.2.1报文的语法
3.2.2起始行
3.2.3 首部
3.2.4实体的主体部分
3.2.5版本0.9的报文
3.3方法
3.3.1安全方法
3.3.2 GET
3.3.3 HEAD
3.3.4 PUT
3.3.5 POST
3.3.6 TRACE
3.3.7 OPTIONS
3.3.8 DELETE
3.3.9扩展方法
3.4状态码
3.4.1 100～199——信息性状态码
3.4.2 200～299——成功状态码
3.4.3 300～399——重定向状态码
3.4.4 400～499——客户端错误状态码
3.4.5 500～599——服务器错误状态码
3.5首部
3.5.1 通用首部
3.5.2请求首部
3.5.3响应首部
3.5.4实体首部
3.6更多信息
4章连接管理
4.1 TCP连接
4.1.1 TCP的可靠数据管道
4.1.2 TCP流是分段的、由IP分组传送
4.1.3保持TCP连接持续不断地运行
4.1.4用TCP套接字编程
4.2对TCP性能的考虑
4.2.1 HTTP事务的时延
4.2.2性能聚焦区域
4.2.3 TCP连接的握手时延
4.2.4延迟确认
4.2.5 TCP慢启动
4.2.6 Nagle算法与TCP—NODELAY
4.2.7 TIME WAIT累积与端口耗尽
4.3 HTTP连接的处理
4.3.1常被误解的Connection首部
4.3.2串行事务处理时延
4.4并行连接
4.4.1 并行连接可能会提高页面的加载速度
4.4.2并行连接不一定更快
……
第二部分 HTTP结构
第5章 Web服务器
第6章 代理
第7章 缓存
第8章 集成点：网关、隧道及中继
第9章 Web机器人
第10章 HTTP—NG
第三部分 识别、认证与安全
第11章 客户端识别与cookie机制
第12章 基本认证机制
第13章 摘要认证
第14章 安全HTTP
第四部分 实体、编码和国际化
第15章 实体和编码
第16章 国际化
第17章 内容协商与转码
第五部分 内容发布与分发
第18章 Web主机托管
第19章 发布系统
第20章 重定向与负载均衡
第21章 日志记录与使用情况跟踪
第六部分 附录
附录A URI方案
附录B HTTP状态码
附录C HTTP首部参考
附录D MIME类型
附录E Base—64编码
附录F 摘要认证
附录G 语言标记
附录H MIME字符集注册表
索引