php - 是否有可能提高这种迭代算法的效率？

Question

我是一名研究人员，研究车辆 parking 行为和 parking 占用模式。我正在尝试编写一种高效且强大的算法来计算一段时间内的 parking 占用率。

这是我的故事:

我使用澳大利亚墨尔本市各地的地下 parking 传感器记录了 parking 数据。您可以在这里查看数据:https://data.melbourne.vic.gov.au/Transport/Parking-Events-From-Parking-Bays-With-Sensors/8nfq-mtcn ？。

我的初始任务是将这些数据绘制为时间序列图，以便我可以直观地分析不同时间段(天、周、月等)的 parking 位占用趋势。

该市各街道安装了 7,112 个传感器。每个传感器都会记录汽车到达和离开 parking 位时的数据(我们称之为“事件”)。从 2011 年到 2012 年，他们记录了 12,208,417 起事件。每个事件都是数据库中的一行，并且具有我感兴趣的以下列:

• 传感器 ID
• 到达时间
• 出发时间
• parking 时长
• 该传感器所在的街道

现在，我不想分别绘制来自每个传感器的数据，而是绘制固定时间间隔(秒、分钟、小时等)内属于街道的一组传感器的数据。因此，街道“A”可能有 10 个 parking 位(= 10 个传感器)，街道“B”= 12 个传感器，依此类推。

对于给定街道“A”的 (10/10/2011 12:00:00 AM) 到 (11/10/2011 12:00:00 AM) 之间的 24 小时时间序列图，以下是我所绘制的已完成:

使用 SQL

1. 通过运行 SQL 查询，检索给定日期之间位于街道“A”的传感器的所有事件

使用 PHP

在从 (10/10/2011 12:00:00 AM) 到 (11/10/2011 12:00:00 AM) 的时间循环上迭代，每次迭代偏移 1 分钟。

开始解析数据:

— 每分钟(时间样本):

——foreach 传感器位于街道“A”

——foreach事件

————如果当前传感器记录了此事件，并且时间样本位于汽车到达和出发时间之间，则将这一分钟的占用率+1

<小时/>

有关运行时的统计信息:

• SQL 查询时间:约 260 毫秒
• PHP 执行时间:33.1s
• 时间样本数量:1,440(即 24 小时周期中的分钟数)
• 算法必须处理的传感器数量:49
• 算法必须处理的事件数:508

我能够获取给定分钟街道上停有多少辆车的信息，这样我就可以使用折线图轻松绘制它。

我感觉我的算法不是很高效/智能。我知道对于更大的时间范围，我需要减少时间样本的数量。但是，我想知道是否有任何可能的方法可以在不影响时间样本的情况下实现这一目标？

<小时/>

SQL 查询引用

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 代码引用

//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 是所有系列的间隔总数。