V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
ideacco
V2EX  ›  程序员

算法问题:平均入睡时间

  •  
  •   ideacco · 2019-01-11 17:33:30 +08:00 · 3765 次点击
    这是一个创建于 1904 天前的主题,其中的信息可能已经有所发展或是发生改变。

    最新项目有关看起来简单,却挺考验算法的题:

    用户 A 23:59 分入睡, 用户 B 0:01 分入睡, 用户 C 0:02 分入睡, 用户 D 23:58 分入睡,

    求 4 个人的平均入睡时间。

    结题思路: 通过圆形分布把时间换算成角度,算出平均值,再反推回时间。

    然而。。。。。要用代码实现出来貌似没那么容易……

    第 1 条附言  ·  2019-01-11 18:23:32 +08:00
    感谢大家的回复。
    这里有几个点没交代清楚的

    1,我们定义的睡眠时间是从起床时间的那一天算起的,比如 1 月 11 日 凌晨 1:20 分入睡,早上 8:20 分起床,那么入睡时间是 1/11 01:20 , 还有可能是 从 1 月 10 日晚上 23:20 分入睡。那么我的入睡时间 是 1/10 23: 20

    2. 跨天问题是核心,因为我们也不知道用户啥时候睡觉,有可能他是每天中午 12 点睡到第二天 凌晨 1 点(极端情况)

    3. 有用户 第一天早上 10 点睡,然后第二天下午 14 点睡(极端情况),这里有一个象限问题。
    49 条回复    2019-01-12 16:43:34 +08:00
    ideacco
        1
    ideacco  
    OP
       2019-01-11 17:34:30 +08:00
    大家有什么新奇思路可以出来聊聊
    Raymon111111
        2
    Raymon111111  
       2019-01-11 17:35:57 +08:00   ❤️ 1
    啥?

    把时间换成 unixtime 直接求平均的问题在于?
    TomatoYuyuko
        3
    TomatoYuyuko  
       2019-01-11 17:38:18 +08:00
    用几何模型(求圆的弧长再求中点)做或者设立数轴取中点(自主选择方便计算的原点)
    初中数学题√
    yinjunjian0
        4
    yinjunjian0  
       2019-01-11 17:39:51 +08:00
    如果是具体时间 2018-01-01 23:59:00,直接转时间戳求平均
    如果是题目上 23:59 也可以拼接模拟日期转时间戳求平均
    reself
        5
    reself  
       2019-01-11 17:40:03 +08:00 via Android
    跨日了,需要定义和处理边界问题。
    Ediacaran
        6
    Ediacaran  
       2019-01-11 17:40:56 +08:00 via Android
    转时间戳就行有啥难的?
    jinhan13789991
        7
    jinhan13789991  
       2019-01-11 17:41:05 +08:00
    把具体时间转换成时间戳,全部相加然后 /总用户数量。
    菜蔬学前,只能想到这里了
    ppyybb
        8
    ppyybb  
       2019-01-11 17:41:49 +08:00
    我的理解: 最后需要知道平均在 00:01 或者 23:59 入睡这样一个指标

    以零点作为分界线,只计算 offset
    最后得到一个平均 offset
    偏移一下就知道了
    ShineSmile
        9
    ShineSmile  
       2019-01-11 17:43:51 +08:00
    用 30 小时计时法解决跨日问题吧 (笑
    bxb100
        10
    bxb100  
       2019-01-11 17:46:19 +08:00
    不能换成时间戳?
    baicheng10
        11
    baicheng10  
       2019-01-11 17:51:41 +08:00
    计算的问题楼上的都行吧。我倒是觉得得看如何定义业务的吧,比如三班倒,中午 12 点睡着,这个怎么算的……
    lhx2008
        12
    lhx2008  
       2019-01-11 17:53:34 +08:00 via Android
    转成分就可以,基准容量是 24*60*2

    如果是 23:XX 入睡,初始值为 23*60+XX
    如果是 0:02 入睡,初始值为 24*60+2

    终值直接计算,如果小于初值,则加 24*60

    结果是终值减初值
    lhx2008
        13
    lhx2008  
       2019-01-11 17:55:30 +08:00 via Android
    当然,业务里面,转时间戳就行了,这个根本用不上
    xnode
        14
    xnode  
       2019-01-11 17:56:05 +08:00
    换成时间戳 先排序 然后 取出这些时间戳的平均值 不就是平均时间?
    lhx2008
        15
    lhx2008  
       2019-01-11 17:58:04 +08:00 via Android
    #12
    0:02 入睡不用加 24*60 也可以
    xpresslink
        16
    xpresslink  
       2019-01-11 18:05:37 +08:00
    告诉楼主一个基本常识不带日期的时间是不具备任何意义的。0:01 并不能知道是今天还是昨天。
    有了日期的时间就非常简单了。

    先找出最早的一个时间 min_time, 然后求其它每个时间和这个 min_time 的时间差 offset,
    求这个差的平均值 offset_avg,然后 min_time+offset_avg

    小学二年级数学水平就可以了吧?
    sjw199166
        17
    sjw199166  
       2019-01-11 18:08:10 +08:00
    想象成一维坐标点呢? 0 点在坐标点中心 单位为分钟 每个人睡眠时间就是睡觉时间点到 0 点的长度 靠左边是负数 右边是正数 最后计算平均值
    dlutdanielkong
        18
    dlutdanielkong  
       2019-01-11 18:08:36 +08:00
    对于凌晨这种的值,加 24,得出来的平均数如果大于 24,再减去 24,
    不知道可以吗
    shellj
        19
    shellj  
       2019-01-11 18:18:42 +08:00
    @xpresslink 确实,今天的 0:01 和今天的 23:59 平均在中午,但昨天的 23:59 和今天的 0:01 平均就不一样了
    sjw199166
        20
    sjw199166  
       2019-01-11 18:26:46 +08:00
    @shellj 如果换成坐标不就 ok 了么
    dremy
        21
    dremy  
       2019-01-11 18:28:46 +08:00 via iPhone
    这种只应该统计正常入睡情况吧,那些很反常的比如早上或者上午睡,下午或者晚上才醒很明显应该作为异常数据排除,定义一个类似的业务规则就好了
    across
        22
    across  
       2019-01-11 18:29:21 +08:00
    咦,刚好想做个闹钟 app··· 进来学习学习
    ideacco
        23
    ideacco  
    OP
       2019-01-11 18:29:40 +08:00
    @Ediacaran 今天 18:00 入睡的,然后第二天你又 18:00 入睡的。。。。转化成时间戳再平均,你确定还是 18:00 ?
    Ediacaran
        24
    Ediacaran  
       2019-01-11 18:35:11 +08:00 via Android
    @ideacco 多人同日当然可以时间戳。跨日用 30 小时值换算不就得了
    across
        25
    across  
       2019-01-11 18:38:00 +08:00
    设定当天入睡标准时间为 00:00,实际入睡时间是相对于零点的偏移量 X 分钟。
    X 范围在 [-24 * 60,24*60] 之间,关键这里应该要进行数据筛选,比如多次入睡取绝对值最小的一个,醒来时间应该在入睡后绝对值最小的那个,或者不需要前后 24 个小时偏移值。
    padeoe
        26
    padeoe  
       2019-01-11 18:38:51 +08:00 via Android
    多人同日用时间戳算平均,得出特定某日所有人平均的入睡时间 t,再对所有日的 t 加和除以总天数,获得多人多日平均
    liprais
        27
    liprais  
       2019-01-11 18:39:55 +08:00
    回去想明白了怎么定义入睡时间再来问
    ahsiu
        28
    ahsiu  
       2019-01-11 18:42:39 +08:00
    一共有 24 个人,每一个小时整点都有人入睡,请问这二十四个人的入睡平均时间是几点?
    necomancer
        29
    necomancer  
       2019-01-11 18:43:45 +08:00
    circular mean
    ideacco
        30
    ideacco  
    OP
       2019-01-11 18:45:11 +08:00
    @liprais 入睡时间是根据醒来时间 减去睡眠时长的。 比如醒来时间是 1/11 日 8:00 ,睡眠时长是 9 小时,那么你入睡时间就是 1/10 23:00
    laqow
        31
    laqow  
       2019-01-11 18:45:34 +08:00 via Android
    时刻和时长是两个量啊,分两个变量,一个入睡时间,一个睡眠时长存起来不行吗?至于分析,先有一定数据基础以后看看两个量的分布,如果差的很大就聚个类分别分析不就好了
    ballshapesdsd
        32
    ballshapesdsd  
       2019-01-11 18:45:53 +08:00
    用圆上的点表示,矢量相加后求角度
    ideacco
        33
    ideacco  
    OP
       2019-01-11 18:47:27 +08:00
    @ballshapesdsd 对的兄弟,这是一个统计学上的问题,求到了角度再反推回去时间才行,然而貌似不知道咋写的。
    necomancer
        34
    necomancer  
       2019-01-11 18:47:28 +08:00
    from scipy.stats import circmean
    circmean(t, high=12,low=0)
    或者 24 小时制:
    circmean(t, high=24,low=0)
    necomancer
        35
    necomancer  
       2019-01-11 18:48:35 +08:00
    @ideacco 那个东西就叫 circular mean,具体看喂鸡百科。想自己写用 arctan2 函数。
    l00t
        36
    l00t  
       2019-01-11 18:49:32 +08:00   ❤️ 1
    我觉得你的圆形算角度的做法挺好的啊。后面的三个难点是想多了吧。你不是只要具体的时间点吗,那管它是哪天睡的…… 全部去掉日期,只保留时间点,放到圆上计算就行。每天中午 12 点睡到早上一点,那也是 12 点入睡,为什么要管它是哪天的 12 点呢?第一天早上 10 点睡,第二天下午 14 点睡,平均入睡时间显然应该是 12 点嘛,不然你觉得应该是几点?
    ideacco
        37
    ideacco  
    OP
       2019-01-11 18:51:27 +08:00
    @l00t 是的是的。
    ideacco
        38
    ideacco  
    OP
       2019-01-11 18:51:44 +08:00
    @necomancer 感谢,学到了。
    necomancer
        39
    necomancer  
       2019-01-11 18:52:14 +08:00
    流程是先投影数据到角度 X->x in (0,2pi),然后求向量集 (sin(x),cos(x)) 的平均,然后用 arctan2 函数返回角度,根据周期再逆投影回数据。
    necomancer
        40
    necomancer  
       2019-01-11 18:54:02 +08:00   ❤️ 1
    抱歉,是向量集 (cos(x), sin(x)), arctan2(mean_sin, mean_cos) 这样调用。写差了。
    ideacco
        41
    ideacco  
    OP
       2019-01-11 19:14:58 +08:00
    找到了 一个挺好的资料 《圆形分布资料的统计分布》这个是上海第二医科大学的研究资料 地址 wenku.baidu 点 COM/view/55a343cba1c7aa00b52acbe5.html
    shm7
        42
    shm7  
       2019-01-11 19:23:06 +08:00 via iPhone
    平均的意思不就是转换成一个可估量的维度,求和再 /个数么?
    这个维度为啥是奇葩的时钟呢。你用通用时间不就好了,要么是毫秒级起始于 1970 的那个,要么你自己定义最靠前的用户当天 00 点么?时间转换应该很容易吧~
    shm7
        43
    shm7  
       2019-01-11 19:23:29 +08:00 via iPhone
    真看不出难在哪
    necomancer
        44
    necomancer  
       2019-01-11 19:23:55 +08:00
    scipy.stats.circmean 方法比较适用于中 /小规模高计算精度要求。大数据允许一定小偏差可以用 circular mean = main angle of 1st harmonic of density kernel 的方法搞定:

    1. 求密度分布:
    d, _ = histogram(t, bins=1000, range=(0,24)) # 24 小时制,划 1000 个格子,精度为 24/1000 小时
    2. 求 1st harmonics:
    w = np.exp(-2j*np.pi*np.arange(1000) / 1000)
    F1 = w.dot(d)
    3. 求主幅角 (0, 2pi)
    angle = np.angle(F1.conj())
    if angle < 0:
    ....angle += 2*np.pi
    4. 映射回平均值
    t_mean = 24 * angle / (2 * np.pi) # 起始点是 0

    这样空间复杂度小,算得快,数据量大的话这个方法好一些。
    necomancer
        45
    necomancer  
       2019-01-11 19:28:29 +08:00
    两个方法本质是一样的,只是分布方法会引入划格子引起的偏差,不过数据量大,结果模糊个一丁点儿也就无所谓了吧。起始我倒是觉得这种问题排除那种每天随机抽点睡的傻逼,把时间做个转换:以每天 16:00 为 0:00,次日 16:00 为 24:00 (t=(t+16) %24),然后直接求平均再转化回来(tmean=(tmean+16)%24)就行了吧,运算的时候排除掉 18 点之前睡觉的就行了。结果很粗略但是算得快啊,毕竟大部分人睡觉时间挺恒定的。
    ideacco
        46
    ideacco  
    OP
       2019-01-11 20:00:27 +08:00
    @shm7

    import time

    Day1 = 1547823600 #18 日 23 点
    Day2 = 1547830800 #19 日 1 点
    Day3 = 1547913600 #20 日 0 点
    Day4 = 1548000000 #21 日 0 点

    Ave = int((Day1+Day2+Day3+Day4)/4)

    Time = time.localtime(Ave)
    dt = time.strftime("%Y-%m-%d %H:%M:%S",Time)

    print (dt)

    -------

    得到 2019-01-19 18:00:00

    有时间象限问题
    dayoushen
        47
    dayoushen  
       2019-01-12 13:24:49 +08:00 via Android
    先看表盘 12 小时的求解,a 在 1 点吃饭,b 在 11 点吃饭,那么“平均”吃饭时间是,(1+(11-12))/2 = 0,即把时间分成[0,6),[6,12)两段。比如 a 在 6 点,b 在 7 点,那么平均计算是,(6-12)-(7-12)/2 =-5.5 = 7.5。
    环形上加法平均是,把环形分成两半,0-middle,middle-max,1)如果数值大于等于 middle 则减去 max 变成负数,小于 middle 保持不变;2 )对 1 中结果做正常加法;3 )规整结果,如果结果为负数,则加上 max,否则输出正值。手机打字太墨迹。
    dayoushen
        48
    dayoushen  
       2019-01-12 13:30:52 +08:00 via Android
    6 和 7 例子,写错了,(-6+(-5))/2 =-5.5 +12 = 6.5 小时
    dingyaguang117
        49
    dingyaguang117  
       2019-01-12 16:43:34 +08:00
    这个问题和考勤很像,其实只要设定一个时间阈值就可以了, 比如早上 6 点前的,全部算到前一天
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2878 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 30ms · UTC 11:19 · PVG 19:19 · LAX 04:19 · JFK 07:19
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.