CODEWITHSUNDEEP
javascriptarraysalgorithm
user578895
user578895

Reputation:

Optimizing an algorithm subtracting first elements from last elements

I'm trying to optimize a slow part of a larger algorithm.

I have an array of random-looking numbers:

[295, 292, 208, 393, 394, 291, 182, 145, 175, 288, 71, 86, 396, 422]

(actual arrays are much longer), and an index: N (N = 5)

What I want to do is subtract subtract 1 from the last M elements for each of the first N elements that are smaller

So (pseudo-code):

for a = 1..5
  for b = 6..N
    if ary[a] < ary[b]
      ary[b]--;

Obviously this is a horribly inefficient O(N^2) algorithm. I'm trying to think of a faster way to do it, but can't. It seems like I should be able to pre-compute the values to subtract somehow, and reduce it to:

for a = 1..5
  // ???
for b = 6..N
  ary[b] -= ???

but I'm missing something.

[edit] I feel like an idiot. I didn't properly explain what I want, fixed.

Upvotes: 3

Views: 95

Answers (2)

Bert te Velde
Bert te Velde

Reputation: 853

It seems to me that Petr's solution doesn't follow the specification of the problem: we should subtract 1 (one) for each "hit", not the VALUE of ary[a].

Here's an alternative:

  1. place the testvalues ary[j], j=0..N-1 in a SORTED array: sortedSmallAry[N].

  2. Then run over all b, i.e. b=N, ..., Total-1, and for each ary[b]:

  3. run j=0..N-1 over the sortedSmallAry, test whether sortedSmallAry[j] is smaller than ary[b], count the hits, exit as soon as it fails (because it's sorted). If N is relatively large you can use a binary search in sortedSmallAray to determine how many of its elements satisfy the condition.

  4. Subtract the hitcount from ary[b].

Upvotes: 0

Petr
Petr

Reputation: 9997

Let's reorganize the loops:

for b = 6..N
  for a = 1..5
    if ary[a] < ary[b]
      ary[b] -= ary[a];

The result will be the same. But now the logic is more clear: from each element from the second part of array you subtract ary[1], then ary[2] and so on until some ary[a] is bigger that what remains from ary[b].

This can be optimized the following way. Calculate the cumulative sums of the first half of array: let sum[1]=ary[1], sum[2]=sum[1]+ary[2], sum[3]=sum[2]+ary[3], and so on. This can be done in O(N).

Now for each b you need to find such a_last that sum[a_last]<ary[b], but sum[a_last+1]>=ary[b] -- this will mean that from ary[b] you will subtract ary[1]+...+ary[a_last]=sum[a_last]. You can find such a_last using binary search in O(log N), thus making the overall algorithm O(N log N).

The pseudocode:

sum[0] = 0
for a = 1..5
    sum[a] = sum[a-1] + ary[a]
for b = 6..N
    a_last = maximal a such that sum[a]<ary[b] // use binary search
    ary[b] -= sum[a_last]

Upvotes: 2

Related Questions