#coding4fun#词频统计优化思路

简介:

关于这期的coding4fun,我选择的是hashmap方式实现。整体思路和流程大家可能都差不多,C++同学们的总结写的很好,一些逻辑优化都有总结,我这里介绍下java实现的一些优化吧。

使用ByteString代替String

开始读出文件转成String对象,然后通过String对象操作,代码写起来都比较方便。

但是有一个问题,文件读取出来的byte[]转成String对象非常耗时,一个1G的String对象分配内存时间就很长了,String对象内部使用char[],通过byte[]构造String对象需要根据编码遍历byte[]。这个过程非常耗时,肯定是可以优化的。

于是我使用ByteString类代替String

class ByteString{
    byte[] bs;
    int start;
    int end;
}

hashcode()和equals()方法参考String的实现。

在code4fun的16核机器上测试如下代码:

代码1:

byte[] bs = new byte[1024*1024*1024];
long st = System.currentTimeMillis();
new String(bs);
System.out.println(System.currentTimeMillis() - st);  // 2619ms

代码2:

byte[] bs = new byte[1024*1024*1024];
long st = System.currentTimeMillis();
int count = 100000;
for(int i = 0; i < count; i++)
   new ByteString(bs, 0, 100);
System.out.println(System.currentTimeMillis() - st);  //10ms

循环中代码要精简

Hashmap的实现,给单词计数时避免不了如下的代码:

ByteString str = new ByteString(bs, start, end);
Count count = map.get(str);
If(count == null){
  count = new Count(str,1);
  map.put(str,count);
} else{
  count.add(1);
}

本来这段代码没什么问题,但是当单词个数足够大的时候(最终1.1G的文件,有2亿多单词),这段代码就值得优化了。第一行创建的对象,只有单词第一次出现有用,其他时间都可以不用创建。

于是创建一个Pmap类,继承HahsMap,并添加了一个get(ByteString bs, int start, int end)方法。上面的代码改为

Count count = map.get(bs, start, end);
If(count == null){
  ByteString str = new ByteString(bs, start, end);
  count = new Count(str,1);
  map.put(str,count);
} else{
  count.add(1);
}

能避免锁就不用锁,不能避免就减小范围

concurrentHashMap的实现固然精妙,只是能不用锁尽量不用,实在用的时候,尽量减少范围。CAS的方式虽然比锁好,但是还是有消耗。

我们使用多线程的方式统计,所以统计结果对象需要线程安全。开始使用AtomicInteger,但是跟count++比起来效率还是差的非常多,单词个数越多越明显。

尝试使用volatile关键字效果也是不理想,然后比不上count++。

最后使用两个字段来解决这个问题:在线程内部统计单词个数时,使用count++方式;到合并环节,单词数已经不多,使用AtomicInteger的方式累加,基本不影响效率。

通过减少锁的范围和锁的次数,来达到提升效率的目标。

相关文章
|
12天前
|
弹性计算 关系型数据库 微服务
基于 Docker 与 Kubernetes(K3s)的微服务:阿里云生产环境扩容实践
在微服务架构中,如何实现“稳定扩容”与“成本可控”是企业面临的核心挑战。本文结合 Python FastAPI 微服务实战,详解如何基于阿里云基础设施,利用 Docker 封装服务、K3s 实现容器编排,构建生产级微服务架构。内容涵盖容器构建、集群部署、自动扩缩容、可观测性等关键环节,适配阿里云资源特性与服务生态,助力企业打造低成本、高可靠、易扩展的微服务解决方案。
1262 5
|
1天前
|
存储 关系型数据库 分布式数据库
PostgreSQL 18 发布,快来 PolarDB 尝鲜!
PostgreSQL 18 发布,PolarDB for PostgreSQL 全面兼容。新版本支持异步I/O、UUIDv7、虚拟生成列、逻辑复制增强及OAuth认证,显著提升性能与安全。PolarDB-PG 18 支持存算分离架构,融合海量弹性存储与极致计算性能,搭配丰富插件生态,为企业提供高效、稳定、灵活的云数据库解决方案,助力企业数字化转型如虎添翼!
|
11天前
|
机器学习/深度学习 人工智能 前端开发
通义DeepResearch全面开源!同步分享可落地的高阶Agent构建方法论
通义研究团队开源发布通义 DeepResearch —— 首个在性能上可与 OpenAI DeepResearch 相媲美、并在多项权威基准测试中取得领先表现的全开源 Web Agent。
1280 87
|
12天前
|
云栖大会
阿里云云栖大会2025年9月24日开启,免费申请大会门票,速度领取~
2025云栖大会将于9月24-26日举行,官网免费预约畅享票,审核后短信通知,持证件入场
1823 13