当前位置: 首页 > news >正文

java最优建树算法

建树算法

树的数据结构

{"code": "1111","name": "","parentcode": "0000","children": null
},	
{"code": "2222","name": "","parentcode": "0000","children": [{"code": "1234","name": "","parentcode": "2222","children": null},{"code": "4561","name": "","parentcode": "2222","children": ["code": "7894","name": "","parentcode": "4561","children": null]}]
}

常见建树方式

    public List<TreeNodeInfo> getChildren(List<TreeNodeInfo> infos, String id) {return infos.stream().filter(g -> Objects.equals(g.getParentid(), id)).map(g -> {List<TreeNodeInfo> children = getChildren(infos, g.getId());g.setChildren(children);return g;}).collect(Collectors.toList());}
  1. 效率问题:在每一层递归中,都需要遍历整个节点列表来查找匹配的子节点。这样的操作可能会导致性能下降,尤其是当节点列表很大时。时间复杂度为O(n^2)
  2. 内存消耗:递归算法需要不断地创建新的函数调用栈,每次递归调用都会占用一定的内存空间。对于大型树结构或节点列表,递归调用可能导致栈溢出或占用过多的内存。
  3. 重复遍历:在每一层递归中,都需要遍历整个节点列表来查找匹配的子节点。这意味着同一个节点可能会被多次遍历,导致了重复的工作。
  4. 综上所述,该建树算法在处理小型、非循环引用的节点列表时可能是有效的,但在处理大型、存在循环引用或需要排序的节点列表时可能存在一些缺点

优化后的建树方式

