Как ускорить выполнение кода для решения проблемы удаления битов

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

Это небольшая чистая программа Python 3, использующая поиск в обратном направлении с некоторыми жадными эвристиками порядка. Он очень быстро решает N = 3, 6 и 9 экземпляров. Он также быстро находит покрытие размером 10 для N = 12, но, по-видимому, потребуется намного больше времени для исчерпания пространства поиска (у меня нет времени для этого, и он все еще работает). При N = 15 время инициализации уже медленное.

Бистроны представлены здесь равными N-битовыми целыми числами, поэтому они потребляют мало памяти. Это облегчает перекодировку на более быстром языке. Он действительно использует множество целых чисел, но не имеет других «продвинутых» структур данных.

Надеюсь, это поможет кому-то! Но ясно, что комбинаторный взрыв возможностей с ростом N гарантирует, что ничего не будет «достаточно быстро», не углубляясь в математику проблемы.

 def dump(cover): for s in sorted(cover): print(" {:0{width}b}".format(s, width=I)) def new_best(cover): global best_cover, best_size assert len(cover) < best_size best_size = len(cover) best_cover = cover.copy() print("N =", N, "new best cover, size", best_size) dump(best_cover) def initialize(N, X, I): from itertools import combinations # Map a "wide" (length N) bitstring to the set of all # "narrow" (length I) bitstrings that generate it. w2n = [set() for _ in range(2**N)] # Map a narrow bitstring to all the wide bitstrings # it generates. n2w = [set() for _ in range(2**I)] for wide, wset in enumerate(w2n): for t in combinations(range(N), X): narrow = wide for i in reversed(t): # largest i to smallest hi, lo = divmod(narrow, 1 << i) narrow = ((hi >> 1) << i) | lo wset.add(narrow) n2w[narrow].add(wide) return w2n, n2w def solve(needed, cover): if len(cover) >= best_size: return if not needed: new_best(cover) return # Find something needed with minimal generating set. _, winner = min((len(w2n[g]), g) for g in needed) # And order its generators by how much reduction they make # to `needed`. for g in sorted(w2n[winner], key=lambda g: len(needed & n2w[g]), reverse=True): cover.add(g) solve(needed - n2w[g], cover) cover.remove(g) N = 9 # CHANGE THIS TO WHAT YOU WANT assert N % 3 == 0 X = N // 3 # number of bits to exclude I = N - X # number of bits to include print("initializing") w2n, n2w = initialize(N, X, I) best_cover = None best_size = 2**I + 1 # "infinity" print("solving") solve(set(range(2**N)), set()) 

Пример вывода для N = 9:

 initializing solving N = 9 new best cover, size 6 000000 000111 001100 110011 111000 111111 

Следовать за

Для N = 12 это в конечном итоге закончилось, подтвердив, что минимальный набор покрытий содержит 10 элементов (которые он нашел очень скоро в начале). Я не успел, но потребовалось не менее 5 часов.

Почему это? Потому что это близко к мозгу, мертвому 😉 Полностью наивный поиск попробует все подмножества 256 8-битных коротких строк. Есть 2 ** 256 таких подмножеств, около 1,2e77 – это не закончилось бы в ожидаемом периоде жизни Вселенной 😉

Упорядочивающие трюки здесь сначала обнаруживают, что «все 0» и «все 1» короткие строки должны быть в любом наборе покрытий, поэтому выбирайте их. Это оставляет нам смотреть на «только» 254 оставшихся коротких строк. Тогда жадный «выбрать элемент, который покрывает самую» стратегию, очень быстро находит набор покрытий с 11 полными элементами, а вскоре после этого – покрытие с 10 элементами. Это бывает оптимальным, но для исчерпания всех других возможностей требуется много времени.

В этот момент любая попытка набора покрытий, которая достигает 10 элементов, прерывается (тогда она не может быть меньше 10 элементов!). Если бы это было сделано полностью наивно, нужно было бы попробовать добавить (к строкам «все 0» и «все 1») все 8-элементные подмножества оставшихся 254, а 254-select-8 – около 3.8e14. Очень меньше 1,2e77 – но все же слишком большой, чтобы быть практичным. Это интересное упражнение, чтобы понять, как код справляется намного лучше, чем это. Подсказка: он имеет много общего с данными в этой проблеме.

Промышленно-силовые решатели несравненно сложнее и сложнее. Я был приятно удивлен, насколько хорошо эта простая маленькая программа сделала на небольших проблемах! Ему повезло.

