一、序言
我们群里发了了一个挑战,题目大概是:2亿随即字符串,在一个txt 文本里面,找出出现频率最高的前100 个字符串,双核CPU,4G 内存,当然JVM 只开了1G。
其实类似的题目,很多公司也都有了,但是可能思想说得多,实战稍微少点,这里我抽空也写了一种通用的,凡是上诉题目都可以按方法进行处理,也做可以做其他扩展和优化。
二、设计原理
1.我用他们提供的字符串生产文件,接近3G,肯定不能全部放入内存
2.我创建了一个2亿的int 数组,但是由于想hash 分布均匀,采用hashMap的算法模式,需要额外的空间,也就是268435456,相当于2.6亿空间,要刚好1G的内存,加上其他需要的空间分配,超过了限制,我这里分配的是1200M空间,当然原理类似,这里我们没对算法做更多的优化,后面有时间再单独研究。bits = new int[2.6亿];
3.然后读取每一行数据,进行hash 计算,以及index = indexFor(int hash,int length) 确定位置。这样我们就知道每一行数据存放的位置,然后进行 bit[index] ++运算,也就是说我们就可以知道所有字符串所出现的次数,当然可能会出现hash冲突,几率很小,这种算法允许低冲突率。
4.同时我们需要建立一个数组new Entry[100],这里用于存放我们的高频词的位置,当我们遍历每一行的同时,还需要将该行字符串出现的次数保存,按出现次数保留前100.最后就是我们要的结果。
三、实现代码
/** * 工具类,处理每行信息记录的数据结构 * 未解决hash冲突,暂时允许一部分重复,需要改进 * 这是初级版本,后续在改变 * @author Michael_Ran * @param <V> */ public class CountMap<V> { // 内容数组 transient Entry<V>[] table; // 下标数组 transient int[] bits;; // 光标移动位置,实际长度 transient int size; // 实际允许长度 transient int threshold; // 下标位置 transient int position; // 容量长度 transient static int bits_capacity = 16; // 初始化长度 @SuppressWarnings("unchecked") public CountMap(int initTopNum,int initTotalLines) { int capacity = 1; // 初始化内容数组 while (capacity < initTopNum) capacity <<= 1; table = new Entry[capacity]; // 初始化下标数组 while(bits_capacity < initTotalLines) bits_capacity <<= 1; bits = new int[bits_capacity]; this.threshold = initTopNum; } // 判断是否存在 boolean contains(Object value) { for (Entry<V> e : table) { if (e != null && hash(value.hashCode()) == e.hash) return true; } return false; } // 计算hash,这里需要进行改进 int hash(int h) { h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); // ConcurrentHashMap 的算法 // h += (h << 15) ^ 0xffffcd7d; // h ^= (h >>> 10); // h += (h << 3); // h ^= (h >>> 6); // h += (h << 2) + (h << 14); // return h ^ (h >>> 16); } // 计算位置 int indexFor(int h, int length) { return h & (length - 1); } // 计算容量位置 int putBits(V value,int hash){ int index = indexFor(hash,bits_capacity); return ++ bits[index]; } // 存放 public void put(V value) { int hash = hash(value.hashCode()); int count = putBits(value,hash); // 未存满 if (size < threshold) { if (count == 1) { Entry<V> newEntry = new Entry<V>(value, hash); table[size] = newEntry; if (size > 0) { table[size - 1].after = newEntry; newEntry.before = table[size - 1]; } size++; } else { for (int i = 0; i < threshold; i++) { Entry<V> e = table[i]; // 获取最小的元素位置,直接替换 if (e.value.equals(value)) { e.count = count; e.hash = hash; return; } } } } // 已经存满,因此从个数大于1开始寻找 if (count > 1) { if(position == threshold){ position = 0; } for (int i = position; i < threshold; i++) { Entry<V> e = table[i]; if (e.count < count) { replace(e, value, count, hash); return; } } } } public void replace(Entry<V> oldEntry,V value,int count,int hash){ oldEntry.count = count; oldEntry.value = value; oldEntry.hash = hash; } // 获取对象 public Entry<V> getEntry(Object value) { for (Entry<V> e : table) { if (e != null && e.equals(value)) return e; } return null; } // 获得集合 public Entry<V>[] getEntries() { return table; } // 获得实际长度 public int size() { return size; } // 内部类 static class Entry<V> { int count, hash; V value; Entry<V> before, after; public Entry(V value, int hash) { super(); this.count = 1; this.value = value; this.hash = hash; } // 自增 public int incrementAndGet() { return count++; } @Override public String toString() { return this.value + ":" + count; } } }
import java.io.BufferedReader; import java.io.File; import java.io.FileNotFoundException; import java.io.FileReader; import java.io.IOException; public class T { // 文件路径 static final String FILEPATH = "d:/b.txt"; // 出现次数排名最多的数 static int TOP_NUM = 100; // 文件行数,只要大于总行数就行,默认2亿 static int TOTAL_LINES = 200000000; // 容器 static CountMap<String> map = new CountMap<String>(TOP_NUM, TOTAL_LINES); public static void main(String[] args) throws ClassNotFoundException, InstantiationException, IllegalAccessException { long begin = System.currentTimeMillis(); // 计算 getTopN(FILEPATH); long result = System.currentTimeMillis()-begin; System.out.println("总时间为:"+result +"毫秒"); System.out.println("-------数据结果---------"); for(int i = 0;i<map.size();i++){ System.out.println(map.getEntries()[i]); } } // 计算 public static void getTopN(String filepath){ BufferedReader bw = null; try { File f = new File(filepath); bw = new BufferedReader(new FileReader(f)); String str = null; while ((str = bw.readLine()) != null) { map.put(str); } } catch (FileNotFoundException e) { e.printStackTrace(); } catch (IOException e) { e.printStackTrace(); } finally { try { if(bw != null){ bw.close(); } } catch (IOException e) { e.printStackTrace(); } } } }
四、优化方案
1.可以看出我们仍然需要比较大的空间,我们可以改进hash算法,不用那么大的空间
2.在重复率比较高的情况下,我们大概知道不重复数据只有N 的时候,就根据N 创建空间
3.在上面都不能实现的情况,我们可以分块空间,比如我们刚才最糟糕的情况,全都不重复,需要2亿空间,实际空间接近2.7亿,浪费很大。那么我们可以我可以开辟2个空间,第一个在获得2.7亿之前,也就是小于2亿的的空间,然后计算这部分行数的排行,同理计算第二批空间的排行,这样可能出现有一部分字符串分布 不均匀和 均匀问题,导致汇总数据不对,那么我们可以对每个空间进行扩大范围查询,也就是我们可以对第一个空间查询100*10 的排行,第二个空间同理,最后再汇总 计算前100,可以避免很大部分误差。
4.上面是以空间换时间,我们可以采用链表结构,不创建那么大的数组,以链表的形式记录每行的hash值,以及count次数,然后每次遍历进行循环,这样链表节点必定小于不重复的数据。这里需要做链表节点的优化,最好用hash树的形式,节约查找的时间。同时也可以用hash范围空间 进行查找,反正得减少每次循环的次数。
小结:
1.上面方法临时写的,很多没来得及优化,大概想了一下方法,为了减少一定比较,也没直接继承hashMap,欢迎大家吐槽!
2.关于hash 分布的问题,我也考虑过寻址 以及 链表的形式 或者树的形式,算法这块不强,有熟悉的朋友可以介绍接晒。
3.对于现在数据,几亿数据,10G以内的文件,我相信这种方法 在现在计算机内存运算来说还比较快的,虽然损耗了一部分准确率。
4.大数据很多的处理,可以先采用文件分割,然后多线程(和CPU数量有关)处理,放大结果集,然后合并的也是不错的选择。
5.不好的地方请指教,有更好的方法欢迎提供,非常感谢!后续有更好的,我也会给大家分享。
6.JDK 1.8 有个特性,好像是用堆外内存来处理OOM,也就是说暂时可以借系统内存,也可以限定范围,有兴趣的朋友可以研究研究!
相关推荐
- **高频率词的识别**:在有限内存条件下,通过滑动窗口与哈希表结合的技术来识别高频词汇,同时考虑到时间和空间的优化。 - **IP访问统计**:利用哈希表结构,结合滑动窗口算法,有效统计特定时间内的高频IP访问。 ...
在实战实例中,PPT课件可能涵盖了以下步骤:数据收集(如社交媒体、新闻网站等)、预处理(去除停用词、标点符号,进行词干提取)、特征工程(构建关联矩阵)、关联度计算(如皮尔逊相关系数、斯皮尔曼等级相关等)...
内容概要:本文详细介绍了基于MATLAB GUI界面和卷积神经网络(CNN)的模糊车牌识别系统。该系统旨在解决现实中车牌因模糊不清导致识别困难的问题。文中阐述了整个流程的关键步骤,包括图像的模糊还原、灰度化、阈值化、边缘检测、孔洞填充、形态学操作、滤波操作、车牌定位、字符分割以及最终的字符识别。通过使用维纳滤波或最小二乘法约束滤波进行模糊还原,再利用CNN的强大特征提取能力完成字符分类。此外,还特别强调了MATLAB GUI界面的设计,使得用户能直观便捷地操作整个系统。 适合人群:对图像处理和深度学习感兴趣的科研人员、高校学生及从事相关领域的工程师。 使用场景及目标:适用于交通管理、智能停车场等领域,用于提升车牌识别的准确性和效率,特别是在面对模糊车牌时的表现。 其他说明:文中提供了部分关键代码片段作为参考,并对实验结果进行了详细的分析,展示了系统在不同环境下的表现情况及其潜在的应用前景。
嵌入式八股文面试题库资料知识宝典-计算机专业试题.zip
嵌入式八股文面试题库资料知识宝典-C and C++ normal interview_3.zip
内容概要:本文深入探讨了一款额定功率为4kW的开关磁阻电机,详细介绍了其性能参数如额定功率、转速、效率、输出转矩和脉动率等。同时,文章还展示了利用RMxprt、Maxwell 2D和3D模型对该电机进行仿真的方法和技术,通过外电路分析进一步研究其电气性能和动态响应特性。最后,文章提供了基于RMxprt模型的MATLAB仿真代码示例,帮助读者理解电机的工作原理及其性能特点。 适合人群:从事电机设计、工业自动化领域的工程师和技术人员,尤其是对开关磁阻电机感兴趣的科研工作者。 使用场景及目标:适用于希望深入了解开关磁阻电机特性和建模技术的研究人员,在新产品开发或现有产品改进时作为参考资料。 其他说明:文中提供的代码示例仅用于演示目的,实际操作时需根据所用软件的具体情况进行适当修改。
少儿编程scratch项目源代码文件案例素材-剑客冲刺.zip
少儿编程scratch项目源代码文件案例素材-几何冲刺 转瞬即逝.zip
内容概要:本文详细介绍了基于PID控制器的四象限直流电机速度驱动控制系统仿真模型及其永磁直流电机(PMDC)转速控制模型。首先阐述了PID控制器的工作原理,即通过对系统误差的比例、积分和微分运算来调整电机的驱动信号,从而实现转速的精确控制。接着讨论了如何利用PID控制器使有刷PMDC电机在四个象限中精确跟踪参考速度,并展示了仿真模型在应对快速负载扰动时的有效性和稳定性。最后,提供了Simulink仿真模型和详细的Word模型说明文档,帮助读者理解和调整PID控制器参数,以达到最佳控制效果。 适合人群:从事电力电子与电机控制领域的研究人员和技术人员,尤其是对四象限直流电机速度驱动控制系统感兴趣的读者。 使用场景及目标:适用于需要深入了解和掌握四象限直流电机速度驱动控制系统设计与实现的研究人员和技术人员。目标是在实际项目中能够运用PID控制器实现电机转速的精确控制,并提高系统的稳定性和抗干扰能力。 其他说明:文中引用了多篇相关领域的权威文献,确保了理论依据的可靠性和实用性。此外,提供的Simulink模型和Word文档有助于读者更好地理解和实践所介绍的内容。
嵌入式八股文面试题库资料知识宝典-2013年海康威视校园招聘嵌入式开发笔试题.zip
少儿编程scratch项目源代码文件案例素材-驾驶通关.zip
小区开放对周边道路通行能力影响的研究.pdf
内容概要:本文探讨了冷链物流车辆路径优化问题,特别是如何通过NSGA-2遗传算法和软硬时间窗策略来实现高效、环保和高客户满意度的路径规划。文中介绍了冷链物流的特点及其重要性,提出了软时间窗概念,允许一定的配送时间弹性,同时考虑碳排放成本,以达到绿色物流的目的。此外,还讨论了如何将客户满意度作为路径优化的重要评价标准之一。最后,通过一段简化的Python代码展示了遗传算法的应用。 适合人群:从事物流管理、冷链物流运营的专业人士,以及对遗传算法和路径优化感兴趣的科研人员和技术开发者。 使用场景及目标:适用于冷链物流企业,旨在优化配送路线,降低运营成本,减少碳排放,提升客户满意度。目标是帮助企业实现绿色、高效的物流配送系统。 其他说明:文中提供的代码仅为示意,实际应用需根据具体情况调整参数设置和模型构建。
少儿编程scratch项目源代码文件案例素材-恐怖矿井.zip
内容概要:本文详细介绍了基于STM32F030的无刷电机控制方案,重点在于高压FOC(磁场定向控制)技术和滑膜无感FOC的应用。该方案实现了过载、过欠压、堵转等多种保护机制,并提供了完整的源码、原理图和PCB设计。文中展示了关键代码片段,如滑膜观测器和电流环处理,以及保护机制的具体实现方法。此外,还提到了方案的移植要点和实际测试效果,确保系统的稳定性和高效性。 适合人群:嵌入式系统开发者、电机控制系统工程师、硬件工程师。 使用场景及目标:适用于需要高性能无刷电机控制的应用场景,如工业自动化设备、无人机、电动工具等。目标是提供一种成熟的、经过验证的无刷电机控制方案,帮助开发者快速实现并优化电机控制性能。 其他说明:提供的资料包括详细的原理图、PCB设计文件、源码及测试视频,方便开发者进行学习和应用。
基于有限体积法Godunov格式的管道泄漏检测模型研究.pdf
嵌入式八股文面试题库资料知识宝典-CC++笔试题-深圳有为(2019.2.28)1.zip
少儿编程scratch项目源代码文件案例素材-几何冲刺 V1.5.zip
Android系统开发_Linux内核配置_USB-HID设备模拟_通过root权限将Android设备转换为全功能USB键盘的项目实现_该项目需要内核支持configFS文件系统
C# WPF - LiveCharts Project