Algoritmo para encontrar tiempos superpuestos

7

Parte de nuestro sistema ERP es un subsistema para ejecutar trabajos en segundo plano. Realizamos un seguimiento de una variedad de metadatos sobre nuestros trabajos en una tabla que incluye las marcas de tiempo para los tiempos de envío, inicio y finalización.

Estoy creando un informe que muestra el rendimiento de nuestro sistema de trabajo, detallado por día. Un KPI es el número máximo de trabajos que se ejecutan a la vez. El algoritmo que estoy usando actualmente es:

dim cnt as integer    'number of overlapping jobs
dim max as integer    'maximum number of jobs running at one time

for each Job where 
         Job.SubmitTs = today

  'bJob is a 2nd instance of Job
  for each bJob where
           bJob.SubmitTs =  today and
           bJob.StartTs  <= Job.EndTs and
           bJob.EndTs    >= Job.EndTs
    cnt = cCnt + 1
  next

  if cnt > max then max = cnt
next

El problema con este algoritmo es que es muy lento debido a todos los bucles. Me preguntaba si hay una forma más rápida de implementar esto?

Editar No puedo usar consultas SQL para acceder a los datos.

    
pregunta briddums 18.05.2012 - 17:49

2 respuestas

14
  1. Incluya todos los puntos de inicio y finalización (en el tiempo) de los trabajos en una matriz (esto crea 2 * N elementos (1 para el inicio 1 para el final))
  2. ordene el ordenamiento de la matriz por la marca de tiempo del evento,
  3. luego itere sobre los elementos (2 * N) de la siguiente manera:

    for each element X 
    do 
      if(X.type == start)
        counter++
      else
        counter--
      ans=max(ans, counter);
    end
    

Complejidad : O (n.log (n)) para la construcción inicial de la estructura ordenada + O (n) para la iteración a través de sus elementos.

Editar: Giorgio ha sugerido que se use una matriz, que es una mejor opción. (La sugerencia originalmente era utilizar un árbol rojo / negro, pero no parece necesaria la capacidad de eliminación de tareas, por lo que mantener el orden es trivial).

    
respondido por el K.Steff 18.05.2012 - 18:18
1

SQL sabe cómo ordenar las cosas, y apostaría a que su motor utiliza el algoritmo más eficiente que puede (es decir, O(n log(n)) ), mientras sigue funcionando si el conjunto de resultados no cabe en la RAM (en contraste con K. La respuesta de Steff que fallará si la matriz no encaja en la RAM). En python:

import sqlite3
connection = sqlite3.connect("database.db")
cursor = connection.cursor()
cursor.execute("SELECT isStart from (" +
               "  SELECT startTime AS time, 1 AS isStart FROM myTable " +
               "  UNION ALL " +
               "  SELECT endTime as time, -1 AS isStart FROM myTable " +
               "  ORDER BY time ASC, isStart ASC" +
               ")")
maxOverlap = 0
currentOverlap = 0
for (isStart,) in cursor:
    currentOverlap += isStart
    maxOverlap = max(maxOverlap, currentOverlap)
print maxOverlap

Tenga en cuenta que el orden isStart ASC es necesario, por lo que los intervalos [10,15] y [15,23] no se consideran superpuestos.

Para una mejora adicional, es probable que las columnas startTime y endTime tengan un índice, por lo que el motor SQL debería fusionar eficientemente las dos tablas ya ordenadas, dando como resultado una operación O(n) (el factor O(log(n)) ocurre entonces en el momento de la inserción para cada fila, cuando se agrega al índice, pero ya lo tiene de todos modos). Si su motor SQL no es lo suficientemente inteligente como para hacer una fusión eficiente, hágalo usted mismo sobre la marcha (aún en python):

import sqlite3
connection = sqlite3.connect("database.db")
cursorStart = connection.cursor()
cursorStart.execute("SELECT startTime FROM myTable ORDER BY startTime ASC")
cursorEnd = connection.cursor()
cursorEnd.execute("SELECT endTime FROM myTable ORDER BY endTime ASC")
maxOverlap = 0
currentOverlap = 0
currentStart = cursorStart.fetchone()
currentEnd = cursorEnd.fetchone()
while currentStart is not None and currentEnd is not None:
    if currentStart < currentEnd:
        currentOverlap += 1
        currentStart = cursorStart.fetchone()
    else:
        currentOverlap -= 1
        currentEnd = cursorEnd.fetchone()
    maxOverlap = max(maxOverlap, currentOverlap)
print maxOverlap
    
respondido por el Georges Dupéron 19.05.2012 - 11:23

Lea otras preguntas en las etiquetas