碰到一个颇有难度的算法问题

tristone

工作当中遇到的，不是面试，不过自己觉得很有意思，因为挠了很长时间头皮还是没找到好的解决办法。发上来看看大家有啥高见。


需要按天为单位处理大量的数据。每个数据元素有一个时间戳，在一天里是随机分布的。由于处理能力有限，因此需要限定每批处理的数目在一个合理的范围内（比如说1000条，正负100），同时又要保证处理完一天的所有元素。现在有一个函数count(a, b)可以快速取得时间点a和b之间的元素数量。处理函数process(a, b)对a和b时间点之间的元素进行处理。

当然，如果取得一天当中每一秒的元素数量，然后对时间积分，肯定能简单的达到目的，但是这个代价太大了。我现在希望能够有一个最优或者次优的算法能够实现。最好是python的。

tristone

我其实已经想到一个算法，但是实现起来不是很容易，感觉写出来的代码也不干净，所以想听听大家还有什么新颖的解决方案。

woodheadz

你的意思是count本身也会比较耗资源？

tristone

woodheadz 发表于 17-7-2013 17:16

                               
登录/注册后可看大图

你的意思是count本身也会比较耗资源？

其实count本身在数据库里有一个索引，所以速度还可以。但是对每一小段时间平均做count的做法比较傻吧？如果对每一秒做count，一天有 24 * 3600秒。。。。。

woodheadz

tristone 发表于 17-7-2013 17:22

                               
登录/注册后可看大图

其实count本身在数据库里有一个索引，所以速度还可以。但是对每一小段时间平均做count的做法比较傻吧？如 ...

