NuCS es un solucionador de restricciones escrito 100% en Python, desarrollado por mí, acelerado por NumPy y Numba. Choco es uno de los solucionadores de restricciones de código abierto de referencia, escrito en Java y desarrollado durante más de dos décadas.
Compararlos parece desigual: un lenguaje interpretado frente a un solucionador JVM muy optimizado con un rico catálogo de restricciones globales coherentes con el arco. La realidad es más interesante. Cuando ambos solucionadores ejecutan el mismo modelo, a todos los efectos prácticos, tienen la misma velocidad, y en los casos más grandes, NuCS realmente toma la delantera, porque una vez que Numba ha compilado los bucles internos, el impuesto de Python desaparece y solo queda el costo por nodo. Cuando los modelos difieren, el resultado es un intercambio genuino en lugar de una derrota: en algunos problemas, la consistencia del arco de Choco es la herramienta rápida y adecuada; en otros, la consistencia encuadernada barata de NuCS más un poco de remodelación gana por completo; y en al menos un problema, la libertad de modelado de NuCS le permite resolver casos que ningún solucionador simple puede.
Este artículo recorre cinco problemas de referencia, brinda la línea de comando NuCS exacta para cada uno, detalla las restricciones y la estrategia de búsqueda, dibuja las curvas de rendimiento y finaliza con la decisión de diseño que explica el panorama completo: NuCS representa dominios como intervalos min..max y, por lo tanto, se limita a la consistencia ligada, mientras que Choco también puede representar dominios con agujeros y ejecutar consistencia de arco completo.
Todo el código NuCS que se muestra aquí se encuentra en el repositorio de NuCS bajo la licencia MIT.
nucs
Historia
NuCS es un proyecto que comencé recientemente. Su primera fecha de lanzamiento público es de 2024 y se ha repetido muy rápidamente desde entonces: la versión comparada aquí es 11.2.0. Se construyó en torno a una apuesta deliberadamente inusual: escribir un solucionador de restricciones de dominio finito competitivo completamente en Python y recuperar el rendimiento que normalmente se pierde debido a la interpretación a través de una compilación justo a tiempo en lugar de un núcleo C o C++. Se distribuye en PyPI (pip install nucs), lo que mantiene la instalación tan simple como cualquier otro paquete de Python: sin cadena de herramientas nativa, sin JVM.
Arquitectura
Un problema lleva una matriz NumPy de dominios variables (un par (mínimo, máximo) por variable, una variable vinculada cuando min == max) junto con una lista de propagadores. Un propagador es un algoritmo de filtrado de restricciones, registrado bajo un identificador numérico ALG_*. Cada propagador tiene tres pequeñas funciones:
Compute_domains_*: el filtrado real, la inconsistencia de retorno, la coherencia o la vinculación; get_triggers_* — qué eventos de dominio deberían reactivar el propagador; get_complexity_*: una estimación de costo utilizada para ordenar la cola de propagación.
BacktrackSolver intercala la propagación a un punto fijo con una decisión de bifurcación, elegida mediante una heurística de variable (qué variable independiente se bifurcará) y una heurística de dominio (qué valor probar). Un MultiprocessingSolver impulsa varias búsquedas de retroceso en una división del espacio de búsqueda.
Lo que hace que esto sea rápido a pesar de ser Python es que esencialmente todas las funciones activas están decoradas con @njit(cache=True, fastmath=True). Numba los compila en código nativo en el primer uso y almacena en caché el resultado en el disco, por lo que un proceso en caliente ejecuta código de máquina compilado, no código de bytes interpretado. Los dominios son matrices NumPy simples mutadas en su lugar, y los propagadores intercambian NDArrays escritos y números enteros, nunca objetos Python. El precio es una compilación de inicio en frío (mitigada por el caché) y una disciplina de codificación dentro del código Jitted: sin diccionarios, sin excepciones, sin isinstance, sin cadenas. La recompensa es doble: un rendimiento similar al de C y un modelado rápido y económico: agregar una restricción redundante, intercambiar una heurística o escribir un algoritmo de coherencia para un problema específico son solo un puñado de líneas de Python común y corriente. Como veremos, esa segunda propiedad es de donde provienen varias de las victorias de NuCS.
La elección de diseño más importante es que un dominio sea siempre un intervalo. No hay representación para un agujero en el medio de un dominio, que es exactamente lo que hace que todo el motor sea expresable como operaciones en dos matrices NumPy y lo que limita a NuCS a una coherencia limitada. Volveremos sobre esto al final; es el hilo que recorre cada resultado a continuación.
Chocó
Historia
Choco es un veterano del mundo de la programación de restricciones. Apareció por primera vez a principios de la década de 2000 y ha pasado por varias reescrituras completas. El linaje moderno (Choco 3, luego 4 y ahora 6) es un rediseño desde cero desarrollado en gran medida en IMT Atlantique (el grupo de investigación TASC/LS2N en Nantes) por Charles Prud'homme, Jean-Guillaume Fages y colaboradores. Es una biblioteca Java de código abierto, distribuida bajo una licencia BSD, y se utiliza ampliamente tanto en la investigación como en la industria. La versión comparada aquí es 6.0.1, una versión actual.
Arquitectura
Choco es un solucionador de restricciones basado en eventos en JVM. Un modelo contiene variables enteras, booleanas, establecidas y reales junto con restricciones; cada restricción delega el filtrado a uno o más propagadores controlados por un motor de propagación/eventos detallado. En la parte superior se encuentra un bucle de búsqueda configurable con una gran biblioteca de estrategias de ramificación, políticas de reinicio y, históricamente una característica distintiva, explicaciones (aprendizaje basado en conflictos).
Donde Choco se diferencia fundamentalmente de NuCS es en la representación de su dominio: admite dominios acotados (intervalos, como NuCS) y dominios enumerados (conjuntos de bits), que pueden representar subconjuntos arbitrarios: dominios con agujeros. Esa representación más rica es lo que desbloquea la amplitud y la fuerza de su catálogo de restricciones globales: todas diferentes en varios niveles de consistencia (incluido el algoritmo de consistencia de arco de Régin), restricciones de cardinalidad y conteo, restricciones acumulativas, de circuito, de autómata/regulares, y muchas más, la mayoría respaldadas por un filtrado cuidadosamente diseñado, a menudo consistente en arco.
Un solucionador JVM maduro aporta dos cosas que un proyecto joven de Python no puede igualar hoy en día: un JIT (HotSpot) ajustado durante veinte años y una biblioteca profunda de fuertes restricciones globales que puede incluir en un modelo y en la que puede confiar. La otra cara es que esos filtros fuertes también son donde Choco puede volverse costoso: las restricciones globales consistentes con el arco hacen mucho trabajo por nodo, y ese trabajo no siempre se amortiza por sí solo.
La configuración de comparación
Algunas advertencias honestas antes de leer cualquier número:
Todos los tiempos están en milisegundos y se miden en la misma máquina. Los micropuntos de referencia entre idiomas son siempre aproximados; Trate las proporciones y las formas de las curvas, no los valores absolutos, como la señal. Los tiempos de NuCS se toman después de que la caché Numba JIT se calienta; el costo único de compilación no es lo que queremos medir. Incluso en caliente, NuCS paga un pequeño costo de inicio fijo de unos pocos cientos de milisegundos (lectura del caché, calentamiento de NumPy) que puede verse como un piso en las instancias más pequeñas. Se paga una vez por proceso, no por nodo de búsqueda, por lo que es ruidoso para una resolución larga y dominante para una solución pequeña. Cada ejecución de NuCS utiliza el directorio de caché y el mismo patrón de opciones; el NUMBA_CACHE_DIR=.numba/cache inicial y el ERROR final –no-display-solutions –no-display-stats –log-level ERROR (que simplemente silencia la salida) se omiten de las líneas de comando siguientes para facilitar la lectura. Cada problema muestra la línea de comando NuCS, las restricciones y la estrategia de búsqueda, un diagrama de curva (cuanto más bajo, mejor), la tabla sin formato y un breve análisis. En cualquier columna de "aceleración", un valor mayor que 1 significa que NuCS es más rápido en ese factor.
Los cinco problemas se dividen naturalmente en dos grupos: aquellos en los que ambos solucionadores ejecutan esencialmente el mismo modelo (por lo que estamos comparando motores) y aquellos en los que los modelos difieren (por lo que estamos comparando estrategias de modelado tanto como motores).
Grupo 1: mismo modelo, comparando motores
Aquí ambos solucionadores publican las mismas restricciones con el mismo nivel de coherencia y una estrategia de búsqueda comparable. Lo único que se está probando es el motor.
Series de intervalos (encontrar una solución)
El problema (CSPLIB #7). Una serie de todos los intervalos es una permutación de los números enteros 0..n-1 de modo que la secuencia de diferencias absolutas entre términos consecutivos es en sí misma una permutación de 1..n-1: cada intervalo aparece exactamente una vez. El nombre proviene de la música dodecafónica, donde dicha serie suena una vez en cada intervalo; combinatoriamente es un problema de permutación compacto y estrechamente acoplado que enfatiza un todoDiferente tanto sobre los valores como sobre sus diferencias. Buscamos una única solución.
Ambos solucionadores utilizan consistencia limitada y una heurística de primer error (dominio más pequeño) en la misma formulación.
Línea de comando NuCS:
python ‐m nucs.examples.all_interval_series -n 500 –var-heuristic 3 –symmetry-breaking –cp-max-height 10000
Restricciones y estrategia. Para cada i, un propagador SUM_EQ define diff_i = x_{i+1} – x_i y un propagador ABS_EQ define |diff_i|; dos ALLDIFFERENTs imponen que los valores y las diferencias absolutas sean cada uno una permutación; dos propagadores LEQ_C rompen las obvias simetrías de inversión/complemento. –var-heuristic 3 selecciona la heurística de variable de dominio más pequeño (primer error), ramificándose solo en las n variables de la serie (variables_decisión).
para i en el rango(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)) si simetría_breaking: self.add_propagator(ALG_LEQ_C, [0, 1], [-1]) self.add_propagator(ALG_LEQ_C, [3 * n – 3, 2 * n – 1], [-1])
Este es el gráfico más revelador de todo el benchmark porque nada difiere excepto el motor, y para los primeros cinco tamaños las dos curvas se ubican una encima de la otra (dentro de ~3%). Luego, en n=16000 se separan: Choco tarda 120 s, NuCS 85 s; NuCS es 1,41 veces más rápido. El resultado principal es un solucionador de Python puro que no solo iguala sino que vence a Choco en un modelo idéntico: una vez que Numba ha compilado los propagadores, el trabajo vectorizado por nodo de NuCS es genuinamente competitivo y, en el caso más grande, gana su factor constante más bajo.
Lema de Schur (no demostrar solución)
El problema (CSPLIB #15). El lema de Schur pregunta si los números enteros 1..n se pueden dividir en un número dado de conjuntos sin suma: conjuntos que no contienen triples x, y, z con x + y = z (donde x e y no necesitan ser distintos). Con tres conjuntos hay un n más grande para el cual existe una partición válida (vinculada al número de Schur S(3) = 13); más allá de esto el problema es inviable. Lo usamos aquí como una instancia insatisfactoria, que obliga al solucionador a agotar todo el árbol de búsqueda para demostrar que no existe ninguna partición: una prueba limpia del rendimiento de propagación sin procesar.
Ambos solucionadores utilizan consistencia limitada y, para mantener los modelos idénticos, la ejecución se realiza sin romper la simetría.
Línea de comando NuCS:
python ‐m nucs.examples.schur_lemma -n 100 –no-symmetry-breaking
Restricciones y estrategia. Cada uno de los n números obtiene tres variables de membresía 0/1; un SUM_EQ_C lo fuerza a formar exactamente un conjunto; por cada triplete válido (x, y, z = x+y+1), un SUM_LEQ_C prohíbe que los tres estén en el mismo conjunto (la condición sin suma). Con –no-symmetry-breaking la restricción de orden LEXICOGRAPHIC_LEQ se elimina para que el modelo coincida con el de Choco. La heurística de variable predeterminada impulsa la búsqueda.
para x en rango(n): self.add_propagator(ALG_SUM_EQ_C, [x * 3, x * 3 + 1, x * 3 + 2],[1]) para k en el rango(3): para x en el rango(n): para y en el rango(n): z = x + y + 1 si 0 <= z < n: self.add_propagator(ALG_SUM_LEQ_C, [3 * x + k, 3 * y + k, 3 * z + k],[2])
En el tamaño más pequeño, Choco es realmente más rápido: aproximadamente 2 veces. Pero observe cómo la brecha se cierra monótonamente a medida que el árbol crece: 0,47 × → 0,61 × → 0,67 × → 0,87 × → 1,22 ×. Ese déficit cada vez menor es la sobrecarga por proceso aproximadamente constante de NuCS que se amortiza frente a un tiempo de ejecución absoluto creciente; para n=1600 no sólo ha desaparecido, sino que se ha revertido: NuCS demuestra su inviabilidad en 14,6 s frente a los 17,9 s de Choco. NuCS paga un costo de instalación aquí, no algorítmico, y una vez que la búsqueda es lo suficientemente grande, su propagación por nodo más barata sale adelante.
Conclusión para el Grupo 1. Cuando el modelo es fijo, NuCS y Choco se ejecutan esencialmente a la misma velocidad asintótica, y en los tamaños más grandes, NuCS se adelanta en ambos problemas. La única desventaja visible es un costo inicial pequeño y constante de NuCS que domina las instancias pequeñas y es irrelevante en las grandes. Para un solucionador de Python puro frente a un motor JVM de dos décadas de antigüedad, ese es un resultado notable.
Grupo 2: diferentes modelos, comparando estrategias
En estos tres problemas, los dos solucionadores no ejecutan el mismo algoritmo, por lo que comparamos tanto estrategias de modelado como motores. Choco busca restricciones globales o dominios enumerados fuertes y consistentes; NuCS busca una coherencia limitada económica además de restricciones redundantes, canalización o un filtro escrito a mano. Los resultados son mixtos, y esa es la parte honesta e interesante.
Cuadrado latino (encuentra una solución)
El problema. Un cuadrado latino de orden n es una cuadrícula de n × n llena de n símbolos, de modo que cada símbolo aparece exactamente una vez en cada fila y exactamente una vez en cada columna; de manera equivalente, cada fila y cada columna es una permutación de 0..n-1. Es la estructura abstracta detrás del Sudoku (que agrega restricciones de cuadro) y subyace a muchos diseños combinatorios. Los cuadrados latinos existen para cada n, por lo que encontrar uno es fácil en principio; el interés aquí es qué tan bien escala la propagación de un modelo de restricción a medida que n crece. Buscamos una única solución.
El modelo sencillo, utilizado por ambos solucionadores, publica un allDifferent coherente con límites por fila y por columna.
Líneas de comando NuCS:
# modelo simple y coherente con límites python -m nucs.examples.latin_square -n 20 –cp-max-height 10000 # modelo redundante (fila/columna) python -m nucs.examples.latin_square -n 20 –model-rc –cp-max-height 10000
Restricciones y estrategia. El modelo simple es solo 2n propagadores TODOS DIFERENTES (uno por fila, uno por columna) sobre las n² variables de celda, con la ramificación predeterminada de primera instancia no instanciada:
para i en rango(self.n): self.add_propagator(ALG_ALLDIFFERENT, self.row(i)) self.add_propagator(ALG_ALLDIFFERENT, self.column(i))
El modelo redundante (–model-rc, clase LatinSquareRCProblem) agrega dos vistas adicionales de la misma cuadrícula, una indexada por (color, columna) → fila, otra por (fila, color) → columna, cada una con sus propias filas/columnas ALLDIFFERENTs y vincula las tres vistas con restricciones de canalización (PERMUTATION_AUX), de modo que la poda encontrada en una vista se propague inmediatamente a las demás:
# fila[c,j]=i <=> color[i,j]=c self.add_propagator(ALG_PERMUTATION_AUX, [*self.column(j), *self.column(j, M_ROW)]) # fila[c,j]=i <=> columna[i,c]=j self.add_propagator(ALG_PERMUTATION_AUX, [*self.row(c, M_ROW), *self.column(c, M_COLUMN)]) # color[i,j]=c <=> columna[i,c]=j self.add_propagator(ALG_PERMUTATION_AUX, [*self.row(i), *self.row(i, M_COLUMN)])
Dos cosas para leer aquí. Primero, en el mismo modelo BC simple, Choco es más rápido que NuCS en las instancias pequeñas con solución: la conocida brecha de sobrecarga constante, con NuCS en su piso de ~376 ms mientras que Choco comienza cerca de 105 ms. En segundo lugar, y más importante: ambos modelos BC simples caen por un precipicio en el orden 50 y no logran terminar. La formulación simple simplemente no poda lo suficiente, y ese es un muro algorítmico, no de motor: Choco también lo golpea.
El modelo redundante NuCS pasa directamente por ese muro. Su curva es casi plana (412 → 728 ms mientras el orden crece de 20 a 50) porque las vistas canalizadas podan tanto que la búsqueda apenas se expande. La victoria aquí no es una buena relación de aceleración; es cualitativo: NuCS resuelve, en mucho menos de un segundo, una instancia que ningún solucionador BC simple puede terminar en absoluto. Y lo que lo hizo posible no es el motor sino la facilidad de remodelación: un par de bucles propagadores adicionales en Python normal./h
Secuencia mágica (encuentra una solución)
El problema (CSPLIB #19). Una secuencia mágica de longitud n es una secuencia autodescriptiva x_0,…, x_{n-1} de enteros no negativos en la que cada x_i cuenta exactamente cuántas veces aparece el valor i en toda la secuencia. El giro es que cada variable contribuye y depende de los conteos, lo que hace que esta sea una prueba de estrés clásica de restricciones de cardinalidad y conteo. Buscamos una única solución.
El modelo natural de Chocó utiliza una fuerte restricción global consistente en arco. NuCS utiliza sólo restricciones de recuento simples más restricciones lineales redundantes.
Líneas de comando NuCS:
# recuento + una restricción lineal redundante python -m nucs.examples.magic_sequence -n 100 –var-heuristic 3 –model-r1 # agrega una segunda restricción redundante de suma ponderada python -m nucs.examples.magic_sequence -n 100 –var-heuristic 3 –model-r1 –model-r2
Restricciones y estrategia. Para cada i, un propagador COUNT_EQ vincula x_i al número de celdas igual a i. La primera restricción redundante (–model-r1, a SUM_EQ_C) establece que los valores deben sumar n; el segundo (–model-r2, un AFFINE_EQ) es una identidad de suma ponderada Σ i·x_i = n. Ambas ejecuciones utilizan la heurística de dominio más pequeño (primer error) mediante –var-heuristic 3.
para i en rango(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]) # redundante: los valores suman n si model_r2: self.add_propagator(ALG_AFFINE_EQ, range(n), range(n + 1)) # redundante: identidad de suma ponderada
Este es el cruce más dramático del set. El filtrado consistente en arco de Choco es excelente en instancias pequeñas: en n=100 es ~2,5 veces más rápido que el mejor modelo NuCS. Pero su curva sube mucho más rápido: Choco crece ~12× de n=100 a n=400 (149 → 1783 ms), mientras que el modelo NuCS de dos redundancias crece sólo ~2,4× (387 → 942 ms). Las líneas se cruzan alrededor de n=250, y en n=400 NuCS es 1,89 veces más rápido: 942 ms frente a los 1783 ms de Choco. La segunda restricción redundante es qué lo hace: comparando las curvas naranja y verde, sumando Σ i·x_i = n se corta el tiempo n=400 de 2913 ms a 942 ms. La lectura no es "AC es un desperdicio" – claramente vale la pena en instancias pequeñas – sino "BC barato más el par correcto de restricciones redundantes tiene un costo por nodo mucho más plano y supera decisivamente a medida que crece la instancia".
Gobernante Golomb (minimizar)
El problema (CSPLIB #6). Una regla Golomb es un conjunto de n marcas enteras colocadas en una regla de modo que todas las n (n-1)/2 distancias por pares entre marcas sean distintas. Una regla Golomb óptima es aquella que tiene una longitud total mínima para un número determinado de marcas. Es un problema de optimización engañosamente pequeño que se vuelve muy difícil a medida que crece el número de marcas, y un punto de referencia básico tanto para la fuerza de poda como para la rentabilidad de representar agujeros en dominios. Minimizamos la longitud.
Golomb es la comparación más interesante porque se apoya más en la representación del dominio: encuentre n marcas 0 = m_0 < m_1 <… < m_{n-1} cuyas distancias por pares sean todas diferentes, minimizando m_{n-1}. La muestra de Choco utiliza dominios enumerados (consistencia efectivamente más fuerte) lo que le permite podar valores en el medio de los intervalos de distancia. La coherencia simple vinculada a NuCS no puede hacer eso, y se nota. Por lo tanto, NuCS ofrece un algoritmo de consistencia específico del problema: unas pocas docenas de líneas de Python alterado (golomb_consistency_algorithm) que podan previamente las variables de distancia con un argumento de suma mínima de enteros distintos antes de ejecutar la consistencia ligada estándar.
Líneas de comando NuCS:
# consistencia simple (–consistency-algorithm 0 fuerza BC) python -m nucs.examples.golomb -n 9 –symmetry-breaking –consistency-algorithm 0 # algoritmo de consistencia personalizado de Golomb (el valor predeterminado del ejemplo) python -m nucs.examples.golomb -n 9 –symmetry-breaking
Restricciones y estrategia. Las variables de distancia dist_ij están vinculadas por SUM_EQ (dist_ij = m_j − m_i), un único ALLDIFFERENT impone todas las distancias distintas, los límites LEQ_C redundantes relacionan cada distancia con la longitud de la regla, y un LEQ_C rompe la simetría especular. El objetivo m_{n-1} se minimiza con solver.minimize(…). La variante personalizada intercambia el algoritmo de consistencia límite simple por golomb_consistency_algorithm, que ajusta los límites inferiores de distancia antes de delegar abound_consistency_algorithm; –consistency-algorithm 0 anula el retorno al BC simple para la comparación.
para i en rango(1, mark_nb – 1): para j en rango(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)) # límites de longitud redundantes + ruptura de simetría omitida por brevedad
Plain NuCS BC (naranja) es aproximadamente 2 veces más lento que Choco en todos los ámbitos: exactamente la penalización que esperarías cuando el oponente puede hacer agujeros que tú no puedes. Pero la variante de consistencia personalizada (verde) cierra la brecha casi a la perfección: con 11 puntos, 6791 ms frente a los 6800 ms de Choco; con 12 puntos, 67319 ms frente a 65705 ms, dentro de ~2%. NuCS no necesita dominios enumerados para recuperar la poda faltante; necesita un propagador dedicado que codifique la misma lógica. El costo es el esfuerzo del desarrollador, no la capacidad del solucionador.
Lo que dicen los números
Modelos iguales, velocidad igual: entonces NuCS avanza. Cuando ambos solucionadores ejecutan el mismo algoritmo, NuCS iguala a Choco en los tamaños medios y gana en las instancias más grandes de ambos problemas (series de todos los intervalos y lema de Schur). La única brecha visible es una pequeña y constante sobrecarga de inicio de NuCS que desaparece a medida que crece la búsqueda. Una mayor consistencia a menudo vale la pena, pero su costo por nodo aumenta. En la secuencia mágica, la restricción global consistente en arco de Choco es más rápida en instancias pequeñas, sin embargo, el BC liviano de NuCS más dos restricciones redundantes tiene una pendiente mucho más plana y es casi 2 veces más rápido en n=400. La libertad de modelado puede cambiar la viabilidad, no sólo la velocidad. En el cuadrado latino, el modelo BC simple tiene un orden 50 para ambos solucionadores; El modelo de canalización redundante de NuCS lo resuelve en 728 ms, porque la remodelación en Python es barata. A veces la CA es realmente decisiva. En el gobernante Golomb, los dominios enumerados le dan a Choco una poda que BC simple simplemente no puede reproducir, y NuCS solo se pone al día escribiendo un propagador personalizado.
La causa raíz: dominios y coherencia
Si nos alejamos de los problemas individuales, una decisión de diseño explica el panorama completo.
NuCS representa cada dominio variable como un único intervalo mínimo..máximo. Un dominio son dos números enteros; vincular una variable significa min == max. Esto es compacto, compatible con caché y trivialmente vectorizable con NumPy, que es precisamente lo que permite a Numba hacer que los propagadores sean tan rápidos. Pero tiene una dura consecuencia: NuCS sólo puede reducir los límites de un dominio. No puede perforar un agujero en el medio. Por lo tanto, el filtrado más potente que puede expresar es la coherencia vinculada (BC): garantiza que los puntos finales de cada dominio sean compatibles, nada más.
Choco representa dominios con agujeros (representaciones enumeradas / de conjunto de bits junto con las acotadas). Puede eliminar un valor arbitrario de la mitad de un dominio. Eso es lo que hace posible la consistencia del arco (AC): un algoritmo de filtrado puede eliminar todos los valores no admitidos, no solo recortar los extremos. El catálogo de Choco se apoya en esto: todo diferente (AC), cardinalidad consistente en arco y restricciones de conteo, propagación de dominio enumerado, y estas son exactamente las restricciones detrás de sus resultados en la secuencia mágica y Golomb arriba.
Entonces los dos solucionadores ocupan puntos genuinamente diferentes en el espacio de diseño:
Y aquí está el matiz que revelan los puntos de referencia. La consistencia "más débil" de NuCS rara vez es la desventaja que parece en el papel. Debido a que los propagadores BC son tan baratos, y debido a que la remodelación en Python es tan fácil, el movimiento productivo en NuCS es recuperar la poda faltante con restricciones redundantes, canalización o un filtro personalizado en lugar de con un costoso algoritmo AC. En la secuencia mágica, ese menor costo por nodo permite a BC superar decisivamente la restricción global consistente en arco de Choco una vez que la instancia es grande; en cuadrado latino es la diferencia entre resolver el orden 50 y no resolverlo en absoluto; e incluso en los modelos idénticos del Grupo 1, el factor constante más bajo es lo que sitúa a NuCS por delante en el extremo superior.
La otra cara es igual de real. Cuando un problema realmente necesita valores eliminados del medio de los dominios, los dominios enumerados y globales consistentes en arco de Choco son la herramienta adecuada lista para usar: rápida en instancias pequeñas de secuencia mágica y adelante en Golomb hasta que NuCS responda con código escrito a mano. Choco te da esa fuerza gratis; NuCS te permite construirlo, pero te permite construirlo en unas pocas líneas.
Conclusión
Leer el punto de referencia como "qué solucionador es más rápido" no tiene sentido. Se están midiendo dos cosas diferentes:
Mismo modelo, comparando motores (series de todos los intervalos, lema de Schur). Los dos están esencialmente empatados en el rango medio, separados solo por un pequeño costo constante de inicio de NuCS, y en la instancia más grande de cada problema, NuCS sale adelante (1,41 × en todos los intervalos en n = 16000, 1,22 × en Schur en n = 1600). Que un solucionador de Python puro esté a un paso de un solucionador JVM maduro de dos décadas de antigüedad y luego lo supere a escala es el resultado más agradablemente sorprendente. Numba no sólo cierra la penalización de Python; El costo por nodo resultante es realmente bajo. Diferentes modelos, comparando estrategias (secuencia mágica, regla de Golomb, cuadrado latino). Aquí se trata de un comercio genuino. La consistencia del arco de Choco es rápida y decisiva en algunos casos (pequeñas secuencias mágicas, Golomb); El BC barato más restricciones redundantes de NuCS tiene una curva de costos más plana y gana mucho a escala en otros (secuencias mágicas grandes, ~1.9×), recupera la paridad donde AC lideraba (Golomb, con un propagador personalizado) y, gracias a lo barata que es la remodelación, resuelve un cuadrado latino que ningún modelo de BC simple puede.
Detrás de ambas observaciones se esconde un hecho arquitectónico. NuCS almacena dominios como intervalos min..max y, por lo tanto, está limitado a una coherencia limitada; Choco almacena dominios con agujeros y puede ejecutar consistencia de arco. Ésa es la diferencia honesta y duradera entre los dos solucionadores. Es por eso que Choco impone fuertes restricciones globales de CA que NuCS no puede replicar directamente, y es también por qué el estilo de BC barato más restricciones redundantes de NuCS puede competir –y ganar cada vez más– cuando existe un buen modelo redundante. Ninguno de los dos enfoques domina; Son apuestas diferentes.
Para alguien que quiere la amplitud de Choco de limitaciones globales consistentes y probadas en batalla, infraestructura de búsqueda madura y explicaciones, Choco sigue siendo la referencia. Para alguien que quiera experimentar con modelos en Python y aun así obtener velocidad de código nativo, NuCS presenta un argumento sólido: el lenguaje ya no es el cuello de botella, y la libertad de remodelar el modelo (agregando redundancia, canalización o un filtro BC personalizado en unas pocas líneas) a menudo importa tanto como la velocidad bruta del motor o la fuerza de consistencia bruta.
Algunos enlaces útiles para ir más allá con NuCS: