En programación de computadoras , un valor centinela (también conocido como valor de bandera , valor de disparo , valor deshonesto , 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, típicamente en un bucle o algoritmo recursivo.
El valor centinela es una forma de datos dentro de banda que permite detectar el final de los datos cuando no se proporcionan datos fuera de banda (como una indicación explícita de tamaño). 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 señalaría prematuramente el final de los datos (el problema del semipredicado ). Un valor centinela a veces se conoce como " Elefante en El Cairo ", debido a una broma en la que se lo utiliza como centinela físico. En lenguajes seguros, la mayoría de los valores centinela podrían reemplazarse 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, utilizada en circunstancias ligeramente diferentes, es colocar algún valor específico al final de los datos, para evitar la necesidad de una prueba explícita para la terminación en algún bucle de procesamiento, porque el valor desencadenará la terminación por parte de las pruebas que ya presente por otras razones. A diferencia de los usos anteriores, no es así como se almacenan o procesan los datos de forma natural, sino que se trata de una optimización, en comparación con el sencillo algoritmo que comprueba la terminación. Esto se utiliza normalmente en la búsqueda. [1] [2]
Por ejemplo, cuando se busca un valor particular en una lista sin ordenar , cada elemento se comparará con este valor y el ciclo terminará cuando se encuentre la igualdad; sin embargo, para afrontar el caso de que el valor esté ausente, también se debe comprobar después de cada paso si se ha completado la búsqueda sin éxito. Al agregar el valor buscado al final de la lista, ya no es posible realizar una búsqueda fallida y no se requiere ninguna 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 sólo una vez y no en cada iteración. [3] Knuth llama al valor así colocado al final de los datos un valor ficticio en lugar de un centinela.
Por ejemplo, si busca un valor en una matriz en C, una implementación sencilla es la siguiente; tenga en cuenta el uso de un número negativo (índice no válido) para resolver el problema de semipredicado de devolver "sin resultado":
int buscar ( int arr [], size_t len , int val ) { for ( int i = 0 ; i < len ; i ++ ) if ( arr [ i ] == val ) devolver i ; devolver -1 ; // extraviado } Sin embargo, esto realiza dos pruebas en cada iteración del bucle: si se ha encontrado el valor y si se ha alcanzado el final de la matriz. Esta última prueba es la que se evita utilizando un valor centinela. Suponiendo que la matriz se puede ampliar en un elemento (sin asignación o limpieza de memoria; esto es más realista para una lista vinculada, como se muestra a continuación), esto se puede reescribir como:
int buscar ( int arreglo [], tamaño_t len , int val ) { int i ; arr [ len ] = val ; // agrega valor centinela para ( i = 0 ;; i ++ ) if ( arr [ i ] == val ) break ; si ( i < len ) devuelve i ; de lo contrario , devuelve -1 ; // extraviado } La prueba for i < lentodavía está presente, pero se ha movido fuera del bucle, que ahora contiene solo una prueba (para el valor) y se garantiza que terminará debido al valor centinela. Hay una única verificación de la terminación si se alcanza 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 arreglo [], tamaño_t len , int val ) { int último ; si ( len == 0 ) devuelve -1 ; último = arr [ len - 1 ]; arr [ len - 1 ] = val ; // agregar valor centinela ent yo ; para ( i = 0 ;; i ++ ) si ( arr [ i ] == val ) romper ; arr [ len - 1 ] = último ; si ( arr [ i ] == val ) devuelve i ; de lo contrario , devuelve -1 ; // extraviado }