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


一个名为“ id”的ID属性(整数)
称为“组”的属性(整数)
录取时间称为“ 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, df1.iloc[i]), 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,种类:“开始”},
{t:row.endAt,种类:“ end”}


制作大量事件并按t asc对其进行排序

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


最好同时存储最多同时访问的患者。

解释类似于:


活动开始时,我们会在当前访客的基础上增加一个新访客
活动结束时,访客已离开泳池。
我们只想跟踪池的长度


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

下面考虑PatientPool:[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')

关于python - 如何加快找到时间重叠的算法?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/59349681/

10-13 02:58
查看更多