我使用函数 mmax 来计算一千万长度的整数向量的移动最大值。我运行了 10 次来计算总执行时间。窗口大小 132(15,025 毫秒)的运行时间是窗口大小 22(2,425 毫秒)的 6 倍。 mmax 的复杂度似乎是 O(nw) 而不是 O(n)，其中 w 是滑动窗口的长度)。
为了检查其他类似产品是否如此，我在 DolphinDB 上尝试了相同的实验，这是一个具有内置分析功能的时间序列数据库 (https://www.dolphindb.com/downloads.html)。相比之下，DolphinDB 的 mmax 具有 O(n) 的线性复杂度，与窗口大小无关:1,277 毫秒(窗口大小 132)和 1,233 毫秒(窗口大小 22)。
本实验使用的硬件:
Server: Dell PowerEdge R630
Architecure: x86_64
CPU Model Name: Intel(R) Xeon(R) CPU E5-2650 v4 @ 2.20GHz
Total logical CPU cores: 48
Total memory: 256G
实验设置
我使用了 KDB+ 4.0 64 位版本和 DolphinDB_Linux_V2.00.7(DolphinDB 社区版本:2 核和 8GB 内存)。这两个实验都是使用 2 个 CPU 内核进行的。
KDB 实现
// Start the server
rlwrap -r taskset -c 0,1 ./l64/q -p 5002 -s 2
// The code
a:10000000?10000i
\t do[10; 22 mmax a]
2425
\t do[10; 132 mmax a]
15025
DolphinDB 实现
// Start the server
rlwrap -r ./dolphindb -localSite localhost:5002:local5002 -localExecutors 1
// The code
a=rand(10000,10000000)
timer(10) mmax(a,22);
1232.83 ms
timer(10) mmax(a,132);
1276.53 ms
任何kdb专家可以确认函数mmax的复杂性吗？如果内置函数mmax确实有O(nw)的复杂度，有没有第三方kdb插件可以提高性能？
最佳答案
是的，它会随着窗口的大小以及列表的大小而缩放。如果你看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/
关于kdb - kdb的移动最大函数的复杂度是mmax O(n)吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/73748499/