想了下，你看这个算法如何？
调用 pickTime(上次处理截止时间, 0，1小时）就可以获得下次该处理到的时间。

function pickTime(startTime, duration, offset){
        if(duration > 1day){
                return startTime + 1day;               
        }
        if(duration < 0){
                return pickTime(startTime, 0, 0.5*abs(offset));
        }

        duration += offset;
        var endTime = startTime + duration;
               
        var n = count(startTime, endTime);
        if(n - 1000 > 100){               
                if(offset>0){
                        offset *= -1/2;
                }
        }
        else if(n-1000 < -100){
                if(offset<0){
           offset *= -1/2;
        }
        }
    else
       return endTime;

    return pickTime(startTime, duration, offset);
}

woodheadz

woodheadz 发表于 17-7-2013 17:38

                               
登录/注册后可看大图

想了下，你看这个算法如何？
调用 pickTime(上次处理截止时间, 0，1小时）就可以获得下次该处理到的时 ...

如果在你数据库的一个最小时间粒度内会出现超过1100条数据，那么这个算法就会堆栈溢出。真有这种情况加几个判断就可以。

classtom

两个字：
抽象。

v8fans

感觉这是经典simplify问题的一种。

问题集合A：  含有海量有序元素
解子集合B：  含有精简的有序元素，并符合一个预定义的规则
规则：  给定任意相邻 Bn,Bn-1,  count(Bn, Bn-1) < 1000

结果很显然 = proccess（集合B）

实现算法有很多，主要看count函数的特性，O(n)，O(logn)还是O(1)，以及规则是精确还是模糊的。
其中一个常用的：
http://en.wikipedia.org/wiki/Ram ... 93Peucker_algorithm

把distance check变成你的count check就可以了。这个算法是递归的，我用python，cython和C都实现过。

doudou720

aha good work mate

mason00

count(a,b)>1000的话二分，递归count(a, （a+b)/2), count((a+b)/2,b)

ricowang

v8fans 发表于 17-7-2013 20:45

                               
登录/注册后可看大图

感觉这是经典simplify问题的一种。

问题集合A：  含有海量有序元素

v8 is nice

chen_edward

真是高手如云，我都没看明白问题问的是什么。

freeAus

tristone 发表于 17-7-2013 17:22

                               
登录/注册后可看大图

其实count本身在数据库里有一个索引，所以速度还可以。但是对每一小段时间平均做count的做法比较傻吧？如 ...

Use "counting sort" first since 24 * 3600 is not that big?

darrenlee

我第一反应也是二分,和@mason00一样
不过@v8fans给的算法换成count效率可能会有问题吧??

tristone

下面是我写的python代码，还没测试过

1. 
   
2. 
   
3.         REQ_MAX = 1000 + 100
   
4.         REQ_MIN  = 1000 - 100
   
5.         all_days = list(date_range(start, end))
   
6.         for day in all_days:
   
7.                 midnight        = datetime.datetime.combine(day, datetime.time(0))
   
8.                 tomorrow        = midnight + datetime.timedelta(days=1)
   
9.                
   
10.                 c = count(midnight, tomorrow)
    
11.                 count_map = [(midnight, tomorrow, c)]
    
12.                
    
13.                 cur_order_count = 0
    
14.                 while len(count_map) > 0:
    
15.                         #find a good time period to process
    
16.                         (start_time, end_time, count) = count_map.pop(0)
    
17.                         while cur_order_count + count > REQ_MAX
    
18.                                 #split in half
    
19.                                 new_end_time = start_time + datetime.datetime.timedelta(seconds= (end_time - start_time).seconds / 2 )
    
20.                                 new_count = count(start_time, new_end_time)
    
21.                                 count_map.insert(0, (new_end_time, end_time, count - new_count))
    
22.                                 count_map.insert(0, (start_time, new_end_time, new_count))
    
23.                                 count = new_count
    
24.                        
    
25.                         cur_order_count += count
    
26.                         if cur_order_count > REQ_MIN or len(count_map) = 0:
    
27.                                 cur_order_count = 0
    
28.                                 #get the orders
    
29.                                 process(start_time, end_time)
    

复制代码

这个问题确实很像v8fans描述的。但是他给的算法貌似在我的这个场合有点问题。因为count(a, b)虽然不是很消耗资源，但是每次也需要几秒钟。process(a, b)最长可以到100秒，所以我希望用尽可能少的count()次数达到有效处理的目的。

我的算法用的是二分法，因为我觉得在完全随机的情况下这个应该是最优了。没有用递归，而是用了一个堆栈来保存（a, b, count），确实类似于一个线段的集合。每次开始处理前不断的出栈直到当前count大于处理的最低门槛或者空栈。如果高于处理最大值，二分时间，把前后两段压栈，然后接着看二分后的第一段是否符合要求。

tristone

tristone 发表于 18-7-2013 09:50

                               
登录/注册后可看大图

下面是我写的python代码，还没测试过这个问题确实很像v8fans描述的。但是他给的算法貌似在我的这个场合有点 ...

呃上面的算法有有个小问题，处理的时候start_time不对。应该用另一个列表存储所有未处理的段，然后当count符合要求时取第一个开始时间。

woodheadz

tristone 发表于 18-7-2013 09:50

                               
登录/注册后可看大图

下面是我写的python代码，还没测试过这个问题确实很像v8fans描述的。但是他给的算法貌似在我的这个场合有点 ...

咱俩算法本质上是差不多的，都是折半查找法，时间复杂度一样。只不过我用递归，而且是伪代码所以看起来稍微简洁些。
但如果我的算法里初始的offset设置的比较好的话，可能会比你少调用几次count哦

tristone

woodheadz 发表于 18-7-2013 10:24

                               
登录/注册后可看大图

咱俩算法本质上是差不多的，都是折半查找法，时间复杂度一样。只不过我用递归，而且是伪代码所以看起来稍 ...

呵呵，其实Python的代码比类C的伪代码还要简洁，你再仔细看看，两段代码长度是一样的，python的代码包含了所有数据结构处理。

至于时间复杂度，递归的一个缺点是，前一次count查询的结果都被丢弃了没有加以利用，所以效率不见得比堆栈高。尤其是你可以考虑一下如果每天的数据都少于1000的情况。

我觉得这个问题最难的地方是在于寻找合适的数据结构来有效存储和处理信息。

woodheadz

tristone 发表于 18-7-2013 10:39

                               
登录/注册后可看大图

呵呵，其实Python的代码比类C的伪代码还要简洁，你再仔细看看，两段代码长度是一样的，python的代码包含 ...

所以我说在设置了适当的初始offset的情况下嘛。我这个算法的一个好处就是可以通过参数调优，你把初始offset设成1天，再把函数修改为调用process而不是返回endtime， 那么就是你的算法得递归版。
我们思路不同，我得这种查找方式在数据虽然分布随机，但第一量很大，第二总体分布的不均匀程度不是特别大情况下会有很好的效果。
你的方式在数据分布极为不均匀的情况下可能会有更好的表现。

tristone

woodheadz 发表于 18-7-2013 10:52

                               
登录/注册后可看大图

所以我说在设置了适当的初始offset的情况下嘛。我这个算法的一个好处就是可以通过参数调优，你把初始offs ...

其实我的也可以，只要一开始在堆栈里面放进几个count()的结果就可以了。而且如果预先知道pattern，还可以放进比如0:00 - 8:00，8:00 - 9:00， 9:00 - 10:00，10：00 - 14:00，14:00 - 23:59:59。完全非线性的。

这个算法实际处理的是证券市场的order，因此在大多数交易日，数据是集中在上下午开市和关市前后一两小时的，但是例外也有不少。还有在非交易日，竟然也有可能有数据（系统设计比较脑残，没办法）。而且不同客户的数据量相差非常之大，所以我不得不想到如何有效处理所有情况。

superopengl

问题描述很模糊，提供的信息不足以搞清楚怎么优化。从描述上看不像是个很有难度的问题，只是很多point没说清楚。
1. 数据的时间戳是不是一定严密递增的？（有没有下午插入的数据的时间戳是上午或昨天或去年的？）
2. 每次所处理的数据1000+-100是否是互不相关的？（我猜应该是互不相关的）
3. 执行count和process是realtime执行还是scheduled task执行？
4. count读和process写是同一个系统（DB）还是不同的系统（DB）？
5. count和process是在同一server上跑还是不同server？两个方法的通信是inprocess memory还是其他DB/storage/queue/messaging？
6. count和process是否可以并行处理？Multi-threading或Distributed process?
7. 另外所说的“处理能力有限”指的是什么，是memory不够还是什么原因？是时间不够还是空间不够？（运用时空互换原理加以解决）
8. 还有count方法慢，index的设计是否有问题，有没有可能改善index或用其他方法提高性能？

另外根据LZ的描述，只有count和process两个API吗？感觉这两个方法的设计很白痴，必须每次用count去探测返回的数量是不是在900到1100之间，可能要探测N次才能合法调用一次process。为什么count不返回所有时间戳Array，然后程序切割成N段，这样就是探测一次，就能调用N次process。

如果数据间没有相关性，那count和process很容易并行，比如24个threads/process/server，每个处理1小时时间窗内的数据，切割好后（每个900到1100之间）再交给X个worker thread同时调用process。

还有如果必须用count去探测返回值是否在900-1100之间的话，可以采取智能调整时间窗——时间窗小了就乘2，大了就除以2（也可以根据经验乘除1.5，1.8等）。
比如以毫秒为单位的话,
var timeWindow = 1000  // 1秒
while(startTime is in today){
    var dataCount = count(startTime, startTime + timeWindow)
    if(900 <= dataCount <= 1100) {
        call process(startTime, startTime + timeWindow)
        startTime = startTime + timeWindow
    }else if (dataCount < 900){
        call process(startTime, startTime + timeWindow)
        startTime = startTime + timeWindow
        timeWindow = timeWindow * 2;
    }else if (dataCount > 1100){
        timeWindow = timeWindow / 2;
    }
}

总之如果数据量很大的话，优先考虑并行算法吧，单线程的如论如何都有资源限制浪费发生。

tristone

superopengl 发表于 1-8-2013 11:35

                               
登录/注册后可看大图

问题描述很模糊，提供的信息不足以搞清楚怎么优化。从描述上看不像是个很有难度的问题，只是很多point没说清 ...

数据存储在数据库里的时候，并行是无法提高性能的。除非用的是NOSQL数据库，不过这个远远超出了这个问题的范围。“返回一个包括所有时间戳的数组”确实是一个最简单的办法，但是最多可以有八千多万条记录，所以我一开始就排除了，而且如果有更多数据呢？“时间窗乘2除以2”大家好像都想到了，也确实是我最终用的。就是你的代码并未保证最小处理数量，每次低于900都会调用一次process，理想情况是除非是最后一批数据不然都应该在900到1100之间。

之所以问题描述的模糊，是因为想focus在算法上。因为不然的话要考虑的因素太多。哪怕并行的话，也要考虑每次处理的数据尺寸大小和CPU的L2 Cache大小，还有alignment之类的，不是么？再说，多线程不见得比单线程快。投行用的kdb（脚本语言），比C++写的多线程通常快出许多倍。确实是用了CPU的并行处理功能，但是是单线程的。

奔腾

这样的问题也不需要考虑太复杂的算法。

一般碰上这种大数据的问题，最麻烦的往往是数据处理完毕后删除等操作导致的不同步，所以楼主可以看看这样是否可行：
1）假设原始数据是一个列表或者数组，那么完全可以在处理完毕前不动它们。
2）为了对数据分组处理，可以建立一系列索引列表。例如一天24小时可以对每小时的数据分别创建一个列表List<int>；
3）遍历原始数据，按照其时间戳将其索引放到这24个索引列表中，这个过程一次就可完成。
4）对于24个索引列表，分别对其中索引项代表的数据做处理，应该得到希望的结果。
5）处理完毕后原始数据和索引列表都可以删除了。

tristone

奔腾 发表于 1-8-2013 21:46

                               
登录/注册后可看大图

这样的问题也不需要考虑太复杂的算法。

一般碰上这种大数据的问题，最麻烦的往往是数据处理完毕后删除等 ...

呵呵多谢！

其实这个问题纯粹是我自己没事找事。最后我的解决方案也没被采用。因为发现process()的性能能够满足要求处理一天的数据（但是一星期呢？一年呢？任意时间段呢？纯粹是自己没事瞎想，呵呵）。

按照小时定期索引数据的问题是，没有办法适应随机数目的数据。比方说，从午夜到开市（0-9点）几乎没有数据，关市以后（15点～）也几乎没有数据，而所有的数据有可能都集中在几个小时内。甚至某天因为市场上的某个事件造成交易量激增。这些都是不可预见的。另外，如我前面所说，数据根据客户的规模也有很大的变化，大小之间相差数百倍也属于正常。一些抄捷径的办法不可避免的要人为的去调整参数，而且不能保证处理成功。

其实这个问题的真正挑战在于，面对完全未知数目的数据，找到一个确保能顺利处理的方法。并且尽可能的提高处理的效率。

对于我的这个具体化的case，其实最佳最高效的解决方案是每生成一条数据时一并调用process()。不过因为process()并非critical的功能，所以这个方案不可行。或者定期处理其实也可以，不少数据报表软件比如cognos就是这么做的，不过也被领导否决了，呵呵。

nihaowohao

通过讨论，共同提高。
欢迎这样的帖子越来越多。

ubuntuhk

信息量很高

woodheadz

tristone 发表于 2-8-2013 10:00

                               
登录/注册后可看大图

呵呵多谢！

其实这个问题纯粹是我自己没事找事。最后我的解决方案也没被采用。因为发现process()的性能 ...

人为调整参数我倒觉得问题不大，现在很多算法都有参数调优的设计，这是一种很常见的优化方法。 楼上有人提到可以在折半的基础上考虑不除以2而是除以1.8，1.7，1.6的idea，也算是一个进一步参数优化的想法。
我的算法只是随手写的伪代码，没经过调试。 你发现了什么漏洞会导致处理失败吗？

tristone

woodheadz 发表于 4-8-2013 16:18

                               
登录/注册后可看大图

人为调整参数我倒觉得问题不大，现在很多算法都有参数调优的设计，这是一种很常见的优化方法。 楼上有人 ...

1.8，1.7，1.6是错的。我一开始就想到了，但是只要数据分布是随机的，前一半／后一半包含合适数量的数据的概率是相等的。

你的代码我没试，因为你回的时候我那段已经写好了，而且性能还算满意。

tristone

我前面也许没说的很明白。我觉得这个问题的真正挑战在于。

1   有一个算法能够保证处理任意数量并且随机分布的数据。这个是基本要求，也比较简单，代码我几分钟就写好了

2  用尽可能少的重试次数找到合适的处理时间段。时间折半／加倍是比较直觉的方法。
3  实际应用当中数据的分布有一个大致的趋势。一天当中早9－10点，下午12、15点。但是也有可能不是这样。是否有个好的办法能够使得代码能够学习这种模式？按照猜测的分布使用预定义的模式有可能由于参数不准确导致效率不佳。此外，周末一般没有或者只有很少数据，这种情况下交易日模式效果不佳。当然可以根据日历区分交易日与非交易日，只是觉得这种方式比较傻。