本章篇幅较短，着重举了一个例子——Appel优化N体问题的过程。这是发表于1985年的一篇文章，Appel从多个层面对该问题进行了相互独立的优化，包括算法和数据结构、算法调优、数据结构重组、代码调优、硬件等层面。最终获得了400倍的加速系数，使得原先需要运行一年的程序现在只需要一天时间。
&l[......]编程珠玑笔记（8）-程序性能分析
回复
标签归档：编程珠玑
编程珠玑笔记（7）-编程小事
本章的内容与第4章一脉相承。第4章详细叙述了如何获得正确的二分搜索程序，并给出了详细的伪代码和正确性证明。本章则是在其基础上真正实现二分搜索的C语言程序。在叙述的过程中，作者展示了如何利用脚手架和断言技术来对代码段进行测试。
第5小节还介绍了计时的概念，但根据习题7中的讨论，书中展示的计时[……]
编程珠玑笔记（6）-编写正确的程序
作者在这一章叙述了编写正确程序的基本方法，在这个过程中介绍了断言、不变式等重要概念，主要介绍了人工程序验证这种检验程序正确性的方法。
用到的例子是二分搜索，作者在第一小节便强调，二分搜索从论文的发表到第一个没有错误的程序出现，历经了16年的时间，以此来强调编写正确程序的重要性和本章的必要性[……]
编程珠玑笔记（5）-数据决定程序结构
在这一章节中，作者通过几个不同的事例叙述了数据结构和程序之间的关系，中心思想只有一个：我们应当采取更好的数据结构，起码不是显然不适合这个程序的数据结构，以此来使得程序的编写得到简化，并获得其他的诸多好处。至于这样做是否值得，作者的答案显然是肯定的。
各个事例的精髓是一致的：“能用[……]
编程珠玑笔记（4）-啊哈！算法（III）
给定一个英语字典，找出其中的所有变位词集合。例如，“pots”、“stop”和“tops”互为变位词，因为每一个单词都可以通过改变其他单词中字母的顺序来得到。
我们获得的啊哈！灵光一现就是标识字典中的每一个词，使得在相同变位词类中的单词具有相同的标识。然后，将所有相同标识的单词集中[……]
编程珠玑笔记（3）-啊哈！算法（II）
将一个n元一维向量向左循环移位i个位置。简单的代码使用一个n元的中间向量在n步内完成该工作。你能够仅使用数十个额外字节的存储空间，在正比于n的时间内完成向量的旋转？
可以通过如下方式解决该问题：首先将x的前i个元素复制到一个临时数组中，然后将余下的n-i个元素向左移动i个位置，最后将[……]
编程珠玑笔记（2）–啊哈！算法（I）
给定一个最多包含40亿个随机排列的32位整数的顺序文件，找出一个不在文件中的32位整数（在文件中至少缺失一个这样的整数）。在具有足够内存的情况下，如何解决该问题？如果有几个外部的“临时”文件可用，但是仅有几百字节的内存，又该如何解决该问题？
我们从表示每个整数的32位的视角来[……]
编程珠玑笔记（1）–开篇
-
输入：一个最多包含n个正整数的文件，每个数都小于n，其中n=107。如果在输入文件中有任何整数重复出现就是致命错误。没有其他数据与该整数相关联。
输出：按升序排列的输入整数的列表。
约束：最多有（大约）1MB的内存空间可用，有充足的磁盘存储空间可用。[……]