往事看到一道支付宝笔试题,自己做了一下,尽管效率不高,也是个人思考的结果。题目如下:
有一个100G大小的文件里存的全是数字,并且每个数字见用逗号隔开。现在在这一大堆数字中找出100个最大的数出来。
做法:
假设数字为4字节整数,逗号为2字节unicode字符,100G文件本人电脑无法容纳,所以取2亿整数,文件大小1.2G
1. 生成二进制文件(使用DataOutputStream,使用缓冲区,耗时79秒):
File file = new File("E:\\test.dat"); if (!file.exists()) { file.createNewFile(); } long time = System.currentTimeMillis(); DataOutputStream stream = new DataOutputStream(new BufferedOutputStream(new FileOutputStream(file))); Random random = new Random(); long count = 200000000; System.out.println(count+"is max long int in java"); int temp; for (long i = 0; i < count; i++) { temp = random.nextInt(); stream.writeInt(temp); stream.writeChar(','); } System.out.println("循环完成"); stream.flush(); stream.close(); time = System.currentTimeMillis() - time; System.out.println(time+"毫秒");
2. 分析文件(使用DataInputStream,使用缓冲区,耗时65秒)
a. 读取前100个整数
b. 排序,把排序后的数组看成堆,最小值在根节点
c. 遍历整个文件,把读到的数和最小值比较,如果比最新值小,则丢弃,如果比最小值大则替换最小值重建堆。
d. 文件读取完毕,堆中的元素就是要找的100个最大值,再执行一次排序。
TestRead.java
public static void main(String[] args) throws IOException, InterruptedException { File file = new File("E:\\test.dat"); long time = System.currentTimeMillis(); DataInputStream stream = new DataInputStream(new BufferedInputStream(new FileInputStream(file))); int len = 100; long count = 100; int arr[] = new int[100]; for (int i = 0; i < len; i++) { arr[i] = stream.readInt(); stream.readChar(); } Arrays.sort(arr); print(arr); int temp = 0; while(true) { try { temp = stream.readInt(); stream.readChar(); count++; if(temp > arr[0]) { addToheap(arr,temp); } else { continue; } } catch(EOFException ioe) { break; } } stream.close(); time = System.currentTimeMillis() - time; System.out.println(time+"毫秒"+":"+count+"个"); Arrays.sort(arr); print(arr); } static void addToheap(int arr[], int temp){ arr[0] = temp; int index = 0; int left = 1; int right = 2; int minIndex = index; while (left < arr.length) { if (arr[index] > arr[left]) { minIndex = left; } if (right < arr.length && arr[minIndex] > arr[right]) { minIndex = right; } if (minIndex == index) { break; } else { temp = arr[minIndex]; arr[minIndex] = arr[index]; arr[index] = temp; index = minIndex; left = 2*index + 1; right = 2*index + 2; } } }
static void print(int[] aa) { for (int i = 0; i < aa.length; i++) { System.out.print(aa[i] + ","); if ((i + 1) % 10 == 0) { System.out.println(); } } }
3. 使用内存映射,nio,代替DataInputStream,用时12秒,只能使用MyEclipse6.5jre, 使用jdk1.5,jdk1.6时
存储空间不足,堆空间不足。
4. 对文件进行分段映射(暂时分为10段),每个线程负责读取一段,找出该段最大的100个,
在找到10X100个数中找最大的100个,用时10秒,性能没有显著改善。
package test; import java.io.RandomAccessFile; import java.nio.MappedByteBuffer; import java.nio.channels.FileChannel; import java.util.Arrays; import java.util.HashSet; import java.util.LinkedList; public class MultiThreadReader { /** * @param args */ public static void main(String[] args) { long time = System.currentTimeMillis(); long len = 200000000 * 6; int reads = 200; LinkedList<RandomReader> randomReaders = new LinkedList<RandomReader>(); RandomReader randomReader = null; for(int i = 0; i < reads; i++) { randomReader = new RandomReader(i*len/reads, len/reads/6); randomReaders.add(randomReader); new Thread(randomReader).start(); } int numberNeedFound = 100; int firstArr[] = new int[numberNeedFound]; boolean firstFound = false; HashSet<RandomReader> set = new HashSet<RandomReader>(); try { Thread.sleep(100); } catch (InterruptedException e) { // TODO Auto-generated catch block e.printStackTrace(); } while(set.size() < reads) { for(int i = 0; i < reads; i++) { randomReader = randomReaders.get(i); if (randomReader.done && !firstFound) { firstFound = true; firstArr = randomReader.arr; set.add(randomReader); } else if (firstFound && randomReader.done && !set.contains(randomReader)) { set.add(randomReader); for (int j = 0; j < randomReader.arr.length; j++) { if (randomReader.arr[j]>firstArr[0]) { TestRead.addToheap(firstArr, randomReader.arr[j]); }
} } } } time = System.currentTimeMillis() - time; Arrays.sort(firstArr); TestRead.print(firstArr); System.out.printf("使用时间%d秒\n", time); } } class RandomReader implements Runnable { long offset = 0; long len = 10; RandomAccessFile file; boolean done = false; int numberNeedFound = 100; int arr[] = new int[numberNeedFound]; MappedByteBuffer buffer; static int id = 0; int sid; public RandomReader(long offset, long len) { sid = id++; this.offset = offset; this.len = len; try { file = new RandomAccessFile("E:\\test.dat", "r"); buffer = file.getChannel().map(FileChannel.MapMode.READ_ONLY, offset, len*6); } catch (Exception e) { e.printStackTrace(); } } public void run() { int count = 0; for (int i = 0; i < numberNeedFound; i++) { arr[i] = buffer.getInt(); buffer.getChar(); count++; } Arrays.sort(arr); try { int temp = 0; while (count < len) { temp = buffer.getInt(); buffer.getChar(); count++; if (temp > arr[0]) { TestRead.addToheap(arr, temp); } if(count == len/2) { System.out.printf("reader %d completed 50 percent\n", sid); } } done = true; System.out.printf("reader %d completed 100 percent count = %d \n", sid,count); } catch (Exception e) { System.out.printf("reader %d is dead count = %d\n", sid,count); e.printStackTrace(); } } }
相关推荐
2010支付宝笔试题.rar2010支付宝笔试题.rar
2010支付宝笔试题.rar 2010支付宝笔试题.rar
在深入探讨支付宝招聘笔试题的知识点之前,我们需理解,此类题目主要考察应聘者在IT领域的专业技能、逻辑思维能力和解决问题的能力。虽然给定的部分内容并未提供具体题目,但基于支付宝作为全球领先的数字支付和生活...
阿里巴巴旗下的支付宝 于2009年10月15日在成都的校园招聘笔试题 全是选择题,分成4个部分 一、计算机基础知识 17个单选题 二、逻辑推理 15个单选题 三、网络及系统 9个单选题 四、数据库及SQL 7个单选题
### 支付宝Java工程师笔试题解析 #### 智力部分 1. **烧绳问题** **题目:** 烧一根不均匀的绳子需要一个小时,如何利用这根绳子判断出半小时的时间? **解答:** 将绳子的两端同时点燃,由于燃烧不均匀,无法...
特别声明一下,我发上去的是去年的技术类笔试题。但本人参加了武汉地区支付宝2011的笔试,做过以后发现总体情况差不多,题型基本类似,考数据结构比较多,没算法的题,有逻辑推理题、编译原理的后缀表达式、数据库、...
【支付宝2011 笔试题】涉及到的IT知识点涵盖了计算机网络、数据库管理、软件工程、数据结构与算法、操作系统等多个领域。以下是这些知识点的详细解释: 1. **计算机网络**:笔试题可能包含了TCP/IP协议栈的理解,如...
因此,我无法直接提供与"2010年支付宝最新笔试题A卷"相关的具体IT知识点。不过,我可以分享一些关于支付宝以及可能在笔试中出现的IT主题的一般性知识。 支付宝是中国领先的第三方在线支付平台,由阿里巴巴集团于...
- **移动互联网业务**:如微信、支付宝等应用的网络架构和挑战。 - **物联网(IoT)**:NB-IoT、eMTC等窄带物联网技术的应用场景。 通过学习移动公司笔试试题和答案,不仅可以了解移动通信的基本原理和技术,还能...
蚂蚁金服社招java笔试题目编码面试学习指南 该存储库包含我为准备编码面试而收集的笔记。 这些笔记基于流行的书籍:和。 第 1 章:数组和字符串 笔记哈希表:一种将键映射到值以实现高效查找的数据结构。 ArrayLists...
在百度这样的大型互联网公司中,产品岗位的校招笔试题往往旨在评估应聘者的行业理解、产品思维、分析能力和创新意识。以下是根据题目内容解析的相关知识点: 1. **互联网金融产品的应用分析**: - 使用经历:此题...
根据给定的信息,我们可以推断出这份文档包含了2014年支付宝面试的相关知识点,包括笔试题目和面试问题。下面将对这些知识点进行详细的解析。 ### 1. Cookies与Session Cookies是一种存储在用户浏览器上的小文本...
阿里作为中国顶尖的互联网巨头,其校招面试笔试题历来备受关注,因为它反映了公司对人才的需求和期望。这些试题不仅测试应聘者的编程能力,还考察逻辑思维、问题解决、团队协作以及对公司业务的理解等多个方面。以下...
针对“淘宝2010,2011,2012年笔试题”这一主题,我们可以深入探讨历年笔试题中可能涉及的IT知识点,帮助准备应聘者了解淘宝对技术人才的期望和要求。 首先,淘宝笔试题目通常会涵盖计算机基础,包括数据结构、算法、...
根据给定文件的信息,我们可以提炼出以下几个重要的C++知识点: ### 1. 字符串比较问题 #### 问题描述: 给定了三个字符串比较的例子,并询问它们的比较结果。 ```cpp char str1[] = "abc";...char str2[] = "abc";...
通过以上分析,我们可以看出支付宝2011年的校园招聘在线测评题覆盖了逻辑推理、数字规律、图形推理等多个方面,旨在全面考察应聘者的基本素质和能力。对于应聘者来说,除了具备相应的知识技能外,还需要在实际操作中...
2016年百度的校园招聘中,产品岗位的笔试题便聚焦在对互联网产品的理解和分析上,这对于我们理解产品设计的思路以及人性的洞察具有极大的启示。 首先,题目的第一部分涉及到对互联网金融产品的实际应用和分析。...
【阿里巴巴2016年校园招聘研发类笔试题解析】 阿里巴巴作为全球知名的技术驱动型企业,其校园招聘笔试题历来备受关注,尤其是对于技术研发类岗位。这些题目不仅考察候选人的技术基础,还涉及到逻辑思维、问题解决...