为自己搭建一个分布式 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,则会把下面所有有色的字符拼起来作为结果集合。


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


相关文章
|
1月前
|
存储 自然语言处理 机器人
实战揭秘:当RAG遇上企业客服系统——从案例出发剖析Retrieval-Augmented Generation技术的真实表现与应用局限,带你深入了解背后的技术细节与解决方案
【10月更文挑战第3天】随着自然语言处理技术的进步,结合检索与生成能力的RAG技术被广泛应用于多个领域,通过访问外部知识源提升生成内容的准确性和上下文一致性。本文通过具体案例探讨RAG技术的优势与局限,并提供实用建议。例如,一家初创公司利用LangChain框架搭建基于RAG的聊天机器人,以自动化FAQ系统减轻客服团队工作负担。尽管该系统在处理简单问题时表现出色,但在面对复杂或多步骤问题时存在局限。此外,RAG系统的性能高度依赖于训练数据的质量和范围。因此,企业在采用RAG技术时需综合评估需求和技术局限性,合理规划技术栈,并辅以必要的人工干预和监督机制。
84 3
|
2天前
|
算法 关系型数据库 MySQL
分布式唯一ID生成:深入理解Snowflake算法在Go中的实现
在分布式系统中,确保每个节点生成的 ID 唯一且高效至关重要。Snowflake 算法由 Twitter 开发,通过 64 位 long 型数字生成全局唯一 ID,包括 1 位标识位、41 位时间戳、10 位机器 ID 和 12 位序列号。该算法具备全局唯一性、递增性、高可用性和高性能,适用于高并发场景,如电商促销时的大量订单生成。本文介绍了使用 Go 语言的 `bwmarrin/snowflake` 和 `sony/sonyflake` 库实现 Snowflake 算法的方法。
10 1
分布式唯一ID生成:深入理解Snowflake算法在Go中的实现
|
13天前
|
存储 运维 负载均衡
构建高可用性GraphRAG系统:分布式部署与容错机制
【10月更文挑战第28天】作为一名数据科学家和系统架构师,我在构建和维护大规模分布式系统方面有着丰富的经验。最近,我负责了一个基于GraphRAG(Graph Retrieval-Augmented Generation)模型的项目,该模型用于构建一个高可用性的问答系统。在这个过程中,我深刻体会到分布式部署和容错机制的重要性。本文将详细介绍如何在生产环境中构建一个高可用性的GraphRAG系统,包括分布式部署方案、负载均衡、故障检测与恢复机制等方面的内容。
63 4
构建高可用性GraphRAG系统:分布式部署与容错机制
|
2天前
|
机器学习/深度学习 人工智能 算法
基于Python深度学习的【垃圾识别系统】实现~TensorFlow+人工智能+算法网络
垃圾识别分类系统。本系统采用Python作为主要编程语言,通过收集了5种常见的垃圾数据集('塑料', '玻璃', '纸张', '纸板', '金属'),然后基于TensorFlow搭建卷积神经网络算法模型,通过对图像数据集进行多轮迭代训练,最后得到一个识别精度较高的模型文件。然后使用Django搭建Web网页端可视化操作界面,实现用户在网页端上传一张垃圾图片识别其名称。
15 0
基于Python深度学习的【垃圾识别系统】实现~TensorFlow+人工智能+算法网络
|
2天前
|
机器学习/深度学习 人工智能 算法
基于深度学习的【蔬菜识别】系统实现~Python+人工智能+TensorFlow+算法模型
蔬菜识别系统,本系统使用Python作为主要编程语言,通过收集了8种常见的蔬菜图像数据集('土豆', '大白菜', '大葱', '莲藕', '菠菜', '西红柿', '韭菜', '黄瓜'),然后基于TensorFlow搭建卷积神经网络算法模型,通过多轮迭代训练最后得到一个识别精度较高的模型文件。在使用Django开发web网页端操作界面,实现用户上传一张蔬菜图片识别其名称。
10 0
基于深度学习的【蔬菜识别】系统实现~Python+人工智能+TensorFlow+算法模型
|
8天前
|
机器学习/深度学习 算法 5G
基于MIMO系统的SDR-AltMin混合预编码算法matlab性能仿真
基于MIMO系统的SDR-AltMin混合预编码算法通过结合半定松弛和交替最小化技术,优化大规模MIMO系统的预编码矩阵,提高信号质量。Matlab 2022a仿真结果显示,该算法能有效提升系统性能并降低计算复杂度。核心程序包括预编码和接收矩阵的设计,以及不同信噪比下的性能评估。
25 3
|
14天前
|
存储 缓存 算法
分布式缓存有哪些常用的数据分片算法?
【10月更文挑战第25天】在实际应用中,需要根据具体的业务需求、数据特征以及系统的可扩展性要求等因素综合考虑,选择合适的数据分片算法,以实现分布式缓存的高效运行和数据的合理分布。
|
15天前
|
分布式计算 Java 开发工具
阿里云MaxCompute-XGBoost on Spark 极限梯度提升算法的分布式训练与模型持久化oss的实现与代码浅析
本文介绍了XGBoost在MaxCompute+OSS架构下模型持久化遇到的问题及其解决方案。首先简要介绍了XGBoost的特点和应用场景,随后详细描述了客户在将XGBoost on Spark任务从HDFS迁移到OSS时遇到的异常情况。通过分析异常堆栈和源代码,发现使用的`nativeBooster.saveModel`方法不支持OSS路径,而使用`write.overwrite().save`方法则能成功保存模型。最后提供了完整的Scala代码示例、Maven配置和提交命令,帮助用户顺利迁移模型存储路径。
|
27天前
|
监控 算法 数据安全/隐私保护
基于三帧差算法的运动目标检测系统FPGA实现,包含testbench和MATLAB辅助验证程序
本项目展示了基于FPGA与MATLAB实现的三帧差算法运动目标检测。使用Vivado 2019.2和MATLAB 2022a开发环境,通过对比连续三帧图像的像素值变化,有效识别运动区域。项目包括完整无水印的运行效果预览、详细中文注释的代码及操作步骤视频,适合学习和研究。
|
1月前
|
消息中间件 中间件 数据库
NServiceBus:打造企业级服务总线的利器——深度解析这一面向消息中间件如何革新分布式应用开发与提升系统可靠性
【10月更文挑战第9天】NServiceBus 是一个面向消息的中间件,专为构建分布式应用程序设计,特别适用于企业级服务总线(ESB)。它通过消息队列实现服务间的解耦,提高系统的可扩展性和容错性。在 .NET 生态中,NServiceBus 提供了强大的功能,支持多种传输方式如 RabbitMQ 和 Azure Service Bus。通过异步消息传递模式,各组件可以独立运作,即使某部分出现故障也不会影响整体系统。 示例代码展示了如何使用 NServiceBus 发送和接收消息,简化了系统的设计和维护。
46 3

热门文章

最新文章