跳转至

G. Top-K

分数：200分

通知

如果你需要装包，可以这样做：

import Pkg
Pkg.activate(temp=true)
Pkg.add("包")

背景

【提醒：附件 Tab 中有数据生成器与主程序 】

小 T 最近在学习并行计算，他发现在大规模数据处理中，寻找最大的 K 个元素是一个非常常见的需求。比如在搜索引擎中，需要找出最相关的前 K 个结果；在推荐系统中，需要推荐最匹配的 K 个商品。

小 T 想要实现一个高效的 Top-K 算法，他希望你能帮助他完成这个任务。而 Julia 最近在科学计算领域，因其方便的并行计算和高性能的特性，受到了越来越多的关注。所以小 T 希望你使用 Julia 语言来实现这个算法，并尽可能地优化其性能。

说明

给定一个包含 N 个数（整数或浮点数）的数组，找出其中最大的 K 个数。

你需要实现一个签名为 topk(data, k) 的函数，其中 data 是一个包含 N 个数（整数或浮点数）的数组，k 是一个正整数。

函数的返回值是一个包含 K 个整数的数组，这 K 个数是输入数组中最大的 K 个数的下标（从 1 开始），且应当按照下标对应数值从大到小排序。如果输入数组中存在多个相同的数，则下标小的优先。

你不需要考虑文件输入或输出，只需要实现 topk 函数。评测程序将会调用你的实现进行评测。

评测环境

容器镜像：julia。已设置环境变量 JULIA_PKG_SERVER，无需担心装包的网络问题。

运行选手程序前，会先运行 julia -e 'using Pkg; Pkg.instantiate()' 来安装依赖。

评测方法

提交一个 impl.jl 文件，包括 topk函数，函数签名是：

@inbounds function topk(data::AbstractVector{T}, k) where T
# your code here
end

评测时使用 Julia 1.11.2 版本。

程序会在配备 Intel® Xeon® Platinum 8358 Processor 的服务器上以 julia -t 8 的方式运行，也即可以使用 8 个线程。

评分标准

所有结果必须正确，否则不得分。

测试点如下所示，其中 N 是数组长度，K 是需要找的最大数的个数，N 和 K 都为 2 的幂。每道题中整型（Int64）与浮点型（Float64）测试点分开计算，占比均为50%。

  1. N = 8192，K = 8 ：10 分，结果正确即可得分，运行时间需小于 1 分钟。

  2. N = 32768, K = 128：20分，结果正确即可得分，运行时间需小于 1 分钟。

  3. N = 2^{20} , K = 256：40分，按性能赋分。

  4. N = 2^{30}, K = 1024：130分，按性能赋分。

对于按性能赋分的测试点，对比你的实现与标准库中单线程的实现，计算加速比为 x，得分计算方法如下。其中 f(x) 为 sigmoid 函数变体。

得分 整形加速比 浮点加速比
0% x < 2 x < 2
f(x) x x
100% x >= 10 x >= 13

我们给出评测用的baseline用时和std运行时间如下：

  1. N = 8192, baseline: 0.238063315, 0.246213896, std: 0.000169, 0.000112

  2. N = 32768, 0.000344826, 0.000510477, std: 0.000118, 0.000142

  3. N = 2^{20}, 0.006957641, 0.014872915, std: 0.000611, 0.000951

  4. N = 2^{30}, 9.672722409, 18.007807025, std: 0.470093, 0.769184

提示

Julia 标准库中的 partialsort 和 partialsortperm 函数可以实现 Top-K 的计算。

  1. 关于 Julia 性能优化，可以参考官网的 Performance Tips。
  2. 可能会有帮助的一些第三方 Julia 库：
    • BenchmarkTools
    • JET
    • PProf
  3. 陈久宁老师的Julia讲座对新手很友好。Julia 教程可以参考 官方文档。中文材料可以参考李东风老师的 Julia 语言入门。我们的 Julia沙龙介绍了一些 Julia 可能出现性能问题的原因。
  4. TopK 算法的一种实现思路是使用基数排序，可以参考这篇文章。
  5. impl.jl 中也有一些提示，可以参考。

附件