LC4给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。算法的时间复杂度应该为 O(log (m+n)) 。class Solution { public: double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { int m = nums1.size(), n = nums2.size(), k = 0, i = 0, j = 0;//把重复使用的数据用一个变量代替 vector<int> sub(m + n, 0); while (i < m && j < n) sub[k++] = nums1[i] < nums2[j] ? nums1[i++] : nums2[j++]; while (i < m) sub[k++] = nums1[i++]; while (j < n) sub[k++] = nums2[j++]; return k % 2 ? sub[k / 2] : (sub[k / 2] + sub[k / 2 - 1]) / 2.0; // 判断奇偶 } };//要会用a[i++]-->>a[i],i++;

LC2给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。请你将两个数相加，并以相同形式返回一个表示和的链表。你可以假设除了数字 0 之外，这两个数都不会以 0 开头。输入：l1 = [2,4,3], l2 = [5,6,4] 输出：[7,0,8] 解释：342 + 465 = 807./** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode*dummy=new ListNode(); ListNode*cur=dummy;//用dummy作哨兵节点head=dummy->next int carry=0; while(l1||l2||carry){ carry+=(l1?l1->val:0)+(l2?l2->val:0);//(l1?l1->val:0)当l1=nullptr很好的避免了空节点的干扰 cur=cur->next=new ListNode(carry%10);//精简代码相当于 //cur=cur->next;cur=new ListNode(carry%10); carry/=10; if(l1)l1=l1->next; if(l2)l2=l2->next; } return dummy->next; } };

interactor.cpp的第356-357行，判断条件写的是>1，这样的话对于pg.partitions等于1的情况就会出错（与题目描述不符）。

算法步骤每次POD请求过来了，通过估价函数+排序，获取每一个Pod亲和的Flavor列表利用DFS递归指定层数，搜索每个Flavor亲和的Pod列表第一轮分配：遍历每个Flavor，遍历Flavor亲和的Pod列表，依次采用FirstFit分配第二轮分配：遍历每个Flavor，遍历Flavor亲和的Pod列表，通过估价函数设计，是否需要新建Node，还是允许其填入其他未亲和的Node中

华为算法精英实战营第4期 - 云集群成本优化 参赛经验分享赛题核心点介绍由于未提供测试集特征，主要通过线上测试调整放置策略。最核心的一条是不同规格的Pod要放在不同的Node中算法步骤每次CREATE时，将节点按CPU由大到小排序寻找同类CPU MEM空闲节点优先放入放不下时开新的Node,新的Node通过拟合了一个代价函数来选取代价函数由前200个Pod信息更新得到,每个Node是放更多的Pod还是更少的Pod重复以上步骤

中奖结果公示感谢各位小伙伴参与本次活动，欢迎关注华为云DTSE Tech Talk 技术直播更多活动~本次活动获奖名单如下：请@Sakura、 于7月8日前在此问卷中反馈您的中奖邮寄信息~直播简介【直播主题】智能优化揭秘 - GaussDB数据库查询重写的自动挖掘与生成【直播时间】2024年6月26日 16:30-18:00【直播专家】王肇国 上海交通大学软件学院副院长Ethan 华为云数据库 DTSE技术布道师【直播简介】在数据库世界里，查询重写是提升性能的关键环节。现有系统依赖人工发现重写规则，过程缓慢且费时。而WeTune的诞生，彻底改变了这一现状！WeTune是一种革命性工具，能自动发现新重写规则，通过枚举和验证等效查询计划，大幅优化查询性能。加入我们的直播，共同探索数据库查询优化的前沿技术，见证性能提升的神奇瞬间！活动介绍【互动方式】直播前您可以在本帖留下您疑惑的问题，专家会在直播时为您解答。直播后您可以继续在本帖留言，与专家互动交流。我们会在全部活动结束后对参与互动的用户进行评选。【活动时间】即日起—2024年6月27日【奖励说明】评奖规则：活动1：直播期间在直播间提出与直播内容相关的问题，对专家评选为优质问题的开发者进行奖励。奖品：华为云定制T恤活动2：在本帖提出与直播内容相关的问题，由专家在所有互动贴中选出最优问题贴的开发者进行奖励。奖品：华为云定制Polo衫​更多直播活动直播互动有礼：官网直播间发口令“华为云 DTSE”抽华为云定制雨伞等好礼。​【注意事项】1、所有参与活动的问题，如发现为复用他人内容或直播间中重复内容，则取消获奖资格。2、为保证您顺利领取活动奖品，请您在活动公示奖项后2个工作日内私信提前填写奖品收货信息，如您没有填写，视为自动放弃奖励。3、活动奖项公示时间截止2024年6月29日，如未反馈邮寄信息视为弃奖。本次活动奖品将于奖项公示后30个工作日内统一发出，请您耐心等待。4、活动期间同类子活动每个ID（同一姓名/电话/收货地址）只能获奖一次，若重复则中奖资格顺延至下一位合格开发者，仅一次顺延。5、如活动奖品出现没有库存的情况，华为云工作人员将会替换等价值的奖品，获奖者不同意此规则视为放弃奖品。6、其他事宜请参考【华为云社区常规活动规则】。

核心策略：   在测试中发现线上baseline是基于一个服务器只放一个节点的方法，为此分别使用模拟退火、服务器只存放同一种结点的贪心以及一个服务器只放一个节点三个策略，用评价公式分别对三个策略打分，哪个分数高就选用哪种策略。算法细节：1、前面时刻购买的服务器利用率小于某个值后不要强塞节点2、开始先用一个服务器只存放一种结点的贪心策略，程序运行一会，数据统计有参考性时再采用动态策略3、一组数据分配到最后只剩余一个节点时，只要为该节点购买最优的服务器， 不要考虑下一组数据的节点

为什么任务书没有时间和内存的限制

Q：这是一场什么样的比赛？“挑战杯”全国大学生课外学术科技作品竞赛是由共青团中央、中国科协、教育部、中国社会科学院和全国学联共同主办的全国性的大学生课外学术实践竞赛。“揭榜挂帅”作为“挑战杯”专项赛之一，企业提需求出题，面向高校广发“英雄帖”，学生团队竞争揭榜。旨在促进产教融合，打造校、企、研成果转化为“桥头堡”。Q：谁可以参加这个比赛？有学生赛道和青年科技人才两个赛道；学生赛道：2024年6月1日以前正式注册的全日制非成人教育的各类高等院校在校专科生、本科生、硕士研究生（不含在职研究生）均可申报作品参赛，以个人或团队形式参赛均可。本校硕博连读生（直博生）若在2024年6月1日以前未通过博士资格考试的，可以按研究生学历申报作品。没有实行资格考试制度的学校，前两年可以按硕士学历申报作品。本硕博连读生，按照四年、两年分别对应本、硕申报，后续则不可申报。青年科技人才赛道：在高等学校、科研院所、企业等各类创新主体中工作的、具有一定科研热情和科研能力的青年科技工作者或者在读博士。参赛人员年龄应在18至35周岁，即1989年6月1日至2006年6月1日期间出生。符合高校学生赛道报名条件的在读博士不得参加青年科技人才赛道比赛，高校青年教师在指导学生参赛的同时不得以参赛人员身份参加同一选题比赛，发榜单位及同发榜单位有相关隶属关系单位的青年不得参加本单位选题比赛。Q：怎么报名参加比赛？登录挑战杯官网（https://fxyh-t.bocmartech.com/jbgs/#/login），在线填写报名信息；点击“挑战杯”官网左侧“作品报名”选项，下载报名信息表打印，并加盖学校公章回传至官网；选手需登录华为云大赛平台（学生：cid:link_0；青年科技人才赛道：https://competition.huaweicloud.com/information/1000042071/introduction）进行实名校验；点击华为云大赛平台菜单栏中的“我的团队”，并点击“组建团队”，所有成员都必须完成实名校验并加入该团队。Q：有问题如何求助？论坛发帖求助：比赛过程中参赛选手可以在论坛中发帖，详细描述您遇到的问题，大赛组委会工作人员将会在工作日工作时间09:00-18:00在社区回复（为保证大赛公平公正原则，大赛官方仅针对报名方式、赛制、赛题、大赛安排等问题进行答疑）。赛事交流群求助：请扫描进入交流群，赛事相关资讯也会第一时间在群内同步，请所有报名选手务必加群。                                      （青年科技人才赛道）                                                             （学生赛道）联系大赛工作人员：如没有得到及时回复，可以添加大赛工作人员微信：15889847842（微信号：HW88886712）。Q：华为云AI开发平台的编程语言用的是华为独创的，还是python、C语言等其他编程语言都能兼容？AI开发，还是主流的Python、C++，没有独创的语言。Q：请问项目检测的样品必须是pcb板吗？可以是其他工业样品吗？是PCB板，数据样例集已给出，请见赛事页面。Q：本次比赛是只会提供这样一个小数据集吗？还是后面会有大数据集呢？本次大赛发放的是样例集，选手可以参考样例集缺陷自行寻找或制作开源数据集制作模型。Q：请问一下后期测试数据里是否也是五类缺陷，会不会有其他类别呢？不会了，缺陷种类是一样的。Q：我们需要检测的就是这块pcb板吗？还是说我们可以基于这个平台检测其他物品，缺陷由我们自己来定。赛题确定为PCB板检测，并且缺陷是样例集里固定的几种。Q：训练的材料也是公司这边提供吗？赛事页面已提供样例集，我们选手可以自行寻找合适的开源数据集。Q：评分用的数据集也是和样例数据集一样吗？一张pcb板只会有一种错误，还是说有几种错误同时在一张板子上的情况？是的，缺陷种类一样，初赛是一张板子一种缺陷。Q：大赛中使用的算法是否必须为本人提出的？使用开源的sota方案是否符合要求？初赛不做限制的，看最终的得分。Q：能够用自己买的910来训练吗？也可以，但不推荐，910很贵。Q：为什么我跑提供的初赛指导里面的yolov5，有调用了HAM，但是NPU AI那个调用一直是0%呀？其实 npu有调用，只是训练消耗的不多，有时候只有小一段时间会使用，所以会看到0这种情况。Q：打榜的分数是累计的吗这个每提交一次就有分，取最高分。Q：收费平台是训练的npu和储存两部分吗，代金券用完要分别在两个平台充钱吗收费是包括npu和存储两部分，但是代金券应该是都包含的，所以不用担心。Q：preprocess的入参date一次只包含一张图吗？是的。Q：请问老师样例集和训练集是同分布的吗，还是只有格式是一样的只能说格式一样。

核心思路1. 贪心思想：小的pod尽量放在小的服务器中。2. 同时兼顾每个服务器利用率。算法流程1. 当pod节点列表来，按照容量大小排序（mem*cpu）2. 遍历已申请的服务器列表，找到 服务器资源利用率 / 服务器价格 最大的pod组合1，此外也遍历所有服务器类型列表，找到 服务器资源利用率 / 服务器价格最大的组合2，如果组合1 大于0.2 * 组合2 则使用已有服务器，反之则申请新服务器。然后在pod列表中将该组合pod节点移除。3. pod组合必须从pod列表第一个节点开始，并且必须连续。// https://competition.huaweicloud.com/information/1000042012/introduction#include <iostream>#include <vector>#include <algorithm>#include <random>#include <cstdlib>#include <ctime>struct Flavor { int cpu; int mem; double cost;};struct Pod { int cpu; int mem; int node; int idx;};struct Node { int cpu; int mem; double cost; double start; int flavorIdx; int podNum; void allocate(Pod& pod) { if (cpu < pod.cpu || mem < pod.mem) { throw std::runtime_error("Trying to place pod " + std::to_string(pod.idx) + " on node " + std::to_string(flavorIdx) + ", but it has not enough resources for the pod."); } cpu -= pod.cpu; mem -= pod.mem; } void deallocate(Pod& pod) { cpu += pod.cpu; mem += pod.mem; }};struct Action { std::string kind; double timestamp; int size; std::vector<Pod> pods;};struct Score{ double level1; double level2; double level3;};struct Scorer { int id; int PodId2; Score score;};struct Game { std::vector<Node> nodes; std::vector<Flavor> flavors; std::vector<Pod> pods;};Game initInput() { int K; std::cin >> K; std::vector<Flavor> flavors; for (int i = 0; i < K; ++i) { int cpu, mem; double cost; std::cin >> cpu >> mem >> cost; flavors.push_back({cpu, mem, cost}); } Game game{{Node{0, 0, 0, 0, 0, 0}}, flavors, {Pod{0, 0, 0, 0}}}; return game;}Action inputAction() { double timestamp; std::string kind; int size; std::cin >> timestamp >> kind >> size; std::vector<Pod> pods; if (kind == "END") { return {kind, timestamp, size, pods}; } if (kind == "DELETE") { std::vector<int> podIds(size); for (int i = 0; i < size; ++i) { std::cin >> podIds[i]; pods.push_back({0, 0, -1, podIds[i]}); } return {kind, timestamp, size, pods}; } for (int i = 0; i < size; ++i) { int podId, podCpu, podMem; std::cin >> podId >> podCpu >> podMem; pods.push_back({podCpu, podMem, -1, podId}); } return {kind, timestamp, size, pods};}Score flavor_score(Game &game, Pod &pod,Flavor &flavor){ // double _score = 1 ; double _score = double(pod.cpu) / double(flavor.cpu) * double(pod.mem) / double(flavor.mem) ; // double _score = 1 / double(flavor.cpu-pod.cpu) * 1 / double(flavor.mem-pod.mem) ; _score /= flavor.cost; // _score /= std::log(flavor.cost + 1.1); return {_score,0,0};}Score node_score(Game &game, Pod &pod,Node &node){ // 更快释放node的方案 double _score1 = double(pod.cpu) / double(node.cpu) * double(pod.mem) / double(node.mem) ; // double _score1 = 1 / double(node.cpu-pod.cpu) * 1 / double(node.mem-pod.mem); // _score *= node.cost / double(node.cpu) / double(node.mem); // double _score1 = node.podNum; _score1 *= 1 / node.cost; // _score += return {_score1,0,0};}void printOutput(std::vector<int> &allocateNodes, std::vector<int> &putNodeIds){ std::cout << allocateNodes.size(); for (int node : allocateNodes) { std::cout << " " << node; } std::cout << std::endl; std::flush(std::cout); for (int nodeId : putNodeIds) { std::cout << nodeId << " "; } std::cout << std::endl; std::flush(std::cout);}void createCombinePods(Game& game, Action& action) { std::vector<int> allocateNodes; std::vector<int> putNodeIds(action.size,0); int start_idx = action.pods[0].idx; for (int podI = 0; podI < action.size; ++podI){ game.pods.push_back(action.pods[podI]); } int podI = 0; while(podI < action.size) { Pod combinePod = {0,0,0,0}; std::vector<Scorer> flavorScores; std::vector<Scorer> nodeScores; // for (int podI2 = podI; podI2 < action.size && podI2 < podI + 3; ++podI2){ for (int podI2 = podI; podI2 < action.size; ++podI2){ combinePod.cpu += action.pods[podI2].cpu; combinePod.mem += action.pods[podI2].mem; for (int i = 1; i < game.nodes.size(); ++i) { auto& node = game.nodes[i]; if (node.cpu >= combinePod.cpu && node.mem >= combinePod.mem) { nodeScores.push_back({i, podI2,node_score(game,combinePod,node)}); } } for (int i = 0; i < game.flavors.size(); ++i) { auto& flavor = game.flavors[i]; if (flavor.cpu >= combinePod.cpu && flavor.mem >= combinePod.mem) { flavorScores.push_back({i, podI2, flavor_score(game,combinePod,flavor)}); } } } std::sort(nodeScores.begin(), nodeScores.end(), [](auto& a, auto& b) { if (a.score.level1 > b.score.level1) return true; else if(a.score.level1 < b.score.level1) return false; else{ if (a.score.level2 > b.score.level2) return true; else if(a.score.level2 < b.score.level2) return false; else return a.score.level3 > b.score.level3; } }); std::sort(flavorScores.begin(), flavorScores.end(), [](auto& a, auto& b) { if (a.score.level1 > b.score.level1) return true; else if(a.score.level1 < b.score.level1) return false; else{ if (a.score.level2 > b.score.level2) return true; else if(a.score.level2 < b.score.level2) return false; else return a.score.level3 > b.score.level3; } }); int chooseNodeIdx = -1; int choosePodI2 = -1; // if (nodeScores.size() > 0){ if (nodeScores.size() > 0 && nodeScores[0].score.level1 > flavorScores[0].score.level1*0.20){ chooseNodeIdx = nodeScores[0].id; choosePodI2 = nodeScores[0].PodId2; }else{ int chooseFlavorIdx = flavorScores[0].id; allocateNodes.push_back(chooseFlavorIdx + 1); game.nodes.push_back({game.flavors[chooseFlavorIdx].cpu, game.flavors[chooseFlavorIdx].mem, game.flavors[chooseFlavorIdx].cost, action.timestamp, chooseFlavorIdx, 0}); chooseNodeIdx = game.nodes.size() - 1; choosePodI2 = flavorScores[0].PodId2; } for (int i = podI; i<=choosePodI2;++i){ putNodeIds[action.pods[i].idx - start_idx] = chooseNodeIdx; game.pods[action.pods[i].idx].node = chooseNodeIdx; game.nodes[chooseNodeIdx].allocate(action.pods[i]); ++game.nodes[chooseNodeIdx].podNum; } podI += (choosePodI2 - podI + 1); } printOutput(allocateNodes, putNodeIds);}void deletePods(Game& game, const Action& action) { for (Pod _pod : action.pods) { auto& pod = game.pods[_pod.idx]; game.nodes[pod.node].deallocate(pod); --game.nodes[pod.node].podNum; if (game.nodes[pod.node].podNum == 0) { game.nodes[pod.node].cpu = 0; game.nodes[pod.node].mem = 0; } }}int main() { Game game = initInput(); while (true) { Action action = inputAction(); if (action.kind == "END" && action.size == 0) { break; } if (action.kind == "CREATE") { createCombinePods(game, action); } else { deletePods(game, action); } } return 0;}

优化细节1、自定义函数解析float2、使用simd加速3、将32bit的float数据压缩到1bit，用海明距离求topNK（N需要根据数据特征调整，完全随机数据N=2500）4、排序不要用全量数据，只排序大于0.48*D的数据（如果数据小于NK，就是用全量数据排序）5、对topNK数据的float压缩到1byte求欧式距离6、使用缓存7、欧氏距离只需要计算x*y，其它项都可以约掉

华为算法精英实战营第5期 - 高维向量数据的近似检索 参赛经验分享赛题核心点介绍赛题目标是在保证精度的前提下追求极致性能优化，所有需要做到两点：通过预处理及数据压缩快速筛选数据尽可能的使用硬件加速向量化处理计算逻辑SIMD向量化经过测试，线上环境支持avx2和avx512指令集本题中为了确保精度需要求欧式距离$\sum_{i=1}^n(x_i-y_i)^2=\sum_{i=1}^nx_i^2+\sum_{i=1}^ny_i^2-2\sum_{i=1}^nx_iy_i$其中$\sum_{i=1}^{n}x_{i}^2$ 部分可以预处理时求得,$\sum_{i=1}^{n}y_{i}^2$在单次查询时不需要计算,只需要求$\sum_{i=1}^nx_iy_i$核心代码示例如下:__attribute__((target("avx512bw", "avx512f"), optimize("O3", "unroll-loops"))) float prod_avx512(const float *p, const float *q, size_t size) { float __attribute__((aligned(64))) tmp[16]; size_t align = size / 16 * 16; __m512 v1, v2; __m512 sum = _mm512_set1_ps(0); for (size_t i = 0; i < align; i += 16) { v1 = _mm512_loadu_ps(&p[i]); v2 = _mm512_loadu_ps(&q[i]); sum = _mm512_add_ps(sum, _mm512_mul_ps(v1, v2)); } _mm512_store_ps(tmp, sum); float res = tmp[0] + tmp[1] + tmp[2] + tmp[3] + tmp[4] + tmp[5] + tmp[6] + tmp[7] + tmp[8] + tmp[9] + tmp[10] + tmp[11] + tmp[12] + tmp[13] + tmp[14] + tmp[15]; for (size_t i = align; i < size; ++i) { res += (p[i] - q[i]) * (p[i] - q[i]); } return res; }汉明距离在数据预处理时，将32bit的float数据压缩到1bit,将1bit数据按列凑成uint64_t类型,这样就可以使用汉明距离做快速筛选明距离的计算相对于欧式距离来说更加高效，因为它只涉及到按位的异或（XOR）操作和按位计数（POPCOUNT）操作，这些操作在现代CPU上可以非常快速地执行。核心代码示例如下(这里测试avx2性能比avx512更高):__attribute__((target("avx2"), optimize("O3", "unroll-loops"))) uint64_t xor_uint64_avx2(const uint64_t *p, const uint64_t *q, const uint64_t size) { uint16_t res = 0; size_t size_a = size / 4 * 4; for (size_t i = 0; i < size_a; i += 4) { __m256i avx2_p = _mm256_loadu_si256(reinterpret_cast<const __m256i *>(&p[i])); __m256i avx2_q = _mm256_loadu_si256(reinterpret_cast<const __m256i *>(&q[i])); __m256i result = _mm256_xor_si256(avx2_p, avx2_q); res += _mm_popcnt_u64(_mm256_extract_epi64(result, 0)) + _mm_popcnt_u64(_mm256_extract_epi64(result, 1)) + _mm_popcnt_u64(_mm256_extract_epi64(result, 2)) + _mm_popcnt_u64(_mm256_extract_epi64(result, 3)); } for (uint64_t i = size_a; i < size; ++i) { uint64_t r = (*(p + i)) ^ (*(q + i)); res += _mm_popcnt_u64(r); } return res; }压缩代码如下(这里耗时较少，未做并行化处理):void construct(float *d, uint64_t *h) { for (int c = 0; c < D / 64; c++) { uint64_t v = 0; for (int n = 0; n < 64; n++) { int j = c * 64 + n; // mid_col is the median of the column v = (v << 1) + (d[j] > mid_col[j] ? 1 : 0); } h[c] = v; } if (D % 64 > 0) { uint64_t v = 0; for (int n = 0; n < D % 64; n++) { int j = (D / 64) * 64 + n; v = (v << 1) + (d[j] > mid_col[j] ? 1 : 0); } h[D / 64] = v; } }为了确保精度,数据快速筛选后保留10%的数据继续通过欧式距离求得TOPK

赛题核心点介绍这道题的核心赛点在于设计算法将结点分配给适当类型的服务器来最小化费用。整体思路介绍1. 对每一个CREATE操作，把同类（CPU和MEM相同）的查询规为一类，先看看之前有没有空位可填，剩下的做一个最优化dp。对于任意一种类型，令dp[n]表示给n个结点分配服务器的最小代价。则有两种转移，第一种把所有结点塞到一个服务器里，第二种是dp[n] = min{dp[i] + dp[n - i]}。2. 注意每个服务器只存放同类的结点就行了。这样做的原因是同类结点持续时间一般相同，更有可能同时删除，利用率会更高。更具体一点，就比如说在调用new分配内存的时候，同样大小的块是会被放在一起的，因为他们可能会被同时访问，这样基于空间局部性性能就会更高。放到这题里就是：同类结点的持续时间更一致，放到一组里利用率会更高。因为给一个结点分配了服务器之后就不能改变了，而且当服务器空闲的时候会自动释放。3. 一个服务器只能放一个类型结点，如果有结点结束了，之后往里面添加的，也必须同类型。也就是说服务器对应的类型在创建的时候就确定了。核心策略详解当着前面的只是基本思路，要像得到更高的分数需要更多的优化：1. 维护实时的服务器占用率，对每种类型的服务器维护一个占用率的期望值，然后在dp分配结点的时候用 价格/利用率 作为这种服务器的真实价格。对于单台服务器，其占用率的定义为：所有在这个服务器上执行过的结点的持续时长的和 / (服务器存在的时长 * 能存放的结点数量)。对于一个类型的服务器，其占用率的期望定义为到目前为止所有该类型服务器占用率的平均值。2. 基于上面的策略，假设对于某个类型x的结点，其最优的服务器类型是y，那么对于一次CREATE操作，我们的dp算法要做的就是分配足够数量的y服务器，此时剩下的少量结点会分配非y类型的服务器。举例来说：假设y能放10个x的结点，但是如果CREATE了11个，那么我们只会创建1一个y，剩下单出来的x有一个容量更小的服务器运行即可。这个算法看起来很合理，但是如果下一次CREATE操作很快就会到来的话，不如直接一次创建2个y，虽然会有一个y的占用率很低，但是这个低占用率的持续时间是很短的。对此我们要做的事情也就很明确了：根据之前的CREATE操作维护一些信息来预测下一次CREATE到来的期望时间，然后根据这个信息来决定最后一次分配是选择y还是更小型的服务器。

高维向量数据的近似检索-huaweifirst_worldlatter团队赛题核心点介绍1.采用c++编写可执行程序单纯python+numpy的版本分数在1600.0374左右，上限较低，改用纯c++实现可以达到1600.0474分左右2.采用循环展开由于无法开启编译器simd指令优化，因此采用了循环展开(采用4/8/16)展开。对于M个doc向量在与query计算时可以使用循环展开，每次计算N(4/8/16)个doc的相似度，编译器会尝试生成向量化指令，从而加速整体的运算速度3.采用简化数据计算根据(x-y)^2=x^2+y^2-2xy可知，如果将向量doc提前归一化后可以将x^2和y^2的计算舍弃，进而只有一次乘法近似计算4.采用cache对于已经计算过的输入则不会重复计算，没有计算过的输入会保存其输出到cache中方便之后相同输出差表。整体思路介绍核心策略详解1.提前分配内存避免后面动态分配内存造成额外耗时由于已知doc的数量和每次只查询一个query，因此占用的内存是固定，可以提前开辟一块连续的大块内存，避免后面算法在动态分配内存造成内存碎片。2.数据读取阶段加速，关闭io相关的同步，加快数据读取由于c++的流机制存在的同步，因此关闭同步并且解绑输入输出流可以加快io的速度。3.通过使用doc归一化手段简化欧式距离计算，只用一次乘法即可获取结果简化了欧式距离的流程，由原来长度为L的向量需要计算两次减法一次乘法一次跟号共4L次运算，变换为只需要计算一次乘法L次运算。4.通过循环展开由于无法使用simd，因此采用循环展开，对于M个doc进行分块，按照4/8/16分块后每次计算4/8/16个doc与query的欧式距离，最后将剩余的块单独计算。经过编译器优化后可以产生一次加载4/8/16元素的向量化访存和计算的指令，从而加快整个doc的计算。5.通过优先队列计算topk由于topk的计算不需要全部doc的分数进行排序，只需要排序好前topk个即可，因此采用了堆排序的优先队列，可以避免全量doc的分数排序。6.使用cache缓存由于推理时可能有重复的query请求，为了避免重复query请求浪费计算力，会在计算时缓存旧的结果，如果遇到已经缓存的结果则直接取缓存值。

附件为出题专家组撰写的赛题介绍，以及关于第六期赛题的一些算法思路建议，对于各位选手的解题相信会有很大的启发，大家赶紧下载查看转发起来吧！以下为正文：Cloud computing has emerged as a new paradigm for on-demand access to a huge pool of computing resources. During the last decade it has formed a large-scale ecosystem of technologies, products and services which enabled the rapid innovation and development of new applications with millions of users. At the same time, cloud computing has posed new challenging problems to cloud providers that should operate the huge resource pools in a cost efficient way while providing a high quality of service to their users.To win the competition, major cloud service providers are focusing on improving the utilization of cloud resources, as this will allow to reduce the cost of cloud services. It is estimated that even a 1% increase in cloud service resource utilization can save millions of dollars in costs. The optimization of resource utilization, in turn, requires the development of advanced algorithms and technologies for cloud resource management. The virtual machine (VM) placement algorithm considered in this contest is one of these critical algorithms. This algorithm works online by finding a suitable server for running each requested user VM. The algorithm should compute its decision fast while providing a dense packing of VMs and avoiding rejections due to the lack of free space. The increase of the scale and complexity of cloud services and deployed applications has led to new user requirements. In particular, instead of a single VM, users often need to deploy a set of VMs with specific requirements on the quality of their placement. For example, to ensure high availability each VM must be placed in a separate fault domain, a set of servers that share a single point of failure, such as rack. In other situation, like neural network training, it may be preferable to place VMs "close" to each other in terms of cloud network topology to reduce the communication latency and speed up the computations.These new requirements bring new challenges to VM placement problem – how to quickly and efficiently place large sets of VMs while satisfying numerous constraints. Basic algorithms that place each VM independently cannot adapt to such complex scenarios. So the context of this Challenge is development of topology-aware VM placement algorithm that can both satisfy new constraints and ensure efficient resource utilization.The algorithm operates a large pool of servers by processing incoming user requests on creation and deletion of virtual machines. The resource pool is organized in a hierarchical topology with multiple levels. Servers live in racks with form separate fault domains, because the failure of the rack network switch or power supply leads to the failure of all servers from the rack. Racks are grouped into pods and network domains. The network communication inside the network domain is much faster than between different network domains.Cloud users create VMs from the predefined set of VM types. A user can request creation of multiple VMs of the same type at once. A user can request the deletion of any previously created VM at any time. Each VM is associated with some placement group (PG). The main role of PG is to define the requirements on placement of VMs belonging to this group. These requirements are specified as affinity and anti-affinity constraints. For example, each VM in group should be placed in a separate rack is an anti-affinity constraint. It is also possible to combine multiple constraints in a PG.The algorithm processes requests one by one, in online fashion. That means that the algorithm must output its decision regarding the current request without knowledge about the next requests. This is exactly how such algorithm runs in a real cloud. Your main goal will be to maximize the number of successfully placed VMs. As the algorithm runs on a resource pool of fixed size the more requests are allocated, the less resources are wasted and the more resource efficient is the algorithm.The first version of this problem was published as the ICPC 2022 Online Challenge powered by Huawei which attracted many algorithm enthusiasts from all over the world. For the new competition, the problem has been reworked to introduce more complex topology and placement constraints, new test cases and solution scoring. Below we describe the main differences.To model new placement constraints arising in AI training scenarios, a new topology level (pod) has been introduced which corresponds to a set of racks. Training of large AI models requires a massive amount of computations and typically runs in parallel across a large number of servers. The communication speed between these servers is crucial, therefore such workloads require allocation of one or several whole pods in a single network domain. Such constraints has been added to this challenge. We have also added more complex real-world constraints which combine affinity and anti-affinity on different topology levels.57 completely new test cases have been prepared for this challenge. While the previous challenge featured only synthetic test cases, this challenge also features test cases based on real cloud requests. The generator of synthetics cases has also been improved.Finally, the solution scoring is also reworked. While in ICPC Challenge the achieved results were compared with simple baseline algorithm, now we compare them with an upper bound on the number of successfully placed VMs which is a hard theoretical limit.The problem being solved shares many similarities with the classic bin packing and knapsack problems. Indeed, we need to pack items represented by VMs into bins represented by servers. Therefore algorithms for solving these well-known problems can be used to efficiently pack VMs into servers without leaving unused resources. However, our problem is remarkably harder than these classic problems because of the following features. First, we consider online scheduling in which future requests are unknown in advance, while most of classic algorithms consider offline setting where all packed items are given as input. Development of online algorithm requires dealing with uncertainty. One approach is to minimize the risks by preparing to challenging requests. For example, we can be prepared for upcoming requests for large VM by reserving enough free space to accommodate such VMs. Another approach is to try to anticipate future requests by using some predictive model based on already processed requests. For example, the distribution of requested VM types, or what kind or requests arrived recently, may provide some hints about the upcoming requests.Second, we consider the dynamic packing problem where the items may depart from the bins, which also quite different from the classic bin packing. While item departures are not as challenging as dynamic item arrivals and can even simplify the packing, they can also be leveraged to improve the packing efficiency. For example, by packing together VMs with similar lifetime, we can improve the availability of large free space on servers for packing large VMs. This requires predicting the VM lifetime, which can be also done using the already observed information. Note also that VMs from the same PG are usually deleted in batches, so their lifetime is similar.Third, the most complexity comes from the placement constraints. Consider a PG with affinity constraint on rack level. When placing the first request from this group, we need to choose a rack with enough free space to accommodate the VMs from this request and the VMs from upcoming requests of this group. This means that it is no longer safe to pack VMs one by one, without considering whether the whole request will fit a rack. It also means that a care should be taken to provide some room for possible future growth of the group inside the chosen rack. One possible approach is to choose a rack with the most available free space. Note also that groups cannot grow infinitely, there is some limit on their size. Anti-affinity constraints are usually less challenging but they also require the strategical management of available space to success. For example, for anti-affinity on rack level with partitions it is better to choose the racks where the request partition is already present to avoid occupying too much racks for some partition, since it will reduce possible racks for accommodating other partitions. Think about what kind of similar strategies can be applied for other constraints. Finally, when choosing a topology domain for placing VMs it is convenient to select domains in a top-down fashion using some scoring metrics or rules for each domain on some level.As a last recommendation and a word of caution, try to avoid overfitting your solution parameters and even placement strategies to individual tests. This will both complicate your algorithm and make it inapplicable in a real cloud setting. Strive for simpler and general algorithms with a clear intuition behind them and a small number of parameters, and also add comments in the code to explaining them. That is what we expect from a perfect solution to our challenge.