为自己搭建一个分布式 IM 系统二【从查找算法聊起】(中)

简介: 把一些影响较大的 bug 以及需求比较迫切的 feature 调整了,本次更新的 v1.0.1 版本: 客户端超时自动下线。 新增 AI 模式。 聊天记录查询。 在线用户前缀模糊匹配。 下面谈下几个比较重点的功能。 客户端超时自动下线 这个功能涉及到客户端和服务端的心跳设计,比较有意思,也踩了几个坑;所以准备留到下次单独来聊。

回调接口


至于收到其他客户端发来的消息时则是利用之前预留的消息回调接口来写入日志。



收到消息后会执行自定义的回调接口。



于是在这个回调方法中实现写入逻辑即可,当后续还有其他的消息处理逻辑时也能在这里直接添加。


当处理逻辑增多时最好是改为责任链模式,更加清晰易维护。


查找算法


接下来是本文着重要讨论的一个查找算法,准确的说是一个前缀模糊匹配的算法。


实现的效果如下:



使用命令 :qu prefix 可以按照前缀的方式搜索用户信息。


当然在命令行中其实意义不大,但是在移动端中确是比较有用的。类似于微信按照用户名匹配:



因为后期打算出一个移动端 APP,所以就先把这个功能实现了。


从效果也看得出来:就是按照输入的前缀匹配字符串(目前只支持英文)。


在没有任何限制的条件下最快、最简单的实现方式可以直接把所有的字符串存放在一个容器中 (List、Set),查询时则挨个遍历;利用 String.startsWith("prefix") 进行匹配。


但这样会有几个问题:


  • 存储资源比较浪费,不管是 list 还是 Set 都会有额外的损耗。


  • 查询效率较低,需要遍历集合后再遍历字符串的 char 数组

String.startsWith 的实现方式)。


字典树


基于以上的问题我们可以考虑下:


假设我需要存放 java,javascript,jsp,php 这些字符串时在 ArrayList 中会怎么存放?



很明显,会是这样完整的存放在一个数组中;同时这个数组还可能存在浪费,没有全部使用完。


但其实仔细观察这些数据会发现有一些共同特点,比如 java,javascript 有共同的前缀 java;和 jsp 有共同的前缀 j


那是否可以把这些前缀利用起来呢?这样就可以少存储一份。


比如写入 java,javascript 这两个字符串时存放的结构如下:



当再存入一个 jsp 时:



最后再存入 jsf 时:



相信大家应该已经看明白了,按照这样的存储方式可以节省很多内存,同时查询效率也比较高。


比如查询以 jav 开头的数据,只需要从头结点 j 开始往下查询,最后会查询到 ava 以及 script 这两个个结点,所以整个查询路径所经历的字符拼起来就是查询到的结果java+javascript


如果以 b 开头进行查询,那第一步就会直接返回,这样比在 list 中的效率高很多。

但这个图还不完善,因为不知道查询到啥时候算是匹配到了一个之前写入的字符串。


比如在上图中怎么知道 j+ava 是一个我们之前写入的 java 这个字符呢。


因此我们需要对这种是一个完整字符串的数据打上一个标记:



比如这样,我们将 ava、script、p、f 这几个节点都换一个颜色表示。表明查询到这个字符时就算是匹配到了一个结果。


而查到 s 这个字符颜色不对,代表还需要继续往下查。


比如输入关键字 js 进行匹配时,当它的查询路径走到 s 这里时判断到 s 的颜色不对,所以不会把 js 作为一个匹配结果。而是继续往下查,发现有两个子节点 p、f 颜色都正确,于是把查询的路径 jspjsf 都作为一个匹配结果。


而只输入 j,则会把下面所有有色的字符拼起来作为结果集合。


这其实就一个典型的字典树。


