2

Помогите решить следующую проблему (язык не важен, важен алгоритм, а в вопросе я для простоты на питоне запишу):

есть все возможные 5-битовые маски:

0b00000
0b00001
0b00010
...
0b11111

требуется применить каждую маску для анализа

analyze(mask)

при этом если результат анализа положительный, то не рассматривать все остальные маски имеющие со сработавшей хотя бы один общий установленный бит, т.е. если сработала маска 0b00001, то маской 0b01101 анализировать уже не следует

в лоб алгоритм выглядит так:

excluded = 0

for mask in masks:
    # если маска в исключениях - перейти к следующей маске
    if mask & excluded:
        continue

    # проанализировать текущую маску и установить исключения
    if analyze(mask):
        excluded |= mask

алгоритм неплохой, но медленный, поэтому (+ была еще одна целесообразность) я разбил все маски на группы по кол-ву установленных бит, а каждую группу разбил на 0b100000 групп, в результате алгоритм приобрел вид:

excluded = 0

for size in range(0, 6):

    # анализировать только требуемыми масками
    for mask in masks_groups[size][excluded]:

        # проанализировать текущую маску и установить исключения
        if analyze(mask):
            excluded |= mask

такой подход увеличил производительность в 2 раза с незначительным увеличением использования памяти

И тут встал вопрос:

а можно ли (вернее чувствую, что можно, но голова уже не варит) сделать не дискретную выборку маски по кол-ву бит в маске, а плавный - т.е. чтобы после каждого анализа на основании значения из excluded выбиралась следующая маска?

я думаю это можно сделать с помощью заранее подготовленного дерева, где алгоритм будет выглядеть примерно так:

mask = tree

while mask != 0:
    mask = mask[excluded]

    if analyze(mask):
        excluded |= mask

подскажите, можно ли так сделать и если можно, то как?

т.е. с помощью текущей маски и исключений я определяю следующую маску, которая не содержит бит из исключений

например, если analyze постоянно будет отрицательным мне придется пройти по всем существующим маскам, а если analyze для масок 0b10000, 0b01000, 0b00100, 0b00010, 0b00001, будет положительным, то после последней маски цикл прекратится

как я понимаю должно быть дерево (по сути некоторый массив) где каждый элемент массива содержит индекс массива в который надо заглянуть и этот индекс и есть текущая маска, если элемент массива с этим индексом нулевой (содержит 0 или -1 не суть) значит обход масок закончился

19
  • Не сказал бы, что мне все понятно, и мне кажется тут нужны пояснения больше о том что вы имеете и что хотите получать. Если хотите получать маску, где все биты с data отличаются, то это ~data. Кто то минусом наградил вопрос, поэтому мне кажется, что не только я один не понял... 24 янв 2021 в 10:26
  • @AR Hovsepyan, а что не так с вопросом? есть 2^5 масок, все маски надо проанализировать с некоторыми данными, если маска была успешно проанализирована, то другие маски у которых есть те же установленные биты, что и у успешно проанализированной игнорировались, при чем тут ~data? data - это некоторые данные к вопросу не имеющие отношение, надо было написать analyze(mask) - сейчас исправлю, чтобы не давать лишней информации
    – Zhihar
    24 янв 2021 в 10:30
  • кстати интересно а кто вляпал минус по пункту Вопросы с просьбами помочь с отладкой («почему этот код не работает?»)... Код работает, вопрос стоит как сделать обход другим способом, т.е. применить другой, более эффективный алгоритм, требующий меньшее кол-во проверок
    – Zhihar
    24 янв 2021 в 10:35
  • А мне кажется надо построить массив масок сгруппированных по номерам установленных бит. Вернее ключами я бы наверное сделал числа с нужным битом (0b00001, 0b00010, 0b00100, ...) и сложил в эти ключи списки масок включающих этот бит (да, какие то из них замножатся). после срабатывания одной маски мы сразу можем выйти из обработки текущей группы и знаем группы в которых искать более не следует (excluded & key != 0).
    – Mike
    24 янв 2021 в 10:38
  • хотя .... наверное в группы много лишнего попадет ...
    – Mike
    24 янв 2021 в 10:40

2 ответа 2

2

Посмотрите, правильно ли я понял задачу?

check - эмуляция, ловля двух масок. После того, как найдена маска 0b00010, числа, в которых включен второй бит, в проверках уже не участвуют.

