Volcano 社区 v1.7.0 版本正式发布 | 云原生批量计算

摘要:北京时间2023年1月9日,Volcano社区v1.7.0版本正式发布。

本文分享自华为云社区《Volcano 社区 v1.7.0 版本正式发布 | 云原生批量计算》,作者:华为云云原生团队 。

北京时间2023年1月9日,Volcano社区v1.7.0版本正式发布。此次版本增加了以下新特性:

  • Pytorch Job插件功能强化
  • Ray on Volcano
  • 增强Volcano对Kubernetes通用服务的调度能力
  • 支持Volcano的多架构镜像
  • 优化队列状态信息等

Volcano是业界首个云原生批量计算项目,于2019年6月在上海KubeCon正式开源,并在2020年4月成为CNCF官方项目。2022年4月,Volcano正式晋级为CNCF孵化项目。Volcano社区开源以来,受到众多开发者、合作伙伴和用户的认可和支持。截止目前,累计有490+全球开发者向项目贡献了代码。

Volcano v1.7.0 关键特性介绍

▍1. Pytorch Job强化功能插件

Pytorch是当下最流行的AI框架之一,已被广泛应用于计算机视觉,自然语言处理等深度学习领域,并且已有越来越多的用户开始以容器化的方式在Kubernetes上运行Pytorch来获得更高资源利用率和并行效率。

本次1.7版本提供了Pytorch Job强化功能插件,,免去了容器端口、MASTER_ADDR、MASTER_PORT、WORLD_SIZE、RANK环境变量等众多繁琐的手动配置环节,让用户可以用极简的方式在Volcano上运行Pytorch Job。

Volcano社区当前提供了TensorFlow、MPI和Pytorch等Job强化功能插件,帮助用户更简洁高效的运行对应的训练框架和计算作业。

此外,Volcano还提供了Job插件的扩展开发框架,满足高阶用户针对复杂场景定制Job插件的需求。

设计文档:Pytorch-plugin

http://github.com/volcano-sh/volcano/blob/master/docs/design/distributed-framework-plugins.md#pytorch-plugin

用户手册:Pytorch-plugin-user-guide

http://github.com/volcano-sh/volcano/blob/master/docs/user-guide/how_to_use_pytorch_plugin.md#pytorch-plugin-user-guide

Issue:#2292

http://github.com/volcano-sh/volcano/issues/2292

▍2. Ray on Volcano

Ray 是一个用于扩展 AI 和 Python 应用程序的统一框架,可以在任何机器、集群、云提供商和 Kubernetes 上运行,并具有不断发展完善的社区生态。

当前,机器学习工作负载的计算密集度越来越高,单节点开发环境已无法满足训练任务在资源上的需求,Ray可以将同一套代码从单机运行无缝扩展到集群中运行。Ray是面向通用场景进行的设计,可以高效运行任何类型的工作负载。

