Алгоритм определения того, принадлежит ли число группе или нет

Я даже не уверен, что это возможно, но я думаю, что все равно стоит его просить.

Скажем, у нас есть 100 устройств в сети. Каждое устройство имеет уникальный идентификатор.

Я хочу сказать группе этих устройств что-то сделать, передавая только один пакет (пакет, который все устройства получают). Например, если я хотел сказать устройствам 2,5,75,116 и 530, чтобы что-то сделать, я должен транслировать это: 2-5-75-116-530 Но этот пакет может стать довольно длинным, если я захочу (например) 95 устройств сделать что-то!!! Поэтому мне нужен метод для сокращения длины этого пакета.

Подумав немного, я придумал идею:

что, если я использовал только простые числа в качестве идентификаторов устройств? Затем я мог бы отправить продукт идентификаторов устройств группы, в которой я нуждаюсь, так как пакет и каждое устройство будут проверять, осталось ли оставшееся число полученного номера и его идентификатор устройства.

Например, если бы я хотел, чтобы устройства 2,3,5 и 7 что-то делали, я бы транслировал 2 * 3 * 5 * 7 = 210, и тогда каждое устройство будет вычислять "210 идентификатор самообучения модема" и только устройства с идентификаторами 2, 3,5 и 7 получат 0, чтобы они знали, что они должны что-то сделать.

Но этот метод неэффективен, потому что 100-е число простых чисел - 541, а широковещательный номер может стать действительно большим, а вычисления "мод" могут стать очень трудными (устройства имеют 8-битные процессоры).

Поэтому мне просто нужен метод для устройств, чтобы определить, должны ли они что-то делать или игнорировать полученный пакет. И мне нужно, чтобы пакет был как можно короче.

Я изо всех сил пытался объяснить вопрос, если его все еще неясно, скажите, пожалуйста, чтобы объяснить больше.

Ответ 1

Вы можете просто использовать битовую строку, в которой каждый бит представляет собой устройство. Затем вам просто нужно поразрядно И сказать, должна ли данная машина реагировать.

Вам понадобится один бит на устройство, которое будет, например, 32 байта для 256 устройств. По общему признанию, это немного расточительно, если вам нужна только одна машина, чтобы реагировать, но она довольно компактна, если вам нужно, скажем, 95 устройств для ответа.

Вы упомянули, что вам нужно, чтобы идентификатор устройства был <= 4 байта, но это не проблема: 4 байта = 32 бит = достаточно места для хранения 2 ^ 32 идентификаторов устройств. Например, идентификатор устройства для 101-го компьютера (если вы начинаете с 0) может быть просто 100 (0b01100100) = 1 байт. Вам просто нужно использовать это, чтобы выяснить, какой байт используемого пакета (ceil(100 / 8)= 13-й) и побитовый И, который байт против 100 % 8= 4= 0b00000100.

Как cobarzan сказал, вы также можете использовать гибридную схему, позволяющую индивидуальную адресацию. В этом сценарии вы можете использовать первый бит в качестве сигнала для обозначения множественной или одномашинной адресации. Как сказал cobarzan, это требует большей обработки, а это означает, что первый байт может хранить только 7 машинных сигналов, а не 8.

Ответ 2

Как и Эд Коттрелл, небольшая строка будет выполнять эту работу. Если машины помечены как {1,..,n}, существует 2 ⁿ -1 возможных подмножеств (при условии, что вы не отправляете запросы без намеченной цели). Таким образом, вам нужна структура данных, способная хранить каждую возможную подпись такого подмножества, независимо от того, что вы решаете подписи. И n бит (по одному для каждой машины) лучше всего подходит для размера такой структуры данных. Оценка, выполняемая на машинах, занимает постоянное время (на машине с меткой l просто посмотрите на l th бит).

Но можно пойти на какую-то гибридную схему. Предположим, что у вас есть задача только для одного устройства, тогда было бы жаль отправить n bits (все 0s, кроме одного). Таким образом, вы можете взять еще один бит T, который указывает тип пакета. Значение T устанавливается равным 0, если вы отправляете бит строку длиной n, как описано выше, или установите значение 1, если вы используете более подходящую схему (т.е. Меньше бит). В случае только одной машины, которая должна выполнить задачу, вы можете отправить непосредственно метку машины (длиной O(log n) бит). Этот подход уменьшает размер пакета, если у вас меньше, чем O(n/log n) машин, необходимых для выполнения задачи. Оценка на машинах дороже, хотя.