Возможно ли повысить эффективность этого итерационного алгоритма?

Question

Я исследователь, изучающий поведение парковки автомобилей и модели парковки. Я пытаюсь написать эффективный и надежный алгоритм для расчета количества парковки с течением времени.

Вот моя история:

У меня есть данные, записанные с помощью парковки вкапываемых парковочных датчиков со всех концов города Мельбурн, Австралия. Вы можете просмотреть данные здесь: https://data.melbourne.vic.gov.au/Transport/Parking-Events-From-Parking-Bays-With-Sensors/8nfq-mtcn?.

Моя первоначальная задача - нарисовать эти данные как график временных рядов, чтобы я мог визуально анализировать тенденции при парковке в разные периоды времени (день, неделя, месяц и т. Д.).

На разных улицах города установлено 7,112 датчиков. Каждый датчик регистрирует данные, когда автомобиль прибывает и уходит из места парковки (позволяет назвать это «событием»). С 2011 по 2012 год они зарегистрировали 12 208 417 событий. Каждое событие является строкой в ​​базе данных и имеет следующие столбцы, которые интересуют меня:

• датчик ID
• время прибытия
• время вылета
• продолжительность стоянки
• улица, где этот датчик расположенный

Теперь я не хочу отображать данные с каждого датчика отдельно, но группа датчиков, принадлежащих улице, по фиксированной интервалы времени (секунды, минуты, часы и т. д.). Таким образом, на улице «А» может быть 10 парковочных мест (= 10 датчиков), улица «B» = 12 датчиков и т. Д.

В течение 24-часового графика времени между (10/10/2011 12:00:00 AM) до (11/10/2011 12:00:00 AM) для данной улицы «А», вот что Я сделал:

ИСПОЛЬЗОВАНИЕ SQL

1. Получить все события от датчиков, расположенных на улице "А" между указанными датами, выполнив SQL-запрос

ИСПОЛЬЗОВАНИЕ PHP

2. Итерацию по временному циклу от (10/10/2011 12:00:00 AM) до (11/10/2011 12:00:00 AM) с 1 минутой компенсировать каждую итерацию.
3. Begin синтаксического анализа данных:

- Foreach минуту (время выборки):

- датчик Еогеасп на улице «А»

--- Еогеасп событие

--- - если это событие было записано с помощью текущего датчика; И образец времени лежит между прибытием автомобиля и временем отправления, ТОГДА добавьте +1 к заполнению за эту минуту

---

Статистика о времени выполнения:

• времени SQL-запросов: ~ 260ms
• РНР времени Exec: 33.1s
• Количество временных выборок: 1440 (т.е. количество минут в 24-часовой цикл)
• Количество датчиков алгоритм должен был иметь дело с: 49
• Количество событий алгоритм должен был иметь дело с: 508

Я был в состоянии получить информацию о том, сколько автомобилей было припаркован на улице в заданную минуту, поэтому я могу легко построить его с помощью линейной диаграммы.

У меня такое чувство, что мой алгоритм не очень эффективен/умный. Я понимаю, что для большей временной шкалы мне нужно уменьшить количество временных выборок. Однако я хотел бы знать, есть ли какой-либо возможный способ достижения этого без ущерба для временных образцов?

---

SQL QUERY ССЫЛКА

SELECT sensors.device_id, events.arrival_time, events.departure_time, events.duration 
FROM events, sensors 
WHERE 
    STR_TO_DATE(arrival_time, '%d/%m/%Y %r') >= STR_TO_DATE(:start_time,'%d/%m/%Y %r') && 
    STR_TO_DATE(arrival_time, '%d/%m/%Y %r') <= STR_TO_DATE(:end_time,'%d/%m/%Y %r') && 
    events.device_id = sensors.device_id && 
    sensors.street_name= :street_name && 
    sensors.street_1 = :street_1 && 
    sensors.street_2 = :street_2 

PHP CODE ССЫЛКА

//TIME RANGE 
$start_time = "10/10/2011 12:00:00 AM"; 
$end_time = "11/10/2011 12:00:00 AM"; 

//SETUP ARRAYS FOR PLOTTING 
$x_time = array(); 
$y_occupancy = array(); 

//ITERATE THROUGH TIME 
for($i=strtotime($start_time); $i<=strtotime($end_time);$i+=60) { 

    $current_time = date("d/m/Y h:i:s A",$i); echo "<br>"; 

    $current_occupancy = 0; 

    //ITERATE THROUGH SENSORS 
    foreach($sensors as $sensor) { 

     //ITERATIVE THROUGH EVENTS 
     foreach($events as $event) { 

      //CHECK IF THIS SENSOR IS ACTIVE AT THIS EVENT 
      if (($sensor->device_id == $event->device_id) && (strtotime($current_time) >= strtotime($event->arrival_time) && strtotime($current_time) <= strtotime($event->departure_time))) { 
       $current_occupancy++; 
      } 

     }//end event iterations 

    }// end sensor iterations 

    $x_time[] = $current_time; 
    $y_occupancy[] = $current_occupancy; 

}// end time iterationS 



//SHOW TIME VS OCCUPANCY 
for($i=0; $i<count($x_time);$i++) { 
    echo $x_time[$i]; echo " "; echo $y_occupancy[$i]; echo "<br>"; 
} 

Answer 1

struct MyIterator 
{ 
    Iterator i; 
    DateTime t; 
} 

struct DataPoint 
{ 
    DateTime t; 
    int count; 
} 

List<DataPoint> CalculateIntervalCount(List<List<Interval>> series) 
{ 
    initialise min-heap H 
    foreach (List<Interval> S in series) 
    { 
     Iterator i=S.begin(); 
     H.push(new MyIterator(i, i.ArrivalTime)); 
    } 
    int count=0; 
    List<DataPoint> result=new List<DataPoint>(); 
    while(!H.emtpy()) 
    { 
     Iterator min= H.pop(); 
     if(min.t==min.i.ArrivalTime) 
     { 
      ++count; 
      result.Add(new DataPoint(min.t, count)); 
      H.push(new MyIterator(min.i, i.DepartureTime); 
     } 
     else 
     { 
      --count; 
      result.Add(new DataPoint(min.t, count)); 
      if (can advance min.i) 
      { 
       H.push(new MyIterator(min.i, i.ArrivalTime); 
      } 
     } 
    } 
    return result; 
} 

Объяснение:

CalculateIntervalCount - это функция, которая берет список интервальных рядов и возвращает серию, которая дает количество интервалов в момент времени t.

Предполагая, что у вас есть «стандартная» конструкция итератора для списка, и итератор знает, как продвигаться вперед и знает, как проверить, доходит ли до конца, MyIterator - это обтекание «стандартного» итератора с дополнительным полем DateTime который либо принимает значение времени ArrivalTime или DepartureTime интервала.

Мини-куча H использует MyIterator.t для сравнения между двумя объектами MyIterator.

Алгоритм просто реализует то, что я описал в своем комментарии. Он должен работать в O (n lg k) времени, где k - число интервальных рядов, n - количество интервалов в общем по всем сериям.