`
zxxapple
  • 浏览: 79506 次
  • 性别: Icon_minigender_1
  • 来自: 南京
社区版块
存档分类
最新评论

编程珠玑开篇--磁盘文件排序问题

阅读更多

转载。。。。


编程珠玑开篇--磁盘文件排序问题

输入:

所输入的文件,至多包含n个正整数,每个正整数都小于n,题目中n = 10^7,如果输入时某个正整数重复出现俩次,就会产生致命的错误,这些整数,与其他任何数据都不相关.

输出:

以增序形式输出经过排序的整数列表

约束

至多只有1MB(包括程序本身)可用的主存,但是可以用的磁盘空间是充足的,运行时间至多几分钟,10秒针是最适宜的运行时间.

作者第一个方案使用基于磁盘的合并排序.将每个号码用32位整数表示,可以在1MB的空间里存储250000个号码,使用一个带有40个通道的程 序,在第一个通道中将0到249999之间的整数读入内存,并对它们进行排序,可以使用高效的快速排序,第一个通道中将250000到499999之间的整数读入内存,并对它们进行排序,直到第40个通道,读取9750000到9999999之间的证书进行排序,但是完成整个任务,我们要牺牲读文件40次的代价.

 

还有一种归并排序。。。。。。

 

最后作者引出了另外一种解决方案位图和位向量:

我们可以用一个20位的字符串可以表示小于20的非负数集合.例如,我们可以将集合{1,2,3,5,8,13}存储在下面字符串中:

集合中代表数字的各个位设置为1 ,而其他的位全部设置为0

     在上面问题中,我们使用一千万位的字符串表示该文件,当且仅当整数i在该文件中的时候,第i位才被设置为1,这种表示法使用了这个问题中的三中属性,输入的范围相对小一些,并且还不包括重复的数据,而且没有数据和单个整数以外的每一记录相关联

算法实现分三阶段

1 设置每个位为0

2 读取文件,将相应的位设置为1

3 检查每个位,当为1时,将整数写入

这些函数使用常量来设置,清除并测试位值

分享到:
评论

相关推荐

    ASP.NET\ASP.NET 2.0编程珠玑--来自MVP 2.0编程珠玑--来自MVP的权威开发指南

    《ASP.NET 2.0编程珠玑--来自MVP的权威开发指南》一书深入探讨了ASP.NET 2.0的核心概念和技术,旨在帮助开发者熟练掌握这一平台。 在ASP.NET 2.0中,控件是构建用户界面的关键组件。它们包括服务器控件和HTML控件,...

    asp.net 2.0编程珠玑--来自mvp的权威开发指南

    通过阅读《ASP.NET 2.0编程珠玑--来自MVP的权威开发指南》,开发者不仅可以学习到ASP.NET 2.0的精髓,还能获取解决实际问题的策略和技巧,从而在Web开发领域更加游刃有余。书中包含的丰富示例和案例分析将帮助读者更...

    编程珠玑--算法

    编程中的一本关于算法的好书。

    ASP.NET 2.0编程珠玑--来自MVP的权威开发指南

    这本书“ASP.NET 2.0编程珠玑--来自MVP的权威开发指南”深入讲解了这个框架的关键特性和最佳实践,旨在帮助开发者充分利用其功能。 在ASP.NET 2.0中,最重要的改进之一是页面生命周期管理。与前一版本相比,2.0版...

    ASP.NET+2.0编程珠玑--开发指南

    本书“ASP.NET+2.0编程珠玑--开发指南”是针对这个版本的专业指南,由MVP(Microsoft最有价值专家)撰写,旨在帮助开发者深入理解和掌握ASP.NET 2.0的核心概念和技术。 书中可能涵盖了以下关键知识点: 1. **ASP...

    ASP.NET+2.0编程珠玑--来自MVP的权威开发指南(无密码)

    此压缩包文件提供的"ASP.NET+2.0编程珠玑--来自MVP的权威开发指南"是一本深入探讨ASP.NET 2.0技术的书籍,可能包含了以下关键知识点: 1. **ASP.NET 2.0概述**:ASP.NET 2.0在ASP.NET 1.x的基础上进行了许多改进,...

    编程珠玑 -- swap section

    NULL 博文链接:https://philoscience.iteye.com/blog/1010964

    编程珠玑 编程珠玑 编程珠玑 编程

    书中涵盖了一系列实用的编程问题和解决方案,这些“珠玑”般的编程智慧,无论对于初学者还是经验丰富的开发者,都有着极高的参考价值。 编程珠玑的核心概念之一是数据结构与算法的选择和设计。书中的例子多以实际...

    编程珠玑源码下载编程珠玑书后源代码

    3. **问题解决策略**:书中提出了解决编程问题的一些通用方法,如预处理、分治法、动态规划等,帮助读者建立系统化的思维模式。 4. **性能分析**:讲解如何分析和改进程序性能,包括时间复杂度和空间复杂度的计算,...

    编程珠玑-[美]乔恩美特利.mobi

    编程珠玑-[美]乔恩美特利.mobi、kindle文档、第二版修订版

    编程珠玑 第2版(修订版)_编程珠玑修订_资料_

    《编程珠玑 第2版(修订版).pdf》这个文件包含了所有这些精彩的内容,无论你是新手还是有经验的开发者,都可以从中汲取知识,提升自己的编程素养。通过深入阅读和实践书中的例子,你将能够更好地应对编程挑战,成为一...

    编程珠玑-第2版-修订版

    本书的特色是通过一些精心设计的有趣而又颇具指导意义的程序,对实用程序设计技巧及基本设计原则进行了透彻而睿智的描述,为复杂的编程问题提供了清晰而完备的解决思路。《编程珠玑(第 2版·修订版)》对各个层次的...

    编程珠玑-中文第二版

    ### 编程珠玑-中文第二版 #### 知识点概述 《编程珠玑-中文第二版》是一本在计算机科学领域内享有极高声誉的经典著作。本书虽然篇幅不长,但却以其深刻的见解和丰富的内涵深受广大程序员和技术爱好者的推崇。通过...

    编程珠玑-英文版+中文版+source code

    《编程珠玑》是计算机科学领域的一本经典之作,由Jon Bentley 编著,它以其深入浅出的方式探讨了程序设计中的许多核心问题。这本书主要关注如何有效地处理和存储大量数据,以及如何在时间和空间效率之间找到平衡。...

Global site tag (gtag.js) - Google Analytics