0

Basically I have a set of redundant data that could have an error in one (bonus points: one or more) of the values. Some values could also be 0, which means ignore/invalid. What would be the most efficient way to return the "good" value?

The dumb solution would be a for loop that iterates over the set and returns once it finds the same non-zero value twice. But I feel like there might be some logical/bit-hacking expression that would be better.

booshong
  • 782
  • 6
  • 21
  • How is your data stored? What ratio of the list are zeros? Do you have a target platform/language? – mfa Jul 11 '12 at 18:54
  • also, a similar SO question: http://stackoverflow.com/questions/1332527/what-are-the-fast-algorithms-to-find-duplicate-elements-in-a-collection-and-grou – mfa Jul 11 '12 at 18:58
  • I'm actually implementing this as hardware so I figured I'd be as theoretical as possible. But I'm using Verilog if you know it :). No assumptions on the number of zeros. – booshong Jul 11 '12 at 19:16

1 Answers1

0

The 'dumb' solution might be the best one to use, especially if there aren't many zeros in the data set. You would break from the loop very early in most cases.

In the case where there are a lot of zeros, your speed can be optimized if your hardware is able to quickly scan for non-zero entries. I imagine that searching for non-zeros is very easy on FPGA hardware, but I don't have personal experience with this myself.

mfa
  • 5,017
  • 2
  • 23
  • 28