如何加快找到时间重叠的算法？

2024-06-03 • 问答

我有一个包含4个属性的数据集：

一个名为“ id”（整数）的id属性
一个名为“ group”（整数）的属性
录取时间称为“ aankomstdt”（日期时间）
放电时间称为“ ontslagdt”（日期时间）

数据集如下：

id    group          aankomstdt                   ontslagdt
 1   A         Thu Nov 14 04:31:00 CET 2019 Thu Nov 14 09:43:00 CET 2019
 2   A         Thu Nov 14 05:38:00 CET 2019 Thu Nov 14 06:19:00 CET 2019
 3   A         Thu Nov 14 05:52:00 CET 2019 Thu Nov 14 09:14:00 CET 2019
 4   A         Thu Nov 14 05:54:00 CET 2019 Thu Nov 14 10:02:00 CET 2019
 5   B         Thu Nov 14 06:06:00 CET 2019 Thu Nov 14 11:22:00 CET 2019

我想计算同时被承认的例子的数量。因此，新的属性应向我提供在他/她的入院时间范围内每个患者（id）的入院患者数。我创建了以下工作代码：

import pandas as pd
import numpy as np
from datetime import datetime



admission_time = "aankomstdt"
discharge_time = "ontslagdt"
group = 'group'
date_format = '%Y-%m-%d %H:%M:%S'
path = 'D:/Lionel/Formations_DataScience/Rapidminer/Tests_Rapidminer/count_overlaps_sven.xlsx'


def convert_to_datetime(a) :

  a = datetime.strptime(str(a),date_format)
  return a


def interval_overlaps(a,b):
  return min(a[discharge_time],b[discharge_time]) - max(a[admission_time],b[admission_time]) > np.timedelta64(-1)


def count_overlaps(df1):
  return pd.Series([df1.apply(lambda x: interval_overlaps(x,df1.iloc[i]),axis=1).sum() - 1 for i in range(len(df1))],df1.index)
  #return pd.Series([df1.apply(lambda x: interval_overlaps(x,axis=1).sum() - 1 for i in range(len(df1))])
def rm_main():

  data = pd.read_excel(path)
  data[admission_time] = data[admission_time].apply(convert_to_datetime)
  data[discharge_time] = data[discharge_time].apply(convert_to_datetime)
  data["count"] = data.groupby(group).apply(count_overlaps).values
  return data

但是我的原始数据集有大约7万个示例，因此我估计计算时间约为1个月（24h / 24）。我的问题是：Python中是否有解决方案可以大大加速该算法？

谢谢

经典之作是当您只想要一个总和。

召回方式如下：对于每一行，请考虑两个事件：

{t：row.startAt，kind：'start'}，
{t：row.endAt，kind：'end'}

制作大量事件，然后按t asc排序

best = 0
pool = 0
foreach event:
  if event.kind == 'start':
    pool++
    if pool > best
      best = pool
  else
    pool--

同时访问患者的最大值存储在最佳位置。

说明类似于：

活动开始时，我们会在现有访客的基础上再增加一个访客
事件结束时，访客已离开游泳池。
我们只想跟踪池的长度

在您的情况下，wa可以适应：将一个池与每个患者相关联。

在下面考虑一下病人池：[patient.id] => maxVisitors

patientPool = {}
pool = 0
foreach event:
  if event.kind == 'start':
    patientPool[event.id] = pool
    pool++
    forall id in patientPool
      if pool > patientPool[id]
        patientPool[id] = pool //eventually think about giving a reference to your row for the count instead..
  else
    pool--
    delete patientPool[event.id]

在以下用于说明目的的标记（js）中，70k行（随机）大约需要15秒。对于python，请参考上面的伪算法（相差不大）

我只测试了以下样本的准确性。

let seed = 4;
function random() {
    let x = Math.sin(seed++) * 10000;
    return parseInt((x - Math.floor(x))*1000);
}

let qs = Array(10).fill(0).map(random).reduce((qs,t,i)=>{
  return (i%2 === 0 ? qs.push([{ t,i: i/2 }]) : qs[qs.length - 1].push({ t,i: (i - 1)/2 })),qs
},[]).map(([a,b])=> a.t < b.t ? [{ ...a,open: true },b] : [{ ...b,open:true},a])

function go(qs){
  const events = qs.flatMap(x => x).sort((a,b) => a.t - b.t)
  //patients is an array where patients[i] maps to patient.id == i
  const patients = Array(events.reduce((acc,x)=> Math.max(acc,x.i),0) + 1)
  const patientPool = new Set
  let pool = 0
  events.forEach(ev => {
    if (ev.open) {
      if (!patientPool.has(ev.i)) {
        patients[ev.i] = pool
        patientPool.add(ev.i)
      }
      pool++
      for(let patientI of patientPool){
        if (pool > patients[patientI]) {
          patients[patientI] = pool
        }
      }
    } else {
      pool--
      patientPool.delete(ev.i)
    }
  })
  return patients
}
console.time('disp')
const res = go(qs)
console.log('go',qs,res)
console.timeEnd('disp')

如何加快找到时间重叠的算法？

jiao860809 回答：如何加快找到时间重叠的算法？

大家都在问