- 浏览: 100006 次
- 性别:
- 来自: 西安
文章分类
最新评论
-
feikiss:
wuchsh2013 写道英文水平很牛逼。不敢当。。。小儿科- ...
java socket performance investigation -
wuchsh2013:
英文水平很牛逼。
java socket performance investigation -
feikiss:
随着业务逻辑的深入,重构也会无处不在。
测试驱动开发的实践 -
feikiss:
li498833284 写道不好意思阿 ,发了点测试用的东西, ...
头疼的快捷键 -
li498833284:
不好意思阿 ,发了点测试用的东西,别介意呀
头疼的快捷键
前两天看到一哥们百度面试归来后发的帖子,并分享了其百度面试题,其中有一个题大意如下:
现有两个上亿行的文件,每一行都只有一个数字,求这两个文件的交集。
我的思路如下:首先是分别对这两个文件排序,然后,再同时遍历这两个文件。求出交集即可。
下面我对大文件的排序进行了简单的实现。
基本思路如下,首先对大文件进行拆分,一亿行的大文件可以拆分成10个小文件,并分别对这10个小文件进行排序,之后对这10个有序的小文件进行遍历,比较,再合并成一个大文件即可完成排序。
里面文件的路径为D://bigfile
代码如下。
main函数在bigFile中。
SourceFolder.java: 主要负责对文件夹下拆分后的小文件进行比较并合并成一个新的有序文件。
FileGenerator.java主要是负责将生成好的链表写入到一指定的文件中,可以选择是覆盖文件或者是在文件后添加。里面也有生成上亿行文件的方法(测试时可以事先用此方法生成大文件。 : ) ).
至此,完成了大文件的排序。至于下一步就是对着两个有序的大文件进行遍历比较了,
1.两个索引分别指向两个大文件的第一行。
2.如果两个索引所指的数据一样,记录当前数据到新的文件,并将两个指针分别下移一位。
如果二者不相等,则将数据较小的指针下移一位。
3.判断是否到其中一个文件的结尾,如果是,结束比较,否则重复步骤2。
这样就可以取出二者的交集,代码到此结束。
现有两个上亿行的文件,每一行都只有一个数字,求这两个文件的交集。
我的思路如下:首先是分别对这两个文件排序,然后,再同时遍历这两个文件。求出交集即可。
下面我对大文件的排序进行了简单的实现。
基本思路如下,首先对大文件进行拆分,一亿行的大文件可以拆分成10个小文件,并分别对这10个小文件进行排序,之后对这10个有序的小文件进行遍历,比较,再合并成一个大文件即可完成排序。
里面文件的路径为D://bigfile
代码如下。
main函数在bigFile中。
package com.fly.lee.bigfile; import java.io.BufferedReader; import java.io.File; import java.io.FileReader; import java.util.ArrayList; import java.util.Collections; import java.util.List; public class BigFile { private List<String> subFileNameList = new ArrayList<String>(); private String bigFilePath = "D:/bigfile/"; private String bigFileName = "Source1.txt"; private FileGenerator fGenerator = new FileGenerator(); private static final int theMaxNumber = 10000000; private List<Integer> theContentWritingToSubFile = new ArrayList<Integer>(theMaxNumber); public void sortTheBigfile(String destination){ splitTheBigFile(); SourceFolder sFolder = new SourceFolder(); sFolder.setFilenameList(subFileNameList); sFolder.setDestination(destination); try { sFolder.compareFiles(); } catch (Exception e) { // TODO Auto-generated catch block e.printStackTrace(); } removeTheSubFiles(); } public void setBigFilePath(String bigFilePath) { this.bigFilePath = bigFilePath; } public void setBigFileName(String bigFileName) { this.bigFileName = bigFileName; } private void removeTheSubFiles() { for(String fileName:subFileNameList){ File file = new File(fileName); if(file.exists()&&file.canWrite()){ System.out.println(fileName+":"+file.delete());; } } } public void splitTheBigFile(){ System.out.println("begin to spliting the big files..."); int counter = 0; File file = new File(bigFilePath+bigFileName); BufferedReader reader = null; FileReader fReader; int fileFlag = 1; try { fReader = new FileReader(file); reader = new BufferedReader(fReader); String tempString = null; while ((tempString = reader.readLine()) != null) { if(tempString.trim().equals("")){ break; } int tempInt = Integer.valueOf(tempString); theContentWritingToSubFile.add(tempInt); if(isTheListFull(counter)){ handleTheFullList(fileFlag); theContentWritingToSubFile.clear(); fileFlag ++; } } handleTheFullList(fileFlag); fReader.close(); reader.close(); System.out.println("finishing the spliting work."); }catch(Exception e){ e.printStackTrace(); } } private void handleTheFullList(int fileFlag) throws Exception { System.out.println("handle the full list..."); String tempFilePath = bigFilePath + fileFlag + ".txt"; writeTheContentToSubFile(tempFilePath); subFileNameList.add(tempFilePath); theContentWritingToSubFile.clear(); System.out.println("the full list is clear now..."); } private void writeTheContentToSubFile(String tempFilePath) throws Exception { System.out.println("begin to write the content to sub file..."); System.out.println("sub file path:"+tempFilePath); Collections.sort(theContentWritingToSubFile); fGenerator.setFileName(tempFilePath); fGenerator.setTheListNeedToWriteTofile(theContentWritingToSubFile); fGenerator.writeToFileFromTheList(true); System.out.println("finishing this loop of writing the content to sub file..."); } private boolean isTheListFull(int counter) { return theContentWritingToSubFile.size() >= theMaxNumber; } public static void main(String[] args) { BigFile bf = new BigFile(); bf.setBigFileName("Source1.txt"); bf.sortTheBigfile("D:/bigfile/Source1_sorted.txt"); } }
SourceFolder.java: 主要负责对文件夹下拆分后的小文件进行比较并合并成一个新的有序文件。
package com.fly.lee.bigfile; import java.io.BufferedReader; import java.io.FileNotFoundException; import java.io.FileReader; import java.io.IOException; import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; public class SourceFolder { private List<String> filenameList; private Map<Integer, Integer> numberCache; private List<BufferedReader> bufferedReaderList; private int endFlagNumber = 0; private List<Integer> contentListWritingToFile; private FileGenerator fileGenerator; private String destination = "D:/bigfile/AllSource.txt"; public SourceFolder() { contentListWritingToFile = new ArrayList<Integer>(); filenameList = new ArrayList<String>(); bufferedReaderList = new ArrayList<BufferedReader>(); fileGenerator = new FileGenerator(); } public void setDestination(String destination) { this.destination = destination; } public void addFile(String filename) { this.filenameList.add(filename); } public void setFilenameList(List<String> filenameList) { this.filenameList = filenameList; } public void compareFiles() throws Exception { System.out.println("filenameList:"+filenameList); initTheBufferedReaderList(); initTheNumberCache(); while(!isAllFilesFinishTheComparing()){ int theIndexOfReaderNeedingToMove = findTheLastIndexOfTheMinNumber(); addTheNumberToFile(theIndexOfReaderNeedingToMove); updateNumberCache(theIndexOfReaderNeedingToMove); } addTheLastListToFile(); closeAllIOStreams(); } private void closeAllIOStreams() throws IOException { for(BufferedReader bReader:bufferedReaderList){ if(bReader != null){ bReader.close(); } } } private int findTheLastIndexOfTheMinNumber() { int theIndexOfTheMinNumber = 0; int mixNumber = getTheFirstNumberFromTheCache(); for (int index = 0; index < numberCache.size(); index++) { if(numberCache.get(index) == null){ continue; } int theNumberWillBeCompared = numberCache.get(index); if (mixNumber >= theNumberWillBeCompared) { mixNumber = theNumberWillBeCompared; theIndexOfTheMinNumber = index; } } return theIndexOfTheMinNumber; } private int getTheFirstNumberFromTheCache() { for (int index = 0; index < numberCache.size(); index++) { if(numberCache.get(index) == null){ continue; } return numberCache.get(index); } return 0; } private void addTheNumberToFile(int theIndexOfReaderNeedingToMove) throws Exception { contentListWritingToFile.add(numberCache.get(theIndexOfReaderNeedingToMove)); if(contentListWritingToFile.size() == 1000000){ fileGenerator.setTheListNeedToWriteTofile(contentListWritingToFile); fileGenerator.setFileName(destination); fileGenerator.writeToFileFromTheList( false); contentListWritingToFile.clear(); } } private void updateNumberCache(int index) throws Exception { BufferedReader bufferedReader = bufferedReaderList.get(index); String tempString = null; if ((tempString = bufferedReader.readLine()) != null) { if (!"".equals(tempString.trim())) { int tempInt = Integer.valueOf(tempString); numberCache.put(index, tempInt); } } else { numberCache.put(index, null); endFlagNumber ++; } } private void addTheLastListToFile() throws Exception { fileGenerator.setTheListNeedToWriteTofile(contentListWritingToFile); fileGenerator.setFileName(destination); fileGenerator.writeToFileFromTheList(false); } private void initTheBufferedReaderList() throws FileNotFoundException { System.out.println("begin to initial the buffered reader..."); for (String filename : filenameList) { BufferedReader bufferedReader = new BufferedReader(new FileReader( filename)); bufferedReaderList.add(bufferedReader); } System.out.println("finish initialing the buffered reader..."); } private void initTheNumberCache() throws Exception { System.out.println("begin to initial the number cache..."); numberCache = new HashMap<Integer, Integer>(filenameList.size()); for (int index = 0; index < filenameList.size(); index++) { updateNumberCache(index); } System.out.println("finish initialing the number cache..."); } private boolean isAllFilesFinishTheComparing() { return endFlagNumber == filenameList.size(); } }
FileGenerator.java主要是负责将生成好的链表写入到一指定的文件中,可以选择是覆盖文件或者是在文件后添加。里面也有生成上亿行文件的方法(测试时可以事先用此方法生成大文件。 : ) ).
package com.fly.lee.bigfile; import java.io.File; import java.io.FileWriter; import java.io.IOException; import java.util.ArrayList; import java.util.List; public class FileGenerator { private int wholeLineNumber = 100000000; private List<Integer> theListNeedToWriteTofile; private String fileName; private FileWriter fWriter = null; // public void write public static void main(String[] args) { String fileName = "D:/bigfile/Source_yiwan.txt"; FileGenerator fileGenerator = new FileGenerator(); fileGenerator.setFileName(fileName); try { fileGenerator.createRandomFile(); fileGenerator.closeFileWriter(); } catch (Exception e) { e.printStackTrace(); } } public void setFileName(String fileName) { this.fileName = fileName; } public void setWholeLineNumber(int wholeLineNumber) { this.wholeLineNumber = wholeLineNumber; } public void setTheListNeedToWriteTofile(List<Integer> theListNeedToWriteTofile) { this.theListNeedToWriteTofile = theListNeedToWriteTofile; } public void createRandomFile() throws Exception { int listSize = 10000000; theListNeedToWriteTofile = new ArrayList<Integer>(listSize); for(int i = 0; i < wholeLineNumber; i ++){ int tempRandomInt = (int)(Math.random()*100000000); theListNeedToWriteTofile.add(tempRandomInt); if(theListNeedToWriteTofile.size()==listSize){ System.out.println("begin to write to the file..."); writeToFileFromTheList(false); theListNeedToWriteTofile.clear(); System.out.println("finish this loop..."); } } writeToFileFromTheList(false); } public void writeToFileFromTheList(boolean isNeedToCreateNewFile) throws Exception { System.out.println("write the content to file..."); try { if(isNeedToCreateNewFile){ createNewFile(fileName); } StringBuilder contentWritingToFile = new StringBuilder(); int cycleLineNumber = 1000000; int counter = 0; fWriter = new FileWriter(fileName,true); for(int index = 0; index < theListNeedToWriteTofile.size(); index ++){ int tempRandomInt = theListNeedToWriteTofile.get(index); contentWritingToFile.append(tempRandomInt+"\n"); if(counter == cycleLineNumber){ fWriter.append(contentWritingToFile.toString()); counter = 0; contentWritingToFile = new StringBuilder(); } } // while(theListNeedToWriteTofile.size() != 0){ // int tempRandomInt = theListNeedToWriteTofile.remove(0); // contentWritingToFile.append(tempRandomInt+"\n"); // if(counter == cycleLineNumber){ // fWriter.append(contentWritingToFile.toString()); // counter = 0; // contentWritingToFile = new StringBuilder(); // } // } fWriter.append(contentWritingToFile.toString()); System.out.println("done.........."); } catch (Exception e) { // TODO Auto-generated catch block e.printStackTrace(); } finally{ closeFileWriter(); } } private void closeFileWriter() throws IOException{ if(fWriter != null){ fWriter.close(); } } private void createNewFile(String fileName) throws IOException { File file = new File(fileName); if(file.delete()){ file.createNewFile(); } } }
至此,完成了大文件的排序。至于下一步就是对着两个有序的大文件进行遍历比较了,
1.两个索引分别指向两个大文件的第一行。
2.如果两个索引所指的数据一样,记录当前数据到新的文件,并将两个指针分别下移一位。
如果二者不相等,则将数据较小的指针下移一位。
3.判断是否到其中一个文件的结尾,如果是,结束比较,否则重复步骤2。
这样就可以取出二者的交集,代码到此结束。
发表评论
-
(Java)墙内利用goagent调用facebook API 进行Java应用开发
2013-08-12 20:21 3266今天花费了一下午的时 ... -
java socket performance investigation
2013-07-17 18:26 1678these days I'm confused about t ... -
[java] change the env in java code
2013-05-30 17:04 1102In Java API, there is the metho ... -
[unit test] how to test real-time based method. (for example new Date() )
2013-05-30 16:59 1443While we are writing the unit t ... -
日常笔记(持续更新记录中)
2012-12-03 18:44 1344以此作为笔记,记录一 ... -
Java client端如何判断server端socket是否已经断开
2012-06-11 15:10 4309最近在开发中遇到一个问题,就是如何判断远端服务器是否已经断开连 ... -
Java中反射机制探索
2012-03-07 10:34 1431忙里偷闲,做了一些反 ... -
(转载)Java中对HashMap的深度分析
2012-03-01 23:01 920原文地址:http://developer ... -
HashMap 中的keySet()和entrySet()方法的比较
2012-02-10 16:18 7756在用Coverity(代码检视工 ... -
Effective java: 覆盖equals时总要覆盖hashCode 的探究
2011-12-15 17:33 2391在Effective Java中的第九条说:覆盖equals总 ... -
Java中new Integer() 和Integer.valueOf()二者效率的比较
2011-11-30 11:02 5637最近在公司参与一个项 ...
相关推荐
1. **交集(Intersection)**:两个DataTable中都存在的行集合。 2. **并集(Union)**:包含两个DataTable所有不重复行的集合。 3. **差集(Difference)**:在一个DataTable中存在的,但在另一个DataTable中不存在...
在计算机科学和地理信息系统(GIS)中,计算两个点集构成的封闭图形的交集是一项常见的几何操作。这个过程涉及到几何对象的操作,如线、多边形和点,以及它们之间的关系判断。以下是对这个任务的详细解释: 首先,...
5. **计算交集**:有了两个图形的轮廓后,我们可以进行布尔运算,例如使用`bitwise_and()`函数计算两个图形的交集。这个函数会按像素级别进行比较,返回的结果是两个图形重叠部分的像素值。 6. **结果展示**:最后...
有2个txt文件:qq1.txt和qq2.txt,现用vbs代码实现:提取两者的交集保存为qq3.txt
本文实例讲述了Python实现求两个csv文件交集的方法。分享给大家供大家参考,具体如下: #!/usr/bin/env python rd3 = open('data_17_17_2.csv') base = open('data_17_17_3.csv') wr3 = open('delNoBuyed3...
例如,逻辑表达式 (A ∧ B) ∨ (¬C ∧ D) 是一个合取范式,其中 (A ∧ B) 和 (¬C ∧ D) 是两个子句。 析取范式则是由一个或多个子句的析取(OR)组成,每个子句是若干个变量或其否定的合取(AND)。例如,(A ∨ B...
本示例将深入探讨如何找到两个数组的交集。交集是指存在于两个数组中的共同元素,它可以帮助我们进行数据过滤和分析。让我们首先从`main.js`文件中的代码开始。 在`main.js`中,我们可能会看到以下用于找出两个数组...
在数学中,交集(Intersection)和并集(Union)是集合论的基本概念,用于描述两个或多个集合之间元素的共享关系。交集表示两个集合共同拥有的元素组成的集合,而并集则包含两个集合中所有的元素,不区分重复。 在...
这个压缩包文件“2_链表_求la和lb的交集_源码.zip”似乎包含了一个关于如何寻找两个链表(称为la和lb)交集的源代码实现。下面我们将深入探讨链表以及如何找到它们的交集。 首先,让我们理解链表的基本概念。链表...
交集(Intersection)是指两个集合中都存在的元素组成的集合,而并集(Union)则是将两个集合中的所有元素合并,不考虑重复。 在单链表中实现这些操作,我们需要遍历两个链表,并进行适当的比较和操作。以下是一个...
例如,对于两个有序表A和B,要找到它们的交集,我们只需从较小的表开始,逐个比较元素,如果元素同时存在于两个表中,就将其添加到结果集中。对于并集,我们可以简单地将两个表连接起来,然后去重,保持原有的排序...
这是一份手游《野蛮时代》的用户数据,共有训练集...数据处理:将两个数据文件合并,只取分析要用的字段。然后把数据写到 mysql。 >只取用于分析的字段,因为字段数太多,去掉没用的字段可以极大的节省内存和提高效率
根据提供的文件信息,本文将详细解释“时间区间取并集Oracle存储过程算法实现”的核心概念、设计思路以及具体实现步骤。 ### 一、背景与需求分析 在许多业务场景中,比如日程管理、时间线合并等,我们需要对一系列...
在此代码段中,首先将两个Series对象转换为集合,然后使用intersection方法求出两个集合的交集。交集结果又被转换为一个Series对象,该对象最后被保存为CSV文件。这里还展示了如何将Python集合中的元素提取到一个...
“取数组内容异同”通常指的是比较两个数组之间的差异。在实际编程中,可能存在多种情况:元素个数不同、元素值不同、部分元素相同等。下面是一些处理这类问题的常见方法: 1. **循环遍历法**:通过两个for循环分别...
3. 交集计算:Rhino中,当两个自由曲面相交时,Rhino会准确的依据用户所设置的公差值生成相交线。Rhino 默认的精度(公差)为 1/100 mm。 Rhino转换 Catia 文件时,我们需要注意模型的封闭性、破面的问题、精度问题...
若关注的是只在一个数组中存在的元素,可以使用“并集”和“差集”的概念,即找出两个数组的元素之并,然后减去交集,得到的就是差异元素。 四、易语言取数组内容异同源码 易语言的源码可能包含以下部分: 1. 定义...
- 大小、小大取交集:如果两个不等式中一个是“大于”另一个是“小于”,解集取两者解集的交集部分。 6. 课堂应用:通过在数轴上表示不等式的解集,学生可以更加直观地掌握一元一次不等式组的概念,理解解集的含义...
在比较两个大文件时,我们可以先将每个文件中的数据读取到两个列表(list)中,然后转换成集合,最后通过集合的`difference`方法来找出两个集合的差集,即两个文件中不同之处。 以下是一个简单的Python代码示例,展示...
- 输入文件为`input.txt`,包含多组测试数据,每组数据由两行组成,每行包含两个整数,分别表示一个区间的端点。 - 文件中的每个整数范围在`1`至`1,000,000`之间。 **输出格式**: 对于每组测试数据,输出一个整数...