Помогите решить следующую проблему (язык не важен, важен алгоритм, а в вопросе я для простоты на питоне запишу):
есть все возможные 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 не суть) значит обход масок закончился
~data
. Кто то минусом наградил вопрос, поэтому мне кажется, что не только я один не понял...~data
? data - это некоторые данные к вопросу не имеющие отношение, надо было написатьanalyze(mask)
- сейчас исправлю, чтобы не давать лишней информацииВопросы с просьбами помочь с отладкой («почему этот код не работает?»)...
Код работает, вопрос стоит как сделать обход другим способом, т.е. применить другой, более эффективный алгоритм, требующий меньшее кол-во проверок