Но для N = 15 этот простой подход безнадежен. Он быстро находит обложку с 18 элементами, но не делает видимого прогресса в течение как минимум часов. Внутри он по-прежнему работает с needed наборами, содержащими сотни (даже тысячи) элементов, что делает тело solve() довольно дорогостоящим. Он все еще имеет 2 ** 10 – 2 = 1022 коротких строк, и 1022-select-16 составляет около 6e34. Я не ожидаю, что это заметно поможет, даже если этот код будет ускорен на миллион.

Было интересно попробовать, хотя 🙂

И небольшая перезапись

Эта версия работает как минимум в 6 раз быстрее при полном запуске N = 12, просто отсекая бесполезные поиски на один уровень раньше. Также ускоряет инициализацию и сокращает использование памяти путем изменения наборов 2 ** N w2n в списки (на них не используются никакие заданные операции). Это все еще безнадежно для N = 15, хотя 🙁

 def dump(cover): for s in sorted(cover): print(" {:0{width}b}".format(s, width=I)) def new_best(cover): global best_cover, best_size assert len(cover) < best_size best_size = len(cover) best_cover = cover.copy() print("N =", N, "new best cover, size", best_size) dump(best_cover) def initialize(N, X, I): from itertools import combinations # Map a "wide" (length N) bitstring to the set of all # "narrow" (length I) bitstrings that generate it. w2n = [set() for _ in range(2**N)] # Map a narrow bitstring to all the wide bitstrings # it generates. n2w = [set() for _ in range(2**I)] # mask[i] is a string of i 1-bits mask = [2**i - 1 for i in range(N)] for t in combinations(range(N), X): t = t[::-1] # largest i to smallest for wide, wset in enumerate(w2n): narrow = wide for i in t: # delete bit 2**i narrow = ((narrow >> (i+1)) << i) | (narrow & mask[i]) wset.add(narrow) n2w[narrow].add(wide) # release some space for i, s in enumerate(w2n): w2n[i] = list(s) return w2n, n2w def solve(needed, cover): if not needed: if len(cover) < best_size: new_best(cover) return if len(cover) >= best_size - 1: # can't possibly be extended to a cover < best_size return # Find something needed with minimal generating set. _, winner = min((len(w2n[g]), g) for g in needed) # And order its generators by how much reduction they make # to `needed`. for g in sorted(w2n[winner], key=lambda g: len(needed & n2w[g]), reverse=True): cover.add(g) solve(needed - n2w[g], cover) cover.remove(g) N = 9 # CHANGE THIS TO WHAT YOU WANT assert N % 3 == 0 X = N // 3 # number of bits to exclude I = N - X # number of bits to include print("initializing") w2n, n2w = initialize(N, X, I) best_cover = None best_size = 2**I + 1 # "infinity" print("solving") solve(set(range(2**N)), set()) print("best for N =", N, "has size", best_size) dump(best_cover) 

Сначала подумайте, есть ли у вас 6 бит. Вы можете выбросить 2 бита. Поэтому любой баланс шаблонов 6-0, 5-1 или 4-2 может быть преобразован в 0000 или 1111. В случае 3-3 баланса нуля один любой шаблон может быть преобразован в один из четырех случаев: 1000, 0001 , 0111 или 1110. Следовательно, один возможный минимальный набор для 6 бит:

 0000 0001 0111 1110 1000 1111 

Теперь рассмотрим 9 бит с 3 выброшенными. У вас есть следующий набор из 14 шаблонов:

 000000 100000 000001 010000 000010 110000 000011 001111 111100 101111 111101 011111 111110 111111 

Другими словами, каждый набор шаблонов имеет одни / нули в центре, причем каждая перестановка n / 3-1 бит на каждом конце. Например, если у вас есть 24 бита, тогда у вас будет 17 бит в центре и 7 бит на концах. Так как 2 ^ 7 = 128, у вас будет 4 x 128 – 2 = 510 возможных шаблонов.

Чтобы найти правильные удаления, существуют различные алгоритмы. Один из способов – найти расстояние редактирования между текущим набором бит и каждым шаблоном. Шаблон с минимальным расстоянием редактирования – это тот, для которого нужно преобразовать. Этот метод использует динамическое программирование. Другим методом будет поиск дерева по шаблонам с использованием набора правил для поиска совпадающего шаблона.