该特性实现Volcano和Ray的协同工作,使用Volcano为Ray提供批量调度功能。目前该特性已在KubeRay v0.4(http://github.com/ray-project/kuberay/releases/tag/v0.4.0)版本正式发布。

用户手册:KubeRay-integration-with-Volcano

http://ray-project.github.io/kuberay/guidance/volcano-integration/#kuberay-integration-with-volcano

Issue:

#2429:http://github.com/volcano-sh/volcano/issues/2429#213:http://github.com/ray-project/kuberay/issues/213

▍3. 增强对Kubernetes通用服务的调度能力

在不同的业务场景下,调度器发挥的价值与能力各有不同。比如,在批量计算场景中,Volcano的调度策略和能力更为丰富;通用服务调度场景中,Kubernetes默认调度器的能力更为均衡。但用户的集群中通常不会只运行一种类型的任务,在既有批量计算任务运行,又需要调度通用服务的场景下,如何兼顾不同类型任务的调度是一项值得研究的工作。

从1.7版本开始,Volcano提供对Kubernetes 默认调度器完全兼容的能力,可用于调度管理长期运行的服务。通过本次功能强化,用户可以使用 Volcano 统一调度长时间运行的服务和批处理工作负载。

重点增强项如下:

Volcano的 scheduler 和 webhook 支持多调度器

支持 NodeVolumeLimits 插件

支持 VolumeZone 插件

支持 PodTopologySpread 插件

支持 SelectorSpread插件

另外,本次版本将对Kubernetes的支持升级到了v1.25。

Issue:

#2394:http://github.com/volcano-sh/volcano/issues/2394

#2510:http://github.com/volcano-sh/volcano/issues/2510

▍4. 支持Volcano的多架构镜像

该特性通过交叉编译实现一键化编译Volcano多架构镜像功能,比如,可以在amd64架构机器上,一键化编译amd64和arm64架构的Volcano基础镜像,并上传至镜像仓库。用户安装部署时,会根据自身环境中机器架构自动选择合适的镜像运行,对开发者和用户更友好。

使用手册:building-docker-images

http://github.com/volcano-sh/volcano/blob/master/docs/development/development.md#building-docker-images

Issue:#2435

http://github.com/volcano-sh/volcano/pull/2435

▍5. 优化队列状态信息

该特性在队列状态信息中增加已分配资源实时统计功能,通过该功能,用户可以实时查看队列的资源分配情况,方便管理员动态规划资源,使集群资源得到最大化利用。Volcano通过队列的方式对集群资源进行分配管理,使用Capability字段来限制每个队列的资源上限,这是我们进行队列资源分配的硬约束。当前,在集群运行过程中,用户无法清楚的了解到队列中已分配资源和Capability中空闲资源的详细信息,有可能会在队列空闲资源不足时提交大量工作负载,导致作业挂起和autoScaler非预期的触发集群扩容,从而增加云资源的使用成本。通过该特性中新增加的状态信息,用户可以更清晰有效的管理集群资源,控制使用成本。

Issue:#2571

http://github.com/volcano-sh/volcano/issues/2571

致谢贡献者

致谢贡

Volcano v1.7.0 版本包含了来自29位贡献者的数百次代码提交,在此对各位贡献者表示由衷的感谢:

贡献者 GitHub ID:

相关链接

Release note:v1.7.0 http://github.com/volcano-sh/volcano/releases/tag/v1.7.0

Branch:release-1.7 http://github.com/volcano-sh/volcano/tree/release-1.7

深入了解Volcano

Volcano云原生批量计算项目主要用于 AI、大数据、基因、渲染等诸多高性能计算场景,对主流通用计算框架均有很好的支持。社区已吸引2.6万+全球开发者,并获得2.8k Star和670+ Fork,参与贡献企业包括华为、AWS、百度、腾讯、京东、小红书等。目前,Volcano在人工智能、大数据、基因测序等海量数据计算和分析场景已得到快速应用,已完成对Spark、Flink、Tensorflow、PyTorch、Argo、MindSpore、Paddlepaddle 、Kubeflow、MPI、Horovod、mxnet、KubeGene、Ray等众多主流计算框架的支持,并构建起完善的上下游生态。

Volcano社区技术交流地址

Volcano官网:http://volcano.sh

GitHub: http://github.com/volcano-sh/volcano

每周例会: http://zoom.us/j/91804791393

添加社区小助手k8s2222回复“Volcano”进入技术交流群

 

点击关注,第一时间了解华为云新鲜技术~

本文转载于网络 如有侵权请联系删除

相关文章

  • HTML中的setCapture和releaseCapture使用介绍

    大家好,又见面了,我是你们的朋友全栈君。setCapture函数的作用就是将后续的mouse事件都发送给这个对象,releaseCapture就是将鼠标事件还回去,由document、window、object之类的自行来处理。这样就保证了在拖动的过程中,不会由于经过了其它的元素而受到干扰 – 另外,还有一个很重要的事情是,在Win32上,mousemove的事件不是一个连续的,也就是说,并不是我们每次移动1px的鼠标指针,就会发生一个mousemove,windows会周期性检查mouse的位置变化来产生mousemove的事件。 所以,如果是一个很小的页面对象,比如一个直径5px的圆点,如果没有setCapture和releaseCapture,那么在鼠标按住之后,快速的移动鼠标,就有可能鼠标移动走了,但是小圆点还在原地,就是因为下一次的mousemove事件已经不再发给这个圆点对象了。web开发和windows开发最大的区别就是windows开发是有状态的,而web开发是无状态的,在windows中,一切操作都可以由程序来控制,除非强制执行ctrl+alt+del;但web操作就

  • THINKPHP框架的优秀开源系统推荐

    THINKPHP框架的优秀开源系统推荐众所周知,国内众多优秀的开源框架,ThinkPHP从诞生以来一直秉承简洁实用的设计原则,在保持出色的性能和至简的代码的同时,也注重易用性。并且拥有众多的原创功能和特性,在社区团队的积极参与下,在易用性、扩展性和性能方面不断优化和改进,众多的典型案例确保可以稳定用于商业以及门户级的开发。在thinkphp发展的同时也诞生了一批基于thinkphp的优秀系统,在这里我们看看都有哪些。1.内容管理系统:ThinkCMFXThinkCMF是一款基于PHP+MYSQL开发的中文内容管理框架。ThinkCMF提出灵活的应用机制,框架自身提供基础的管理功能,而开发者可以根据自身的需求以应用的形式进行扩展。每个应用都能独立的完成自己的任务,也可通过系统调用其他应用进行协同工作。在这种运行机制下,开发商场应用的用户无需关心开发SNS应用时如何工作的,但他们之间又可通过系统本身进行协调,大大的降低了开发成本和沟通成本。ThinkCMFX是在ThinkCMFV1.1.1基础上采用最新的ThinkPHP3.2.2框架的优化版本,以满足更高端用户需求,支持PHP5.3.0+

  • Windows chrome再爆0day

    参考资料:https://mp.weixin.qq.com/s/G-ffg_TDRkvcwM4tug8ZlAhttps://github.com/avboy1337/1195777-chrome0day0x01漏洞描述在2021年4月13日之前,WindowsChrome浏览器在版本号小于89.0.4389.114的版本中存在非沙箱模式0day,4月14日windowsChrome浏览器全部更新,目前最新版本号为89.0.4389.128,该最新版本存在远程代码执行漏洞(需要关闭沙箱!!!)0x02漏洞复现网上已有poc:https://github.com/avboy1337/1195777-chrome0day同样需要使用非沙箱模式进行运行:复现截图效果如下:复现视频如下: 0x03最后前天和他们说,你Chrome浏览器更新了也没用,最新版存在0day,昨天更新之后,又爆出一个0day。。。。最近一直在传微信自带浏览器的攻击链,我自己未能复现(菜),如果真的有大佬可以复现的话,能否分享下思路?复制

  • 再见笨重的ELK!这套轻量级日志收集方案要火!

    之前一直使用的日志收集方案是ELK,动辄占用几个G的内存,有些配置不好的服务器有点顶不住!最近发现一套轻量级日志收集方案:Loki+Promtail+Grafana(简称LPG),几百M内存就够了,而且界面也挺不错的,推荐给大家!简介LPG日志收集方案内存占用很少,经济且高效!它不像ELK日志系统那样为日志建立索引,而是为每个日志流设置一组标签。下面分别介绍下它的核心组件:Promtail:日志收集器,有点像Filebeat,可以收集日志文件中的日志,并把收集到的数据推送到Loki中去。Loki:聚合并存储日志数据,可以作为Grafana的数据源,为Grafana提供可视化数据。Grafana:从Loki中获取日志信息,进行可视化展示。日志收集流程图安装实现这套日志收集方案需要安装Loki、Promtail、Grafana这些服务,直接使用docker-compose来安装非常方便。使用的docker-compose.yml脚本如下,直接使用docker-compose命令运行即可;version:"3" services: #日志存储和解析 loki: imag

  • 新型开源语音编码器Lyra最新进展

    问题背景:Google最近开源了一种语音压缩的新型超低比特率编解码器,这种编码器的最大特点是基于机器学习原理,能够使用最少的数据来重建语音,这是和传统AAC和Opus编码原理的本质区别,这种基于机器学习的编码思想也逐渐应用的图像编码和视频编码上。 其次Lyra牛逼的地方在于不仅实现了以每秒3kb网络宽带提供听起来自然清晰的语音聊天,还可以在仅90ms延迟的情况下在从高端云服务器到中端智能手机的任何设备上运行。随着谷歌的推广,估计WebRTC后续也有相关动作支持起来,特别在网络比较差带宽较低的场景下进行实时音视频互动有一定的优势。目前已经在GoogleDuo中进行了应用。PapersKleijn,W.B.,Lim,F.S.,Luebs,A.,Skoglund,J.,Stimberg,F.,Wang,Q.,&Walters,T.C.(2018,April).Wavenetbasedlowratespeechcoding.In2018IEEEinternationalconferenceonacoustics,speechandsignalprocessing(ICASSP)(pp.

  • linux虚拟网络设备之vlan配置详解

    简介VLAN是网络栈的一个附加功能,且位于下两层。首先来学习Linux中网络栈下两层的实现,再去看如何把VLAN这个功能附加上去。下两层涉及到具体的硬件设备,日趋完善的Linux内核已经做到了很好的代码隔离,对网络设备驱动也是如此,如下图所示:这里要注意的是,Linux下的网络设备net_dev并不一定都对应实际的硬件设备,只要注册一个structnet_device{}结构体(netdevice.h)到内核中,那么这个网络设备就存在了。该结构体很庞大,其中包含设备的协议地址(对于IP即IP地址),这样它就能被网络层识别,并参与路由系统,最有名的当数loopback设备。不同的设备(包括硬件和非硬件)的ops操作方法各不相同,由驱动自己实现。一些通用性的、与设备无关的操作流程(如设备锁定等)则被Linux提炼出来,我们称为驱动框架。linux虚拟网络设备之vlan配置我们通过一个网桥两个设备对,来连接两个网络名字空间,每个名字空间中创建两个vlan借助vconfig来配置vlan:#创建网桥 brctladdbrbr-test-vlan #创建veth对儿 iplinkaddveth0

  • Shaka Streamer:直播/点播内容准备工具

    本文是来自SeattleVideoTech的演讲,讲者是来自于Google公司的JoeyParrish。使用ffmpeg来准备视频内容需要写出冗长的难以理解的脚本,本次演讲介绍了ShakaStreamer这一开源工具来简化配置。ShakaStreamer包装了ffmpeg和ShakaPackager,使用简单的配置文件来代替复杂的命令行,以此简化直播、点播、DASH和HLS的内容准备工作。工具通过pip发布:pip3installshaka-streamer,支持Linux和Mac平台。工具不做分辨率上变换。单纯使用ffmpeg来准备1080p的视频内容,可能需要232词的难以理解的命令,使用ShakaPackager只需86词,使用ShakaStreamer则可以利用配置文件,方便维护:shaka-streamer-iinput.yaml-ppipeline.yaml-cgs://bucket/folder复制输入配置示例:inputs: -name:llama_original.mp4 -media_type:viedo -name:llama_original.mp4 -

  • [Java基本功] 一文搞懂Java中的异常机制

    本文非常详尽地介绍了Java中的异常,几乎360度无死角。从异常的概念,分类,使用方法,注意事项和设计等方面全面地介绍了Java异常。为什么要使用异常首先我们可以明确一点就是异常的处理机制可以确保我们程序的健壮性,提高系统可用率。虽然我们不是特别喜欢看到它,但是我们不能不承认它的地位,作用。在没有异常机制的时候我们是这样处理的:通过函数的返回值来判断是否发生了异常(这个返回值通常是已经约定好了的),调用该函数的程序负责检查并且分析返回值。虽然可以解决异常问题,但是这样做存在几个缺陷:1、容易混淆。如果约定返回值为-11111时表示出现异常,那么当程序最后的计算结果真的为-1111呢? 2、代码可读性差。将异常处理代码和程序代码混淆在一起将会降低代码的可读性。 3、由调用函数来分析异常,这要求程序员对库函数有很深的了解。在OO中提供的异常处理机制是提供代码健壮的强有力的方式。使用异常机制它能够降低错误处理代码的复杂度,如果不使用异常,那么就必须检查特定的错误,并在程序中的许多地方去处理它。而如果使用异常,那就不必在方法调用处进行检查,因为异常机制将保证能够捕获这个错误,并且,只需在一个地

  • Kubernetes揭秘:解决服务依赖问题

    本系列文章探讨了企业客户在使用Kubernetes时遇到的一些常见问题。ContainerService客户经常提出的一个问题是,“我如何处理服务之间的依赖关系?”在应用程序中,组件依赖性指的是中间件服务和业务服务。在传统的软件部署方法中,必须按特定顺序完成应用程序启动和停止任务。当使用Kubernetes,DockerSwarm和其他容器编排技术在分布式环境中部署应用程序时,不同的组件会同时启动,因此无法确保某个启动顺序。此外,当应用程序运行时,它们所依赖的服务可能会失败或被迁移。因此,解决容器之间的服务依赖性是客户经常提出的问题。方法1:检查应用程序中的依赖项我们可以在应用程序启动逻辑中添加服务依赖性检查逻辑。如果无法访问应用程序所需的服务,则会重试该服务。如果在经过一定次数的重试后服务仍然无法访问,则应用程序会自动放弃。根据容器的重启策略,Kubernetes和Docker等待一段时间后再自动放弃。在下文中,我们使用一个简单的Golang应用程序作为示例来检查MySQL服务依赖性是否已准备就绪。... //Connecttodatabase. hostPort:=net.Join

  • golang goquery selector(选择器) 示例大全

    本文为原创文章,转载注明出处,欢迎扫码关注公众号flysnow_org或者网站http://www.flysnow.org/,第一时间看后续精彩文章。觉得好的话,顺手分享到朋友圈吧,感谢支持。 最近研究Go爬虫相关的知识,使用到goquery这个库比较多,尤其是对爬取到的HTML进行选择和查找匹配的内容时,goquery的选择器使用尤其多,而且还有很多不常用但又很有用的选择器,这里总结下,以供参考。如果大家以前做过前端开发,对jquery不会陌生,goquery类似jquery,它是jquery的go版本实现。使用它,可以很方便的对HTML进行处理。基于HTMLElement元素的选择器这个比较简单,就是基于a,p等这些HTML的基本元素进行选择,这种直接使用Element名称作为选择器即可。比如dom.Find("div")。funcmain(){ html:=`<body> <div>DIV1</div> <div>DIV2</div> <span>SPAN<

  • Openresty最佳案例 | 第7篇: 模块开发、OpenResty连接Redis

    Lua模块开发在实际的开发过程中,不可能把所有的lua代码写在一个lua文件中,通常的做法将特定功能的放在一个lua文件中,即用lua模块开发。在lualib目录下,默认有以下的lua模块。lualib/ ├──cjson.so ├──ngx │├──balancer.lua │├──ocsp.lua │├──re.lua │├──semaphore.lua │├──ssl ││└──session.lua │└──ssl.lua ├──rds │└──parser.so ├──redis │└──parser.so └──resty ├──aes.lua ├──core │├──base64.lua │├──base.lua │├──ctx.lua │├──exit.lua │├──hash.lua │├──misc.lua │├──regex.lua │├──request.lua │├──response.lua │├──shdict.lua │├──time.lua │├──uri.lua │├──var.lua │└──worker.lua ├──core.lua ├──dn

  • 快速排序到底是什么?

    1,快速排序概念通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。主要采用分治法和挖坑填数等方法,分治法就是大问题分解成各个小问题,对小问题求解,使得大问题得以解决。2,算法思路我们先搞清楚这个堆排序思想,先把逻辑搞清楚,不着急写代码。我们首先有一个无序数组,比方说int[]arr={4,2,8,0,5,7,1,3,9}; 复制2.1,第一步,取基准数基准数(枢轴),取数组的第一个元素,此时基准数:arr[0]=4基准数图并定义两个变量i和j分别指向无序数组的第一个元素start和最后一个元素end。//起始 inti=start; intj=end; //获取基准数 inttemp=arr[start]; 复制2.2,第二步,分区过程分区过程,将比基准数大的数全放到它的右边,比基准数小的或者相等的数全放到它的左边。我们首先把第一个元素arr[0]=4定义为基准元素,此时数组第一个位置就是坑,那么我们要从数组的右边向左开始查找小于基准数的元素,并与坑互换位置。从右至左查找while(i<

  • 我的BFS格式

    写在正文前 BFS大家肯定都知道(前不久刚讲过),这里就不讲了(以后没准会),本文主要讲一下BFS格式。 正文 BFS(广度优先搜索),是将搜到的每一个数压入队列,达到广度,所以一般用到queue和pair来实现(你也可以手打),拿p2895举例,代码如下: #include<iostream> #include<cstring> #include<utility>//pair所用库 #include<queue> usingnamespacestd; intn,a[401][401]; intd[401][401]; intv[401][401]; intdx[5]={0,0,0,1,-1}; intdy[5]={0,1,-1,0,0}; queue<pair<int,int>>q; intcmp(inta){ if(a==-1)return999999; returna; } intmain(){ cin>>n; memset(a,-1,sizeof(a)); for(inti=1;

  • linux修改权限

    修改system目录(包括子目录)的所有者和组 sudochown-Rseven:sevensystem复制  

  • 武大OJ 706.Farm

    FarmerJohnhasafarm.Betsy,afamouscow,lovesrunninginfarmerJohn'sland.ThenoiseshemademakesJohnmad.SohewantstorestricttheareaBetsycanrun.Thereare nn (4<n\le20000004<n≤2000000)pointsofinterest(orPOI)onthefarm,thei-thonelocatedat (x_i,y_i)(x​i​​,y​i​​), 0\le|x_i|,|y_i|\le10^60≤∣x​i​​∣,∣y​i​​∣≤10​6​​.SofarmerJohnsaid:Youcanselectfourpoints,andtheareayoucanrunistheconvexhullofthefourpointsyouselect.Betsyisclever,butshedoesn'tlikecomputing,sosheaskedyouforhelptocalculatethemaxar

  • [心得] SQL Server Partition(表分區) 資料分佈探討

    最近在群裡有個朋友問了個問題是這樣的 用户表有一千多万行,主键是用户ID,我做了分区。但经常查询时,其它的表根据用户ID来关联,这样跨区查询,reads非常高。有什么好的处理办法?不分区的话,索引维护要好久的时间 在查看了他提供的分區資訊後,發現只有23個分區(包含一定要有的Null分區) Null分區在這裡的定義其實很簡單,當你的資料沒有辦法放到你先前建立的分區時,就會將該資料放到所謂的Null分區(預設分區)。 因此如果在探尋分區規則時沒有依照現有的資料進行分區的設計,將會很容易導致資料偏斜(DataBias),一但資料出現了偏斜時在查找時就會很容易在NULL區出現過多的讀取 以今天的案例來看待,當要比對的ID不在這22個分區中時就會到NULL分區進行查找的動作。而在群友提供的資料中其實有出現了oGpI0w_、mGpI0w等字眼 可以想見的是,該NULL分區的資料是相當多的 以下就一個測試情境來探討在分區規則不同時的效能比較 首先建立二張結構一樣的表,資料量約一千二百萬筆 接下來分別建立給表Demo1與Demo2的表分區函數(請注意圖中的註解)(注意,以下示範並沒有利用到分區F

  • Oracle行转列、列转行的Sql语句总结

    多行转字符串 这个比较简单,用||或concat函数可以实现  SQLCode  12  select concat(id,username) str from app_userselect id||username str from app_user字符串转多列 实际上就是拆分字符串的问题,可以使用substr、instr、regexp_substr函数方式 字符串转多行 使用unionall函数等方式 wm_concat函数 首先让我们来看看这个神奇的函数wm_concat(列名),该函数可以把列值以","号分隔起来,并显示成一行,接下来上例子,看看这个神奇的函数如何应用准备测试数据  SQLCode  123456  create table test(id number,name varchar2(20));insert into tes

  • nacos

    startup.sh-mstandalone复制  访问:http://localhost:8848/nacos/  默认用户名和密码都是nacos 项目中集成 pom springboot要低于2.4版本 <?xmlversion="1.0"encoding="UTF-8"?><projectxmlns="http://maven.apache.org/POM/4.0.0"xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"        xsi:schemaLocation="http://maven.apache.org/POM/4.0.0https://maven.apache.org/xsd/maven-4.0.0.xsd">   <modelVersion>4.0.0</modelVersion><!---->

  • 每日一题 0210

    (2022.02.10)每日一题(labuladong版)二叉树相关 今天去医院打了狂犬疫苗,到家都三点多了,把昨天没看完的左程云看完,主要讲了链表相关的题目,有两个技巧,一个是快慢指针,一个是额外数据结构记录。 左神提到几个面试关键点,笔试主要时间复杂度着重,空间复杂度尽可能控制,控制不了就不控制了,因为笔试过了就完了,要快。 面试的时候,主要考你的coding能力,时间复杂度和空间复杂度要并重,要有亮点的解法。 接下来就是继续二叉树的题目: classSolution{ private: unordered_map<int,int>index; public: //我用了好多辅助空间。。。。。,其实主要就是确定根节点,并根据根节点的index获取左右子树在先序和中序数组内的范围,进行递归建树 TreeNode*buildTree(vector<int>&preorder,vector<int>&inorder){ if(preorder.size()==0||inorder.size()==0){ returnnullptr

  • 动态修改maven的jdk版本

    当环境变量jdk为1.7,项目为jdk1.8,用mvncleanpackage指令打包项目时,想不修改环境变量的情况下,修改maven的jdk版本 方法如下: 官网给出了方法 https://maven.apache.org/plugins/maven-compiler-plugin/examples/compile-using-different-jdk.html 1.pom.xml中添加maven插件 <plugin> <groupId>org.apache.maven.plugins</groupId> <artifactId>maven-compiler-plugin</artifactId> <version>3.8.1</version> <configuration> <verbose>true</verbose> <fork>true</fork> <executable>${JAVA_1_8_HOME}/bin/

  • 2021 牛客多校 第六场 选做

    比赛link 施工中…… 比赛小结 净贡献若干发罚时/cy D.GamblingMonster 题意 有一个转盘,每次转动得到\(0\simn-1\)(\(n\)为\(2\)的次幂)的概率分别给出。最开始你有一个数\(x\),每次转动转盘得到一个数\(y\),如果\(x\oplusy>x\)就令\(x=x\oplusy\),否则\(x\)不变。求使\(x=n-1\)期望转动转盘的次数。 Solution 从后往前dp,列出式子: \[f_i=\sum_{j>i,j\oplusk=i}f_j\timesp_k+\sum_{j\oplusi\lei}f_i\timesp_j \]设\(s_i=\sum_{j\oplusi\lei}p_j\),改写一下: \[f_i=\left(\sum_{j>i,j\oplusk=i}f_j\timesp_k+1\right)\times\frac{1}{1-s_i} \]计算\(s_i\)比较简单,我们可以枚举\(j\)的最高位,用前缀和计算一下即可。 计算\(\sum_{j>i,j\oplusk=i}f_j\timesp_k\)

相关推荐

推荐阅读