Interpolate Gaps in a Large Array

[paul_cardinale]

I have a very large array of doubles, and some conditions (that boil down to boolean) that determine whether each element should be kept or discarded; the discarded elements to be replaced by interpolated values.  Because the array is very large, I want the code to be very efficient.  Attached is what I have come up with.  Can anyone come up with something more efficient?

[RavensFan]

What you have works.  Why do you think it would be inefficient?

It looks like you keep one copy of the array and do Replace Array Subset to replace elements.

It looks like you just advance through the array just one time.

Both of those things make it seem efficient to me.

[paul_cardinale]

---

@RavensFan wrote:

What you have works.  Why do you think it would be inefficient?

It looks like you keep one copy of the array and do Replace Array Subset to replace elements.

It looks like you just advance through the array just one time.

Both of those things make it seem efficient to me.

---

It's not that I thought that it was necessarily inefficient; but often people here find clever ways to make things better.

[RavensFan]

If there is a way to make it better, Altenbach will find it!  😄

[altenbach · Accepted solution]

---

@RavensFan wrote:

If there is a way to make it better, Altenbach will find it!  😄

---

Maybe not "better", but certainly faster to program and debug (fewer places of bugs to hide! ;))

(attached VI contains both versions to compare operation)

NOTE: the results differ if the last element of the boolean array is FALSE. It is not clear what you would want in that scenario. See post below to get the same result.

[altenbach · Accepted solution]

---

@altenbach wrote:
NOTE: the results differ if the last element of the boolean array is FALSE. It is not clear what you would want in that scenario.

---

If you want the same result even if the boolean array ends in FALSE, this might work.

[altenbach]

---

@paul_cardinale wrote:

Because the array is very large, I want the code to be very efficient.  Attached is what I have come up with.  Can anyone come up with something more efficient?

---

"Very large" is a fuzzy term. Do you have some numbers? The efficiency between the two algorithms also depends on the TRUE probability of the boolean array. It is sparse or mostly true? (This determines the size of the intermediary data structures in my code).

One problem in your code is the initial "prepending" of elements, which can potentially lead to new array allocations (there is an allocation dot). Try to avoid that.

[paul_cardinale]

Thank you.  That's just what I was looking for.

[paul_cardinale]

---

@altenbach wrote:

---

@paul_cardinale wrote:

Because the array is very large, I want the code to be very efficient.  Attached is what I have come up with.  Can anyone come up with something more efficient?

---

"Very large" is a fuzzy term. Do you have some numbers? The efficiency between the two algorithms also depends on the TRUE probability of the boolean array. It is sparse or mostly true? (This determines the size of the intermediary data structures in my code).

One problem in your code is the initial "prepending" of elements, which can potentially lead to new array allocations (there is an allocation dot). Try to avoid that.

---

There will be a few million to several million elements.  The % of TRUE elements in the boolean array is unpredictable, but most likely from 30% - 50%.

I should have realized that, because of the nature of the data source, the beginning elements will always be keepers, so I really don't need prepend anything. Also, the data near the end of the array is of lesser importance (and declining importance as you go farther up the array).  Most of the upper values will be near 0; and what happens with the very last element is inconsequential.

[altenbach]

---

@paul_cardinale wrote:
I should have realized that, because of the nature of the data source, the beginning elements will always be keepers, so I really don't need prepend anything. Also, the data near the end of the array is of lesser importance (and declining importance as you go farther up the array).  Most of the upper values will be near 0; and what happens with the very last element is inconsequential.

---

I am not sure where that -1 comes from and if it is important. Maybe it can be left out. If the first element is guaranteed to be valid and the last element asymptotically zero, you could just ensure these while keeping all arrays at the same size.

Still, I would recommend some benchmarks.