c****s
发帖数: 241 | 1 被拒的不明不白，实在不甘心。哪位高手能不能指点一下？
// Implement in C++ class Window illustrating the concept of a "sliding tim
e window on a data stream":
// A window object holds continuously arriving messages of type Msg for n mi
llisecs after
// a message is received. After n milliseconds messages are purged.
// For the purpose of this exercise, Msg is defined like this:
struct Msg
{
int m_key; // all keys within a window are unique.
double m_value;
}
// Messages are continuously added by the user of the | h*********e
发帖数: 56 | 2 抛砖引玉，我觉得这个有点像circular buffer.
1) how to manage memory:
Maintain an array of Messages and HEAD and TAIL index. add from HEAD, remove
(when time expires) from TAIL. When HEAD + 1 == TAIL, it's full. When HEAD
== TAIL, it's empty. When HEAD or TAIL equals SIZE, reset to 0.
2) timer:
In the constructor, register timer signal handler, which expires after N
milliseconds. After that, in every one milliseconds, remove all messages
added in N milliseconds before, by TAIL++.
3) efficient interface functio | c****s
发帖数: 241 | 3 这个跟我的idea很像，但是后来就受到据信了，觉得很受伤。
我的idea就是用hash来存message，用ring array来存平均值。希望大侠们能指点一下
迷津
remove
HEAD
【在 h*********e 的大作中提到】
: 抛砖引玉，我觉得这个有点像circular buffer.
: 1) how to manage memory:
: Maintain an array of Messages and HEAD and TAIL index. add from HEAD, remove
: (when time expires) from TAIL. When HEAD + 1 == TAIL, it's full. When HEAD
: == TAIL, it's empty. When HEAD or TAIL equals SIZE, reset to 0.
: 2) timer:
: In the constructor, register timer signal handler, which expires after N
: milliseconds. After that, in every one milliseconds, remove all messages
: added in N milliseconds before, by TAIL++.
: 3) efficient interface functio
| a******n
发帖数: 164 | 4 I also think circular buffer would be a solution:
struct DataSet
{
int nNumberOfEntries;
int iStart;
int iEnd;
uint32_t uKey;
Msg msgSet[MAX_NUMBER]; //MAX_NUMBER can be calculated
//by using max msg rate
float fpTotalSum;
};
void AddMessage(Msg *pMsg)
{
pMsg->m_nKey = uKey++;
memcpy(msgSet + iEnd++, pMsg, sizeof(Msg));
fpTotalSum += pMsg->value;
//check the head of the buffer, to make iStart
//points to Msg that it's still valid,
//and | c****s
发帖数: 241 | 5 thanks a lot for your input. I still have two concerns on this solution:
1) how to get average in the sliding windows.
2) timer is the most important condition. I don't think we can avoid it.
Which one do you think is better, hash table or binary search?
【在 a******n 的大作中提到】
: I also think circular buffer would be a solution:
: struct DataSet
: {
: int nNumberOfEntries;
: int iStart;
: int iEnd;
: uint32_t uKey;
: Msg msgSet[MAX_NUMBER]; //MAX_NUMBER can be calculated
: //by using max msg rate
: float fpTotalSum;
| a******n
发帖数: 164 | 6 1) Since we already keeps the total sum and number of entries, it should be
easy to get avg.
2) Timer is very bad for high performance apps, basically all signals are
bad for high performance apps. Most of the cases, we may want to avoid it. (
for saving context switching) for example we can avoid it using another
wrapper struct:
struct WrapMsg
{
time_t ts; // timestamp, when the message is added to circular buffer.
Msg msg;
};
This way the head always has the oldest message. The latest m
【在 c****s 的大作中提到】
: thanks a lot for your input. I still have two concerns on this solution:
: 1) how to get average in the sliding windows.
: 2) timer is the most important condition. I don't think we can avoid it.
: Which one do you think is better, hash table or binary search?
| h*********e
发帖数: 56 | 7 You are right. The timer is not necessary. We don't have to remove messages
at the EXACT time, as long as we don't use them if obsolete.
be
(
【在 a******n 的大作中提到】
: 1) Since we already keeps the total sum and number of entries, it should be
: easy to get avg.
: 2) Timer is very bad for high performance apps, basically all signals are
: bad for high performance apps. Most of the cases, we may want to avoid it. (
: for saving context switching) for example we can avoid it using another
: wrapper struct:
: struct WrapMsg
: {
: time_t ts; // timestamp, when the message is added to circular buffer.
: Msg msg;
|
|
