Efficient way of searching interval in 1d-array?

[Gunnar_Kulbotten]

I have a 1d-array of U8, which represent the on/off state of 8 signals. The array may be huge, as the sample rate is typically 10ms, and duration may be a week. The array is stored in a datalog-file with records that typically contain an hour of data.

I want to search this data for the intervals of a fixed number of samples where the 8 signals have maximum number of on-state samples.

I tried to do it  in a while-loop with an inner for-loop. The while-loop extract a sub array at each iteration of the interval size, and the for-loop then runs through the sub-array, convert each U8 to a binary array, and counts the number of on-states for each signal in the interval. Then the while-loop advances one sample, and extract the next interval etc.. This works, but is unbaringly slow.. I see a way of improving this by only loop through the complete first interval, and then add the state of the first sample in the next interval, and subtract the state of the first sample in the previous interval. Also tried to slice out subarray of interval size, convert to binary array, convert F/T to 0,1 and use sum array elements. This was much faster, but consumed a lot of memory.

Any suggestions of better ways of doing this is appreciated..

Gunnar

[Kevin_Price]

Interesting problem.  Can't immediately think of a quick & nifty approach but it sounds like the sort of problem that may have an elegant solution.

1. Are you treating the 8 signals individually or in aggregate?  In other words, do you need to find region0 which maximizes # of on-states of signal0, and then a separate region1 which maximimizes # of on-states for signal1...?  Or do you just find the region where the sum total # of on-states for all 8 signals together is maximized?

2. I calculate roughly 60 million U8 samples in a week.  You'll probably need to do your processing in chunks.  You should make sure to use fixed-size chunks so you'll be able to use things like shift registers and Replace Array Subset to maximize memory efficiency by re-using the same memory space over and over.

3. Over roughly what "fixed # of samples" do you need to maximize the # of on-states?  10, 100, 1000, more? 

4. Do you need to keep track of ties?  If the same # of on-states occurs in different regions, do you need to identify all of them?

5. If you're summing the aggregate total # of on-states for all 8 signals combined, this may be a good candidate for a little 256 element lookup table array constant.  Each possible 8-bit pattern has a value from 0 to 255.  The value you store in the array at index i will be the # of on-states in that bit-pattern.   This helps you so that for each u8 sample, you can simply index into the array to get your on-state count rather than converting to boolean array, converting to 0,1, and summing.

-Kevin P.

[johnsold]

Gunnar,

You may not need to convert from U8 to booleans. All the numeric and logic functions are polymorphic and work directly on the U8 numeric reresentation. For example using the AND function with a value of 6 applied to one input will result in the output having a value which contains only the two bits (bit 1 and bit 2) from the data input.

Lynn

[altenbach]

To count the number of ON states is basically determining the number of "1" bits for a U8 number. This is easiest done with a lookup table.

have a look at my code "U16BitsSet.vi", which is a subVI in my Tic Tac Toe code posted here:

http://forums.ni.com/ni/board/message?board.id=170&message.id=247044#M247044

(Sorry, as others have mentioned, some things are mispelled in the code 😉 That's why I don't like text code 🐵

It basically returns the number of bits for each possible 16 bit number. Your case is simpler. To adapt, set the loop count to 256 and the represetation of the input to U8.

On first run, it creates a lookup table in an uninitialized shift register and indexes into the array with the desired input to return the number of bits. In subsequent calls, it uses the existing lookup table in the shift register to return the number. This is probably as fast as you can do your inner task. 🙂

A 8 bit lookup table is so small, that you could actually calculate it once, then turn it into a diagram constant. Now you can even eliminate the loop and case structure, etc. 😉

Message Edited by altenbach on 06-20-2007 09:27 AM

Message Edited by altenbach on 06-20-2007 09:33 AM

[Jarrod_S.]

Great solution. It seems though that your whole for loop is constant folded, meaning its never really being calculated during run-time anyway, so there's not much of a point in having the Case Structure and First Call primitive anyway. It's basically the same thing as a diagram constant by the time you run your VI.

[altenbach]

---

@jarrod S. wrote:
It seems though that your whole for loop is constant folded, meaning its never really being calculated during run-time anyway,

---

Yes, that's right ( I have the folding display always enabled, so I saw this too). 🙂

However, I left things in place in case somebody with an old version of LabVIEW would copy it verbatim. 😉

Also, the folding algorithms have changed over various versions so I'd rather code it explicit, just in case. We never know if LabVIEW 20.0 will still fold this. 😮

Message Edited by altenbach on 06-20-2007 12:11 PM

[Gunnar_Kulbotten]

Thanks for your suggestions!

1. The signals are treated individually,  so I`m not looking for the number of 1`s in a U8 number.

2. I Agree, though I made a test file of about 35MB, and I could read all the data at once rather quickly.

3. Number of samples in an interval will be in the order of 100000.

4. Yes, I would like to keep the resulting count for each interval for all the signals.

5. I really liked the lookup table idea, but I can`t see how I can use it, at least not directly. At least I`m learning something..

Gunnar

[DFGray]

If you are trying to count the number of bits high over an interval of your data, try the following code snippet.  The hidden case has value "..0".  This increments the count if the bit is greater than 0.

Message Edited by DFGray on 06-21-2007 07:42 AM

[Gunnar_Kulbotten]

Thanks!

I tried something similar, except that I AND`ed the U8 number with all the mask bytes within one iteration of the inner loop. It worked, and was usable for searching ONE interval. But in my approach I searched the first interval, then increased the index by one, and sliced out a new interval from the full U8 array, searched this, and so on. The number of iterations for the inner loop will then be about n*n - interval size where n is the number of U8 numbers in my file. Maybe my idea from the first post wasn`t too bad after all? Loop through the first interval, then instead of looping through the rest, subtract count from bits in first sample in interval, and add count from bits in last sample in next interval. Intervals are offset by only one sample.

Gunnar

[altenbach]

Sorry, your initial description "where the 8 signals have maximum number of on-state samples" coul be interpreted in several ways, so I guessed. 😉

All you need to keep is a size 8 array that counts each channel seperately. Here's a simple one-loop version:

---

@Gunnar Kulbotten wrote:
Loop through the first interval, then instead of looping through the rest, subtract count from bits in first sample in interval, and add count from bits in last sample in next interval. Intervals are offset by only one sample.

---

Yes, that should be trivial to implement. All you need is to keep the current count in a shift register, subtract the count for the removed point and add the count for the new point. This can be done in with a single loop containing a case structure. Case for i=0 wound contain the above code. All other cases just index out two elements and adjust the count accordingly. Autoindex the size8 array at the right loop boundary to create a 2D array where you can search for max in each column.

Message Edited by altenbach on 06-21-2007 08:17 AM