NuCS против Choco: решатель ограничений на чистом Python встречается с ветераном JVM.

Подробное сравнение производительности Nuc и Choco.

Делиться

Вкратце:

NuCS — это решатель задач с ограничениями, написанный на 100% на Python, разработанный мной и ускоренный NumPy и Numba. Choco — один из эталонных решателей задач с ограничениями с открытым исходным кодом, написанный на Java и разрабатываемый более двух десятилетий.

Сравнение этих двух подходов выглядит однобоко: интерпретируемый язык против сильно оптимизированного решателя JVM с богатым каталогом глобальных ограничений, согласованных по дугам. В действительности же ситуация гораздо интереснее. Когда оба решателя используют одну и ту же модель, они, по сути, работают с одинаковой скоростью — и на самых сложных задачах NuCS даже опережает конкурента, потому что после компиляции внутренних циклов Numba исчезает «налог Python», и остается только стоимость на узел. Когда модели различаются, результатом является настоящий компромисс, а не полное поражение: на некоторых задачах согласованность по дугам в Choco — это правильный и быстрый инструмент; на других — дешевая согласованность границ в NuCS плюс небольшая переработка модели — побеждает с большим отрывом; и, по крайней мере, на одной задаче свобода моделирования NuCS позволяет ему решать задачи, которые не под силу ни одному из обычных решателей.

В этой статье рассматриваются пять тестовых задач, приводятся точные команды NuCS для каждой из них, подробно описываются ограничения и стратегия поиска, строятся кривые производительности, и в заключение рассматривается проектное решение, объясняющее всю картину: NuCS представляет области определения как интервалы min..max и, следовательно, ограничен согласованностью границ, в то время как Choco может также представлять области определения с пробелами и обеспечивать полную согласованность дуг.

Весь представленный здесь код NuCS находится в репозитории NuCS под лицензией MIT.

NuCS

История

NuCS — это проект, который я недавно начал. Дата его первого публичного релиза — 2024 год, и с тех пор он очень быстро развивался — версия, протестированная здесь, — 11.2.0 . Он был построен на намеренно необычной идее: написать конкурентоспособный решатель задач с ограничениями в конечной области полностью на Python и компенсировать потери производительности, обычно связанные с интерпретацией, за счет компиляции «на лету», а не ядра на C или C++. Он распространяется через PyPI ( pip install nucs ), что делает установку такой же простой, как и у любого другого пакета Python — нет нативного набора инструментов, нет JVM.

Архитектура

Объект Problem содержит массив NumPy с областями определения переменных — по одной паре (min, max) для каждой переменной, при этом значение переменной ограничивается, когда min == max — а также список распространителей. Распространитель — это алгоритм фильтрации ограничения, зарегистрированный под числовым идентификатором ALG_* . Каждый распространитель представляет собой три небольшие функции:

• compute_domains_* — фактическая фильтрация, возвращающая несоответствие, согласованность или следование;
• get_triggers_* — какие доменные события должны повторно активировать распространитель;
• get_complexity_* — оценка стоимости, используемая для упорядочивания очереди распространения.

В алгоритме BacktrackSolver процесс распространения ошибки до неподвижной точки чередуется с решением о ветвлении, выбираемым на основе эвристики переменных (какую неограниченную переменную использовать для ветвления) и эвристики предметной области (какое значение попробовать). В алгоритме MultiprocessingSolver несколько поисков с возвратом распределяются по части пространства поиска.

Быстродействие, несмотря на использование Python, обеспечивается тем, что практически каждая «горячая» функция помечена аннотацией @njit(cache=True, fastmath=True) . Numba компилирует их в нативный код при первом использовании и кэширует результат на диске, поэтому «горячий» процесс выполняет скомпилированный машинный код, а не интерпретируемый байт-код. Домены представляют собой обычные массивы NumPy, изменяемые на месте, а распространители обмениваются типизированными массивами NDArray и целыми числами — никогда не объектами Python. Цена — компиляция с холодным стартом (компенсируемая кэшем) и дисциплина кодирования внутри JIT-компилятора: никаких словарей, никаких исключений, никаких isinstance , никаких строк. Выгода двоякая: производительность, подобная C, и дешевое, быстрое моделирование — добавление избыточного ограничения, замена эвристики или написание алгоритма согласованности, специфичного для конкретной задачи, занимает всего несколько строк обычного кода Python. Как мы увидим, именно второе свойство является источником многих преимуществ NuCS.

