kdb的移动最大函数mmax的复杂度是O(n)吗？

Question

我使用函数mmax来计算一千万长度整数向量的移动最大值。我运行了 10 次来计算总执行时间。窗口大小 132 的运行时间（15,025 毫秒）是窗口大小 22 的运行时间（2,425 毫秒）的 6 倍。看起来复杂度mmax是 O(nw) 而不是 O(n)，其中 w 是滑动窗口的长度）。

\n

为了检查其他类似产品是否也是如此，我在 DolphinDB 上尝试了相同的实验，DolphinDB 是一个具有内置分析功能的时间序列数据库 ( https://www.dolphindb.com/downloads.html )。相比之下，DolphinDB\xe2\x80\x99smmax线性复杂度为 O(n)，无论窗口大小如何：1,277 毫秒（窗口大小 132）和 1,233 毫秒（窗口大小 22）。

\n

本实验使用的硬件：

\n

Server: Dell PowerEdge R630\nArchitecure: x86_64\nCPU Model Name: Intel(R) Xeon(R) CPU E5-2650 v4 @ 2.20GHz\nTotal logical CPU cores: 48\nTotal memory: 256G\n

\n

实验设置

\n

我使用的是KDB+ 4.0 64位版本和DolphinDB_Linux_V2.00.7（DolphinDB社区版本：2核和8GB内存）。两个实验均使用 2 核 CPU 进行。

\n

韩国开发银行实施

\n

// Start the server\nrlwrap -r taskset -c 0,1 ./l64/q -p 5002 -s 2\n\n// The code\na:10000000?10000i\n\\t do[10; 22 mmax a]\n2425\n\\t do[10; 132 mmax a]\n15025\n

\n

DolphinDB 实施

\n

// Start the server\nrlwrap -r ./dolphindb -localSite localhost:5002:local5002 -localExecutors 1\n\n// The code\na=rand(10000,10000000)\ntimer(10) mmax(a,22);\n1232.83 ms\n\ntimer(10) mmax(a,132);\n1276.53 ms\n

\n

任何 kdb 专家都可以确认函数 mmax 的复杂性吗？如果内置函数 mmax 的复杂度确实是 O(nw)，有 kdb 的第三方插件可以提高性能吗？

\n

Answer 1

是的，它会随着窗口的大小以及列表的大小而缩放。如果你看一下 的定义mmax：

q)mmax
k){(x-1)|':/y}

它“相当于”

q)a:8 1 9 5 4 6 6 1 8 5
q)w:3
q)mmax[w;a]~{{max x,y}':[x]}/[w-1;a]
1b

可以更清楚地理解为最后的输出：

q){{max x,y}':[x]}\[w-1;a]
8 1 9 5 4 6 6 1 8 5
8 8 9 9 5 6 6 6 8 8
8 8 9 9 9 6 6 6 8 8

....取每个项目与其前一个项目的最大值，{max x,y}':[x]

....然后对输出再次执行相同的操作，{}\

....对输出再次执行相同的操作 (w-1) 次，\[w-1;a]

由此可见，窗口大小会影响循环执行的次数。至于更快的实现，可能有一种不同但不太“优雅”的算法，它可以更快地实现并且可以用 k/q 编写。否则，您可以导入用 C 编写的实现 - 请参阅https://code.kx.com/q/ref/dynamic-load/