方式一

    public List<TreeNodePO> getTree1(List<TreeNodePO> nodes) {int initialCapacity = (int) (allInfos.size() / 0.75 + 1);Map<String, TreeNodePO> map = new HashMap<>(initialCapacity);for (TreeNodePO info : nodes) {map.put(info.getCode(), info);}List<TreeNodePO> roots = new ArrayList<TreeNodePO>();String pid = null;TreeNodePOpNode = null;for (TreeNodePO node : nodes) {pid = node.getParentcode();//根节点标识if (Objects.equals(pid, "0000")) {roots.add(node);continue;}pNode = map.get(pid);if (pNode != null) {pNode.addChildren(node);}}return roots;}

优点:

  1. 时间效率高:使用了HashMap来存储节点信息,通过节点的code作为key,可以快速查找到对应的节点,因此在构建树的过程中,可以快速地找到父节点并将子节点添加到父节点的children列表中,时间复杂度为O(n)。
  2. 空间效率高:使用了HashMap来存储节点信息,通过节点的code作为key,可以避免重复存储相同的节点,节省了存储空间。

缺点:

  1. 只能处理一级父子关系:该算法只能处理一级父子关系,即每个节点只能有一个直接父节点。如果存在多级父子关系,该算法无法处理。
  2. 需要额外的存储空间:该算法需要使用HashMap来存储节点信息,需要额外的存储空间来存储节点的code和对应的节点对象,可能会占用较多的内存空间

方式二

public List<TreeNodePO> getTree2(List<TreeNodePO> allInfos) {// 创建缓存,用于存储已构建的节点int initialCapacity = (int) (allInfos.size() / 0.75 + 1);Map<String, TreeNodePO> cache = new HashMap<>(initialCapacity);//构建树List<TreeNodePO> roots = new ArrayList<>();for (TreeNodePO info : allInfos) {String code = info.getCode();String parentcode = info.getParentcode();//如果存在则get取出,不存在则put放入TreeNodePO node = cache.computeIfAbsent(code, TreeNodePO::new);node.setName(info.getName());node.setParentcode(info.getParentcode());//根节点标识if (Objects.equals(parentcode, "0000")) {roots.add(node);} else {TreeNodePO parentNode = cache.computeIfAbsent(parentcode, TreeNodePO::new);parentNode.addChildren(info);}}return roots;
}

优点:

  1. 时间效率高:使用HashMap作为缓存,可以快速查找和存储节点,避免了遍历查找的时间消耗,时间复杂度为O(n)。
  2. 空间效率高:使用HashMap作为缓存,可以避免重复构建相同的节点,减少了内存占用。
  3. 算法简洁易懂:通过使用HashMap的方式构建树结构,代码逻辑清晰,易于理解和维护。

缺点:

  1. 依赖HashMap:该算法依赖于HashMap作为缓存结构,如果数据量很大,可能会导致HashMap的内存占用过高,影响性能。
  2. 无法处理循环依赖:如果存在循环依赖的情况,即节点A的父节点是节点B,节点B的子节点是节点A,该算法无法处理,可能会导致死循环或树结构错误。

5w条测试数据算法耗时:

算法\次数12345678910平均耗时(ms)
getTree11818171718181818181917.9
getTree21514151514151515141614.8

5w条测试数据算法空间占用

算法\次数12345678910平均占用空间(KB)
getTree158534127753440515052512179165915412764435614
getTree2919370518096128538476856810983119088918101049615

相关文章:

java最优建树算法

建树算法 树的数据结构 {"code": "1111","name": "","parentcode": "0000","children": null }, {"code": "2222","name": "","parentcode": &q…...

mysql面试题30:什么是数据库连接池、应用程序和数据库建立连接的过程、为什么需要数据库连接池、你知道哪些数据库连接池

该文章专注于面试,面试只要回答关键点即可,不需要对框架有非常深入的回答,如果你想应付面试,是足够了,抓住关键点 面试官:什么是数据库连接池? 数据库连接池是一种用于管理和复用数据库连接的技术。它是在应用程序和数据库之间建立一组数据库连接,并以池的形式存储起…...

【Vue】vscode格式刷插件Prettier以及配置项~~保姆级教程

文章目录 前言一、下载插件二、在项目内创建配置文件1.在根目录创建&#xff0c;src同级2.写入配置3.每个字段含义 总结 前言 vscode格式刷&#xff0c;有太多插件了&#xff0c;但是每个的使用&#xff0c;换行都不一样。 这里我推荐一个很多人都推荐了的Prettier 一、下载插…...

.NET 8 中的调试增强功能

作者&#xff1a;James Newton-King 排版&#xff1a;Alan Wang 开发人员喜欢 .NET 强大且用户友好的调试体验。您可以在您选择的 IDE 中设置断点&#xff0c;启动已经附加上调试器的程序&#xff0c;逐步执行代码并查看 .NET 应用程序的状态。 在 .NET 8 中&#xff0c;我们致…...

1310. 数三角形

知识点&#xff1a;(a, b)与(c, d)两点连线上点的个数为:gcd(x, y) 1(包括端点) &#xff08;设横坐标差的绝对值为x&#xff0c; 纵坐标差的绝对值为y &#xff09; 思路&#xff1a;先算出选三个点的所有情况&#xff0c;再减去三点共线的情况 共线的斜率为0时特判 当共线…...

数据库基础(一)

数据库面试基础 注&#xff0c;本文章内容主要来自于JAVAGUIDE&#xff0c;只是结合网上资料和自己的知识缺陷进行一点补充&#xff0c;需要准备面试的请访问官方网址。 一、范式 参考链接 函数依赖&#xff1a;一张表中&#xff0c;确定X则必定能确定Y&#xff0c;则X->…...

Factory-Method

Factory-Method 动机 在软件系统中&#xff0c;经常面临着创建对象的工作&#xff1b;由于需求的变化&#xff0c;需要创建的对象的具体类型经常变化。如何应对这种变化&#xff1f;如何绕过常规的对象创建方法(new)&#xff0c;提供一种“封装机制”来避免客户程序和这种“具…...

【C++】神奇字符串(力扣481)

神奇字符串的规律&#xff1a; 神奇字符串 s 仅由 ‘1’ 和 ‘2’ 组成&#xff0c;并需要遵守下面的规则&#xff1a; 神奇字符串 s 的神奇之处在于&#xff0c;串联字符串中 1 和 2 的连续出现次数可以生成该字符串。 s 的前几个元素是 s “1221121221221121122……” 。如果…...

elasticsearch索引的数据类型以及别名的使用

在上篇文章写了关于elasticsearch索引的数据类型&#xff0c;这里就详细说下索引的增删改查以及其他的一些操作吧。 1、索引的增、删、改、查 先新建一个索引结构&#xff0c;代码如下 PUT test-3-2-1 {"mappings": {"properties": {"id": {&…...

分布式锁2:基于redis实现分布式锁

一 redis实现分布式锁 1.1 原理 setnxexpiredel 命令实现redis的分布式锁&#xff1b;其中 setnx 不存在则新增&#xff1b;存在则忽略。即先用setnx来抢锁&#xff0c;如果抢到之后&#xff0c;再用expire给锁设置一个过期时间&#xff0c;防止锁忘记了释放。例如&#xf…...

【Vue面试题十六】、Vue.observable你有了解过吗?说说看

文章底部有个人公众号&#xff1a;热爱技术的小郑。主要分享开发知识、学习资料、毕业设计指导等。有兴趣的可以关注一下。为何分享&#xff1f; 踩过的坑没必要让别人在再踩&#xff0c;自己复盘也能加深记忆。利己利人、所谓双赢。 面试官&#xff1a;Vue.observable你有了解…...

Centos7使用nginx搭建rtmp流媒体服务器

为什么写这篇文章 2023年10月份&#xff0c;公司系统中有个需求&#xff0c;需要使用摄像头记录工程师在维修设备时的工作状态&#xff0c;找到了一家做执法记录仪的厂商&#xff0c;通过厂商发过来的文档了解到该执法记录仪支持通过rtmp协议推流至服务器&#xff0c;第一次接…...

Springboot+vue4S店车辆管理系统(有报告),Javaee项目,springboot vue前后端分离项目。

演示视频&#xff1a; Springbootvue4S店车辆管理系统&#xff08;有报告&#xff09;&#xff0c;Javaee项目&#xff0c;springboot vue前后端分离项目。 项目介绍&#xff1a; 本文设计了一个基于Springbootvue的前后端分离的4S店车辆管理系统&#xff0c;采用M&#xff08…...

Docker与Serverless计算的集成: Docker容器如何与Serverless计算结合。

文章目录 1. Docker容器的可移植性2. Serverless计算的自动伸缩性3. 使用Serverless与Docker容器a. 自托管Serverless平台b. 使用容器服务 4. 使用案例&#xff1a;图像处理服务5. 结论 &#x1f388;个人主页&#xff1a;程序员 小侯 &#x1f390;CSDN新晋作者 &#x1f389;…...

Linux下kibana的安装与配置

1. 环境配置 确保Linux服务器上已安装Java 8或更高版本。可以通过运行 java -version 来验证Java的版本。 下载Kibana 7.17.11的压缩文件&#xff0c;可以从Kibana 7.17.11下载 上传服务器&#xff0c;并解压Kibana压缩文件。 2. Kibana配置 编辑Kibana的配置文件 config/k…...

LuatOS-SOC接口文档(air780E)-- http - http 客户端

示例 -- 使用http库,需要引入sysplus库, 且需要在task内使用 require "sys" require "sysplus"sys.taskInit(function()sys.wait(1000)local code,headers,body http.request("GET", "http://www.example.com/abc").wait()log.info(…...

分布式文件服务器——初识MinIO

开篇 MinIO ——开源优秀的分布式对象存储系统。 适用于AI的 高性能分布式云存储 MinIO 提供高性能、与S3 兼容的对象存储系统&#xff0c;让你自己能够构建自己的私有云储存服务。 MinIO原生支持 Kubernetes&#xff0c;它可用于每个独立的公共云、每个 Kubernetes 发行版、私…...

中国34省级行政区及行政区划代码

一、34省级行政区 23个省、4个直辖市、2个特别行政区、5个自治区。 行政区行政区划代码北京市110000天津市120000河北省130000山西省140000内蒙古自治区150000辽宁省210000吉林省220000黑龙江省230000上海市310000 江苏省320000 浙江省330000 安徽省340000 福建省…...

vue、uniapp实现组件动态切换

在Vue中&#xff0c;通过使用动态组件&#xff0c;我们可以实现组件的动态切换&#xff0c;从而达到页面的动态展示效果。 vue 中 component组件 is属性 功能描述 例如&#xff1a;有多个tabs标签&#xff0c;如&#xff1a;推荐、热点、视频等。用户点击标签就会切换到对应组…...

JVM 虚拟机面试知识脑图 初高级

导图下载地址 https://mm.edrawsoft.cn/mobile-share/index.html?uuid3f88d904374599-src&share_type1 类加载器 双亲委派模型 当一个类收到类加载请求,它首先把类加载请求交给父类(如果还有父类,继续往上递交请求).如果父类无法加载该类,再交给子类加载 防止内存中出现…...

AI智能体架构设计:从成本黑洞到价值引擎的解耦之道

1. 从成本黑洞到价值引擎&#xff1a;为什么你的AI智能体架构正在吞噬预算又到了季度技术复盘会&#xff0c;财务那边递过来的云账单和工程人力成本&#xff0c;是不是又让你倒吸一口凉气&#xff1f;你看着报表上那个名为“AI智能体平台”的项目&#xff0c;它的资源消耗曲线几…...

别再死记硬背SMO公式了!用Python手写一个SVM分类器,带你一步步拆解SMO核心逻辑

用Python手写SVM分类器&#xff1a;代码驱动理解SMO算法核心在机器学习领域&#xff0c;支持向量机(SVM)以其优秀的分类性能和坚实的数学基础著称。然而&#xff0c;许多学习者在理解其核心算法——序列最小优化(SMO)时&#xff0c;往往被复杂的数学推导所困扰。本文将采用一种…...

番茄小说下载器终极指南:三步构建你的离线阅读自由王国

番茄小说下载器终极指南&#xff1a;三步构建你的离线阅读自由王国 【免费下载链接】Tomato-Novel-Downloader 番茄小说下载器不精简版 项目地址: https://gitcode.com/gh_mirrors/to/Tomato-Novel-Downloader 你是否曾在地铁里读到精彩章节时突然断网&#xff1f;是否在…...

森优时铁锌维发根养黑用三个月真实效果实测:内服营养养黑的客观测评

"森优时铁锌维发根养黑用三个月真实效果实测显示&#xff0c;针对压力、熬夜引发的早白问题&#xff0c;通过内服补充毛囊所需营养的方式&#xff0c;多数使用者能感受到发根韧性提升、新生发色素沉淀改善&#xff0c;整体改善效果因人而异&#xff0c;合规的营养补充是目…...

2026年LLM推理加速全景:量化、投机解码与KV Cache工程实战

大语言模型推理速度慢、成本高&#xff0c;是阻碍AI大规模落地的核心障碍之一。一个7B参数的模型&#xff0c;在标准配置下每秒只能生成约30个token&#xff0c;对于需要实时响应的应用来说几乎无法接受。但2026年&#xff0c;一系列推理加速技术的成熟&#xff0c;让这一局面发…...

上线前最后一道防线,DeepSeek代码审查如何帮你拦截87%的CVE类缺陷?

更多请点击&#xff1a; https://intelliparadigm.com 第一章&#xff1a;上线前最后一道防线&#xff0c;DeepSeek代码审查如何帮你拦截87%的CVE类缺陷&#xff1f; 在软件交付生命周期末期&#xff0c;传统人工代码审计与通用SAST工具常因误报率高、上下文理解弱而漏检高危漏…...

基于ESP32与MQTT的家庭环境监测系统:从传感器选型到数据可视化实战

1. 项目概述与核心价值最近几年&#xff0c;我身边越来越多的朋友开始关注家里的空气质量、温湿度这些看不见摸不着&#xff0c;但又实实在在影响生活舒适度和健康的环境指标。从新装修的房子担心甲醛&#xff0c;到有老人小孩的家庭在意PM2.5和二氧化碳浓度&#xff0c;再到南…...

终极指南:5步快速掌握免费的3D点云标注工具labelCloud

终极指南&#xff1a;5步快速掌握免费的3D点云标注工具labelCloud 【免费下载链接】labelCloud A lightweight tool for labeling 3D bounding boxes in point clouds. 项目地址: https://gitcode.com/gh_mirrors/la/labelCloud 想要为自动驾驶、机器人视觉或3D目标检测…...

sngan_projection论文解读:ICLR2018两大GAN技术的完美结合

sngan_projection论文解读&#xff1a;ICLR2018两大GAN技术的完美结合 【免费下载链接】sngan_projection GANs with spectral normalization and projection discriminator 项目地址: https://gitcode.com/gh_mirrors/sn/sngan_projection sngan_projection是一个实现了…...

16个分片+2副本:pg_shard的master_create_worker_shards最佳实践

16个分片2副本&#xff1a;pg_shard的master_create_worker_shards最佳实践 【免费下载链接】pg_shard ATTENTION: pg_shard is superseded by Citus, its more powerful replacement 项目地址: https://gitcode.com/gh_mirrors/pg/pg_shard pg_shard作为PostgreSQL的分…...