Наиболее важным проектным решением является то, что область определения всегда представляет собой интервал. Для «дыры» в середине области определения не существует представления, и именно это делает весь механизм выразимым как операции над двумя массивами NumPy — и именно это ограничивает NuCS обеспечением согласованности границ . Мы вернемся к этому в конце; это лейтмотив всех результатов, приведенных ниже.

Шоколад

История

Choco — ветеран мира программирования ограничений. Впервые он появился на рубеже 2000-х годов и пережил несколько полных переработок. Современная версия — Choco 3, затем 4, а теперь 6 — это полностью переработанная библиотека, созданная в основном в IMT Atlantique (исследовательская группа TASC / LS2N в Нанте) Шарлем Прюдомом, Жан-Гийомом Фажем и другими разработчиками. Это библиотека Java с открытым исходным кодом, распространяемая под лицензией BSD, и широко используется как в научных исследованиях, так и в промышленности. Версия, протестированная здесь, — 6.0.1 , текущий релиз.

Архитектура

Choco — это решатель ограничений на основе событий на JVM. Model содержит целочисленные, логические, множественные и вещественные переменные, а также Constraint ; каждое ограничение делегирует фильтрацию одному или нескольким распространителям, управляемым мелкозернистым механизмом событий/распространения. Поверх всего этого находится настраиваемый цикл поиска с большой библиотекой стратегий ветвления, политик перезапуска и — исторически отличительной особенностью — объяснениями (обучение на основе конфликтов).

Главное отличие Choco от NuCS заключается в способе представления доменов : он поддерживает как ограниченные домены (интервалы, как в NuCS), так и перечисляемые домены (битовые наборы), которые могут представлять произвольные подмножества — домены с пробелами. Именно это более богатое представление открывает широту и мощь его глобального каталога ограничений : allDifferent на нескольких уровнях согласованности (включая алгоритм согласованности дуг Регина), ограничения мощности и подсчета, cumulative , circuit , автоматические/регулярные ограничения и многое другое, большинство из которых подкреплено тщательно разработанной, часто согласованной по дугам , фильтрацией.

Зрелый JVM-решатель предоставляет две вещи, недоступные сегодня молодым проектам на Python: JIT-компилятор (HotSpot), настроенный за двадцать лет, и обширную библиотеку надежных глобальных ограничений, которые можно просто добавить в модель и доверять им. Обратная сторона медали заключается в том, что именно эти надежные фильтры делают Choco дорогостоящим: согласованные по дугам глобальные ограничения выполняют большой объем работы на каждом узле, и эта работа не всегда окупается.

Схема сравнения

Несколько важных замечаний, прежде чем читать какие-либо цифры:

• Все измерения времени приведены в миллисекундах и проводились на одном и том же компьютере. Микротесты производительности на разных языках всегда являются приблизительными; в качестве сигнала следует рассматривать соотношения и формы кривых, а не абсолютные значения.
• Замеры времени выполнения NuCS производятся после того, как кэш JIT Numba прогреется — мы не хотим измерять разовые затраты на компиляцию. Даже в прогретом состоянии NuCS несет небольшие фиксированные затраты на запуск в несколько сотен миллисекунд (чтение кэша, прогрев NumPy), которые можно увидеть как нижний предел на самых маленьких экземплярах. Эти затраты оплачиваются один раз за процесс, а не за узел поиска, поэтому они являются шумом для длительного решения и доминирующими для небольшого.
• При каждом запуске NuCS используется каталог кэша и один и тот же шаблон параметров; начальная строка NUMBA_CACHE_DIR=.numba/cache и завершающая --no-display-solutions --no-display-stats --log-level ERROR (которая просто заглушает вывод) опущены в приведенных ниже командных строках для удобства чтения.
• Для каждой задачи показана командная строка NuCS , ограничения и стратегия поиска , диаграмма кривой (чем ниже значение, тем лучше), исходная таблица и краткий анализ. В любом столбце «ускорение» значение больше 1 означает, что NuCS работает быстрее в указанный раз.

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

