我想知道是否有更好的方法可以为数组的部分和生成更好的性能的解决方案。
给定一个说的数组x = [ 0, 1, 2, 3, 4, 5 ]，我生成了项目的子数组，然后计算了每个数组的总和，得出：
[ 0, 1, 3, 6, 10, 15 ]
因此，完整的代码是：
x.map((y,i)=>x.filter((t,j)=>j<=i))
.map(ii=>ii.reduce((x,y)=>x+y,0))
我想知道平面图或其他数组方法是否具有不需要扩展每个子数组的解决方案。
我需要实现前缀和算法,并且需要它尽可能快.例如:
[3, 1, 7, 0, 4, 1, 6, 3]
有没有办法使用SSE/mmx/SIMD cpu指令执行此操作？
我的第一个想法是递归并行地对每一对求和,直到所有的总和都计算如下!
[3, 4, 11, 11, 15, 16, 22, 25]
为了使算法更清晰,"z"不是最终的输出
而是用来计算输出
//in parallel do
for (int i = 0; i < z.length; i++) {
z[i] = x[i << 1] + x[(i << 1) + 1];
}
我试图把握背后的前缀和概念的想法看着由Codility的前缀和课程介绍的例子在这里(蘑菇拾取问题)
我的理解是整个概念基于简单的属性,其中在数组A的两个位置A(pos_left,pos_right)之间找到所有元素的总和,使用第二个数组P,其中所有元素被连续求和并且搜索到的位置sum计算为
值(P(pos_right + 1)) - 值(P(pos_left)).
A 1 2 3 4 5 6
P 0 1 3 6 10 15 21
sum of all elements between A[2] and A[5] = 3+ 4 + 5 = 12
or using the prefix sums" P[5+1] - P[2] = 15 -3 = 12
问题
在每个地方都有一条带有蘑菇的街道,由非空载体代表.鉴于采摘器的初始位置及其移动范围,可以寻找可能的最大蘑菇数量.
看一下这个例子,我不明白循环构造背后的逻辑.任何人都可以澄清这种算法的机制吗？
其次,我发现这个例子中的positoin索引非常混乱和麻烦.通常的做法是将前缀加上的矢量"移位"在开始时为零吗？(事实上,向量中的计数元素从python中的0开始,因为已经引起了一些混乱).
解决方案
def prefix_sums(A):
n = len(A)
P = [0] * (n + 1)
for k in xrange(1, n + 1):
P[k] = …是否有任何数据结构能够返回数组的前缀和 [1]、更新元素以及向数组中插入/删除元素，所有这些都在 O(log n) 中？
[1]“前缀总和”是从第一个元素到给定索引的所有元素的总和
例如，给定非负整数数组，8 1 10 7前三个元素的前缀和是19( 8+ 1+ 10)。将第一个元素更新为7，3作为第二个元素插入并删除第三个元素给出7 3 10 7。同样，前三个元素的前缀和将为20。
对于前缀 sum 和 update，有Fenwick tree。但我不知道如何用它处理 O(log n) 中的添加/删除。
另一方面，有几种二叉搜索树，例如红黑树，它们都在对数时间内处理更新/插入/删除。但我不知道如何维护给定的排序并在 O(log n) 中进行前缀和。
我在实现并行计算前缀总和的算法时遇到问题。尽管此算法有3个步骤，但由于没有给出伪代码，因此我无法编写代码。
我遍历了网络上的各种内容以及堆栈溢出的内容，但是我没有得到Wiki上给出的算法的确切实现。Wiki提及以下内容：
前缀总和可以通过以下步骤并行计算：
- 计算连续项对的总和，其中该对的第一个项具有偶数索引：z0 = x0 + x1，z1 = x2 + x3，依此类推。
- 递归计算序列z0，z1，z2，...的前缀和w0，w1，w2，...
- 将序列w0，w1，w2 ...的每个项扩展为总前缀总和的两个项：y0 = x0，y1 = w0，y2 = w0 + x2，y3 = w1，依此类推。在第一个值之后，每个连续数yi是从w序列的一半位置复制的，或者是x序列中一个值的前一个值
有人可以建议一个伪代码实现让我检查并实现吗？
我一直在解决算法问题，对这些术语有点困惑。
当我们像下面的代码一样想要计算前缀和（或累积和）时，我们可以说我们正在使用动态规划吗？
def calc_prefix_sum(nums):
N = len(nums)
prefix_sum = [0] * (N + 1)
for i in range(1, N + 1):
prefix_sum[i] = prefix_sum[i - 1] + nums[i - 1]
return prefix_sum
nums = [1, 3, 0, -2, 1]
print(calc_prefix_sum(nums))
[0, 1, 4, 4, 2, 3]
根据本页的定义，
动态规划用于遇到问题的地方，可以将问题分成相似的子问题，以便可以重复使用它们的结果。
在我的 prefix_sum 算法中，当前的计算（prefix_sum[i]）被分成类似的子问题（prefix_sum[i - 1] + nums[i - 1]），这样之前的结果（prefix_sum[i - 1]）就可以被重新使用。所以我假设计算前缀和是动态规划的应用之一。
我可以说这是动态规划，还是应该使用不同的术语？（特别是，我正在考虑编码面试中的情况。）
我正在尝试解决Codility 的最小平均两片问题。
我想出了以下代码：
def solution(S, P, Q):
weights = {'A': 1, 'C': 2, 'G': 3, 'T': 4}
retVal = []
for i in range(0, len(P)):
if P[i] == Q[i]:
retVal.append(weights[S[P[i]]])
else:
retVal.append(local_min(S, weights, P[i], Q[i]))
return retVal
minimums = {}
def local_min(S, weights, start, end):
minVal = weights[S[start]]
for i in range(start,end+1):
val = weights[S[i]]
if val == 1:
minimums[i] = 1
return 1
if val < minVal:
minVal = val
minimums[i] = minVal
return minVal
这在正确性方面工作得很好，但是它的时间复杂度为 ，O(n*m) …
首先,这里是算法的链接http://http.developer.nvidia.com/GPUGems3/gpugems3_ch39.html
为了避免存储体冲突,每个NUM_BANKS(即,对于可计算性2.x的设备为32)元素将填充添加到共享存储器阵列.这是通过(如图39-5)完成的:
int ai = offset*(2*thid+1)-1
int bi = offset*(2*thid+2)-1
ai += ai/NUM_BANKS
bi += ai/NUM_BANKS
temp[bi] += temp[ai]
我不明白ai/NUM_BANKS是如何与宏等效的:
#define NUM_BANKS 16
#define LOG_NUM_BANKS 4
#define CONFLICT_FREE_OFFSET(n) \
((n) >> NUM_BANKS + (n) >> (2 * LOG_NUM_BANKS))
不等于
n >> LOG_NUM_BANKS
任何帮助表示赞赏.谢谢
在 Haskell 中计算前缀和的简单方法是
scanl1 (+) [1,2,3,4,5,6]
产生输出
[1,3,6,10,15,21]
我需要写出逆函数，这就是我想出的：
undo_prefix_sum :: (Num a) => [a] -> [a]
undo_prefix_sum s = init $ snd $
foldr (\cur (tot, l) -> (cur, (tot-cur):l))
(last s, [])
(0:s)
这似乎是正确的（但我可能错过了一些东西）。有没有更简单或更有效的方法来做到这一点，可能使用扫描？
我和我的朋友正在做一个简单的 Python 项目。实际上，我们正在以自己的方式实现前缀并行求和算法。
我们正在创建和处理一个非常奇怪的格式的二叉树。我们希望将此格式转换为 Tree 打印库/软件（如 ete2）接受的格式。
因此，树的每一层都以这种方式推送到列表中
[ [level0], [level1], ... [level i-1], [root] ]
在我们的格式中，每个内部列表（树的级别）都有偶数个节点或叶子。
例如，假设我们有这个输入：[1, 2, 3, 4, 5]。这将产生以下输出列表：[[1, 2, 3, 4], [3, 7], [10, 5], [15]]
上述输出示例的问题在于，有时叶子不在最后一层，但它们包含在上层列表中。这使得处理列表列表和区分节点和叶子并将它们排列在正确位置变得困难。
我们想将其可视化如下：
http://i.imgur.com/BKrqNZi.png
其中括号中的数字是节点，其他数字是叶子。
为了产生这个输出树，我们想使用一个树绘图库。他们中的大多数人期望这种格式：[root, [left], [right]]
所以，在我们的例子中，我们的格式应该是这样的：
[15, [10, [3, [1], [2]], [7, [3], [4]] ], [5] ]
因为我们目前无法重写代码的整个逻辑，所以我们正在寻找一种巧妙的方法将我们奇怪的格式转换成那种格式。
欢迎任何想法。非常感谢您提前。
我在 GPU Gems 3, Chapter 39: Parallel Prefix Sum (Scan) with CUDA一书中写了一段代码来调用内核。
然而，我得到的结果是一堆负数而不是前缀扫描。
我的内核调用是错误的还是 GPU Gems 3 书中的代码有问题？
这是我的代码：
#include <stdio.h>
#include <sys/time.h>
#include <cuda.h>
__global__ void kernel(int *g_odata, int *g_idata, int n, int dim)
{
extern __shared__ int temp[];// allocated on invocation
int thid = threadIdx.x;
int offset = 1;
temp[2*thid] = g_idata[2*thid]; // load input into shared memory
temp[2*thid+1] = g_idata[2*thid+1];
for (int d = n>>1; d > 0; d >>= 1) // build sum in place …我一直在leetcode上尝试这个问题。238.除自身之外的数组的乘积
给定一个整数数组nums，返回一个数组answer，使得 answer[i]等于nums中除nums[i]之外 的所有元素的乘积。
nums 的任何前缀或后缀的乘积保证适合 32 位整数。
您必须编写一个在O(n)时间内运行且不使用除法运算的算法。
示例1：
Run Code Online (Sandbox Code Playgroud)Input: nums = [1,2,3,4] Output: [24,12,8,6]示例2：
Run Code Online (Sandbox Code Playgroud)Input: nums = [-1,1,0,-3,3] Output: [0,0,9,0,0]
这是我对上述问题的解决方案。
public int[] productExceptSelf(int[] nums) {
int answer[]=new int[nums.length];
for(int i=0;i<nums.length;i++){
int prod=1;
for(int j=0;j<nums.length;j++){
if(j!=i)
prod=prod*nums[j];
}
answer[i]=prod;
}
return answer;
}
这正在通过 19/20 测试用例。有一个测试用例不起作用，并且我收到错误“超出时间限制”。
失败的测试用例如下：
Run Code Online (Sandbox Code Playgroud)Input: [-1,-1,-1,-1,..............]; Output: Time limit exceeded.
如果有人可以帮助我，我必须对我的代码执行什么版本？