《编程珠玑(第2版•修订版)》—第1章1.1节一次友好的对话-阿里云开发者社区

开发者社区> 开发与运维> 正文
登录阅读全文

《编程珠玑(第2版•修订版)》—第1章1.1节一次友好的对话

简介: 这一部分的5章回顾程序设计的基础知识。第1章介绍一个问题的历史,我们把仔细的问题定义和直接的程序设计技术结合起来,得到优美的解决方案。

本节书摘来自异步社区《编程珠玑(第2版•修订版)》一书中的第1章1.1节一次友好的对话,作者【美】Jon Bentley,更多章节内容可以访问云栖社区“异步社区”公众号查看。

第一部分 基础
编程珠玑(第2版•修订版)
这一部分的5章回顾程序设计的基础知识。第1章介绍一个问题的历史,我们把仔细的问题定义和直接的程序设计技术结合起来,得到优美的解决方案。这一章揭示了本书的中心思想:对实例研究的深入思考不仅很有趣,而且可以获得实际的益处。

第2章讨论3个问题,其中重点强调了如何由算法的融会贯通获得简单而高效的代码。第3章总结数据结构在软件设计中所起到的关键作用。

第4章介绍一个编写正确代码的工具——程序验证。在第9章、第11章和第14章中生成复杂(且快速)的函数时,大量使用了程序验证技术。第5章讲述如何把这些抽象的程序变成实际代码:使用脚手架程序来探测函数,用测试用例来测试函数并度量函数的性能。

本部分内容

第1章 开篇

第2章 啊哈! 算法

第3章 数据决定程序结构

第4章 编写正确的程序

第5章 编程小事

第1章 开篇
编程珠玑(第2版•修订版)
一位程序员曾问我一个很简单的问题:“怎样给一个磁盘文件排序?”想当年我是一上来就犯了错误,现在,在讲这个故事之前,先给大家一个机会,看看能否比我当年做得更好。你会怎样回答上述问题呢?

1.1 一次友好的对话
我错就错在马上回答了这个问题。我告诉他一些有关如何在磁盘上实现归并排序的简要思路。我建议他深入研究算法教材,他似乎不太感冒。他更关心如何解决这个问题,而不是深入学习。于是我告诉他在一本流行的程序设计书里有磁盘排序的程序。那个程序有大约200行代码和十几个函数,我估计他最多需要一周时间来实现和测试该代码。

我以为已经解决了他的问题,但是他的踌躇使我返回到了正确的轨道上。其后就有了下面的对话,楷体部分是我的问题。

为什么非要自己编写排序程序呢?为什么不用系统提供的排序功能呢?
我需要在一个大系统中排序。由于不明的技术原因,我不能使用系统中的文件排序程序。

需要排序的内容是什么?文件中有多少条记录?每条记录的格式是什么?
文件最多包含1千万条记录,每条记录都是7位的整数。

等一下,既然文件这么小,何必非要在磁盘上进行排序呢?为什么不在内存里进行排序呢?
尽管机器有许多兆字节的内存,但排序功能只是大系统中的一部分,所以,估计到时只有1 MB的内存可用。

你还能告诉我其他一些与记录相关的信息吗?
每条记录都是7位的正整数,再无其他相关数据。每个整数最多只出现一次。

这番对话让问题更明确了。在美国,电话号码由3位“区号”后再跟7位数字组成。拨打含“免费”区号800(当时只有这一个号码)的电话是不收费的。实际的免费电话号码数据库包含大量的信息:免费电话号码、呼叫实际中转到的号码(有时是几个号码,这时需要一些规则来决定哪些呼叫在什么时间中转到哪里)、主叫用户的姓名和地址等。

这位程序员正在开发这类数据库的处理系统的一小部分,需要排序的整数就是免费电话号码。输入文件是电话号码的列表(已删除所有其他信息),号码重复出现算出错。期望的输出文件是以升序排列的电话号码列表。应用背景同时定义了相应的性能需求。当与系统的会话时间较长时,用户大约每小时请求一次有序文件,并且在排序未完成之前什么都干不了。因此,排序最多只允许执行几分钟,10秒钟是比较理想的运行时间。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
开发与运维
使用钉钉扫一扫加入圈子
+ 订阅

集结各类场景实战经验,助你开发运维畅行无忧

其他文章
最新文章
相关文章