- 浏览: 3290127 次
- 性别:
- 来自: 北京
文章分类
- 全部博客 (567)
- Web前端-html/表单 (19)
- Web前端-CSS (24)
- Web前端-CSS框架 (4)
- Web前端-JS语言核心 (50)
- Web前端-JS客户端 (26)
- nodejs生态+grunt (10)
- seajs和requirejs (9)
- backbone等框架 (7)
- 模板基础 (7)
- Web前端-deps(不改动) (6)
- Web前端-component (10)
- Web前端-jquery-plugin (13)
- 浏览器兼容性 (6)
- Web前端-使用jQuery (25)
- Web前端-使用jqueryui (6)
- Web前端-性能优化 (3)
- Web协议-HTTP (6)
- ExtJS (13)
- PHP (22)
- PHP面向对象 (4)
- PHP扩展-SOAP (6)
- PHP扩展-curl (4)
- PHP与HTML(导出) (5)
- PHP扩展-综合 (7)
- mysql基础应用 (18)
- 技术心情 (18)
- 算法和面试题 (17)
- 工具(开发)使用 (36)
- memcached原理 (2)
- session和cookie (4)
- UML (2)
- Web前端_FusionCharts (5)
- Web前端_Flex (4)
- Web前端_JSP (3)
- JavaSE (10)
- JavaEE (4)
- tomcat (2)
- Servlet开发 (3)
- Spring开发 (1)
- REST相关 (2)
- 大访问量、高并发 (2)
- 网络编程 (1)
- YII (21)
- linux命令和内核 (12)
- yii与数据库 (10)
- yii与表单 (12)
- yii view层 (1)
- perl (7)
- yii扩展 (7)
- shell (4)
- photoshop (7)
- 视觉设计 (2)
- 我关注的名人在路上 (4)
- 1-自学能力 (1)
- 2-人际沟通能力 (3)
- 3-职业规划能力 (7)
- 4-项目管理能力 (2)
- python (3)
- django (4)
- Mysql高级应用 (6)
- prototype.js (4)
- Web系统安全 (1)
- Web前端-mobile (2)
- egret (6)
- jQuery源码分析 (5)
- fis (4)
最新评论
-
yzq21056563:
感谢作者分享~请教下,http://www.lisa33xia ...
CSS基础:text-overflow:ellipsis溢出文本 -
u012206458:
$.ajax的error,complete,success方法 -
DEMONU:
谢谢,虽然不能给你赞助,但是要给你顶
mysql中key 、primary key 、unique key 与index区别 -
njupt_tolmes:
阿凡达阿凡达阿凡达阿凡达阿凡达阿凡达阿凡达阿凡达阿凡达阿滕庆亚 ...
CSS基础:text-overflow:ellipsis溢出文本 -
zenmshuo:
用过SpreadJS,也包含数据可视化的图表
推荐几个web中常用js图表插件
zccst转载
一、问题描述
有一个大文件,里面有十亿个字符串,乱序的,要求将这些字符串以字典的顺序排好序
二、解决思路
将大文件切割成小文件,每个小文件内归并排序;
对所有的小文件进行归并排序——多重归并排序
三、解决方案
3.1 模拟产生10亿个随机字符
3.2 对大文件进行切割
3.3 对小文件进行递归归并
3.4 运行结果分析
①生成10亿个随机字符串,时间太久了,,字符串长度随机在[1,20]之间时,文件大小大概在10.7 GB (11,500,161,591 字节)
② 切割成小文件,小文件内归并排序,每个文件内的数据100万条时,随机选取五个排序时间如下:
一共发生了410832612 次对比一共发生了 899862656 次交换执行时间为3545毫秒
一共发生了429506513 次对比一共发生了 940765504 次交换执行时间为3512毫秒
一共发生了448181315 次对比一共发生了 981668352 次交换执行时间为3497毫秒
一共发生了466856137 次对比一共发生了 1022571200 次交换执行时间为3497毫秒
一共发生了485530473 次对比一共发生了 1063474048 次交换执行时间为3981毫秒
总共1000个文件切割耗时为
切割小文件所用时间--->4341734ms--->4341.734s--->72.36m--->1.206h
③ 小文件递归归并,1000个文件,
共发生了10次归并,
产生临时文件总共1999个,
总大小为127.8 GB (137,201,789,278 字节),
产生结果文件11.6 GB (12,500,161,591 字节)
比源文件多了10亿个字节......
总耗时为--->7374129ms--->7374.129s--->122.9m--->2.048h
不得不提的是,最后执行结果成功,也不枉我苦苦等待
四、相关技术
4.1 归并排序
排序原理不多介绍,各种到处都有,如果一时不记得,看下面的原理图。秒懂。
4.2 文件读写
本程序很重要的一点就是对于文件的读写,Buffer的文件读写可以很大程度的改善速率
写操作:
BufferedWriter writer = new BufferedWriter(new FileWriter(PATH));
writer.write("hhf\n");
读操作:
BufferedReader br = new BufferedReader(new FileReader(PATH));
text = br.readLine()
五、关于优化
5.1分小文件时优化
前提:数据均匀,保证每个小文件大小不会超过内存的容量
处理:在分数据到小文件时,按字符串按首字母将其分到指定文件中,如A-C分配到1.txt,D-F分配到2.txt.......
优点:只需要小文件内数据排序,排序号后,即可将1.txt、2.txt、3.txt直接连接起来,极大的缩短了归并时间,相当于把递归归并变成了文件连接而已
缺点:前提不是很容易把握,若有一个小文件内的数据量大于内存的大小,则排序失败,存在一定的风险
5.2小文件内排序时优化
前提:保证每个小文件内数据量比较不是特别的大
处理:将小文件内的数据进行快速排序
优点:快排的时间效率是高于归并的
以下是测试数据
排序数量级 10 1000 100000
归并排序7ms 71ms 3331ms
快速排序6ms 52ms java.lang.StackOverflowError
缺点:缺点已经显示在测试数据内了,小文件内的数据量过大就可能导致当前线程的栈满
(附上源代码工程:Merge.zip)
一、问题描述
有一个大文件,里面有十亿个字符串,乱序的,要求将这些字符串以字典的顺序排好序
二、解决思路
将大文件切割成小文件,每个小文件内归并排序;
对所有的小文件进行归并排序——多重归并排序
三、解决方案
3.1 模拟产生10亿个随机字符
public static void generateDate() throws IOException { BufferedWriter writer = new BufferedWriter(new FileWriter(ORIGINALPATH)); Random random = new Random(); StringBuffer buffer = new StringBuffer( "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"); int range = buffer.length(); int length = 1; for (int i = 0; i < BIGDATALENGTH; i++) { StringBuffer sb = new StringBuffer(); length = random.nextInt(20)+1; //System.out.println("length--->"+length); for (int j = 0; j < length; j++) { //System.out.println("j--->"+j); sb.append(buffer.charAt(random.nextInt(range))); } System.out.println("sb---->"+sb); writer.write(sb.toString() + "\n"); } writer.close(); }
3.2 对大文件进行切割
/** * 将原始数据分成几块 并排序 再保存到临时文件 * @throws IOException */ public static void splitData() throws IOException { @SuppressWarnings("resource") BufferedReader br = new BufferedReader(new FileReader(ORIGINALPATH)); tempFiles = new File[BIGDATALENGTH / TEMPFILELENGTH];//将会产生的临时文件列表 for (int i = 0; i < tempFiles.length; i++) { tempFiles[i] = new File(TEMPFILEPATH + "TempFile" + i + ".txt"); BufferedWriter writer = new BufferedWriter(new FileWriter(tempFiles[i])); HashMap<Integer,String> hashMap = new HashMap<Integer,String>();//未排序 //每次读出TEMPFILELENGTH个文件 保存到smallLine中 for (int j = 1; j <= TEMPFILELENGTH; j++) { String text = null; if ((text = br.readLine()) != null) { hashMap.put(j, text); } } hashMap = MergeSort.sort(hashMap); for(int k=1; k<=TEMPFILELENGTH; k++){ writer.write(String.valueOf(hashMap.get(k)) + System.getProperty("line.separator")); //System.getProperty("line.separator")相当于\n } writer.close(); } }
3.3 对小文件进行递归归并
/** * 多路归并排序 * @param files * @throws IOException */ public static void multiWaysMergeSort(String[] files) throws IOException { System.out.println("归并文件-----第 "+mergeSortCount+" 次-----"); //当最后只有一个文件的时候 数据已经排序成功 直接复制保存到结果文件 if (files.length == 1) { String lastFilePath = LASTFILEPATH + LASTFILENAME; copyFile(files[0], lastFilePath, false); //deleteFile(files[0]); return; } for (int i = 0; i < files.length; i+=2) { //开始合并两个相邻的文件 所以一次跳两个 if (i == files.length - 1) { //这时候已经只剩下最后一个文件了 不需要合并 本趟归并结束 renameFile(files[i], i); break; } //将br1 和 br2 写入到Write BufferedReader br1 = new BufferedReader(new FileReader(files[i])); BufferedReader br2 = new BufferedReader(new FileReader(files[i + 1])); BufferedWriter writer = new BufferedWriter(new FileWriter(TEMPFILEPATH + "last_" + mergeSortCount + "_" + i + ".txt")); String s1 = br1.readLine(); String s2 = br2.readLine(); while (s1 != null || s2 != null) { if (s1 != null && s2 != null) { //都不为空 才有比较的必要 int mergeResult = s1.compareTo(s2); if (mergeResult > 0) {//s1在s2后面 writer.write(s2); writer.write(System.getProperty("line.separator")); s2 = br2.readLine(); } if (mergeResult == 0) {//s1=s2 writer.write(s1); writer.write(System.getProperty("line.separator")); writer.write(s2); writer.write(System.getProperty("line.separator")); //System.out.println("write time : " + writeTime++); s1 = br1.readLine(); s2 = br2.readLine(); } if (mergeResult < 0) {//s1在s2前面 writer.write(s1); writer.write(System.getProperty("line.separator")); s1 = br1.readLine(); } } if (s1 == null && s2 != null) { writer.write(s2); writer.write(System.getProperty("line.separator")); s2 = br2.readLine(); } if (s2 == null && s1 != null) { writer.write(s1); writer.write(System.getProperty("line.separator")); s1 = br1.readLine(); } } br1.close(); br2.close(); // deleteFile(files[i]); // deleteFile(files[i + 1]); writer.close(); } mergeSortCount++; multiWaysMergeSort(getTempFiles("last_" + (mergeSortCount-1) + "_")); }
3.4 运行结果分析
①生成10亿个随机字符串,时间太久了,,字符串长度随机在[1,20]之间时,文件大小大概在10.7 GB (11,500,161,591 字节)
② 切割成小文件,小文件内归并排序,每个文件内的数据100万条时,随机选取五个排序时间如下:
一共发生了410832612 次对比一共发生了 899862656 次交换执行时间为3545毫秒
一共发生了429506513 次对比一共发生了 940765504 次交换执行时间为3512毫秒
一共发生了448181315 次对比一共发生了 981668352 次交换执行时间为3497毫秒
一共发生了466856137 次对比一共发生了 1022571200 次交换执行时间为3497毫秒
一共发生了485530473 次对比一共发生了 1063474048 次交换执行时间为3981毫秒
总共1000个文件切割耗时为
切割小文件所用时间--->4341734ms--->4341.734s--->72.36m--->1.206h
③ 小文件递归归并,1000个文件,
共发生了10次归并,
产生临时文件总共1999个,
总大小为127.8 GB (137,201,789,278 字节),
产生结果文件11.6 GB (12,500,161,591 字节)
比源文件多了10亿个字节......
总耗时为--->7374129ms--->7374.129s--->122.9m--->2.048h
不得不提的是,最后执行结果成功,也不枉我苦苦等待
四、相关技术
4.1 归并排序
排序原理不多介绍,各种到处都有,如果一时不记得,看下面的原理图。秒懂。
4.2 文件读写
本程序很重要的一点就是对于文件的读写,Buffer的文件读写可以很大程度的改善速率
写操作:
BufferedWriter writer = new BufferedWriter(new FileWriter(PATH));
writer.write("hhf\n");
读操作:
BufferedReader br = new BufferedReader(new FileReader(PATH));
text = br.readLine()
五、关于优化
5.1分小文件时优化
前提:数据均匀,保证每个小文件大小不会超过内存的容量
处理:在分数据到小文件时,按字符串按首字母将其分到指定文件中,如A-C分配到1.txt,D-F分配到2.txt.......
优点:只需要小文件内数据排序,排序号后,即可将1.txt、2.txt、3.txt直接连接起来,极大的缩短了归并时间,相当于把递归归并变成了文件连接而已
缺点:前提不是很容易把握,若有一个小文件内的数据量大于内存的大小,则排序失败,存在一定的风险
5.2小文件内排序时优化
前提:保证每个小文件内数据量比较不是特别的大
处理:将小文件内的数据进行快速排序
优点:快排的时间效率是高于归并的
以下是测试数据
排序数量级 10 1000 100000
归并排序7ms 71ms 3331ms
快速排序6ms 52ms java.lang.StackOverflowError
缺点:缺点已经显示在测试数据内了,小文件内的数据量过大就可能导致当前线程的栈满
(附上源代码工程:Merge.zip)
发表评论
-
面试题201412——html5 本地存储
2014-12-23 14:58 731作者:zccst 一、LocalStorage 和 sess ... -
面试题201412——client DOM操作和CSS操作
2014-12-17 23:28 1624作者:zccst 一、DOM操作文档树 其实对于DOM系列 ... -
面试题201412——client 脚本化HTTP
2014-12-17 00:22 952作者:zccst Ajax的缺 ... -
面试题201412——core 小算法
2014-12-17 00:22 1057作者:zccst 给数组添加一个去重方法 计算字符串的字 ... -
面试题201412——client 事件
2014-12-17 00:23 1339作者:zccst 如何在i ... -
面试题201412——CSS
2014-12-17 00:24 749作者:zccst CSS的优先级?内联和important哪 ... -
面试题201412——HTML
2014-12-16 21:51 599作者:zccst 严格模式与混杂模式的区分?如何触发这两种模 ... -
面试题201412——杂项待整理
2014-12-16 20:28 580zccst js 1,跨域 2,eval 3 ... -
面试题201412——core this作用域
2014-12-16 17:43 1194作者:zccst 二、setTimeout与while的执 ... -
面试题201412——core 变量作用域
2014-12-16 16:32 1019作者:zccst 1,var a = b = 5; (f ... -
10亿个字符串的排序问题
2014-12-15 15:33 8zccst转载 一、问题描述 有一个大文件,里面有十亿个字符串 ... -
删除数组中的某一个元素
2014-08-01 15:36 0作者:zccst 首先定义一个数组如果 var a = ... -
计算字符串中每个字符出现的次数
2014-08-04 18:30 2127思想原理:把字符串分割为数组,粒度为每一个字符。循环该数组,用 ... -
$("div")和getElementsByTagName("div")区别
2014-08-01 15:22 881作者:zccst <body> < ... -
程序设计模型——向导模型(Wizard model)
2012-08-28 22:39 1778程序设计模型——向导模型(Wizard model) 作者:z ... -
B+树
2011-05-12 22:08 1611一棵m阶的B树满足下列 ... -
堆排序与快速排序的区别及js实现
2011-04-19 23:32 15091,快速排序 核心要点:1,选基础参考点;2,递归 fu ... -
几个算法或逻辑题
2011-04-15 12:59 1215作者:zccst 2014-6-14 PHP 在数值中加入千 ...
相关推荐
应用中,经常需要将字符串压缩成一个整数,即字符串散列。比如下面这些问题: (1)搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来,每个查询串的长度为1-255字节。请找出最热门的10个检索串。 ...
单击即可添加一个自定义的字符串 在所选文本的前后分别添加自定义的字符串 12. 正则表达式 用正则表达式查找/替换多行文本 13. 脚本文件 可以把常用的正则表达式定义在脚本中,直接运行脚本即可替换文字 14. ...
>单击即可添加一个自定义的字符串 >在所选文本的前后分别添加自定义的字符串 12、正则表达式 >用正则表达式查找/替换多行文本 13、脚本文件 >可以把常用的正则表达式定义在脚本中,直接运行脚本...
>单击即可添加一个自定义的字符串 >在所选文本的前后分别添加自定义的字符串 12. 正则表达式 >用正则表达式查找/替换多行文本 13. 脚本文件 >可以把常用的正则表达式定义在脚本中,直接运行脚本即可替换文字 14. 256...
1.<征集答案>给你10台机器,每个机器2个cpu,2g内存,现在已知在10亿条记录的数据库里执行一次查询需要5秒,问用什么方法能让90%的查询能在100毫秒以内返回结果。 2.一个长度为10000的字符串,写一个算法,找出最长...
其中x为字符串/url/ip,m为⼩问题的数⽬,⽐如把⼀个⼤⽂件分解为1000份,m=1000; (4)解决问题辅助数据结构:hash_map,Trie树,bit map,⼆叉排序树(AVL,SBT,红⿊树); (5)top K问题:最⼤K个⽤最⼩堆,最...
2).1000万字符串,其中有些是相同的(重复),需要把重复的全部去掉,保留没有重复的字符串。请问怎么设计和实现? 3).寻找热门查询:查询串的重复度⽐较⾼,虽然总数是1千万,但如果除去重复后,不超过3百万个,每个...
3、编写一个截取字符串的函数,输入为一个字符串和字节数,输出为按字节截取的字符串,但要保证汉字不被截取半个,如“我ABC”,4,应该截取“我AB”,输入“我ABC汉DEF”,6,应该输出“我ABC”,而不是“我ABC+汉...
3、编写一个截取字符串的函数,输入为一个字符串和字节数,输出为按字节截取的字符串,但要保证汉字不被截取半个,如“我ABC”,4,应该截取“我AB”,输入“我ABC汉DEF”,6,应该输出“我ABC”,而不是“我ABC+汉...
3、编写一个截取字符串的函数,输入为一个字符串和字节数,输出为按字节截取的字符串,但要保证汉字不被截取半个,如“我ABC”,4,应该截取“我AB”,输入“我ABC汉DEF”,6,应该输出“我ABC”,而不是“我ABC+汉...
3、编写一个截取字符串的函数,输入为一个字符串和字节数,输出为按字节截取的字符串,但要保证汉字不被截取半个,如“我ABC”,4,应该截取“我AB”,输入“我ABC汉DEF”,6,应该输出“我ABC”,而不是“我ABC+汉...
3、编写一个截取字符串的函数,输入为一个字符串和字节数,输出为按字节截取的字符串,但要保证汉字不被截取半个,如“我ABC”,4,应该截取“我AB”,输入“我ABC汉DEF”,6,应该输出“我ABC”,而不是“我ABC+汉...
3、编写一个截取字符串的函数,输入为一个字符串和字节数,输出为按字节截取的字符串,但要保证汉字不被截取半个,如“我ABC”,4,应该截取“我AB”,输入“我ABC汉DEF”,6,应该输出“我ABC”,而不是“我ABC+汉...
3、编写一个截取字符串的函数,输入为一个字符串和字节数,输出为按字节截取的字符串,但要保证汉字不被截取半个,如“我ABC”,4,应该截取“我AB”,输入“我ABC汉DEF”,6,应该输出“我ABC”,而不是“我ABC+汉...
3、编写一个截取字符串的函数,输入为一个字符串和字节数,输出为按字节截取的字符串,但要保证汉字不被截取半个,如“我ABC”,4,应该截取“我AB”,输入“我ABC汉DEF”,6,应该输出“我ABC”,而不是“我ABC+汉...
3、编写一个截取字符串的函数,输入为一个字符串和字节数,输出为按字节截取的字符串,但要保证汉字不被截取半个,如“我ABC”,4,应该截取“我AB”,输入“我ABC汉DEF”,6,应该输出“我ABC”,而不是“我ABC+汉...
1.5.7. 输入一个表示整数的字符串,把该字符串转换成整数并输出.............. 118 1.5.8. 给出一个数列,找出其中最长的单调递减(或递增)子序列..............121 1.5.9. 四对括号可以有多少种匹配排列方式........