问题标签 [prefix-sum]

我正在尝试解决 Codility 的Min Avg Two Slice问题。

我想出了以下代码：

这在正确性方面效果很好，但是它具有时间复杂度，O(n*m)因为我local_min每次都重新计算而不重用任何结果。

我正在尝试使用prefix_sums这里的算法来计算局部最小值，或者以某种方式使用minimums对象记住计算出的最小值，并在随后的调用中重用它们local_min。

我遇到的问题是 - 假设我们有以下数组：

[1, 13, 2, 8, 20, 5]

smallest values seen up to this point我们可以计算如下数组：

对于范围0, 6，它只是：

[1,1,1,1,1,1]

因为1,6它将是：

[13, 2, 2, 2, 2]

对于2,6：

[2, 2, 2, 2]

最后：

[8, 8, 8] 和 [20, 5]

我正在努力了解如何采用这种方法来计算smallest value in a given range并降低我的解决方案的时间复杂度。

编辑：

我想出了以下解决方案，它在正确性和性能方面实现了 100% 的 Codility，并实现了时间复杂度O(n+m)：

不过，我仍然对此感到有些困惑-我的假设是该in操作将采用的长度O(n)在哪里，因此总体复杂性应该是长度在哪里-任何人都可以解释为什么实际上是复杂性nSO(n * m)mPQO(n + m)

这是我的代码：

当我运行它时，它无法通过示例案例，并且官方评分者说存在运行时错误或内存失败。我怀疑它有一些带输入输出的东西，但没有。这里有什么问题？

我正在编写一个代码来使用 StarPU 执行 prefix_sum。但是，我不确定我是否在这段代码中使用了 starPU。有人可以检查一下吗？谢谢。

代码的第一部分

第二部分代码

我正在处理 CS 分配，我必须使用 p_threads 来计算数组的前缀总和。教授告诉我们使用 Hillis 和 Steele 算法。我在维基百科（这里）上找到了一些伪代码，特别是：

我有点坚持在实际代码中实现这一点。我们的程序应该工作的方式是，用户通过文件或标准输入传入一个数组，然后接下来的 2 个参数是输入数组的大小，以及我们需要使用多少个线程。所以，我假设这张图片中的“n”是“我们需要使用的线程数量”。然后，我不确定 x 上的符号是什么意思。维基百科说“在上面，符号......表示时间步长 i 中数组 x 的第 j 个元素的值。” 但是……什么？我如何实现这个“时间步”？我假设它的意思是：“做 j 的 i+1 次方，然后在数组 x 中找到那个索引元素”。有了这个假设，我写了这段代码：

该行注释了“ISSUE IS HERE”段错误。我可以逐步进入 gdb 并弄清楚为什么它会出现段错误，但我想知道我是否做得对。这是我第一次用多线程做任何事情。我们还应该使用锁和条件变量的组合来创建我们自己的屏障，但我什至不知道该怎么做。

此外，有些代码没有显示出来，例如我的“logbase”函数和读取输入数组的函数。我知道那些工作正常。

感谢您的时间。