2020年5月

Jon Beatlay,
ACM 通讯(communications of the ACM)
awk
计算机程序设计艺术

Fred Brooks
人月神话
Steve Mc Godneell（唐纳德？？？？
代码大全
科学美国人
cobol 怎样解题
如何快速计算一个月有多少天
简单统计一下这本书 4 出现的次数

本文的篇幅可能会过于长，且更新时间周期很长很长，所以请慢慢等待

第一章 开篇

需要对数据库的数据进行排序
密度较大
不能使用系统自带的排序函数

关于排序的几个点

在磁盘上实现归并排序，现在仿佛这本书很是有必要去看
最近物联网的概念还是比较火的，那些低功率的芯片，例如 ESP8266，

文件中最多包含一千万条记录，每一条记录都是 7 位数的整数

（尽管机器有许多兆字节的内存，但是排序功能只是大系统中的一部分，所以大概只有 1MB 的内存（其实这个算是相当奢侈了，ESP8266 里面只有 140K 来着

每个整数最多出现一次，

看到这里，其实有点基础的就会想到一个叫做桶排序的算法，因为不重复，所以可以用 bool 类型进行桶排序（也可以叫做位图法之类的

（七位数其实就是美国的座机电话号码
（由于几个小时就有一次请求，所以排序时间不能太长

可以通过反复读入，进行归并排序，借用外部的文件进行中间存储。但是读写次数过多，也会很影响速度

不过那个时候的软件开发速度真的是完全比不上现在，现在一个排序算法哪需要写一个星期

graph LR;
    A --> B;
    B --> C;
    C --> B;
    B --> D;

就算一个桶排序，也不需要数个小时，这本书的初版是真的很老了，但是就是火的一批

桶排序（位图表示法）适用于数据量很大，不重复，稠密的情况，如果是一个很稀疏的数列，使用这种方法就会格外浪费空间

多趟算法
时间——空间折中与双赢

课后题

  1. 如果不缺内存，如何使用一个具有库的语言来实现一种排序算法以表示和排序集合
  2. 如何使用位逻辑运算（如与、或、位移）来实现位向量
  3. 运行时效率是设计目标的一个重要组成部分，所得到的程序需要足够高效。在你自己的系统上实现位图排序并度量其运行时间。该时间与系统排序的运行时间以及习题1中排序的运行时间相比如何？假设n为10000000，且输入文件包含1000000个整数
  4. 如果认真考虑了习题3，你将会面对生成小于n且没有重复的k个整数的问题，最简单的方法就是使用前k个正整数。这个计算的数据集合将不会明显地改变位图方法的运行时间，但是可能会歪曲系统排序的运行时间。如何生成位于0至n-1之间的k个不同的随即顺序的随机整数？尽量是你的程序简短且高效。
  5. 那个程序员说他有1MB的可用存储空间，但是我们概要描述的代码需要1.25MB的空间。它可以不费力气地索取到额外的空间。如果1MB空间是严格边界，你会推荐如何处理呢？你的算法地运行时间又是多少？
  6. 如果哪个程序员说的不是每个整数最多出现一次，而是每个整数最多出现10词，你又如何建议他呢？你的解决方案如何随着可用存储空间总量地变化而变化？
  7. [R. Weil] 本书1.4节中面熟的程序存在一些缺陷。首先是假定输入中没有出现两次地整数，如果某个数出现超过一次的话，会发生什么？在这种情况下，如何修改程序来调用错误处理函数？当输入整数小于零或大于等于n时，又会发生什么？如果某个输入不是数值又如何？在这些情况下，程序该如何处理？程序还应该包含那些明智地检查？描述一些用以测试程序地小型数据集合，并说明如何正确处理上述及其他地不良情况。
  8. 当那个程序员解决该问题的时候，美国所有地免费电话地区号都是800。现在免费电话的区号包括800、877和888，而且还在增多，如何在1MB空间内完成对所有这些免费电话号码的排序》如何将免费电话号码存储在一个一个集合中，要求可以实现非常快速的查找以判定一个给定的免费电话号码是否可用或者已经存在？
  9. 使用更多的空间来换取更少的运行时间存在一个问题：初始化空间本身需要消耗大量的时间。说明如何设计一种技术，在第一次访问响亮的项时将其初始化为 0.你的方案应该使用常量时间进行初始化和向量访问，使用的额外空间应正比于向量的大小。因为该方法通过进一步增加空间来减少出场我的时间，所以仅在空间很廉价、时间很宝贵且向量很稀疏的情况下才考虑使用。
  10. 在成本低廉的隔日送达时代之前，商店允许顾客通过电话订购商品，并在几天后上门自取。商店的数据库使用客户的电话号码作为其检索的主关键字（客户知道他们自己的电话号码而且这些关键字几乎都是唯一的）。你如何组织商店的数据库，以允许高效的插入和检索操作？
  11. 在 20 世纪 80 年代早期，洛克希德公司加利福尼亚州桑尼维尔市工厂的工程师们每天都要将许多由计算机辅助设计（CAD）系统生成的图纸从工厂送到位于圣克鲁斯市的测试站。虽然仅有 40 公里远，但使用汽车快递服务每天都需要一个多小时的时间（由于交通阻塞和山路崎岖），花费 100 美元。请给出新的数据传输方案并估计每一种方案的费用。
  12. 载人航天的先驱们很快就意识到在外太空的极端环境下实现顺利书写。民间盛传美国国家宇航局（NASA）花费 100 万美元研发出一种特殊的钢笔来解决这个问题。那么，前苏联又会如何解决相同的问题呢？