После того, как проверена маска 0b00101, числа, в которых включены либо первый, либо третий бит, в проверках уже не участвуют (но часть из них уже была проверена ранее, и не похоже, что от этого можно избавиться)

Базовый перебор подмасок - например, здесь описан

def inv(s):
    return s^0b11111

def check(s):
    return((s & 0b10 == 0b10) or (s & 0b101 == 0b101))

mask = 0b11111
excl = 0b00000
sm = mask
while sm:
    sm = (sm - 1) & mask
    sub = inv(sm | excl)
    print("check {0:b}".format(sub))
    if check(sub):
        print('out        ', "{0:b}".format(sub))
        excl |= inv(sm)
        mask = sm

check 1
check 10
out         10
check 1
check 100
check 101
out         101
check 1000
check 10000
check 11000
5
  • смотрите - в моем случае check - это сложный алгоритм работы с данными с использованием маски, т.е. что будет на выходе заранее предсказать нельзя и результат не очень то сильно зависит от самой маски чтобы можно было построить какую-то зависимость, опять же перебор масок должен идти от маски с меньшим кол-вом бит к маске с большим кол-вом бит - так эффективнее идет анализ (больше или лучше сказать раньше лишние маски отсекаются)
    – Zhihar
    24 янв 2021 в 11:36
  • посмотрел вашу ссылку - все верно в общем-то и я с этого когда-то начинал, но оказалось, что по скорости значительно выгоднее двигаться по заранее просчитанным маскам, чем их перерассчитывать (например в ссылке это все комбинации масок), но теперь и этого недостаточно (нашел как описал в вопросе способ как снизить и обход по заранее рассчитанным маскам)
    – Zhihar
    24 янв 2021 в 11:38
  • Так перебор здесь и идёт от малого количества бит к большому.
    – MBo
    24 янв 2021 в 11:47
  • MBo есть один недостаток - сначала надо рассматривать комбинации только с 1 установленным битом, потом с 2, потом с 3 и т.д., а у вас они идут последовательно от 1 до 2^5 в результате то 1 то 2 то 3 и т.д. биты бывает установлено
    – Zhihar
    24 янв 2021 в 12:51
  • Ну да, это понятно, но как такой обход реализовать с фильтрацией - неясно.
    – MBo
    24 янв 2021 в 13:35
0

Придумал как можно сделать

основная мысль - требуется матрица NxN где N = 2^k (по сути кол-во бит в маске), ячейка в матрице показывает какая следующая маска должна выбираться

  1. первоначально создаем совокупность масок при excluded = 0, т.е. как обходили маски по умолчанию

  2. далее рассчитываем таблицу так чтобы ячейка с координатами [excluded][mask] содержала бы следующую маску

код:

# сформировать таблицу для обхода масок
size = 0b10000

table = [[0] * size for _ in range(size)]

# заполнить таблицу для обхода масок
for excluded in range(size):

    # сформировать массив масок в которых не установлены исключённые биты
    masks_prepared = [mask for mask in masks if mask & excluded == 0]
   
    # внести обход подготовленных масок в таблицу
    for mask_index in range(len(masks_prepared) - 1):
        table[excluded][masks_prepared[mask_index]] = masks_prepared[mask_index + 1]

    table[excluded][masks_prepared[len(masks_prepared) - 1]] = -1

    # внести обход оставшихся масок в таблицу
    for mask_index in range(len(masks)):
        # не рассматривать уже обработанные маски
        if masks[mask_index] in masks_prepared:
            continue

        # найти следующую обработанную маску
        found_index = mask_index

        for index in range(mask_index + 1, len(masks)):
            if masks[index] in masks_prepared:
                found_index = index
                break

        table[excluded][masks[mask_index]] = -1 if found_index == mask_index else masks[found_index]

В результате обход получается очень простым и максимально коротким (С++):

int excluded = 0;
int mask = 0;

while ((mask = table[excluded][mask]) != -1)
{
    if (analyze(mask))
        excluded |= mask;
}
3
  • у вас получилось какая смесь c++ и python
    – Danis
    27 янв 2021 в 20:08
  • @Danis, основной код работает на c++ конечно (мне нужна производительность), но статическую таблицу я составил с помощью питона (просто более удобный инструмент). Как я написал в вопросе - мне язык был не важен, главное понять какой алгоритм
    – Zhihar
    27 янв 2021 в 20:36
  • я имел ввиду последний ваш код, создание переменных как в c++, а блок if как в python(двоеточие и отсутствует ;)
    – Danis
    27 янв 2021 в 20:37

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.