RegularSearch (2023), su versión paralela y el correo de Jairo Lefebre¶
Fecha: 2026-11-19. Fuentes: papers/RegularSearch.pdf (Lefebre-Lobaina, Ruiz Shulcloper, Information Sciences 649, 2023, 119665, 11 pp.), papers/ParallelRegularSearch.pdf (preprint sin fecha ni sede, 12 pp.; cita a RegularSearch como «under review», así que es de 2023 o antes) y el correo de Jairo Lefebre (pegado por Vladimir el 2026-11-19). Leí los dos PDF completos, salvo las figuras (son imágenes). Lo marcado (inferencia) no lo verifiqué con código.
Convención de nombres: en el repositorio rs es el reverse search de Murakami y Uno. El RegularSearch de Lefebre se llama aquí RegSearch (y P-RegSearch el paralelo). Jairo avisa en su correo de que en su figura «RS» tampoco es RegularSearch: probablemente es el de Uno (inferencia). Citar siempre con el nombre completo.
1. Qué hace RegularSearch¶
Algoritmo «interno» (familia CC, CT, YYC). Trabaja sobre la matriz básica y busca conjuntos regulares (compatibles sin filas de ceros).
- Preproceso: quita las columnas sin ceros (son testores típicos de tamaño 1). Pone arriba la fila con menos unos. Agrupa a la izquierda las columnas con uno en esa fila. Baja justo debajo las filas que quedan en cero en ese bloque y repite la operación sobre las columnas restantes y esas filas. Guarda en
LV(una lista de tamaño |R|) la última posición de columna permitida según |C|. - Búsqueda: profundidad primero, candidato
Cordenado. Se añadexj(conj > último de C,j ≤ LV[|C|], y que no sea supercolumna de ninguna columna deC) solo si cubre alguna fila aún sin cubrir (ZR ∩ o(xj) ≠ ∅) y todas las columnas deCconservan una fila crítica (DZ). SiZRqueda vacío,nCes un testor típico. - Con otro nombre, es el esquema
crit/uncovde MMCS (Murakami y Uno). Ellos lo definen para minimal hitting sets; Lefebre lo deriva de «conjuntos compatibles», sin citar a Murakami-Uno (ni a Berge, KS, etc.: sus referencias son todas de la escuela de testores).
Lo que veo respecto a MMCS (inferencia, falta confirmarlo con código)¶
- Orden de columnas fijo y solo hacia adelante. No hay
CANDdinámico ni fila pivote elegida por nodo. El conjunto de nodos que visita es el de los conjuntos irredundantes alcanzables en orden de columnas, recortado porLV. MMCS visita solo nodos que se pueden completar a un cubrimiento minimal (por la fila pivote yCAND). Predicción: RegSearch visita más nodos que MMCS en general, con ventaja siLVpoda bien. LVes una versión estática del pivote, por profundidad, no por nodo. La cadena de filas (fila de menos unos, luego la de menos unos entre las que quedan en ceros, etc.) se fija en el preproceso. Esto está más cerca de la fila pivote que BR y fast-BR (que solo la usan en la raíz), aunque no depende del nodo. Esto matiza la afirmación «fila pivote por nodo no está en la línea de testores»: sigue siendo cierta para per-nodo, pero hay que describirLVen la comparación con RegSearch.- La poda por supercolumnas (
Ex) ya la implica el chequeo decrit. Es un cálculo previo, no una poda adicional (inferencia). - Sin hardware comparable. Sus tiempos salen de un portátil Ryzen 7 4800HS, con implementaciones heterogéneas (GCreduct y fast-BR en Java del INAOE contando; RegSearch y YYC de él, en otro lenguaje; la figura 4 usa una reimplementación en Python, Tyfa). No son comparables con los nuestros salvo en forma.
Resultados que reportan¶
- Gana con densidad D(1) > ~0.4 (> 0.32 en matrices de 1000×38) y con filas ≥ 3× columnas. Pierde a densidad baja: «comparaciones con D(1) < 0.3 se descartaron porque no rendía bien» (§4). Es el mismo patrón que RUNC-M frente a MMCS en nuestras medidas (gana en densas, pierde en ralas).
- Tabla 7 (conteo, ms): RegSearch es el más rápido en 6 de 10 UCI (soybean, K-higher edu, HCV, promoter, waveform5000, DARWIN). RoPM gana en anneal y dermatology; fast-BR en cardiotocography. En
kr.vs.kpganan GCreduct y fast-BR. Hay que citar los 4 que pierde, no solo «gana». - Tabla 6 (listando): vs YYC. Matrices UCI con dimensiones de MB y número de TT: sirven de prueba de validación cruzada para
experiments/lib/dtable.py(dermatology: 1124×34, 115 556 TT; K-higher edu: 2367×32, 432 222 TT; promoter: 2761×57, 7 456 943 TT; DARWIN: 1681×451, 29 953 TT; cardiotocography: 9751×35, 164 379 TT; HCV-Egyptian 1442×28, 7052; anneal 93×38, 455; soybean 33×35, 570; kr.vs.kp 29×36, 4; waveform5000 908×40, 1268). Ojo: el paper paralelo dasoybeancon 30 filas y el secuencial con 33, ydermatology, etc., coinciden. Esa discrepancia es suya. - No compara contra MMCS, RS, RUNC-M ni contra nada de la familia de minimal hitting sets. Compara con FastBR, GCreduct, RoPM y YYC. La afirmación de «primera comparación testores vs MMCS» sobrevive respecto a este artículo (como en los #3, #4 y #6).
Verificación de sus ejemplos¶
Calculé por fuerza bruta los conjuntos de las tres matrices pequeñas (Tabla 3 del secuencial, Tabla 1 y Tabla 2 del paralelo). Los conjuntos que publican son correctos: {x6}, {x1,x4}, {x2,x3,x5}, {x2,x4,x5}, {x3,x4,x5}; {x2,x4}, {x1,x2,x3}; {x1,x4}, {x2,x5}, {x1,x2,x3}, {x3,x4,x5}.
2. P-RegSearch (paralelo)¶
- Reparte el árbol por la primera columna: un hilo por cada 1 de la primera fila (fila de menos unos), y une las salidas. Es la ramificación de la raíz de BR/MMCS convertida en paralelismo. Al ser subárboles disjuntos, no hay sincronización. Con la fila con menos unos, el número de hilos queda acotado por esos unos. Los subárboles son muy desiguales (cada hilo prunea la mitad: ver «el espacio se reduce a la mitad en cada hilo siguiente»), así que el tiempo lo manda el primero. Es la limitación obvia (inferencia).
- Simplifica el preproceso: descarta la lista
LV. El texto dice que lo hace «para una descripción más simple». Por tanto, el paralelo no es RegSearch con paralelismo, sino una variante más débil. - Errores en el pseudocódigo impreso del paralelo (inferencia, solo leyendo):
- Alg. 1, línea 20:
if |ZR| = 0 then add C to TT. Debería ser|nZR| = 0ynC, como en el Alg. 2 del secuencial. Como está,ZRnunca es vacío al entrar (se recurre solo connZRno vacío), así que no se añadiría ningún TT de longitud ≥ 2. Su ejemplo (Tabla 3) sí obtiene{x1,x2,x3}, así que su código de GitHub no debería tener el error. Mismo tipo de error que en el Alg. 3 de RCC-MAS (-asprinted, verCLAUDE.md). - Alg. 2, línea 14: llama a
GetRegularitiesT(BM, F, C, ZR, OD)conZRyODsin definir (y con otra aridad que la firma, que llevaTT); línea 11|z(xi) = 0|está mal escrita. - Compara solo contra P-YYC (Piza-Dávila 2018). No compara con ningún paralelo de otras familias.
- Valores de Tabla 4 (ms): P-RegSearch gana desde D(1) ≥ 0.2, hasta 7 h de diferencia (K-higher: 4 272 242 contra 172 153; cardiotocography 23 455 339 contra 125 839; promoter 26 751 971 contra 28 994). Pierde en kr.vs.kp y anneal (densidad baja).
- Código Java publicado en GitHub (
J41R0/RegularSearch, el mismo repositorio que cita el secuencial). Sin licencia verificada. No lo he descargado.
3. El correo de Jairo Lefebre (2026-11-19)¶
Comunicación personal. No citar sin su permiso; el correo no pide confidencialidad, pero habla de trabajo no publicado.
Qué dice (hechos suyos, no verificados):
- Adjunta el artículo y la variante paralela (los dos PDF de arriba) y la imagen de resultados de FastRS con datos sintéticos. Las dos imágenes están en
papers/y se leen en §3.1. - Tiene FastRS (versión rápida de RegularSearch) sin publicar. Dice que corrige el mal desempeño de RegSearch a densidades bajas (justo la debilidad que reconoce el artículo).
- Dice que ha comparado FastRS con otros algoritmos implementados en C++ «y esos no son todos». No sabemos cuáles. Es verosímil que incluyan MMCS y RS de Uno (inferencia por su aviso de que «el RS de la imagen no es RegularSearch»). Si es así, ya existiría una comparación testores–MMCS no publicada, y la reclamación de prioridad de nuestro artículo está en riesgo.
- Advierte de que testores típicos = reductos = minimal traversals = minimal hitting sets, y de que la dualidad MUS/MCS (SAT) equivale a aplicar los algoritmos de testores sobre el conjunto de testores típicos, que devuelve la matriz básica. De ahí concluye que hay muchos algoritmos que desconocemos y con los que no nos comparamos.
- Ofrece más información y referencias.
- Pide que lo tengamos presente porque «si publicas algo existe la posibilidad de que te pregunten».
3.1 Las dos imágenes (papers/)¶
Resultados preliminares de Jairo, sin publicar, de un solo hilo. Son gráficas: leo los valores a ojo, con error de ±10 %.
dataset_n25_fastrs_rs_mmcs_mhs2_htcbdd_5k_n25.png: «Single-thread MHS algorithms (N=25, t=1)». Eje x: tamaño R de cada hiperarista (instancias = subconjuntos de R elementos de un universo de 25), es decir, densidad R/25. Eje y: tiempo medio de búsqueda, escala log, banda ±1 desviación. Algoritmos: FastRS, RS, MMCS, MHS2, HTC-BDD. «5k» en el nombre sugiere 5000 hiperaristas (inferencia). No dice qué es MHS2 ni qué RS es (probablemente el de Uno, por estar junto a MMCS; inferencia).
- FastRS no gana en densidad baja ni media. Para R = 4 a 12 (densidad 0.16–0.48) va por encima de RS y de MMCS: en R = 8 tarda ~7.5 s contra ~3.0 de RS y ~3.6 de MMCS; en R = 4, ~0.22 s contra ~0.11 de RS. RS es el más rápido en toda esa franja (por ~2x sobre FastRS en el pico).
- Se cruzan hacia R ≈ 13–14 (densidad ~0.55). Desde R ≥ 15 FastRS gana, y la ventaja crece: en R = 20, ~0.024 s contra ~0.10 de RS y MMCS (~4x); en R = 23, ~0.002 contra ~0.005–0.006 (~2.5x).
- HTC-BDD queda plano (~0.4–0.5 s en R ≥ 17), muy por encima de los demás en la zona densa y mejor que MHS2 hasta R ≈ 17. MHS2 es el peor en R ≤ 16 (hasta ~80 s en R = 4) y supera a HTC-BDD solo hacia R ≥ 17.
- Lectura: lo que dice Jairo («corrige las dificultades en bajas densidades») es cierto frente a RegSearch (imagen 2), pero no frente a RS y MMCS de Uno: en matrices ralas siguen ganándole. La conclusión coincide con la de RUNC-M contra MMCS (gana en densas, pierde en ralas).
1000_22_time.png: «Testor Algorithm Performance (rows=1000, cols=22, t=1)». Eje x: densidad de unos, 9–86 %. Eje y: tiempo medio en segundos (lineal). Algoritmos: FastBR, GCreduct, RegularSearch, FastRS. No incluye YYC, RoPM, MMCS ni RS.
- RegSearch tiene un pico enorme a densidad baja (~107 s en ~14 %), que FastRS elimina (casi 0 s).
- FastRS es el más rápido en todas las densidades mostradas. Su máximo es ~5 s a 27–36 %, donde GCreduct tarda ~37 s y FastBR ~25–37 s (≈ 7x). A densidad ≥ 65 % las curvas de RegSearch y FastRS se juntan en ~0.
- Consistente con nuestros resultados: la familia MMCS/RS supera a fast-BR y GCreduct (aquí con FastRS en su lugar).
Qué implica para el artículo (valoración):
- Su comparación existe y es la misma que la nuestra en espíritu. «Primera comparación» ya no se puede afirmar sin matices: decir «hasta donde sabemos, no hay una comparación publicada» y citar, con permiso, su trabajo en preparación.
- No lo anula: lo que nos distingue sigue en pie (ablación que explica por qué MMCS y RUNC-M ganan, la auditoría con errores de conteo corregidos, validación por conjunto, RUNC-M como tercer competidor, y matrices reales UCI). Nada de eso aparece en sus imágenes.
- Nuevo baseline pendiente: FastRS y MHS2 (aún sin nombre claro) y HTC-BDD. HTC-BDD ya estaba como «fuera de la primera versión»; con sus datos de que es plano en 0.4 s, vale la pena incluirlo si se consigue código.
- Pregunta para Jairo: ¿instancias de su imagen 1 son matrices básicas con filas de tamaño fijo? ¿Cuántas por punto? ¿Qué RS y qué MHS2 usó?
3.2 Segunda respuesta de Jairo (2026-11-20)¶
Respuesta a docs/correspondencia/04b-lefebre-respuesta-es.md. Comunicación personal, mismo tratamiento que §3. Hechos que afirma él, sin verificar:
- Propone una reunión la próxima semana y deja abierta una colaboración en el tema. Su límite es el tiempo. Tiene algoritmos y notas avanzados (sin revisar) sobre temas relacionados y propiedades equivalentes.
- RS y MMCS de su imagen 1 son los de Murakami y Uno (SHD). Confirma la inferencia de §3.1: sí existe una comparación no publicada de algoritmos de testores con MMCS y RS.
- Instancias de la imagen 1: matrices básicas sintéticas, 10 por punto (no 50, como supuse en el 04b), con a lo sumo 5000 filas. El número de filas no es fijo: con 25 columnas no hay MB de 1000 filas en los extremos de densidad. Es correcto: las filas de una MB forman una anticadena (Sperner) y, con filas de tamaño fijo R, hay a lo sumo C(25, R) filas (25 para R = 1 o 24). Consecuencia para leer la imagen 1: en los extremos el eje x mezcla densidad y número de filas. La ventaja de FastRS en R ≥ 20 se mide sobre matrices de pocas filas (C(25,20) = 53 130, pero C(25,23) = 300) (inferencia sobre cómo las generó; hay que preguntarlo).
- MHS2: Cardoso y Abreu, «An efficient distributed algorithm for computing minimal hitting sets», DX 2014. Código:
github.com/npcardoso/MHS2. - HTC-BDD: Toda,
www.sd.is.uec.ac.jp/toda/htcbdd.html. En sus pruebas es muy eficiente en datasets complejos, sobre todo a densidad media (falta experimentar). - ParTran: Leiserson, Schardl y Sukha, «Parallel computation of the minimal elements of a poset», ACM SPAA 2010, doi:10.1145/1837210.1837221. Código supuesto en BPAS (
bpaslib.org/downloads.html,bpaslib.org/trvgen.tgz). No lo pudo compilar (Cilk). - MUS/MCS: confirma que la dualidad se resuelve con oráculo SAT. Comparó con RC2 y Hitman de PySAT (
pysathq.github.io/docs/html/api/examples/hitman.html; C++ llamado desde Python): «así y todo es lento». Apoya la decisión de dejarlos fuera de alcance; la medición es suya, no nuestra. - Datasets de Murakami y Uno (
research.nii.ac.jp/~uno/dualization.html): los usó en otras pruebas. - Recomienda Gainer-Dewar y Vera-Licona (SIAM J. Discrete Math. 31(1), 2017, 63–100). Ya leído (arXiv 1601.02939, ver
docs/mmcs-y-propuesta-articulo.md). - Permiso: podemos correr RegularSearch como baseline externo. No dice nada de licencia ni de redistribución: tratarlo como RUNC-M (correr, no redistribuir).
- FastRS: sin preprint, solo resultados preliminares y un borrador. Supera a todas sus variantes de testores; quiere comparar implementaciones completas para certificarlo. Tiene variantes mejores que la de la imagen. La comparación con FastRS queda para hablarla.
Qué cambia (valoración):
- El riesgo de prioridad pasa de inferencia a hecho: hay una comparación testores–MMCS/RS no publicada. Sin preprint no hay nada que citar formalmente; en el artículo, «comunicación personal» o «trabajo en preparación», con su permiso.
- La colaboración es una decisión de Vladimir y de los asesores, no técnica. Opciones: (a) artículos separados, con coordinación y citas cruzadas; (b) un artículo conjunto; (c) nuestro artículo como está (framework, auditoría, ablación, RUNC-M) y un segundo trabajo conjunto (FastRS más el banco ampliado: HTC-BDD, MHS2, ParTran). Riesgo de (b): su tiempo es su recurso escaso y FastRS no está listo, así que ata nuestro calendario al suyo. Riesgo de (a): dos artículos con el mismo mensaje compitiendo. (c) separa lo que ya tenemos de lo que depende de él. Decidido por Vladimir el 2026-11-20: opción (c). Interés en colaborar con Jairo, pero sin atar a eso el artículo actual. La respuesta la redacta Vladimir.
- Baselines nuevos: RegSearch (permiso para correr), HTC-BDD y MHS2 (código público; revisar licencias), ParTran (difícil). Los datasets de Uno, como banco adicional.
- Preguntas para la reunión: generador de la imagen 1 (cómo elige las filas para cada R; ¿anticadena?), licencia de
J41R0/RegularSearch, condiciones para incluir FastRS en el marco, qué quiere decir con «diferente distribución de los datos en la MB», y si Ruiz-Shulcloper participa.
Mi valoración¶
- Ya lo sabíamos en parte. La equivalencia con minimal hitting sets es la premisa del proyecto (
CLAUDE.md), y la dualidad de BergeTr(Tr(H)) = Hes clásica. Lo nuevo es la rama MUS/MCS. - MUS/MCS: relevancia incierta. La dualidad es la misma (cada MCS es un hitting set minimal de los MUS y al revés). Pero MARCO, CAMUS y similares trabajan con un oráculo SAT sobre una fórmula implícita, y un hipergrafo explícito en matriz no es su caso de uso. Suponer que no serían competitivos sobre matrices explícitas es una inferencia mía, no la he probado. Para el artículo basta citarlos y decir por qué no se incluyen; para saber más, pedirle a Jairo las referencias que ofrece.
- Riesgo real para el artículo: (a) una comparación no publicada con MMCS/RS de FastRS; (b) que
LVde RegSearch se lea como antecedente de la fila pivote (ver §1.2); (c) que FastRS cambie la conclusión «los latinoamericanos quedan por detrás» en densidades bajas. - Opción directa: preguntarle a Jairo qué algoritmos C++ usó y si FastRS está en un preprint, antes de afirmar prioridad. Mejor preguntárselo que citarlo de memoria.
4. Qué cambia en el proyecto¶
docs/articulos-por-conseguir.md: #5 pasa a leído; nuevo #18 (paralelo). Hecho.docs/revision-bibliografica-br-pivot.md: RegularSearch deja de estar en «sin texto completo». Hecho.- Pendientes nuevos (no hechos):
- Reimplementar RegSearch (
mhs.RegSearch) desde el Alg. 1–2 y compararlo con MMCS ybr-pivot: contar nodos y tiempo, y verificar por conjunto. Es el único modo de confirmar §1.1–1.3. Alternativa: descargar el Java de GitHub, pero no hay licencia (mismo tratamiento que RUNC-M: correr, no redistribuir; pedir permiso). - Usar la Tabla 6 como validación de
dtable.py(ver §1). Necesita los ARFF/CSV originales; algunos están en UCI y enexperiments/audit. - Añadir a la revisión bibliográfica MUS/MCS (Liffiton y Sakallah, CAMUS, MARCO) como «fuera de alcance, con la razón».
- Responder a Jairo (Vladimir): agradecer, pedir la imagen, los nombres de los algoritmos C++ y las referencias, y preguntar por el código y su licencia. Actualizar el borrador
docs/correspondencia/04-..., que ya no pide el artículo.
5. RegularSearch y YYC en el marco (2026-11-20)¶
El repositorio github.com/J41R0/RegularSearch (commit bbc3eff, julio de 2023) trae licencia MIT (Jairo Lefebre, 2023) e incluye también YYC. scripts/fetch_regsearch.sh lo clona y compila sin App.java (pasarela py4j). scripts/RegSearchMain.java llama a su código sin cambios: el mismo preproceso que su FindTT, search_tt() por reflexión, y devuelve los reductos con las columnas del archivo (su regular_sort permuta columnas). En el runner: regsearch y yyc.
Validación por conjunto (experiments/baseline/regsearch_validate.py, results/regsearch_validate.md): 453 de 453 matrices coinciden con la referencia, en los dos algoritmos, incluidos los grupos con columnas repetidas, columnas de ceros y casos borde. No encontré errores en su código.
Lectura del código. Confirma §1.1: orden fijo de columnas, solo hacia adelante, LV como cota por profundidad. La cota es correcta: las filas de la cadena tienen sus unos en bloques disjuntos y crecientes, así que el (k+1)-ésimo elemento de un testor típico está antes de LV[k]. No hay poda por supercolumnas explícita. Su contador hits cuenta llamadas a search_regularities (nodos internos).
Primera comparación (results/regsearch_vs_mmcs.md, 20 matrices, 1 corrida, límite 30 s, ms netos):
- RegularSearch no termina en 30 s en 12 de 20 matrices: las 9 sintéticas de densidad ≤ 0.57, dermatology, lung-cancer y student-mat. Donde termina, va de 7 a 40 veces detrás de MMCS (sint 0.62: 22 109 contra 547; sint 0.80: 677 contra 31). YYC no termina en ninguna de las 14 matrices grandes.
- Sin límite, dermatology tarda 90 s de búsqueda (12,6 millones de nodos). fast-BR corregido tarda 4,6 s con 22 millones de candidatos.
- Los nodos no van tan mal como el tiempo. En las sintéticas densas, RegularSearch visita menos nodos que nuestro
mmcs(0.62: 1,97 M contra 2,10 M; 0.70: 268 K contra 538 K; 0.80: 28 K contra 108 K), pero más queshd-mmcs. Las unidades no son idénticas. - El costo por nodo es el problema (inferencia, sin perfilar).
BitArrayusa bloques de 32 bits y recalcula la cardinalidad en cada operación con un conteo recursivo por nibbles. Por candidato, eso cuesta unas 35 veces lo de fast-BR en dermatology. Es una constante de implementación, no del algoritmo. - Contradice su Tabla 7, donde RegularSearch gana a fast-BR en dermatology. Nuestra MB de dermatology no es la suya (1103 filas y 112 708 reductos contra 1124 y 115 556), pero la diferencia no explica un factor de 20. Posibles causas, sin ordenar por falta de datos: el repositorio no es la versión que midió en el artículo; el fast-BR que midió es el original del INAOE en otras condiciones; diferencia de JVM o de máquina.
Qué hacer:
- Preguntarle a Jairo si el repositorio es la versión del artículo y si tiene una más rápida.
- Reimplementar RegularSearch con los primitivos de
mhs.core(long[],Long.bitCount) para separar algoritmo de implementación. Ya estaba en §4 como pendiente. - En el artículo, reportar las dos: su código tal cual y la reimplementación, con nodos además del tiempo.
5.1 Reimplementación mhs.RegSearch (2026-11-20)¶
java/src/mhs/RegSearch.java reescribe RegularSearch con los primitivos de mhs.Mmcs (long[] por columna, sin recuento de unos). Sigue su código paso a paso, incluido el intercambio de filas de load() que fija los desempates, para recorrer el mismo árbol. En el runner: regsearch-java.
Validación: 453 de 453 por conjunto, y sus Nodes son iguales a los hits del código de Jairo en las 453 matrices. Es el mismo árbol, así que la diferencia de tiempo es solo de implementación.
Comparación (experiments/baseline/results/regsearch_rewrite.md, 1 corrida, límite 30 s, ms netos):
| Matriz | mmcs | ppdual | regsearch-java | regsearch (original) | fastbr |
|---|---|---|---|---|---|
| sint 0.47 | 3 814 | 2 236 | 11 336 | t/o | 15 066 |
| sint 0.57 | 2 039 | 876 | 3 437 | t/o | 4 330 |
| sint 0.62 | 586 | 402 | 1 233 | 22 881 | 2 089 |
| sint 0.70 | 521 | 109 | 266 | 3 489 | 389 |
| dermatology | 148 | 69 | 4 842 | t/o (90 s sin límite) | 4 612 |
| lung-cancer | 1 389 | 1 937 | 11 650 | t/o | 8 696 |
- La implementación publicada cuesta de 10 a 20 veces (dermatology: 90 s contra 4,8 s; sint 0.62: 22,9 s contra 1,2 s).
- Corregida la implementación, RegularSearch queda en la clase de fast-BR, no en la de MMCS. Gana a fast-BR en las sintéticas densas (1,3 a 2,9 veces), empata en dermatology y pierde en lung-cancer. No termina, igual que fast-BR, en las sintéticas de densidad ≤ 0.42 ni en student-mat.
- Frente a MMCS y ppdual sigue de 2 a 70 veces detrás. En dermatology prueba 41,8 millones de columnas como extensión; MMCS, 245 mil candidatos.
- Lectura: la cota
LVpoda menos que la fila pivote por nodo. Esto confirma §1.1 y sostiene la tesis del artículo: el ingrediente que separa a las familias es la fila pivote por nodo, y RegularSearch no lo tiene. - La Tabla 7 de su artículo (RegularSearch gana a fast-BR en dermatology) queda a medio explicar. Con la implementación corregida empatan en nuestra MB. Su fast-BR era el JAR original del INAOE, con los errores de
docs/hallazgos-errores.md, y la MB no es la misma.
Para el artículo: reportar las dos, el código de Jairo tal cual y mhs.RegSearch, con candidatos además del tiempo.