Stack Overflow
Stack Overflow

Questions tagged [prefix-sum]

63 questions
29
votes
11 answers

Is there a better way to do partial sums of array items in JavaScript?

I wonder if there is a better way of generating a better performing solution for partial sums of an array. Given an array say x = [ 0, 1, 2, 3, 4, 5 ], I generated sub-arrays of the items, and then computed the sum of each array which gives: [ 0,…
Patrick Francis Omogbeme
  • 397
  • 3
  • 7
22
votes
5 answers

SIMD prefix sum on Intel cpu

I need to implement a prefix sum algorithm and would need it to be as fast as possible. Ex: [3, 1, 7, 0, 4, 1, 6, 3] should give: [3, 4, 11, 11, 15, 16, 22, 25] Is there a way to do this using SSE SIMD CPU instruction? My first idea is to…
skyde
  • 2,816
  • 4
  • 34
  • 53
15
votes
2 answers

python - prefix sum algorithm

I am trying to grasp the idea behind the prefix sum concept looking at the example presented in the Prefix Sum Lesson by Codility here (The mushroom picker problem) My understanding is that the whole concept is based on the simple property where for…
Chris
  • 767
  • 1
  • 8
  • 23
8
votes
2 answers

Dynamic prefix sum

Is there any data structure which is able to return the prefix sum [1] of array, update an element, and insert/remove elements to the array, all in O(log n)? [1] "prefix sum" is the sum of all elements from the first one up to given index For…
Ecir Hana
  • 10,864
  • 13
  • 67
  • 117
4
votes
1 answer

Minimum reallocations required to make all prefix sum >=0

Give an Array of integers eg : 10, -10, -1, -1, 10 . I have to find minimum reallocations such that all the prefix sums of the array are >=0. The sum of all elements in the array is assumed to be non-negative. In the above example, we can move -10…
rohit
  • 83
  • 7
4
votes
3 answers

Compute all prefix sums in purely functional programming style in O(n) time in Kotlin

Is it possible to compute all prefix sums for an array of numbers in purely functional programming style in O(n) time in Kotlin? What I mean by purely functional programming is allowing using functional programming extension functions for…
Shreck Ye
  • 1,591
  • 2
  • 16
  • 32
4
votes
1 answer

CUDA: atomicAdd takes too much time, serializing threads

I have a kernel which makes some comparisons and decides whether two objects collide or not. I want to store the colliding objects' id's to an output buffer. I do not want to have gap in the output buffer. I want to record each collision to a unique…
phoad
  • 1,801
  • 2
  • 20
  • 31
3
votes
1 answer

Data Parallel Haskell Prefix Sum

I'm playing with some Data Parallel Haskell code and found myself in need of a prefix sum. However I didn't see any basic operator in the dph package for prefix sum. I rolled my own, but, since I'm new to dph, I'm not sure if it's properly taking…
rampion
  • 87,131
  • 49
  • 199
  • 315
3
votes
1 answer

Finding the shortest contiguous subsequence of array for which the sum can be divided by K

For example, given input arr = [4,5,0,-2,-3,1], k = 5, there are 7 subarrays with a sum divisible by 5: [4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]. The shortest one is either [5] or [0], both are correct. If there…
Nathan
  • 350
  • 1
  • 2
  • 11
3
votes
1 answer

Find the number of subarrays whose average is greater than or equal K

Given an array of integers, find the number of subarrays whose average is greater than or equal to K. Constraints: 1 <= N <= 10^5 -10^9 <= A[i] <= 10^9 My solution: If A[i] is prefix sum upto ith index in the array then (A[j] - A[i]) / (j - i) >=…
Ajay Kumar
  • 586
  • 5
  • 21
3
votes
1 answer

Scan for quicksort splitting

I'm trying to write quicksort with OpenMP, and I'm getting stuck in the splitting part. The literature says that this is a parallel prefix operation. Here's the relevant bit: vector under_pivot(values.size()), over_pivot(values.size()); int…
Victor Eijkhout
  • 5,088
  • 2
  • 22
  • 23
3
votes
2 answers

Python - Compute Local Minimum In Array Using Prefix Sums

I'm trying to solve the Min Avg Two Slice question from Codility. I came up with the following code: 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]: …
Alk
  • 5,215
  • 8
  • 47
  • 116
3
votes
1 answer

Any elegant way deal with array margins in OpenGL Compute Shaders?

Is there any elegant way to deal with array margins in Compute Shaders? (considering you are supposed to have the dimension of the work-group hardcoded in the shader) Consider the following shader code that computes a prefix sum for a 2048 array if…
markwalberg
  • 311
  • 2
  • 10
3
votes
2 answers

Parallel algorithm to compute Prefix Sum

I am having a problem with implementing the algorithm for computing a prefix sum in parallel. Even though this algorithm has 3 steps, I am unable to write the code, as no pseudo-code is given. I went through various material on the web and also on…
user1134599
2
votes
1 answer

CONFLICT_FREE_OFFSET macro used in the parallel prefix algorithm from GPU Gems 3

First of all, here is the link to the algorithm: GPU Gems 3, Chapter 39: Parallel Prefix Sum (Scan) with CUDA. In order to avoid bank conflicts, padding is added to the shared memory array every NUM_BANKS (i.e., 32 for devices of computability 2.x)…
user11869
  • 1,083
  • 2
  • 14
  • 29
1
2 3 4 5