En programación informática , un valor centinela (también denominado valor de bandera , valor de viaje , valor no autorizado , valor de señal o datos ficticios ) es un valor especial en el contexto de un algoritmo que utiliza su presencia como condición de terminación, generalmente en un bucle o algoritmo recursivo.
El valor centinela es una forma de datos en banda que permite detectar el final de los datos cuando no se proporcionan datos fuera de banda (como una indicación de tamaño explícita). El valor debe seleccionarse de tal manera que se garantice que sea distinto de todos los valores de datos legales, ya que de lo contrario, la presencia de dichos valores indicaría prematuramente el final de los datos (el problema del semipredicado ). A veces, a un valor centinela se lo conoce como " Elefante en El Cairo ", debido a un chiste en el que se lo usa como centinela físico. En lenguajes seguros, la mayoría de los valores centinela se pueden reemplazar con tipos de opciones , que imponen un manejo explícito del caso excepcional.
Algunos ejemplos de valores centinela comunes y sus usos:
Una práctica relacionada, que se utiliza en circunstancias ligeramente diferentes, es colocar un valor específico al final de los datos, para evitar la necesidad de una prueba explícita de terminación en algún bucle de procesamiento, porque el valor activará la terminación por las pruebas que ya están presentes por otras razones. A diferencia de los usos anteriores, esta no es la forma en que los datos se almacenan o procesan naturalmente, sino que es una optimización, en comparación con el algoritmo sencillo que verifica la terminación. Esto se utiliza normalmente en búsquedas. [1] [2]
Por ejemplo, cuando se busca un valor particular en una lista desordenada , cada elemento se comparará con este valor, y el bucle terminará cuando se encuentre la igualdad; sin embargo, para tratar el caso de que el valor esté ausente, también se debe probar después de cada paso para haber completado la búsqueda sin éxito. Al agregar el valor buscado al final de la lista, ya no es posible una búsqueda fallida y no se requiere una prueba de terminación explícita en el bucle interno . Después de la búsqueda, se debe decidir si se encontró una coincidencia verdadera, pero esta prueba debe realizarse solo una vez en lugar de en cada iteración. [3] Knuth llama al valor colocado al final de los datos, un valor ficticio en lugar de un centinela.
Por ejemplo, si se busca un valor en una matriz en C, una implementación sencilla es la siguiente; observe el uso de un número negativo (índice no válido) para resolver el problema del semipredicado de devolver "ningún resultado":
int find ( int arr [], size_t len , int val ) { for ( int i = 0 ; i < len ; i ++ ) if ( arr [ i ] == val ) return i ; return -1 ; // no encontrado } Sin embargo, esto realiza dos pruebas en cada iteración del bucle: si se ha encontrado el valor y si se ha llegado al final de la matriz. Esta última prueba es lo que se evita al utilizar un valor centinela. Suponiendo que la matriz se puede ampliar con un elemento (sin asignación de memoria ni limpieza; esto es más realista para una lista enlazada, como se muestra a continuación), esto se puede reescribir como:
int buscar ( int arr [], tamaño_t len , int val ) { int i ; arr [ len ] = val ; // agregar valor centinela para ( i = 0 ;; i ++ ) if ( arr [ i ] == val ) break ; if ( i < len ) return i ; else return -1 ; // no encontrado } La prueba para i < lensigue estando presente, pero se ha movido fuera del bucle, que ahora contiene solo una única prueba (para el valor) y se garantiza que finalizará debido al valor centinela. Hay una única comprobación de finalización si se ha alcanzado el valor centinela, que reemplaza una prueba para cada iteración.
También es posible reemplazar temporalmente el último elemento de la matriz por un centinela y manejarlo, especialmente si se alcanza:
int buscar ( int arr [], tamaño_t len , int val ) { int último ; si ( len == 0 ) devuelve -1 ; last = arr [ len - 1 ]; arr [ len - 1 ] = val ; // agrega valor centinela int i ; para ( i = 0 ;; i ++ ) si ( arr [ i ] == val ) romper ; arr [ len - 1 ] = último ; si ( arr [ i ] == val ) devolver i ; de lo contrario devolver -1 ; // no encontrado }