获取一亿数据获取前100个最大值

╰+哭是因爲堅強的太久メ 2023-10-17 15:36 120阅读 0赞

1.  **package** cn.usst.tophundred.quicksort; 
2.  
3.  **import** java.util.Random; 
4.  /\*\*
5.  获取一亿数据获取前100个最大值
6.  1. 假设数组为 array\[N\] (N = 1 亿)，首先利用quicksort的原理把array分成两个部分，左边部分比 array\[N - 1\] (array中的最后一个值，即pivot) 大， 右边部分比pivot 小。然后，可以得到 array\[array.length - 1\] (即 pivot) 在整个数组中的位置，假设是 k.
7.  2. 如果 k 比 99 大，我们在数组\[0, k - 1\]里找前 100 最大值。 （继续递归）
8.  3. 如果 k 比 99 小， 我们在数组\[k + 1, ..., N \]里找前 100 - (k + 1) 最大值。（继续递归）
9.  4. 如果 k == 99, 那么数组的前 100 个值一定是最大的。（退出）
10. \*/
11. 
12. **public****class** TopHundredQuickSort \{ 
13. 
14. **public****static****void** main(String\[\] args) \{ 
15. // the size of the array
16. **int** number = 100000000; 
17. // the top k values
18. **int** k = 100; 
19. // the range of the values in the array
20. **int** range = 1000000001; 
21. 
22. // input for minHeap based method
23. **int**\[\] array = **new****int**\[number\]; 
24. 
25.  Random random = **new** Random(); 
26. **for**(**int** i=0; i<number; i++)\{ 
27.  array\[i\] = random.nextInt(range); 
28.  \} 
29. 
30.  TopHundredQuickSort topHundred = **new** TopHundredQuickSort(); 
31. 
32. // start time
33. **long** t1 = System.currentTimeMillis(); 
34.  topHundred.tophundred(array, 0, array.length-1, k); 
35. 
36. // end time
37. **long** t2 = System.currentTimeMillis(); 
38. 
39.  System.out.println("The total execution time of quicksort based method is" \+ (t2-t1) + " millisecond"); 
40. 
41. // print out the top k largest values in the top array
42.  System.out.println("The top " \+ k + " largest values are:"); 
43. **for**(**int** i=0; i<k; i++)\{ 
44.  System.out.println(array\[i\]); 
45.  \} 
46.  \} 
47. 
48. **private****void** tophundred(**int**\[\] array, **int** start, **int** end, **int** k) \{ 
49. **int** switchPointer = start; 
50. // array最后一个值作为pivot
51. **int** pivot = array\[end\]; 
52. **for**(**int** i=start; i<end; i++)\{ 
53. **if**(array\[i\] >= pivot)\{ 
54.  swap(array, switchPointer, i); 
55.  switchPointer++; 
56.  \} 
57.  \} 
58. 
59. // 交换后 array左边的值比pivot大 右边的值比pivot小
60.  swap(array, end, switchPointer); 
61. 
62. **if**(switchPointer < k-1)\{ 
63.  tophundred(array, switchPointer+1, end, k); 
64.  \}**else****if**(switchPointer == k-1)\{ 
65. **return**; 
66.  \}**else**\{ 
67.  tophundred(array, 0, switchPointer-1, k); 
68.  \} 
69. 
70.  \} 
71. 
72. **private****void** swap(**int**\[\] array, **int** i, **int** j) \{ 
73. **int** temp = array\[i\]; 
74.  array\[i\] = array\[j\]; 
75.  array\[j\] = temp; 
76.  \} 
77. 
78. \}

【来自程序员面试宝典】有1千万条短信，找出重复出现最多的前10条  
  
题目：有1千万条短信，有重复，以文本文件的形式保存，一行一条，有重复。请用5分钟时间，找出重复出现最多的前10条。  
  
解析：对于本题来说，某些面试者想用[数据库][Link 1]的办法来实现：首先将文本导入数据库，再利用select语句某些方法得出前10条短信。但实际上用数据库是满足不了5分钟解决这个条件的。这是因为1千万条短信即使1秒钟录入1万条（这已经算是很快的数据录入了）5分钟才300万条。即使真的能在5分钟内录入完1千万条，也必须先建索引，不然sql语句5分钟内肯定得不出结果。但对1千万条记录建索引即使在5分钟之内都不可能完成的。所以用数据库的办法是不行的。  
这种类型的题之所以会出现，这是因为互联网公司无时无刻都在需要处理由用户产生的海量数据/日志，所以海量数据的题现在很热，基本上互联网公司都会考。重点考察的是你的[数据结构][Link 2]设计和[算法][Link 2]的基本功。类似题目是如何根据关键词搜索访问最多的前10个网站。  
  
答案：  
方法1：可以用哈希表的方法对1千万条分成若干组进行边扫描边建散列表。第一次扫描，取首字节，尾字节，中间随便两字节作为Hash Code，插入到hash table中。并记录其地址和信息长度和重复次数，1千万条信息，记录这几个信息还放得下。同Hash Code且等长就疑似相同，比较一下。相同记录只加1次进hash table，但将重复次数加1。一次扫描以后，已经记录各自的重复次数，进行第二次hash table的处理。用线性时间选择可在O（n）的级别上完成前10条的寻找。分组后每份中的top10必须保证各不相同，可hash来保证，也可直接按hash值的大小来分类。  
  
方法2：可以采用从小到大排序的方法，根据经验，除非是群发的过节短信，否则字数越少的短信出现重复的几率越高。建议从字数少的短信开始找起，比如一开始搜一个字的短信，找出重复出现的top10并分别记录出现次数，然后搜两个字的，依次类推。对于对相同字数的比较常的短信的搜索，除了hash之类的算法外，可以选择只抽取头、中和尾等几个位置的字符进行粗判，因为此种判断方式是为了加快查找速度但未能得到真正期望的top10，因此需要做标记；如此搜索一遍后，可以从各次top10结果中找到备选的top10，如果这top10中有刚才做过标记的，则对其对应字数的所有短信进行精确搜索以找到真正的top10并再次比较。  
  
方法3：可以采用内存映射的办法，首先1千万条短信按现在的短信长度将不会超过1G空间，使用内存映射文件比较合适。可以一次映射（当然如果更大的数据量的话，可以采用分段映射），由于不需要频繁使用文件I/O和频繁分配小内存，这将大大提高数据的加载速度。其次，对每条短信的第i（i从0到70）个字母按ASCII嘛进行分组，其实也就是创建树。i是树的深度，也是短信第i个字母。  
  
该问题主要是解决两方面的内容，一是内容加载，二是短信内容比较。采用文件内存映射技术可以解决内容加载的性能问题（不仅仅不需要调用文件I/O函数，而且也不需要每读出一条短信都分配一小块内存），而使用树技术可以有效减少比较的次数。

【来自程序员面试宝典】执行数据库查询时，如果要查询的数据有很多，假设有1000万条，用什么方法可以提高查询效率（速度）？在数据库方面或[Java][]代码方面有什么优化的办法？

1.在数据库设计方面

（1） 建立索引

（2） 分区（[MySQL][Link 1]，比如按时间分区）

（3） 限制字段长度

2.在数据库I/O方面

（1） 增加缓冲区

（2） 如果设计标的级联，不同的表存储在不同的磁盘上，以增加I/O的读写效率

3.在SQL语句方面

（1） 优化SQL语句，减少比较的次数

（2） 限制返回的条目数（[mysql][Link 1]中使用limit）

4.在Java方面