相关文章
|
5天前
|
机器学习/深度学习 人工智能 算法
猫狗宠物识别系统Python+TensorFlow+人工智能+深度学习+卷积网络算法
宠物识别系统使用Python和TensorFlow搭建卷积神经网络,基于37种常见猫狗数据集训练高精度模型,并保存为h5格式。通过Django框架搭建Web平台,用户上传宠物图片即可识别其名称,提供便捷的宠物识别服务。
111 55
|
7天前
|
机器学习/深度学习 自然语言处理 搜索推荐
深度分析 | 2024主流的智能客服系统有哪些?他们是怎么实现的?
本文深入探讨了智能客服系统的使用方法和相关技术实现逻辑,涵盖前端交互、服务接入、逻辑处理、数据存储四大层面,以及自然语言处理、机器学习、语音识别与合成、数据分析与挖掘、知识库管理和智能推荐系统等核心技术,帮助企业更好地理解和应用智能客服系统,提升服务效率和客户满意度。
44 1
|
15天前
|
机器学习/深度学习 人工智能 算法
【宠物识别系统】Python+卷积神经网络算法+深度学习+人工智能+TensorFlow+图像识别
宠物识别系统,本系统使用Python作为主要开发语言,基于TensorFlow搭建卷积神经网络算法,并收集了37种常见的猫狗宠物种类数据集【'阿比西尼亚猫(Abyssinian)', '孟加拉猫(Bengal)', '暹罗猫(Birman)', '孟买猫(Bombay)', '英国短毛猫(British Shorthair)', '埃及猫(Egyptian Mau)', '缅因猫(Maine Coon)', '波斯猫(Persian)', '布偶猫(Ragdoll)', '俄罗斯蓝猫(Russian Blue)', '暹罗猫(Siamese)', '斯芬克斯猫(Sphynx)', '美国斗牛犬
94 29
【宠物识别系统】Python+卷积神经网络算法+深度学习+人工智能+TensorFlow+图像识别
|
2天前
|
机器学习/深度学习 前端开发 算法
婚恋交友系统平台 相亲交友平台系统 婚恋交友系统APP 婚恋系统源码 婚恋交友平台开发流程 婚恋交友系统架构设计 婚恋交友系统前端/后端开发 婚恋交友系统匹配推荐算法优化
婚恋交友系统平台通过线上互动帮助单身男女找到合适伴侣,提供用户注册、个人资料填写、匹配推荐、实时聊天、社区互动等功能。开发流程包括需求分析、技术选型、系统架构设计、功能实现、测试优化和上线运维。匹配推荐算法优化是核心,通过用户行为数据分析和机器学习提高匹配准确性。
22 3
|
17天前
|
算法 5G 数据安全/隐私保护
基于MIMO系统的PE-AltMin混合预编码算法matlab性能仿真
本文介绍了基于交替最小化(AltMin)算法的混合预编码技术在MIMO系统中的应用。通过Matlab 2022a仿真,展示了该算法在不同信噪比下的性能表现。核心程序实现了对预编码器和组合器的优化,有效降低了硬件复杂度,同时保持了接近全数字预编码的性能。仿真结果表明,该方法具有良好的鲁棒性和收敛性。
31 8
|
12天前
|
存储 算法 安全
分布式系统架构1:共识算法Paxos
本文介绍了分布式系统中实现数据一致性的重要算法——Paxos及其改进版Multi Paxos。Paxos算法由Leslie Lamport提出,旨在解决分布式环境下的共识问题,通过提案节点、决策节点和记录节点的协作,确保数据在多台机器间的一致性和可用性。Multi Paxos通过引入主节点选举机制,优化了基本Paxos的效率,减少了网络通信次数,提高了系统的性能和可靠性。文中还简要讨论了数据复制的安全性和一致性保障措施。
30 1
|
17天前
|
存储 人工智能 运维
最新榜单 | 盘点2024年10大主流工单系统
随着互联网的发展,工单系统因其多样化功能和高效管理能力,成为企业运营的重要工具。本文介绍了10大主流工单系统,包括合力亿捷、阿里云服务中台、华为云ROMA ServiceCore等,它们各具特色,帮助企业提升服务质量和运营效率,实现数字化转型。
40 7
|
1月前
|
算法 关系型数据库 MySQL
分布式唯一ID生成:深入理解Snowflake算法在Go中的实现
在分布式系统中,确保每个节点生成的 ID 唯一且高效至关重要。Snowflake 算法由 Twitter 开发,通过 64 位 long 型数字生成全局唯一 ID,包括 1 位标识位、41 位时间戳、10 位机器 ID 和 12 位序列号。该算法具备全局唯一性、递增性、高可用性和高性能,适用于高并发场景,如电商促销时的大量订单生成。本文介绍了使用 Go 语言的 `bwmarrin/snowflake` 和 `sony/sonyflake` 库实现 Snowflake 算法的方法。
42 1
分布式唯一ID生成:深入理解Snowflake算法在Go中的实现
|
1月前
|
算法 数据安全/隐私保护 索引
OFDM系统PAPR算法的MATLAB仿真,对比SLM,PTS以及CAF,对比不同傅里叶变换长度
本项目展示了在MATLAB 2022a环境下,通过选择映射(SLM)与相位截断星座图(PTS)技术有效降低OFDM系统中PAPR的算法实现。包括无水印的算法运行效果预览、核心程序及详尽的中文注释,附带操作步骤视频,适合研究与教学使用。
|
17天前
|
机器学习/深度学习 存储 运维
分布式机器学习系统:设计原理、优化策略与实践经验
本文详细探讨了分布式机器学习系统的发展现状与挑战,重点分析了数据并行、模型并行等核心训练范式,以及参数服务器、优化器等关键组件的设计与实现。文章还深入讨论了混合精度训练、梯度累积、ZeRO优化器等高级特性,旨在提供一套全面的技术解决方案,以应对超大规模模型训练中的计算、存储及通信挑战。
48 4
下一篇
DataWorks