1.7 深入阅读
这个小问题仅仅是令人痴迷的程序说明问题的冰山一角。要深入研究这个重要的课题，参见 Michael Jackson 的 Software Requirements & Specifications 一书（Addison-Eesley 出版社 1995 年出版）。该书用一组独立成章却又相辅相成的短文，以令人愉悦的方式阐述了这个艰涩的课题。
在本章所描述的实例研究中，程序员的主要问题与其说是技术问题，还不如说是心理问题：他不能解决问题，是因为他企图解决错误的问题。问题的最终解决，是通过打破他的概念壁垒，进而去解决一个较简单的问题而实现的。 James L. Adams 所著的 Conceptuel Blockbusting 一书（第 3 版由 Perseus 出版社于 1986 年出版）研究了这类跳越，概述通常是触发创新性思维的理想选择。虽然该书不是专为程序员而写的，其中的许多内容却特别适用于编程问题。Adams 将概念壁垒定义为“阻碍解题者理解问题或者取得答案的心智壁垒”。习题 10、习题 11 和 习题 12 激励读者去打破一些这样的壁垒

Michael Jackson 软件工程先驱。他于 20 世纪 70 年代提出了影响深远的面向数据结构的 Jackson 方法

第二章 啊哈！算法

《啊哈！灵机一动》

数字排序
字符串位移
字符串匹配

二分搜索
——寻找数列中缺失的数字
（限制条件时内存较少，但是有文件可以使用）

众所周知，二分搜索程序要正确运行很困难。
（但事实上，内卷玩家，二分搜索都是小 case 了

二分搜索还可以用于别的方面，并不止局限于有序数列

第三章 数据决定数据结构

第四章 编写正确的程序

第五章 编程小事

第六章 程序性能分析

第七章 粗略估算

第八章 算法设计技术

第九章 代码调优

第十章 节省空间

第十一章 排序

第十二章 取样问题

第十三章 搜索

第十四章 堆

第十五章 字符串

$$W = \\left(\\left[\\frac{c}{4}\\right]-2c+y+\\left[{\\frac{y}{4}}\\right]+\\left[\\frac{13(m+1)}{5}\\right]+d-1\\right) \\bmod 7$$

w：星期； w 对 7 取模得：0 - 星期日，1 - 星期一，2 - 星期二，3 - 星期三，4 - 星期四，5 - 星期五，6 - 星期六
c：世纪 - 1（前两位数）
y：年（后两位数）
m：月（m 大于等于 3，小于等于 14，即在蔡勒公式中，某年的 1、2 月要看作上一年的 13、14 月来计算，比如 2003 年 1 月 1 日要看作 2002 年的 13 月 1 日来计算）
d：日
[ ] 代表取整，即只要整数部分。

https://www.zhihu.com/question/42879877

https://baike.baidu.com/item/%E8%94%A1%E5%8B%92%E5%85%AC%E5%BC%8F/10491767?fr=aladdin

https://blog.csdn.net/S_999999/article/details/88723201

https://www.cnblogs.com/faterazer/p/11393521.html

https://blog.csdn.net/qq_40655981/article/details/98457824

https://www.cnblogs.com/ZhaoxiCheung/p/6803376.html

OJ 必须要了解的算法（如果要和别人比时间的话）

1. 数据量巨大的时候 std::cin, std::cout TLE (超时)

static bool speedUP = [](){std::ios::sync_with_stdio(false); cin.tie(nullptr); return true}();
// 静态变量先于 main 函数初始化，以实现直接调用 lambda 函数
// std::ios::sync_with_stdio (false); 用以关闭 同步功能，不写缓存，不 flush
// cin.tie (nullptr); 用于绑定输入流，nullptr 为当前输入流
// 写了一个 lambda 函数并调用了

