前言
很开心能够参加这次2021华为软挑的比赛，喜欢这样充满挑战性，在任务驱动下不断学习，主动思考解决问题的方法的经历，以及与一群小伙伴讨论问题，一起学习成长进步的感觉，收获满满，真的很棒！
于是在此记录下一点心得，留下我曾经来过的痕迹，为自己这些年来参加的大大小小各式各样的比赛再添一笔，也留下这一段收获满满、值得回味的记忆吧~
赛题解读
今年的赛题是关于对云上资源的规划和调度问题。给了一系列有着不同CPU、内存资源量的服务器，根据用户请求的不同 CPU与内存量的虚拟机资源分配合适的服务器。
资料收集
首先到处查询各种资料，有讲到这个问题的任务可以看成一个变种的多维装箱问题，也就是一个np难问题，比较难找到一个精确的解，但是我们可以找出一个趋近于最优解的方案。
解读参考：
与赛题中服务器选型和请求调度这两个问题最为相似的运筹优化模型是Vector Bin Packing（多维装箱问题），该问题是传统Bin Packing问题的一个变种。该问题模型与赛题中的定义非常相似，如果不考虑虚拟机的删除和服务器的能耗成本，那么服务器选型 + 请求调度这两个问题与该模型是完全等价的。而如果加入虚拟机的删除，则该问题会变成动态的版本，对应于Dynamic Bin Packing的相关扩展模型。
以及参考里面还提到了阿姆达尔定律太懂，于是也去查了一下：
一开始想的是通过服务器CPU资源与内存资源跟机器售价与每日花费之比进行排序，找出性价比最高的一款或几款服务器进行循环购买。于是来整理数据，做图表进一步分析，却在其中发现其实机器售价，每日花费与资源值之间是存在一个线性比例关系的，资源越多，对应的售价与每日花费一样也会增多，且机器售价与每日花费之间的比例也是呈线性变化的。也就是说以这样的方式来排序服务器，对于降低成本结果很可能并没有非常大的帮助。
反倒是虚拟机与服务器的共有属性里面CPU资源与内存资源之间的比例存在很有趣的关系，不同类型的服务器这二者的比例差距大相径庭，于是我决定改变策略，通过分析虚拟机，请求队列里所有虚拟机的CPU资源与内存资源比例作为参考系数 对服务器进行排序，找出与此比例系数最相近的服务器依次排序。于是开始尝试编写算法，这个方法果然好用，一下子让整体成本下降了很多。时间性能优化
其中对服务器进行排序的时候也多方考虑更加省时的算法。因为项目要求在90秒内需要运行完毕，最开始的时候，我们的程序其实一直是要运行超时的。一开始设计数据结构的时候，都只是简单地使用map来设计服务器表、虚拟机表等各项表。map一种根据〈key, value〉进行键值对映射存储数据的数据结构，默认时会以key的值进行排序，内部实现是红黑树的原理，可进行自动排序。他的有序性也是map的优势所在，但对于查询来说却没有unordered_map更省时间。 unordered_map内部是以哈希表的数据结构来进行存储，虽然建立的时候会有一些耗时，但查询的时候是相当快的，时间复杂度只需O(1)。map是有排序的好处，然后我们当时的键值是设置成了服务器类型名称来进行索引查询，我们还是得重写按我们算法的排序方式，根据CPU/内存这两大属性的value值得出比例进行排序，所以map的优势也就对于我们没有什么用处了。我们把map改为unordered_map之后，速度果然大幅度提升了，本地运行只需要20多秒即可完成，与原先超时90秒还迟迟不能完成的速度相比，完全是大大提高了。顺便把各种能改成unordered_map的map都一并换了，惊讶的发现调用排序函数前的顺序更加随机之后，成本居然也莫名降低了不少，也可能是偶然吧，真是双喜临门，可喜可贺，吼吼~
排序算法及相关数据结构优化
啊，对了，在这里要感谢队友进行的排序算法优化。让服务器表可以按unordered_map进行CPU比memory这两个value值属性的排序，同时又实现了可以按照服务器ID 对服务器进行查询的功能，这为后续当遇到删除虚拟机的请求指定时，对照服务器虚拟机分配表中，服务器ID进行对应进行的查找，提供了很大的便利。以及使用set集合的方式来记录每个服务器的剩余资源，还为此编写了添加已有服务器资源表、更新已有服务器资源表的方法，通过删除、更改再插入的方式更新，使得按照服务器ID 进行查询的已有服务器资源表依旧可用借助set默认的排序规则按ID进行排序，更适合于实际操作的要求。
服务器预购方案优化
以及在开始所有的请求之前，我会先按照进行排序处理后的服务器列表默认预购一批服务器，一开始选的是预购前10%的服务器，这样数量的服务器当然是可以满足测试数据的要求的，后来又比较了购买前5%、4%、6%等比例的服务器，发现预购前5%的服务器可以使成本进一步优化降到更低。
服务器前两位预设方案的探索与优化
后来，在实验中发现，依次根据每次来的虚拟机请求进行服务器分配时，当最优比例服务器不符合时才往下寻找次优的服务器，这样的策略处理数据是从整体来看，主要就是排名在前两位的服务器被购买就已经可以符合整个的需求了，也就是说在大多数情况下最关键的就是服务器列表状态是在前两位的服务器。于是开始研究进一步的优化策略，将排名第2位的服务器进一步优化设置。大多数情况下，CPU比慢慢锐的比例在服务器表中寻找，未必能找到百分百匹配的，总是会比所得的标准比例略高或略低于是思考决定，在之前按照性价比排序后，取前7%的服务器进一步优化考虑，将排名第二的服务器设置为这前7%的服务器中，cpu/内存比尽可能与排名第一的服务器互补的服务器，即这两者服务器加权后的服务器最接近所得的虚拟机需求的CPU/内存比例。这样一来所得的成本果然又被优化降低了不少。（不过后来调程序的时候，不知哪里出了问题，上传上去总是 资源分配不足之类的问题也一直没调通，不过这是后话了，经过本地测试的确是性能提高了不少。若是上传能够调得通的话，排名应该又能上升不少吧，有点小遗憾，但是学到了不少知识，还是挺有收获的啦）
分配虚拟机对应服务器的部分
我们决定用装箱问题的思路，首先按照我们当前拥有的服务器，按照剩余资源量的大小从小到大进行排序。然后依次处理各条虚拟机请求，按照贪心算法的方式，按照排序好的服务器剩余资源表（即所拥有的箱子）依次进行尝试放入，每次将单个箱子所填充物虚拟机器请求资源价值量最大化，从而使全局资源分配也达到最优。这个思路也是让我们在初赛上传后，成本能够下降到大致在15亿多的水平的一个很关键的思路。后来发现其实这正是装箱算法里面的一个优化方案，误打误撞居然使用了理论上最优的的方法，哈哈。
装箱问题知识点参考资料调试
C++指定输入格式
问题：需输入的数据过多，控制台窗口缓存不足，用复制粘贴的方式难以在控制台一次性读入全部测试数据（什么我每次测试都手打几千行测试数据！那是不可能哒┗|｀O′|┛ 嗷~~），在控制台窗口属性页设置缓存大小最大也只能设置为999，还是不够用。
解决：后来决定使用重定向的方法，读取文件里的数据作为输入，虽然比赛提交格式是要求不额外读取外部文件的，但思维不能太拘泥教条墨守成规嘛，实验时还是可以用重定向读取进来大量数据方便测试，待准备就绪后再把对应那几句代码注释掉再上传即可。查询资料学习到，其实重定向代码也并不复杂，用来测试操作还是很方便的啦~
C++输入输出重定向（3种方法）对后续优化的思考
对于此次服务器资源分配与调度问题的最优化方案求解，其实如果当时自己早点安排，把握好时间分配，不至于最后阶段时间那么紧的话，还可以进一步优化迁移调度算法。在每一天的请求处理完后，以及新一天请求到来之前，考虑虚拟机迁移调度的方案，当前我们的算法虚拟机迁移量为0，看到排行榜上在我们前排的队伍里迁移调度量为0的队伍是极其极其少的，要是加上这一部分的优化，效果应该会更好些。其实，中途也有稍微尝试写了点迁移调度算法，但也由于我们一开始整体大的思维设计的分配方案用的是贪心算法，所以每次处理到来的虚拟机请求时已经是让每次请求达到最优的效果，以每一次的局部最优从而达到整体全局最优的效果。所以当del类型虚拟机请求量较小，不足以让足够多的已使用服务器都出现较大合适的剩余空间，达到让其中一些所耗资源量较小的已用服务器上的虚拟机全部迁移到其他已用服务器，让自已空闲出来的话，迁移并不能达到很好的节约未使用服务器的每日花费的目的。实验测试也的确如此，甚至居然出现越迁移花费越多的情况！也可能跟我们处理虚拟机请求时总是一条条按队列顺序依次处理，而不是先从全局一口气考虑好所有情况进行分配有关，不过那样的话对为了请求都是默认已知的（初赛这样是可以完成任务的，不过后来我也持续关注了一下后期复赛要求的任务进化，需要对虚拟机请求进行一定的预测，也就是难以使用一开始就一口气分析完全部请求的方案了），后来也一直没想到更好的方案。
感悟
我觉得自己还是超级喜欢这样类型的比赛的，在这段时间里面围绕一个具体的问题，自主对题目进行整理分析，并在 上查找资料，和同学们讨论，对数据分析，然后设计出自己的算法 不断的调试优化代码，看着排行榜上的成绩，不断与大家比拼……短短的这段时间，感觉学到了很多的知识，而且一点点的绞尽脑汁想优化的办法，看着排名榜上的排名一丢丢的挪进一点就会很开心，以及还有看到排行榜上前几位的大佬们不断的卷来卷去，群英角逐，彼此不断优化改进算法降低成本，大家努力地打比赛的样子，也真的好可爱，真是很有意思的事情。很开心能够参加这次比赛，喜欢这样充满挑战性，在任务驱动下不断学习，主动思考解决问题的方法的经历，以及与一群小伙伴讨论问题，一起学习成长进步的感觉，收获满满，真的很棒！
啊对了，最终比赛结果是入围上合赛区初赛前64强，队名叫做“蜗牛之家”，排名好像是第46名，虽然中途对服务器性价比优化排序的算法在上传时遇到点问题没调通，没法让排名再前一些，但整个比赛真的学到了不少知识，不亏~ 起初也是比赛中途才临时决定半路参赛，本来都没想到能得什么奖，也就是冲着锻炼自己而去的，这个结果已经超乎预料了，我感觉已经很开心啦~虽然自己就像在蜗壳中的一只小小的蜗牛，能量很小，总是一点一点缓缓向前，但也要不忘初心，迎接挑战，一直一直努力向前呀，前方的路，虽远必至，我们的征途可是星辰大海呐！背上满载知识的蜗壳行囊继续出发，冲鸭( ?? ω ?? )y文章知识点与官方知识档案匹配，可进一步学习相关知识算法技能树首页概览34273 人正在系统学习中
声明：本站部分文章及图片源自用户投稿，如本站任何资料有侵权请您尽早请联系jinwei@zod.com.cn进行处理,非常感谢！