- 浏览: 183762 次
- 性别:
- 来自: 深圳
文章分类
最新评论
-
为什么昵称都叫没了:
对的,我也在做微信公众平台的开发,发现一个简单的教程 http ...
微信公众平台API -
guji528:
想找一个好一点的调试器,不知eric是否OK,有空再研究一下
Eric IDE安装 -
youyang:
受教了,不得不顶。
NoSQL非关系数据库简介 -
zhongzhai:
谢谢分享,波一个
Java中的UDP协议编程 -
huwenbiao2010:
有实现JPopupMenu透明的案例不,发个给我 ,谢谢了 , ...
一道笔试题
一个文件里,有一堆int,把它们排序一下,输出到另外一个文件。 下面是代码:
这个问题很简单了,把int读入内存,排序一下,输出到文件。
但是,如果加个条件:数据量巨大,内存无法容纳,那这个问题该怎么解决呢?
嗯,直接说答案:
1) 按内存能放下的规模,顺序读入一批批的数据,排序,输出到不同的文件
2) 现在得到一堆文件,每个文件里是排好序的
3) 对这些文件进行两两归并,就是把两个各自有序的文件,归并到一个有序的文件里
4) 最后得到一个文件
假设int存放的格式是文本格式,一行一个。private void button3_Click(object sender, EventArgs e)
{
string from=@"e:\data.txt";
string to=@"e:\target.txt";
SortBigFile(from, to);
Console.WriteLine(GetLineOf(from, 123456789));
}
private void SortBigFile(string from, string to)
{
//读入内存排序的int个数
//2.5e7个int,占内存约 100M
const int BatchRead = 25000000;
//临时文件夹
const string TempDir = @"e:\temp\";
int fileIndex = 0;
StreamReader reader = new StreamReader(from);
try
{
int[] data=new int[BatchRead];
int count = 0;
string line;
while((line=reader.ReadLine())!=null) {
data[count++]=int.Parse(line);
if(count>=BatchRead) {
//读了一批
//排序
Array.Sort(data,0,count);
//写文件
string file=TempDir+"temp"+(++fileIndex)+".txt";
WriteFile(data,count,file);
//继续下一批
count = 0;
}
}
if (count > 0)
{
//余下的不够一批的
Array.Sort(data, 0, count);
//写文件
string file = TempDir + "temp" + (++fileIndex) + ".txt";
WriteFile(data, count, file);
}
}
finally
{
reader.Close();
}
//开始归并排序
string Temp=TempDir+"Temp.txt";
//归并,直到只剩一个文件
while (fileIndex > 1)
{
int c = 0;
for (int i = 1; i <= fileIndex; i += 2)
{
int b = i + 1;
if (b <= fileIndex)
{
MergeFile(TempDir + "temp" + i + ".txt", TempDir + "temp" + b + ".txt", Temp);
c++;
string t = TempDir + "temp" + c + ".txt";
if (File.Exists(t))
{
File.Delete(t);
}
File.Move(Temp, t);
}
else
{
//最后一个,落单了
c++;
string t=TempDir+"temp"+c+".txt";
if(File.Exists(t)) {
File.Delete(t);
}
File.Move(TempDir+"temp"+i+".txt",t);
}
}
fileIndex = c;
}
//归并到一个文件了
File.Move(TempDir + "temp1.txt", to);
}
private void WriteFile(int[] data, int count,string file)
{
if (File.Exists(file))
{
File.Delete(file);
}
StreamWriter writer = new StreamWriter(file, false);
try
{
for (int i=0;i< int.Parse(lb))
{
t.WriteLine(la);
la = ra.ReadLine();
}
else
{
t.WriteLine(lb);
lb = rb.ReadLine();
}
}
else if (la != null)
{
t.WriteLine(la);
la = ra.ReadLine();
}
else
{
//lb!=null
t.WriteLine(lb);
lb = rb.ReadLine();
}
}
t.Flush();
}
finally
{
t.Close();
}
}
finally
{
rb.Close();
}
}
finally
{
ra.Close();
}
}
private string GetLineOf(string file, int n)
{
StreamReader reader = new StreamReader(file);
try
{
string line=null;
for (int i = 0; i < n; i++)
{
line = reader.ReadLine();
if (line == null)
{
break;
}
}
return line;
}
finally
{
reader.Close();
}
}
发表评论
-
UML类图关系(泛化 、继承、实现、依赖、关联、聚合、组合)
2013-04-26 22:32 864继承 指的是一个类(称为子类、子接口)继承另外的一个类( ... -
数据库链接池(DBCP)配置参考
2012-01-31 17:20 999链接池不但能提高数据库的访问效率,也能有效地控制自 ... -
设置半透明的JMenuBar
2011-01-17 17:33 3137源作:陈思羽. 更新:龚德伟. 2008.07.20 ... -
使用svn——项目的目录布局
2011-01-07 21:12 798Subversion有一个很标准的目录结构,是这样的。 比如 ... -
Socket TCP连接和断开过程
2010-11-03 09:22 2316在TCP/IP协议中,TCP协议提供可靠的连接服务,采用三次握 ... -
几个重要的TCP/IP选项解析(Java Socket)
2010-10-28 13:22 10731. SO_LINGER / SO_REUSEADDR ... -
java jvm 参数 -Xms -Xmx -Xmn -Xss 调优总结
2010-10-25 13:41 969常见配置举例 堆大 ... -
jstat,jmap,jconsole,jvisualvm,jps,jinfo等JDK系统监控、性能调优工具
2010-10-11 13:57 798JProfiler在java程序性能调试方便表现优越,推荐使用 ... -
一道笔试题
2010-09-28 23:05 1002问题说明 : 计算一个整形数组里的连续元素和的最大值 ... -
各种系统架构图及其简介
2010-03-01 11:35 2436转载请保留出处 , 不胜人生 一场醉汇总。 ... -
Java抓图软件
2010-01-19 09:52 1012以下代码不是本人所写,乃是从网上搜到,记录下来供以后参考。 ... -
16进制字符串与byte数组互转(转载)
2010-01-13 21:07 1971import java.io.ByteArrayInp ... -
byte,int,char,double的相互转换(java)
2010-01-13 21:05 2689//整数到字节数组的转换 public stat ... -
Java中的UDP协议编程
2009-11-18 14:34 1915一. UDP协议定义 UDP协议的全称是用户数据报 ... -
System.getProperties()
2009-07-26 22:26 28501 、 java 通过 System.g ... -
System.getProperty()参数大全
2009-07-26 22:22 869java.version Ja ... -
JAVA打包后读取自身JAR中的文件
2009-07-26 21:48 5685在编写完Java程序后,打包成Jar时发布,会发现找不到Jar ... -
log4j 日志文件相对路径
2009-07-26 21:32 12961、在Tomcat 5.5中的Log4j ... -
windows下openldap的安装与java操作测试
2009-07-01 15:36 916windows下openldap的安装与 ... -
用Ant编译、junit测试、生成测试报告、最终自动发mail
2009-03-19 14:15 1569测试通过的版本如下:Eclipse:3.3.2jdk:1.6j ...
相关推荐
数据结构中的排序是计算机科学中一个基础且重要的概念,它涉及到如何有效地组织和处理大量数据。在第10章“内部排序”中,主要探讨了数据在内存中的排序方法,这些方法通常适用于数据完全在内存中的情况。排序的目的...
例如,快速排序在大多数情况下表现优秀,而归并排序在处理大量数据时更稳定。理解并掌握这些排序算法,有助于我们根据实际需求选择最适合的排序方法,提高程序的运行效率。在实际编程中,我们还可以结合各种优化策略...
- **功能**: 输入成绩、统计总分、排序输出,需要设计高效算法处理大量数据。 6. **文章编辑器**(B级难度) - **字符串处理**: 统计字符、数字、空格数量,查找子串,删除子串,这些都涉及到字符串操作和算法。 ...
1. **稳定性**:一个排序算法是稳定的,如果在排序过程中相等的元素不会改变它们的相对顺序。例如,对于序列[5, 3, 5, 1],稳定的排序算法会保持两个5的相对位置。题目中提到的选择题涉及到了稳定性和不稳定性排序...
数据结构中的内部排序是计算机科学中处理大量数据的关键技术之一,它主要指在内存中进行的排序过程。这里我们关注的是一组特定的内部排序练习题,涉及到建立和调整堆的过程,以及堆排序算法的应用。 堆是一种特殊的...
数据结构是计算机科学中一个重要的概念,它涉及到数据的组织、管理以及存储方式。良好的数据结构知识是解决算法问题、提升程序效率的基础。 #### 基本数据结构类型 - **线性结构**:如数组、链表、栈、队列等。 - ...
- **简介**: CodeTop 是一个专注于收集各大公司常考算法题目的在线平台,支持按公司、部门、岗位分类检索题目,方便用户针对性地进行练习。 #### 其他网站 - **hihoCoder**: <https://hihocoder.com/> - **计蒜客**...
### 数据结构之折半插入排序 #### 知识点概览 1. **折半插入排序的基本概念** 2. **折半插入排序算法原理** 3. **折半插入排序的时间复杂度分析** 4. **折半插入排序的空间复杂度分析** 5. **折半插入排序与普通...
2. **排序与搜索**:如快速排序、归并排序、堆排序、二分查找、哈希查找等,这些都是解决大量数据处理问题的核心工具。 3. **动态规划**:这是解决复杂问题的有效方法,通过将大问题分解为小问题,找出最优解。 4....
2. **链表**:与数组相比,链表的元素不连续存储,每个元素(节点)包含数据和指向下一个元素的指针。链表在插入和删除时效率较高,但访问速度不如数组。 3. **栈**:是一种后进先出(LIFO)的数据结构,常用于函数...
快速排序通过分治策略高效排序大量数据;选择排序每次选择最小元素放置于序列开头,简单但效率不高;冒泡排序通过相邻元素的比较和交换来排序,也是较为基础的排序方法。 #### 排序性能比较模块 该模块专注于统计...
·自Java语言起源始,循序渐进,知识点剖析细致且每章配备大量随堂练习,让你步步为营,学得透彻、练得明白 ·拒绝晦涩难懂的呆板教学,宋老师语言生动幽默,举例形象生动深入浅出,迅速让你把握问题本质,四两拨千...
综上所述,《王道考研系列:2013年数据结构联考复习指导》是一本全面涵盖数据结构考研知识点的书籍,不仅包含了基础理论知识,还提供了大量的例题解析和模拟试题,非常适合准备参加数据结构联考的学生作为复习资料...
由于其较高的时间复杂度,对于大量数据的排序,插入排序效率较低,但当数据量较小时(如数据规模小于千量级),插入排序是一个不错的选择。 在笔试面试中,尽管插入排序的考察频度不高,但其基本概念和操作容易被...
在实际编程中,sort 排序可以帮助我们快速地对大量数据进行排序。 六、总结 sort 排序是 STL 库中的一个重要函数,它可以对数组、结构体、容器等进行排序。sort 排序的原理是使用类似于快排的方法,时间复杂度为 O...
希尔排序和基数排序在处理大量数据时表现出色;而快速排序、归并排序等算法虽未在题目中提及,但在实际工程中应用更为广泛,因其较高的效率和稳定性。理解这些排序算法的原理和优劣,有助于我们在面对具体问题时做出...
【课程设计】是学习计算机科学和技术的重要实践环节,它涵盖了数据结构、算法、网络、数据库等多个方面的知识。以下是对各个课设题目的详细解析: 1. **链表排序**: - **链表操作**:这里涉及到单链表的创建、...
- **题目:** 对处理大量数据的外存介质而言,索引顺序存取方法是一种方便的文件组织方法。 - **答案:** 正确 - **解析:** 索引顺序存取方法能够有效支持大数据量的快速访问。 **8. ISAM组织方法适用性** - **题目:...
- **第一次排序**:按照个位数排序,将所有数根据个位数的值进行分类,如将个位为 `0` 的放在一个子表中,个位为 `1` 的放在另一个子表中等。 - **第二次排序**:按照十位数排序,重复上一步操作,这次是对十位数...