https://byvoid.com/zhs/blog/fast-readfile/
https://zhuanlan.zhihu.com/p/35652783
https://www.jianshu.com/p/fa8ad995d300

2. 快速整数平方根（牛顿迭代打表）（std::sqrt 的 4 倍）

inline int mysqrt(int n) {
    static int table[256] = {
        0,    16,  22,  27,  32,  35,  39,  42,  45,  48,  50,  53,  55,  57,
        59,   61,  64,  65,  67,  69,  71,  73,  75,  76,  78,  80,  81,  83,
        84,   86,  87,  89,  90,  91,  93,  94,  96,  97,  98,  99, 101, 102,
        103, 104, 106, 107, 108, 109, 110, 112, 113, 114, 115, 116, 117, 118,
        119, 120, 121, 122, 123, 124, 125, 126, 128, 128, 129, 130, 131, 132,
        133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 144, 145,
        146, 147, 148, 149, 150, 150, 151, 152, 153, 154, 155, 155, 156, 157,
        158, 159, 160, 160, 161, 162, 163, 163, 164, 165, 166, 167, 167, 168,
        169, 170, 170, 171, 172, 173, 173, 174, 175, 176, 176, 177, 178, 178,
        179, 180, 181, 181, 182, 183, 183, 184, 185, 185, 186, 187, 187, 188,
        189, 189, 190, 191, 192, 192, 193, 193, 194, 195, 195, 196, 197, 197,
        198, 199, 199, 200, 201, 201, 202, 203, 203, 204, 204, 205, 206, 206,
        207, 208, 208, 209, 209, 210, 211, 211, 212, 212, 213, 214, 214, 215,
        215, 216, 217, 217, 218, 218, 219, 219, 220, 221, 221, 222, 222, 223,
        224, 224, 225, 225, 226, 226, 227, 227, 228, 229, 229, 230, 230, 231,
        231, 232, 232, 233, 234, 234, 235, 235, 236, 236, 237, 237, 238, 238,
        239, 240, 240, 241, 241, 242, 242, 243, 243, 244, 244, 245, 245, 246,
        246, 247, 247, 248, 248, 249, 249, 250, 250, 251, 251, 252, 252, 253,
        253, 254, 254, 255
     };
    int xn;
    if (n >= 0x7FFEA810) return 0xB504;
    if (n >= 0x10000) {
        if (n >= 0x1000000) {
            if (n >= 0x10000000) {
                if (n >= 0x40000000) {
                     xn = table[n>> 24] << 8;
                 } else {
                     xn = table[n>> 22] << 7;
                 }
             } else {
                if (n>= 0x4000000) {
                     xn = table[n>> 20] << 6;
                 } else {
                     xn = table[n>> 18] << 5;
                 }
             }
             xn = (xn + 1 + (n/ xn)) >> 1;
             xn = (xn + 1 + (n/ xn)) >> 1;
            return ((xn * xn) > n) ? --xn : xn;
         } else {
            if (n>= 0x100000) {
                if (n>= 0x400000) {
                     xn = table[n>> 16] << 4;
                 } else {
                     xn = table[n>> 14] << 3;
                 }
             } else {
                if (n>= 0x40000) {
                     xn = table[n>> 12] << 2;
                 } else {
                     xn = table[n>> 10] << 1;
                 }
             }

             xn = (xn + 1 + (n/ xn)) >> 1;
            return ((xn * xn) > n) ? --xn : xn;
         }
     } else {
        if (n>= 0x100) {
            if (n>= 0x1000) {
                if (n>= 0x4000) {
                     xn = (table[n>> 8]) + 1;
                 } else {
                     xn = (table[n>> 6] >> 1) + 1;
                 }
             } else {
                if (n>= 0x400) {
                     xn = (table[n>> 4] >> 2) + 1;
                 } else {
                     xn = (table[n>> 2] >> 3) + 1;
                 }
             }
            return ((xn * xn) > n) ? --xn : xn;
         } else {
            if (n>= 0) {
                return table[n] >> 4;
             }
         }
     }
    return -1;
}

https://blog.csdn.net/hunterlew/article/details/45341253
https://blog.csdn.net/xtlisk/article/details/51249371
https://blog.csdn.net/wanchuanhua/article/details/5996708
http://bbs.mydigit.cn/simple/?t2329623.html
https://www.cnblogs.com/signal/p/3818332.html
https://www.cnblogs.com/atyuwen/archive/2009/11/09/1598942.html

  1. 1
  2. 2