ansaurus

Question

Fast way to get bitmask for delivery to all devices.

Answer 1

+1 A:

Take a look at backtrack search.

Pace 2010-02-25 14:11:07

Looks promising, I will take a look.

Jaakko L. 2010-02-25 14:17:00

Answer 2

+4 A:

Since there may not be a perfect solution and we only have 16 possibilities for the result I would just use a brute force approach and iterate through all 16 possible masks, and see which one(s) is/are optimal (minimum number of repeated messages).

Paul R 2010-02-25 14:13:46

+1 Exactly, iterating over 16 options is no brainer on any usual computation platform; you don't even need to go through all the 256 channels because if you have more than 16 channels some of them are bound to have the same bitmasks; just maintain a table that calculates the counts of different bitmasks in the device table and then optimize using that; 16 x 16 table row checks then suffice---fast

antti.huima 2010-02-25 17:19:42

16 options isn't much, but wouldn't I need to iterate through all devices? There would be 16 * numOfDevices iterations to do to get all valid channel masks.This checking is something that might have to be done every 100 ms, so every 1 ms in execution time adds 1% CPU overhead.

Jaakko L. 2010-02-25 20:58:34

Suppose you spend say 10 instruction clocks processing each device. That's 16 * 256 * 10 clocks = 40k clocks = 20 µs on a 2 GHz CPU. If you do this every 100 ms then it's a 0.02% CPU load.

Paul R 2010-02-25 21:23:17

@Jaakko every device has one of the 16 masks, so it's enough to maintain a table int[16] where each entry counts the *NUMBER* of devices having that bitmask, i.e. if table[0xf]==3 then you have 3 devices with bitmask 1111. You can use that table instead of the actual device list when you do the optimization.

antti.huima 2010-02-25 23:21:55

@antti.huima Thanks for clarifying, now I got your idea. Using an bitmask count array speeds things up a lot.

Jaakko L. 2010-02-26 14:00:18

Answer 3

+1 A:

You could add the number of 1's in each column to find out how many "receptions" will occur for a message on that channel. That way for any valid mask (that reaches all devices) you can easily add up the total number of messages received by all devices. You can then brute force all 16 possible masks seeing which ones will actually work and choosing the one that both works and has the lowest total number of receptions. Getting around the brute-force part is going to require operations on the entire matrix.

Oddly, if you actually had 256 devices you'd probably have to send on all channels anyway.

phkahler 2010-02-25 14:29:25

Thanks, this is similar to what I first came up with. What I didn't think of, is that I could compare the valid masks to number of receptions per channel. I think this is a pretty fast solution, thanks.

Jaakko L. 2010-02-25 14:44:01

ansaurus

tags:

views:

answers:

Fast way to get bitmask for delivery to all devices.

related questions