最近接手了一个关于中学生家庭视频教育的项目，其中核心的部分要求统计用户的视频看时长，并且管理员可以分别查看某一地区或者学校总的观看时长以及上月或上周的观看时长，并且视频的观看时间要求合并及去重复，也就是说一个用户如果多次不同时间重复观看同一视频，是不计入总的观看时间的。业务复杂的地方在于统计观看时间的合并以及去重，以及实时视频观看数据上报平台的搭建以及数据统计服务的搭建（客户端每5S上报一次请求数会很大）。
对于某一用户视频观看时长的合并及去重可以简化为时间区间的合并以及去重，客户端每次上报，都会在服务端记下本次上报的视频开始时间以及结束时间，那么就可以看成一个数字区间，比如第一次上报的是[0, 10] 第二次用户拖动了一点观看，上报的区间是[2,11]，第三次[11,23] ，第四次[13,45] ，那么最终的观看时间区间为 [0,45]，考虑到极端上报情况，区间可能是间断的[0,5] [15,21] [9, 20] 这时最终去得合并后得到[0,5] [9,21]，这么来看的话我们就需要找到一个最优的算法来解决区间的去重及合并。由于每5S上报一次 所以一个视频看完时可能最终会报出成百上千个时间区间。这时候就要求算法的复杂度越小越好。
如果把所有的上报区间看成一个二维数组。先将区间数组排序按开始时间排序 比如[0,5] [15,21] [9, 20]排序后是[0,5] [9, 20][15,21] 然后再将第一个区间的结束时间与第二区间的开始时间进行比较，如果第一个比第二个大就合并，然后将第一个区间剔除，依次类推直到合并到没有重复的区间为止，那么算法就很明显了这其实是一个递归问题 。
下面给出算法代码示例，算法的关键在于getUniqueList方法，大神们如果有更好的解决方案也可以在文章下评论，指导一下，哈哈。
<?php
/**
* Created by PhpStorm.
* User: Administrator
* Date: 2017/6/23
* Time: 11:41
*/
$test = new Test();
print_r($test->actionTest());
class Test
{
public function actionTest()
{
$data = [[0,9],[439,539],[439,539],[439,539],[439,539],[439,539],[439,569],[439,569],[439,569],[439,569],[439,569],[439,569],[439,569],[439,569],[439,569],[479,539],[479,539],[479,539],[479,539],[479,539],[479,539],[479,539],[479,599],[639,869],[639,869],[639,869]];
$uList = $this->getUniqueList($data, $uniqueList);
return $uList;
}
/**
* 获取不重复的观看时间区间
* @param $list
* @param $uniqueList
* @return array
*/
public function getUniqueList($list, &$uniqueList)
{
if(empty($list)) return $uniqueList;
$first = array_shift($list);
$newList = [];
$hasRepeat = false;
for($i = 0; $i < count($list); $i++)
{
$current = $list[$i];
//结束时间比当前开始时间大，合并时间区间
if(($first[1] + 1) >= $current[0])
{
$hasRepeat = true;
$row[0] = min($first[0], $current[0]);
$row[1] = max($first[1], $current[1]);
$first = $row;
}
else
{
$newList[] = $list[$i];
}
}
$uniqueList[] = $first;
//没有重复区间返回
if(!$hasRepeat && empty($list))
{
if(!empty($newList)) $uniqueList = array_merge($uniqueList, $newList);
return $uniqueList;
}
return $this->getUniqueList($newList, $uniqueList);
}
/**
* 二维数组按某个字段排序
* @param $data
* @param $field
* @param string $sort
* @return mixed
*/
protected function sortByField($data, $field, $sort = 'SORT_DESC')
{
if (empty($data))
return [];
$arrSort = array();
foreach ($data as $id => $row) {
foreach ($row as $key => $value) {
$arrSort[$key][$id] = $value;
}
}
array_multisort($arrSort[$field], constant($sort), $data);
return $data;
}
}
运行结果如下
Array
(
[0] => Array
(
[0] => 0
[1] => 9
)
[1] => Array
(
[0] => 439
[1] => 599
)
[2] => Array
(
[0] => 639
[1] => 869
)
)
最终结果是满足我们需求的，不重复的区间得到之后再循环数组相减，就可以得到这个用户总的不重复观看时间了，算法的复杂度为n的二次方，如果n是小于100的话，循环次数不超过1万次，如果将统计的定时任务设定为每隔5分钟（n = 60）统计一次观看时间，下次统计代入上次不重复区间n肯定是小于100的，所以总体算法复杂度还是不错的。
下篇文章中我将会给出视频统计平台的架构设计，如何在请求数较高的情况下低延时统计用户每天的不重复看视频时长，敬请期待哦。
网友评论