Анализ степени наслоения (одновременности) процессов

Полезная программка ведь не обязана быть большой, правда? Пусть у нас есть процессы, для которых известны времена их начала и завершения. Таких в любой системе пруд пруди. Тот же ExecutionLogStorage в MS SQL Reporting Server, SQL server Profiler Trace, плюс куча кастомных метрик, которые есть у каждого.

Как выполняются эти процессы? Спокойно, один за другим, их хотят маршировать все в ногу? Какова средняя и максимальная степень параллелизма выполнения этих процессов? Хотелось бы получить что-то такое (процессы показаны черточками вверху):

Пишем на SQL?

Решение можно написать на SQL, но получается CROSS JOIN с перебором вариантов пересечений. Сложность этого O(n^2), и при 100'000 записях (10^10 вариантов) анализ становится практически невозможным

Решение

Задачу можно решить на традиционном языке за почти линейное время, если данные отсортированы по колонке времени начала процесса. Если число 'наслоений' не очень велико, то все решается за один проход.

Прилагаемая программа получает на вход csv файл (первая строка - заголовок), где должны быть колонки с временем начала и конца процесса в формате yyyy/mm/dd hh:mm:ss (Format cells -> Custom)

Файл должен быть отсортирован по дате начала процесса (если это не так, програмка откажется его обрабатывать). Запускаем:

Второй и третий параметры - номера колонок с датой/временем начала и конца процесса. Нумерация начинается от нуля.

Создаются файлы:

seconds.csv - параллелизм на каждую секунду в детектированном date range:

Далее вычисляются аггрегаты по бОльшим временным периодам, для них вычисляется максимальное и среднее значения:

Et voila, строим график:

А вот собственно код (еще раз извините что крошечная програмка, но было очень полезно анализировать многие вещи):

import os
import sys
import csv
import numpy as np
from datetime import datetime, timedelta

if len(sys.argv) != 4:
   print ('Usage: python parr.py yourfile.csv colstartn colendn')
   print ('  column numbers are counted from 0')
   print ('  start and end columns must be in format yyyy/mm/dd hh:mm:ss')
   exit()
csvfile = sys.argv[1]
start = int(sys.argv[2])
fin = int(sys.argv[3])

prc = []
newprc = []

# check min and max
first = True
newest = datetime(1980,1,1)
oldest = datetime(2030,1,1)
prevs = newest 
with open(csvfile, 'rt', encoding='utf8') as f:
  reader = csv.reader(f)
  for r, row in enumerate(reader):
    if not first:
      s = datetime.strptime(row[start],"%Y/%m/%d %H:%M:%S")
      if s<prevs:
        print('Error: start column is not properly sorted')
        print(f'  Value {s} < previous value {prevs}')
        exit(1)
      prevs = s
      e = datetime.strptime(row[fin],"%Y/%m/%d %H:%M:%S")
      if e>newest: newest=e
      if s<oldest: oldest=s
    first = False
print ('Date range: ', oldest, ' - ', newest)
seconds = int((newest-oldest).total_seconds())+1
grid = np.array([], dtype=np.uint16)
grid = np.zeros(seconds, dtype=np.uint16).reshape(seconds)

first = True
ln = 0
with open(csvfile, 'rt', encoding='utf8') as f:
  reader = csv.reader(f)
  for r, row in enumerate(reader):
     if not first:
       s = datetime.strptime(row[start],"%Y/%m/%d %H:%M:%S")
       e = datetime.strptime(row[fin],"%Y/%m/%d %H:%M:%S")
       # add end time to list of processes
       prc.append(e)
       # check what processes stopped before s
       newprc = [i for i in prc if i >= s]
       prc = newprc
       secnum = int((s-oldest).total_seconds())
       duration = int((e-s).total_seconds())
       for k in range(duration): 
         grid[secnum+k] += 1
       ln += 1
     first = False
print(f'Analysis - {ln} points')

ln = 0
with open('seconds.csv', 'w') as o:
  print('Time,processes', file=o)
  for s in range(seconds):
    print(f'{oldest+timedelta(seconds=s)},{grid[s]}', file=o)
    ln += 1
print(f'File seconds.csv - {ln} lines')

aggregates = [60,300,900,1800,3600]
aggfiles = ['minutes', 'minutes5', 'minutes15', 'minutes30', 'hours']
for aggname in aggfiles:
  demultiplier = aggregates.pop(0)
  ln = 0
  with open(f'{aggname}.csv', 'w') as o:
    print('Time,AvgRuns,MaxRuns', file=o)
    for m in range(seconds//demultiplier):
      sm = 0 
      mx = 0
      for s in range(demultiplier):
        g = grid[m*demultiplier+s]
        sm += g
        if mx<g: mx=g
      print(f'{oldest+timedelta(seconds=m*demultiplier)},{sm/demultiplier},{mx}', file=o)
      ln += 1
  print(f'File {aggname}.csv - {ln} lines')
exit()