algorithm - para - ¿Cuál es la diferencia entre un algoritmo en línea y fuera de línea?
algoritmo del punto medio para circunferencias (7)
Wikipedia
¿Qué, exactamente, no entiendes al mirar la página de Wikipedia?
En informática, un algoritmo en línea es aquel que puede procesar su entrada pieza por pieza en forma de serie, es decir, en el orden en que la entrada se alimenta al algoritmo, sin tener toda la entrada disponible desde el principio. Por el contrario, a un algoritmo fuera de línea se le dan los datos completos del problema desde el principio y se requiere que genere una respuesta que resuelva el problema en cuestión. (Por ejemplo, la ordenación por selección requiere que se proporcione toda la lista antes de que pueda clasificarla, mientras que la ordenación por inserción no lo hace).
Permítanme ampliar lo anterior:
Un algoritmo fuera de línea requiere toda la información ANTES de que comience el algoritmo. En el ejemplo de Wikipedia, la ordenación por selección está fuera de línea porque el paso 1 es Find the minimum value in the list . Para hacer esto, necesita tener toda la lista disponible; de lo contrario, ¿cómo podría saber cuál es el valor mínimo? No puedes.
Por el contrario, la ordenación de inserción está en línea porque no necesita saber nada sobre qué valores ordenará y la información se solicita MIENTRAS el algoritmo se está ejecutando. En pocas palabras, puede obtener nuevos valores en cada iteración.
Todavía no está claro?
Piense en los siguientes ejemplos (¡para niños de cuatro años!). David te está pidiendo que resuelvas dos problemas.
En el primer problema, dice:
"Voy a darte dos bolas de diferentes masas y tienes que soltarlas al mismo tiempo desde una torre ... solo para asegurarte de que Galileo tenía razón. No puedes usar un reloj, simplemente observaremos eso."
Si te di solo una pelota, probablemente me mirarías y te preguntarías qué se supone que debes estar haciendo. Después de todo, las instrucciones fueron bastante claras. Necesitas ambas bolas al comienzo del problema. Este es un algoritmo fuera de línea .
Para el segundo problema, David dice
"Está bien, fue bastante bien, pero ahora necesito que adelante y patear un par de bolas en un campo".
Voy y te doy la primera pelota. Usted patea. Luego te doy la segunda pelota y la pateas. También podría darte una tercera y una cuarta pelota (sin que siquiera sepas que te las iba a dar). Este es un ejemplo de un algoritmo en línea . Como cuestión de hecho, podría estar pateando pelotas todo el día.
Espero que esto esté claro: D
Estos términos se usaron en mi libro de texto de estructuras de datos, pero la explicación fue muy escueta y poco clara. Creo que tiene algo que ver con la cantidad de conocimiento que tiene el algoritmo en cada etapa de cálculo.
(Por favor, no enlace a la página de Wikipedia: ya lo leí y todavía estoy buscando una aclaración. Una explicación como si tuviera doce años y / o un ejemplo sería mucho más útil.)
Podemos diferenciar los algoritmos fuera de línea y en línea en función de la disponibilidad de las entradas antes del procesamiento del algoritmo.
Algoritmo fuera de línea: toda la información de entrada está disponible para el algoritmo y procesada simultáneamente por el algoritmo. Con el conjunto completo de información de entrada, el algoritmo encuentra la manera de procesar eficientemente las entradas y obtener una solución óptima.
Algoritmo en línea: las entradas vienen sobre la marcha, es decir, toda la información de entrada no está disponible para el algoritmo simultáneamente sino parte por parte como una secuencia o en el tiempo. Con la disponibilidad de una entrada, el algoritmo debe tomar una decisión inmediata sin ningún conocimiento de la información de entrada futura. En este proceso, el algoritmo produce una secuencia de decisiones que tendrá un impacto en la calidad final de su desempeño general.
Ejemplo: enrutamiento en la red de comunicación:
Los paquetes de datos de diferentes fuentes llegan al enrutador más cercano. Más de un enlace de comunicación están conectados al enrutador. Cuando llega un nuevo paquete de datos al enrutador, el enrutador debe decidir de inmediato a qué enlace debe enviarse el paquete de datos. (Supongamos que todos los enlaces se enrutan al destino, todos los enlaces de ancho de banda son iguales, todos los enlaces forman parte de la ruta más corta al destino). Aquí, el objetivo es asignar cada paquete de datos entrantes a uno de los enlaces sin conocer los paquetes de datos futuros de forma tal que la carga de cada enlace se equilibre. No se deben sobrecargar los enlaces. Este es un problema de equilibrio de carga.
Aquí, el planificador implementado en el enrutador no tiene idea de los futuros paquetes de datos, pero tiene que tomar la decisión de programación para cada paquete de datos entrantes. En contraste, un planificador fuera de línea tiene pleno conocimiento de todos los paquetes de datos entrantes, luego asigna de manera eficiente los paquetes de datos a diferentes enlaces y puede equilibrar de manera óptima la carga entre los diferentes enlaces.
Se dice que un algoritmo está en línea si no conoce los datos que ejecutará de antemano. Un algoritmo fuera de línea puede ver todos los datos por adelantado.
Un algoritmo en línea es aquel que recibe una secuencia de solicitudes y realiza una acción inmediata en respuesta a cada solicitud.
Por el contrario, un algoritmo fuera de línea realiza una acción después de que se tomen todas las solicitudes.
This documento de Richard Karp ofrece más información sobre los algoritmos en línea y fuera de línea.
Un algoritmo en línea procesa la entrada solo pieza por pieza y no sabe sobre el tamaño de entrada real al comienzo del algoritmo.
Un ejemplo de uso frecuente es la programación: tiene un conjunto de máquinas y una carga de trabajo desconocida. Cada máquina tiene una velocidad específica. Desea borrar la carga de trabajo lo más rápido posible. Pero como no conoce todas las entradas desde el principio (a menudo solo puede ver la siguiente en la cola), solo puede estimar qué máquina es la mejor para la entrada actual. Esto puede dar como resultado una distribución no óptima de su carga de trabajo, ya que no puede hacer ninguna suposición sobre sus datos de entrada.
Un algoritmo fuera de línea, por otro lado, solo funciona con datos de entrada completos. Toda la carga de trabajo debe conocerse antes de que el algoritmo comience a procesar los datos.
Ejemplo:
Workload: 1. Unit (Weight: 1) 2. Unit (Weight: 1) 3. Unit (Weight: 3) Machines: 1. Machine (1 weight/hour) 2. Machine (2 weights/hour) Possible result (Online): 1. Unit -> 2. Machine // 2. Machine has now a workload of 30 minutes 2. Unit -> 2. Machine // 2. Machine has now a workload of one hour either 3. Unit -> 1. Machine // 1. Machine has now a workload of three hours or 3. Unit -> 2. Machine // 1. Machine has now a workload of 2.5 hours ==> the work is done after 2.5 hours Possible result (Offline): 1. Unit -> 1. Machine // 1. Machine has now a workload of one hour 2. Unit -> 1. Machine // 1. Machine has now a workload of two hours 3. Unit -> 2. Machine // 2. Machine has now a workload of 1.5 hours ==> the work is done after 2 hours
Tenga en cuenta que el mejor resultado en el algoritmo fuera de línea solo es posible ya que no usamos la mejor máquina desde el principio. Ya sabemos que habrá una unidad pesada (unidad 3), por lo que esta unidad debe procesarse con la máquina más rápida.
Un algoritmo fuera de línea sabe todo acerca de sus datos de entrada en el momento en que se invoca. Un algoritmo en línea, por otro lado, puede obtener partes o todos sus datos de entrada mientras se está ejecutando.
Problema de caché de caché: en un sistema de computadora, el caché es una unidad de memoria utilizada para evitar la discrepancia de velocidad entre el procesador más rápido y la memoria primaria más lenta. El objetivo de usar el caché es minimizar el tiempo de acceso promedio manteniendo algunas páginas a las que se accede frecuentemente en el caché. La suposición es que estas páginas pueden ser solicitadas por el procesador en un futuro próximo. Generalmente, cuando el procesador realiza una solicitud de página, la página se obtiene de la memoria primaria o secundaria y una copia de la página se almacena en la memoria caché. Supongamos que la memoria caché está llena, luego el algoritmo implementado en la memoria caché debe tomar la decisión inmediata de reemplazar un bloque de memoria caché sin el conocimiento de futuras solicitudes de página. Surge la pregunta: ¿qué bloque de caché debe ser reemplazado? (En el peor de los casos, puede suceder que reemplace un bloque de caché y, en el momento siguiente, la solicitud del procesador para el bloque de caché reemplazado). Por lo tanto, el algoritmo debe diseñarse de tal manera que tome una decisión inmediata al llegar una solicitud entrante sin conocimiento previo de toda la secuencia de solicitud. Este tipo de algoritmos se conocen como ALGORITMO EN LÍNEA