问个题目 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

问个题目

问个题目# JobHunting - 待字闺中

P*b2013-01-12 08:01

1 楼

实时显示前一个小时，前一天，前一星期的总点击量，有什么比较efficient的方法？
谢谢

M*52013-01-12 08:01

2 楼

做这种的系统本身应该就会有一个保存浏览量的container（比如vector），比如说它
的保存单位是1min，那么用sliding window，过一分钟，淘汰最老的，进来最新的，可
以吗？

p*22013-01-12 08:01

3 楼

貌似就是这样。

【在 M********5 的大作中提到】

: 做这种的系统本身应该就会有一个保存浏览量的container（比如vector），比如说它
: 的保存单位是1min，那么用sliding window，过一分钟，淘汰最老的，进来最新的，可
: 以吗？

h*e2013-01-12 08:01

4 楼

建议看看RRDTool:
http://oss.oetiker.ch/rrdtool/index.en.html

f*m2013-01-12 08:01

5 楼

滑动这个窗口，每次只报告落入窗口内的点击次数，对吗？
上次看到有人用Interval tree.

【在 M********5 的大作中提到】

M*52013-01-12 08:01

6 楼

我是这么想的，没有看过interval tree，所以没法做比较。只是觉得sliding window
这个方法，没隔一分钟更新一次都是O(1)的效率，并且不需要额外的存储空间（假设系
统原来本身就有一个container）
你们都知道很多数据结构，怪不得我就面挂了。。。

【在 f*********m 的大作中提到】

: 滑动这个窗口，每次只报告落入窗口内的点击次数，对吗？
: 上次看到有人用Interval tree.

f*m2013-01-12 08:01

7 楼

每隔一分钟就把落入（一分钟）窗口的click次数加起来吗？或者等要数据的时候再加。
要是这样的话，那计算每一天的click数（窗口大小为一天），其计算量不小啊。

window

【在 M********5 的大作中提到】

: 我是这么想的，没有看过interval tree，所以没法做比较。只是觉得sliding window
: 这个方法，没隔一分钟更新一次都是O(1)的效率，并且不需要额外的存储空间（假设系
: 统原来本身就有一个container）
: 你们都知道很多数据结构，怪不得我就面挂了。。。

M*52013-01-12 08:01

8 楼

你没有明白我说的意思，
std::vector num_time; //这个num_time每隔一分钟都会被push进一个新的值，
我们假设这是个系统的container，它里面已经有超过一个week的数据量
//initialization,
{
long sum_one_hour=0;
long sum_one_day=0;
long sum_one_week=0;
size_t len = num_time.size();
for(size_t i=1; i<=60; i++)
sum_one_hour += num_time[len-i];
for(size_t i=1; i<=1440; i++)
sum_one_day += num_time[len-i];
for(size_t i=1; i<=10080; i++)
sum_one_week += num_time[len-i];
}
// 每一分钟call一次
void onTimer(){
size_t len = num_time.size();
sum_one_hour = sum_one_hour - num_time[len-61] + num_time[len-1];
sum_one_day = sum_one_day - num_time[len-1441] + num_time[len-1];
sum_one_week = sum_one_week - num_time[len-10081] + num_time[len-1];
}
没有具体的写class的结构，只是个大概的idea，你可以自己组织这些结构在class里面
该怎么安排，应该不难写

加。

【在 f*********m 的大作中提到】

: 每隔一分钟就把落入（一分钟）窗口的click次数加起来吗？或者等要数据的时候再加。
: 要是这样的话，那计算每一天的click数（窗口大小为一天），其计算量不小啊。
:
: window

f*m2013-01-12 08:01

9 楼

哦，了解，我也想着用一个计数器什么的，不过没有楼主这么具体。
这个方法看样子挺有效的，若是container存在这个假设成立的话（应该总有一个东西
存储不同时刻的点击量）。

【在 M********5 的大作中提到】

: 你没有明白我说的意思，
: std::vector num_time; //这个num_time每隔一分钟都会被push进一个新的值，
: 我们假设这是个系统的container，它里面已经有超过一个week的数据量
: //initialization,
: {
: long sum_one_hour=0;
: long sum_one_day=0;
: long sum_one_week=0;
: size_t len = num_time.size();
: for(size_t i=1; i<=60; i++)