最近接手了一個關(guān)于中學(xué)生家庭視頻教育的項目寺渗，其中核心的部分要求統(tǒng)計用戶的視頻看時長，并且管理員可以分別查看某一地區(qū)或者學(xué)校總的觀看時長以及上月或上周的觀看時長叮盘，并且視頻的觀看時間要求合并及去重復(fù)猜绣，也就是說一個用戶如果多次不同時間重復(fù)觀看同一視頻灰殴，是不計入總的觀看時間的。業(yè)務(wù)復(fù)雜的地方在于統(tǒng)計觀看時間的合并以及去重掰邢，以及實時視頻觀看數(shù)據(jù)上報平臺的搭建以及數(shù)據(jù)統(tǒng)計服務(wù)的搭建（客戶端每5S上報一次請求數(shù)會很大）牺陶。
對于某一用戶視頻觀看時長的合并及去重可以簡化為時間區(qū)間的合并以及去重，客戶端每次上報辣之，都會在服務(wù)端記下本次上報的視頻開始時間以及結(jié)束時間掰伸，那么就可以看成一個數(shù)字區(qū)間，比如第一次上報的是[0, 10] 第二次用戶拖動了一點觀看怀估，上報的區(qū)間是[2,11]狮鸭，第三次[11,23] ，第四次[13,45] 多搀，那么最終的觀看時間區(qū)間為 [0,45]歧蕉，考慮到極端上報情況，區(qū)間可能是間斷的[0,5] [15,21] [9, 20] 這時最終去得合并后得到[0,5] [9,21]康铭，這么來看的話我們就需要找到一個最優(yōu)的算法來解決區(qū)間的去重及合并廊谓。由于每5S上報一次 所以一個視頻看完時可能最終會報出成百上千個時間區(qū)間。這時候就要求算法的復(fù)雜度越小越好麻削。
如果把所有的上報區(qū)間看成一個二維數(shù)組蒸痹。先將區(qū)間數(shù)組排序按開始時間排序 比如[0,5] [15,21] [9, 20]排序后是[0,5] [9, 20][15,21] 然后再將第一個區(qū)間的結(jié)束時間與第二區(qū)間的開始時間進行比較，如果第一個比第二個大就合并呛哟，然后將第一個區(qū)間剔除叠荠，依次類推直到合并到?jīng)]有重復(fù)的區(qū)間為止，那么算法就很明顯了這其實是一個遞歸問題 扫责。
下面給出算法代碼示例榛鼎，算法的關(guān)鍵在于getUniqueList方法，大神們?nèi)绻懈玫慕鉀Q方案也可以在文章下評論，指導(dǎo)一下者娱，哈哈抡笼。
<?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;
}
/**
* 獲取不重復(fù)的觀看時間區(qū)間
* @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];
//結(jié)束時間比當(dāng)前開始時間大，合并時間區(qū)間
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;
//沒有重復(fù)區(qū)間返回
if(!$hasRepeat && empty($list))
{
if(!empty($newList)) $uniqueList = array_merge($uniqueList, $newList);
return $uniqueList;
}
return $this->getUniqueList($newList, $uniqueList);
}
/**
* 二維數(shù)組按某個字段排序
* @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;
}
}
運行結(jié)果如下
Array
(
[0] => Array
(
[0] => 0
[1] => 9
)
[1] => Array
(
[0] => 439
[1] => 599
)
[2] => Array
(
[0] => 639
[1] => 869
)
)
最終結(jié)果是滿足我們需求的黄鳍，不重復(fù)的區(qū)間得到之后再循環(huán)數(shù)組相減推姻，就可以得到這個用戶總的不重復(fù)觀看時間了，算法的復(fù)雜度為n的二次方框沟，如果n是小于100的話藏古，循環(huán)次數(shù)不超過1萬次，如果將統(tǒng)計的定時任務(wù)設(shè)定為每隔5分鐘（n = 60）統(tǒng)計一次觀看時間忍燥，下次統(tǒng)計代入上次不重復(fù)區(qū)間n肯定是小于100的拧晕，所以總體算法復(fù)雜度還是不錯的。
下篇文章中我將會給出視頻統(tǒng)計平臺的架構(gòu)設(shè)計梅垄，如何在請求數(shù)較高的情況下低延時統(tǒng)計用戶每天的不重復(fù)看視頻時長厂捞，敬請期待哦。