Группа 1 — одна и та же модель, сравнение двигателей.

В данном случае оба решателя выдают одинаковые ограничения с одинаковым уровнем согласованности и сопоставимой стратегией поиска. Тестируется только сам решатель.

Ряд, охватывающий все интервалы (найдите одно решение)

Задача (CSPLIB #7). Последовательность, состоящая из одних интервалов, представляет собой перестановку целых чисел 0..n-1 , такую что последовательность абсолютных разностей между последовательными членами сама по себе является перестановкой чисел от 1..n-1 — каждый интервал встречается ровно один раз. Название происходит от двенадцатитоновой музыки, где в такой последовательности каждый интервал звучит один раз; комбинаторно это компактная, тесно связанная задача перестановок, в которой акцент делается на allDifferent как по значениям, так и по их разностям. Мы ищем единственное решение.

Оба решателя используют ограниченную согласованность и эвристику первого сбоя (наименьшей области определения) для одной и той же формулировки.

Командная строка NuCS:

 python ‐m nucs.examples.all_interval_series -n 500 --var-heuristic 3 --symmetry-breaking --cp-max-height 10000

Ограничения и стратегия. Для каждого i , распространитель SUM_EQ определяет diff_i = x_{i+1} - x_i , а распространитель ABS_EQ определяет |diff_i| ; два распространителя ALLDIFFERENT обеспечивают, что значения и абсолютные разности представляют собой перестановки; два распространителя LEQ_C нарушают очевидные симметрии обращения/дополнения. --var-heuristic 3 выбирает эвристику с наименьшей переменной в области определения (первая неудача), разветвляясь только на n переменных ряда ( decision_variables ).

 for i in range(n - 1): self.add_propagator(ALG_SUM_EQ, [n + i, i, i + 1]) # diff_i = x_{i+1} - x_i self.add_propagator(ALG_ABS_EQ, [n + i, 2 * n - 1 + i]) # |diff_i| self.add_propagator(ALG_ALLDIFFERENT, range(n)) self.add_propagator(ALG_ALLDIFFERENT, range(2 * n - 1, 3 * n - 2)) if symmetry_breaking: self.add_propagator(ALG_LEQ_C, [0, 1], [-1]) self.add_propagator(ALG_LEQ_C, [3 * n - 3, 2 * n - 1], [-1]) 

Это наиболее показательный график во всем бенчмарке, поскольку отличается только движок — и для первых пяти размеров две кривые совпадают (с точностью до ~3%). Затем при n=16000 они расходятся: Choco работает за 120 с, NuCS — за 85 с, а NuCS в 1,41 раза быстрее . Главный результат — решатель на чистом Python, который не просто соответствует, но и превосходит Choco на идентичной модели: после того, как Numba скомпилирует пропагаторы, векторизованная работа NuCS по каждому узлу становится действительно конкурентоспособной, а на самом большом экземпляре побеждает его меньший постоянный коэффициент.

Лемма Шура (доказать отсутствие решения)

Задача (CSPLIB #15). Лемма Шура спрашивает, можно ли разбить целые числа 1..n на заданное число множеств без сумм — множеств, не содержащих тройку x, y, z где x + y = z (где x и y не обязательно должны быть различными). При наличии трех множеств существует наибольшее n , для которого существует допустимое разбиение (связанное с числом Шура S(3) = 13 ); за пределами этого значения задача становится неразрешимой. Мы используем его здесь как неудовлетворительный пример, который заставляет решателя перебрать все дерево поиска, чтобы доказать, что разбиения не существует — это надежная проверка пропускной способности распространения.

Оба решателя используют согласованность границ, и для сохранения идентичности моделей выполнение происходит без нарушения симметрии .

Командная строка NuCS:

 python ‐m nucs.examples.schur_lemma -n 100 --no-symmetry-breaking

Ограничения и стратегия. Каждому из n чисел присваиваются три переменные принадлежности 0/1; SUM_EQ_C принудительно помещает их ровно в один набор; для каждой допустимой тройки (x, y, z = x+y+1) SUM_LEQ_C запрещает нахождение всех трех в одном наборе (условие отсутствия сумм). При использовании параметра --no-symmetry-breaking ограничение порядка LEXICOGRAPHIC_LEQ снимается, так что модель соответствует модели Choco. Поиск осуществляется с помощью эвристики переменных по умолчанию.

 for x in range(n): self.add_propagator(ALG_SUM_EQ_C, [x * 3, x * 3 + 1, x * 3 + 2], [1]) for k in range(3): for x in range(n): for y in range(n): z = x + y + 1 if 0 <= z < n: self.add_propagator(ALG_SUM_LEQ_C, [3 * x + k, 3 * y + k, 3 * z + k], [2]) 

При самом малом размере Choco действительно быстрее — примерно в 2 раза. Но обратите внимание, как разрыв монотонно сокращается по мере роста дерева: 0,47× → 0,61× → 0,67× → 0,87× → 1,22× . Этот уменьшающийся дефицит — это примерно постоянные накладные расходы NuCS на каждый процесс, которые амортизируются за счет растущего абсолютного времени выполнения; к n=1600 он не просто исчезает, а обращается вспять — NuCS доказывает невыполнимость за 14,6 с против 17,9 с у Choco. NuCS здесь платит за подготовку, а не за алгоритм, и как только поиск становится достаточно большим, его более дешевое распространение на узел оказывается выгоднее.

Вывод для группы 1. При фиксированной модели NuCS и Choco работают практически с одинаковой асимптотической скоростью, а при самых больших размерах NuCS немного опережает Choco в решении обеих задач. Единственный видимый недостаток — это небольшая, постоянная стоимость запуска NuCS, которая преобладает для крошечных экземпляров и не имеет значения для больших. Для решателя на чистом Python, работающего с JVM двадцатилетней давности, это замечательный результат.

Группа 2 — различные модели, сравнение стратегий.

В этих трех задачах два решателя используют разные алгоритмы, поэтому мы сравниваем не только движки, но и стратегии моделирования. Choco использует жесткие, согласованные по дугам глобальные ограничения или перечисляемые области; NuCS же использует дешевую согласованность границ плюс избыточные ограничения, каналирование или фильтр, написанный вручную. Результаты неоднозначны — и это, честно говоря, самое интересное.

Латинский квадрат (найдите одно решение)

Проблема. Латинский квадрат порядка n — это сетка n×n заполненная n символами, так что каждый символ встречается ровно один раз в каждой строке и ровно один раз в каждом столбце — иными словами, каждая строка и каждый столбец представляют собой перестановку от 0..n-1 . Это абстрактная структура, лежащая в основе судоку (в котором добавляются ограничения в виде ячеек) и многих комбинаторных конструкций. Латинские квадраты существуют для каждого n , поэтому найти один из них в принципе легко; здесь нас интересует, насколько хорошо распространение модели ограничений масштабируется по мере роста n . Мы ищем единственное решение.

Простая модель, используемая обоими решателями, выдает согласованное по границам allDifferent для каждой строки и каждого столбца.

Командная строка NuCS:

 # plain bound-consistent model python -m nucs.examples.latin_square  -n 20 --cp-max-height 10000 # redundant (row/column) model python -m nucs.examples.latin_square  -n 20 --model-rc --cp-max-height 10000

Ограничения и стратегия. Простая модель представляет собой всего лишь 2n ALLDIFFERENT распространителей (по одному на строку, по одному на столбец) по n² переменным ячеек, с ветвлением по умолчанию, когда первый не создан экземпляр:

 for i in range(self.n): self.add_propagator(ALG_ALLDIFFERENT, self.row(i)) self.add_propagator(ALG_ALLDIFFERENT, self.column(i))

Избыточная модель ( --model-rc , class LatinSquareRCProblem ) добавляет два дополнительных представления одной и той же сетки — одно индексируется по (цвет, столбец) → строка, другое — по (строка, цвет) → столбец — каждое со своими собственными значениями ALLDIFFERENT для строк/столбцов, и связывает три представления с помощью ограничений канального соединения ( PERMUTATION_AUX ), так что обрезка, обнаруженная в одном представлении, немедленно распространяется на другие:

 # row[c,j]=i <=> color[i,j]=c self.add_propagator(ALG_PERMUTATION_AUX, [*self.column(j), *self.column(j, M_ROW)]) # row[c,j]=i <=> column[i,c]=j self.add_propagator(ALG_PERMUTATION_AUX, [*self.row(c, M_ROW), *self.column(c, M_COLUMN)]) # color[i,j]=c <=> column[i,c]=j self.add_propagator(ALG_PERMUTATION_AUX, [*self.row(i), *self.row(i, M_COLUMN)]) 

Здесь следует обратить внимание на два момента. Во-первых, на той же простой модели BC Choco быстрее, чем NuCS, на небольших решаемых задачах — знакомый разрыв в постоянных накладных расходах: NuCS находится на своем минимуме примерно в 376 мс, в то время как Choco начинает работу примерно со 105 мс. Во-вторых, и это более важно: обе простые модели BC резко падают на 50-м порядке и не могут завершиться. Простая формулировка просто недостаточно отсеивает лишнее, и это алгоритмический барьер, а не барьер движка — Choco тоже на него натыкается.

Избыточная модель NuCS проходит мимо этого барьера. Ее кривая почти пологая (412 → 728 мс при увеличении порядка с 20 до 50), потому что канальные представления настолько сильно сокращают область поиска, что она практически не расширяется. Победа здесь заключается не в аккуратном коэффициенте ускорения, а в качественном — NuCS решает задачу, которая не поддается решению ни одним из простых решателей BC. И это стало возможным не благодаря движку, а благодаря простоте его модификации: пара дополнительных циклов распространения в обычном Python.

Волшебная последовательность (найдите одно решение)

Задача (CSPLIB #19). Магическая последовательность длины n — это самоописывающая последовательность x_0, …, x_{n-1} неотрицательных целых чисел, в которой каждое x_i точно подсчитывает, сколько раз значение i встречается во всей последовательности. Особенность заключается в том, что каждая переменная как вносит вклад в подсчеты, так и зависит от них, что делает эту задачу классической проверкой ограничений подсчета и мощности множества. Мы ищем единственное решение.

Естественная модель Choco использует строгое глобальное ограничение, согласованное с дугами . NuCS использует только простые ограничения count , а также избыточные линейные ограничения.

Командная строка NuCS:

 # count + one redundant linear constraint python -m nucs.examples.magic_sequence  -n 100 --var-heuristic 3 --model-r1 # adds a second, weighted-sum redundant constraint python -m nucs.examples.magic_sequence  -n 100 --var-heuristic 3 --model-r1 --model-r2

Ограничения и стратегия. Для каждого i , распространитель COUNT_EQ связывает x_i с количеством ячеек, равных i . Первое избыточное ограничение ( --model-r1 , SUM_EQ_C ) гласит, что сумма значений должна равняться n ; второе ( --model-r2 , AFFINE_EQ ) представляет собой взвешенную сумму тождества Σ i·x_i = n . В обоих запусках используется эвристика наименьшей области определения (первая неудача) с помощью --var-heuristic 3 .

 for i in range(n): self.add_propagator(ALG_COUNT_EQ, list(range(n)) + [i], [i]) if model_r1: self.add_propagator(ALG_SUM_EQ_C, range(n), [n]) # redundant: values sum to n if model_r2: self.add_propagator(ALG_AFFINE_EQ, range(n), range(n + 1)) # redundant: weighted-sum identity 

Это наиболее драматичный переход в этом наборе данных. Фильтрация Choco с согласованностью дуг отлично работает на небольших примерах: при n=100 она примерно в 2,5 раза быстрее, чем лучшая модель NuCS. Но её кривая поднимается гораздо быстрее — Choco увеличивается примерно в 12 раз от n=100 до n=400 (149 → 1783 мс), в то время как модель NuCS с двумя избыточными элементами увеличивается всего примерно в 2,4 раза (387 → 942 мс). Линии пересекаются около n=250 , и к n=400 NuCS становится в 1,89 раза быстрее — 942 мс против 1783 мс у Choco. Второе избыточное ограничение играет решающую роль: сравнивая оранжевую и зеленую кривые, добавление Σ i·x_i = n сокращает время для n=400 с 2913 мс до 942 мс. Суть не в том, что «AC — это расточительство» — очевидно, что он окупается на небольших экземплярах — а в том, что «дешевый BC в сочетании с правильной парой избыточных ограничений имеет гораздо более стабильную стоимость на узел и значительно превосходит его по мере роста экземпляра».

Линейка Голомба (минимизировать)

Задача (CSPLIB #6). Линейка Голомба — это набор из n целочисленных меток, расположенных на линейке таким образом, что все n(n-1)/2 попарных расстояний между метками различны. Оптимальная линейка Голомба — это линейка с минимальной общей длиной для заданного числа меток. Это обманчиво небольшая задача оптимизации, которая становится очень сложной по мере роста числа меток, и является основным эталоном как для оценки эффективности обрезки, так и для оценки выгоды от представления отверстий в доменах. Мы минимизируем длину.

Golomb представляет собой наиболее интересное сравнение, поскольку он в наибольшей степени опирается на представление домена: найти n меток 0 = m_0 < m_1 < … < m_{n-1} попарные расстояния между которыми различны, минимизируя m_{n-1} . В примере Choco используются перечисляемые домены — фактически, более сильная согласованность — что позволяет отсеивать значения в середине интервалов расстояний. Обычная согласованность границ NuCS этого сделать не может, и это заметно. Поэтому NuCS предлагает алгоритм согласованности, специфичный для данной задачи : несколько десятков строк скомпилированного Python ( golomb_consistency_algorithm ), которые предварительно отсеивают переменные расстояний с помощью аргумента минимальной суммы различных целых чисел перед запуском стандартной согласованности границ.

Командная строка NuCS:

 # plain bound consistency (--consistency-algorithm 0 forces BC) python -m nucs.examples.golomb  -n 9 --symmetry-breaking --consistency-algorithm 0 # custom Golomb consistency algorithm (the example's default) python -m nucs.examples.golomb  -n 9 --symmetry-breaking

Ограничения и стратегия. Переменные расстояния dist_ij связаны условием SUM_EQ ( dist_ij = m_j − m_i ), единственное ALLDIFFERENT гарантирует, что все расстояния являются различными, избыточные границы LEQ_C связывают каждое расстояние с длиной линейки, а условие LEQ_C нарушает зеркальную симметрию. Целевая функция m_{n-1} минимизируется с помощью solver.minimize(...) . Пользовательский вариант заменяет простой алгоритм согласованности границ на golomb_consistency_algorithm , который ужесточает нижние границы расстояний перед делегированием алгоритму bound_consistency_algorithm ; --consistency-algorithm 0 возвращает к простому алгоритму согласованности границ для сравнения.

 for i in range(1, mark_nb - 1): for j in range(i + 1, mark_nb): self.add_propagator(ALG_SUM_EQ, [index(mark_nb, 0, i), index(mark_nb, i, j), index(mark_nb, 0, j)]) self.add_propagator(ALG_ALLDIFFERENT, range(self.domain_nb)) # redundant length bounds + symmetry breaking omitted for brevity 

Обычный NuCS BC (оранжевый) примерно в 2 раза медленнее, чем Choco, по всем параметрам — именно такое снижение производительности и следовало ожидать, когда противник может отсечь слабые места, которые вам недоступны. Но вариант с пользовательской согласованностью (зеленый) почти идеально сокращает разрыв: при 11 метках — 6791 мс против 6800 мс у Choco; при 12 метках — 67319 мс против 65705 мс — разница составляет около 2%. NuCS не требует перечисленных доменов для восстановления недостающей отсечки; ему нужен специальный распространитель , который кодирует ту же логику. Цена — это усилия разработчиков, а не возможности решателя.

Что говорят цифры

• При одинаковых моделях и одинаковой скорости NuCS немного опережает Choco. Когда оба решателя используют один и тот же алгоритм, NuCS сравняется с Choco в средних размерах и побеждает в самых больших примерах обеих задач (интервальные ряды и лемма Шура). Единственное видимое различие — это небольшие, постоянные накладные расходы NuCS при запуске, которые исчезают по мере роста объема поиска.
• Более строгая согласованность часто окупается, но её стоимость на узел растёт. В алгоритме Magic Sequence глобальное ограничение с согласованностью по дугам в Choco работает быстрее на небольших экземплярах, однако облегчённый алгоритм BC в NuCS с двумя избыточными ограничениями имеет гораздо более пологий наклон и почти в 2 раза быстрее при n=400.
• Свобода моделирования может повлиять на осуществимость, а не только на скорость. На латинском квадрате простая модель BC блокируется на 50-м порядке для обоих решателей; модель избыточного каналирования NuCS решает её за 728 мс — потому что перепроектирование в Python обходится дёшево.
• Иногда AC действительно играет решающую роль. В алгоритме Голомба перечисленные домены обеспечивают обрезку Choco, которую обычный BC просто не может воспроизвести, — и NuCS догоняет его только благодаря написанию собственного распространителя.

Первопричина: домены и согласованность.

Если отвлечься от отдельных проблем, то одно проектное решение объяснит всю картину целиком.

NuCS представляет каждую переменную в виде единого интервала min..max . Область значений — это два целых числа; привязка переменной означает, что min == max . Это компактно, удобно для кэширования и легко векторизуется с помощью NumPy — именно это позволяет Numba создавать такие быстрые распространители. Но у этого есть существенное последствие: NuCS может только сужать границы области значений. Он не может проделать отверстие посередине. Поэтому самая сильная фильтрация, которую он может выразить, — это согласованность границ (BC) — она гарантирует поддержку конечных точек каждой области значений, и ничего больше.

Choco представляет домены с «дырами» (битовые наборы/перечисляемые представления наряду с ограниченными). Он может удалить произвольное значение из середины домена. Именно это делает возможной согласованность дуг (AC) : алгоритм фильтрации может удалить каждое неподдерживаемое значение, а не только обрезать крайние значения. Каталог Choco опирается на это — allDifferent (AC), согласованность дуг по мощности и ограничения подсчета, распространение через перечисляемый домен — и именно эти ограничения лежат в основе результатов, полученных с помощью алгоритмов magic sequence и Golomb, описанных выше.

Таким образом, эти два решателя занимают совершенно разные точки в пространстве проектирования:

И вот в чем заключается нюанс, который показывают результаты тестов. «Более слабая» согласованность NuCS редко оказывается тем недостатком, каким кажется на бумаге. Поскольку распространители BC настолько дешевы, а перепроектирование в Python настолько просто, продуктивным шагом в NuCS является восстановление недостающей обрезки с помощью избыточных ограничений, каналирования или пользовательского фильтра, а не с помощью дорогостоящего алгоритма AC. На магической последовательности эта более низкая стоимость на узел позволяет BC уверенно пройти глобальное ограничение Choco, согласованное с дугами, когда экземпляр задачи становится большим; на латинском квадрате это разница между решением задачи 50-го порядка и ее нерешением вообще; и даже на идентичных моделях Группы 1 именно более низкий постоянный коэффициент выводит NuCS вперед в верхнем диапазоне.

Обратная сторона медали не менее реальна. Когда в задаче действительно необходимо удалить значения из середины доменов, согласованные по дугам глобальные переменные Choco и перечисляемые домены — это подходящий инструмент «из коробки»: быстрый в небольших случаях с магическими последовательностями и опережающий Golomb до тех пор, пока NuCS не ответит написанным вручную кодом. Choco дает вам это преимущество бесплатно; NuCS заставляет вас его создавать, но позволяет создать его всего за несколько строк кода.

Заключение

Интерпретировать результаты теста как «какой решатель быстрее» — значит упускать суть. Измеряются две разные вещи:

1. Одна и та же модель, сравнение движков (все интервальные ряды, лемма Шура). В среднем диапазоне они практически равны, разница лишь в небольшой постоянной стоимости запуска NuCS — и на самом большом экземпляре каждой задачи NuCS вырывается вперед (в 1,41 раза на всех интервалах при n=16000, в 1,22 раза на лемме Шура при n=1600). Самым приятным сюрпризом является то, что решатель на чистом Python работает с минимальным отрывом от зрелого, двадцатилетнего решателя на JVM, а затем обгоняет его в масштабе. Numba не просто компенсирует штраф за Python; результирующая стоимость на узел действительно низкая.
2. Различные модели, сравнение стратегий (магическая последовательность, линейка Голомба, латинский квадрат). Здесь речь идёт о настоящем обмене. Последовательность дуг Choco быстрая и решающая в некоторых случаях (небольшие магические последовательности, Голомб); дешёвый BC плюс избыточные ограничения NuCS имеет более пологую кривую затрат и значительно выигрывает в масштабе в других случаях (большие магические последовательности, ~1,9×), восстанавливает паритет там, где AC лидировал (Голомб, с пользовательским пропагатором), и — благодаря низкой стоимости перестройки — решает латинский квадрат, который не может решить ни одна из моделей с простым BC.

В основе обоих наблюдений лежит один архитектурный факт. NuCS хранит области определения как интервалы min..max и, следовательно, ограничен согласованностью границ; Choco хранит области определения с «дырами» и может обеспечивать согласованность дуг. В этом и заключается честное и устойчивое различие между двумя решателями. Именно поэтому Choco предоставляет жесткие глобальные ограничения AC, которые NuCS не может воспроизвести напрямую, и именно поэтому стиль NuCS, сочетающий дешевые ограничения BC и избыточные ограничения, может конкурировать — и все чаще побеждать — при наличии хорошей избыточной модели. Ни один из подходов не является доминирующим; это разные варианты.

Для тех, кто хочет воспользоваться широким спектром проверенных в боевых условиях глобальных ограничений с согласованностью по дугам, развитой инфраструктурой поиска и подробными объяснениями, Choco остается эталоном. Для тех, кто хочет экспериментировать с моделями на Python и при этом получать скорость нативного кода , NuCS предлагает убедительный аргумент: язык больше не является узким местом, а свобода изменять модель — добавлять избыточность, каналирование или пользовательский фильтр обратной совместимости всего несколькими строками — часто имеет такое же значение, как и скорость работы движка или надежность согласованности.

Несколько полезных ссылок для дальнейшего изучения NuCS:

• Пакет Pip: https://pypi.org/project/NUCS/
• Исходный код: https://github.com/yangeorget/nucs
• Документация: https://nucs.readthedocs.io/en/latest/index.html

Ян Жоржет. Все работы Яна Жоржета.

Источник: towardsdatascience.com