Comments (21)
This would be the time per 200k messages, but I get your idea.
time_per_message = (t2 - t1) / 700000
from challenge_mail_filter.
@feldgendler And if my filter somehow works with xrlarge faster than large, i'll get the negative time %)
from challenge_mail_filter.
The time per message is not the best possible measure, either, because the overhead does matter. A solution with very short per-message time but a huge overhead would not necessarily be the best overall. What is “best” depends on the typical workload sizes, which is why we decided on 100k.
As I wrote, we could pick some kind of weighted sum which would serve as a better measure of performance. But we decided to stick with 100k because it's not entirely invalid, and would be the closest to what was originally announced.
from challenge_mail_filter.
Я за телефоном, поэтому буду по русски:-)
Смысл в том, что эти величины нельзя складывать без приведения к одному порядку.
Иначе прикладные затраты будут оказывать большое влияние на меньшие тайминги. Т.е. бОльшее время содержит в себе в 8 раз больше прикладных затрат, кроме затраты на обработку сообщения.
Т.е. правильная формула на 1 соообщение
time_per_message = (t1 + t2 / 8) / 200000
Но я не стал делать на 200к, т.к. это вносит ненужные округление и потерю точности. По этому для большей точности проще сравнивать без деления.
from challenge_mail_filter.
@feldgendler I do not fully understand. You choose do not measure performance for 800,000 messages, only 100,000?
from challenge_mail_filter.
Yes. We chose to stick with 100k messages, as was originally announced.
@AgentRX, I don't see why you chose this particular formula, t1 + t2/8. Let's assume the simplistic model that the time for n messages is C+k*n, where C is the constant overhead and k is time per message.
t1 = C + 100000*n
t2 = C + 800000*n
t1 + t2/8 = 1.125*C + 200000*n
Ranking by t1 relatively favors smaller overhead (1 microsecond per message is worth as much as 100 ms of overhead), ranking by t2 relatively favors shorter time per message (1 microsecond per message is worth as much as 800 ms of overhead). Your formula is somewhere in between (1 microsecond per message is worth as much as 178 ms of overhead). There are many ways to choose this ratio of relative importance of overhead and time-per-message, and t1 is as fair as anything else.
from challenge_mail_filter.
@feldgendler , I'll answer from home why I choose that formula in 2 hours. The mistake in your formula is the same C value for different amount of messages.
from challenge_mail_filter.
@feldgendler, so let me explain my formula.
I based on the next things:
- The most users algorithms consists these parts:
a. Preparing PDelay = Kprep
b. Preprocessing rules. PrepDelay = Rn * Ad * S(Rn)
c. Processing messages. ProcDelay = Mn * Kopt * S(Mn)
OR
b. Preprocessing messages. PrepDelay = Mn * Ad * S(Mn)
c. Processing rules. ProcDelay = Rn * Kopt * S(Rn)
where Mn - messages number, Rn - rules number,
Ad - algorithm delay
Kopt - is some optimization scalable constant which got because of preprocessing.
Kprep - some preparing delay.
So the next things are very important.
S(Mn) and S(Rn) - scalabilities for Rules and Messages
So, now we have formula for most algorithms:
SumDelay = Kprep + Rn * Ad * S(Rn)+ Mn * Kopt * S(Mn) (1a)
SumDelay = Kprep + Mn * Ad * S(Mn)+ Rn * Kopt * S(Rn) (1b)
If we speak about 100 rules and 100k/800k messages we can use simplier formulas:
SumDelay = Mn * Kopt * S(Mn) (2a)
SumDelay = Mn * Ad * S(Mn) (2b)
Now let's calculate t1 and t2 for 'a' case only (I think it's enougth):
t1 = 100 000 * Kopt * S1
t2 = 800 000 * Kopt * S2
The main your formula:
T = (t1 + t2) / 2 is wrong for scalability evaluation because you try to add different orders:
T = 50 000 * Kopt * S1 + 400 000 * Kopt * S2 = 50 000 * Kopt * (S1 + 8 * S2) (as you can see S2 is take effect 8 times more).
For example if we want to evaluate S2 and S1 values we should use:
Scal = S2 / S1 = t2 / (8 * t1) (smaller is better)
If we want to determine time speed we should use:
Tdet = (8 * t1 + t2) / 800 000 = Kopt * (S1 + S2) (smaller is better)
And finally we could use main formula for rating:
Rank = RankTime + RankScal (smaller is better)
where RankTime and RankScal is rate position by Scal and Tdet (from 1 to Num of participants)
from challenge_mail_filter.
@feldgendler , UPDATE. You can use this formulas to avoid collisions:
RankTime = RankTimeUser / RankTimeMin
RankScal = RankScalUser / RankScalMin
Rank = RankTime * RankScal (smaller is better)
PS. But if you have already chosen to stick with only 100k messages it's not actual now
from challenge_mail_filter.
Where did the constant part go in (2a) and (2b)?
from challenge_mail_filter.
@feldgendler , we can ignore them due to huge messages count. So these constants:
C1 = Kprep + Rn * Ad * S(Rn)
AND
C2 = Kprep + Rn * Kopt * S(Rn)
don't take essential value to the result because of:
- 3 orders (10^3) different between Rn and Mn
- 5 orders (10^5) different between Kprep and Mn
from challenge_mail_filter.
Where does this data come from, that they are negligible? Can you show your calculated values for a few submissions?
from challenge_mail_filter.
@feldgendler, because Kprep / Ad / Kopt variables are for one-few actions only.
If we have these formulas:
y1 = Tact * N + Tact * M + Tact
y2 = Tact * N2 + Tact * M + Tact
Tact - time for one logical action (process rule/message and so on),
N, N2 - messages number
M - rules number
and want for example to sum them:
y1 + y2 = Tact * N + Tact * M + Tact + Tact * N2 + Tact * M + Tact =
= 2 * Tact * ( M + 1) + Tact * N * (1 + N2/N)
In our case we'll get:
y1 + y2 = 2 * Tact * (100 + 1) + Tact * 100 000 * (1 + 8) =
= 202 * Tact + 900 000 * Tact
If we want to determine time for 1 rule we get:
Tone = (y1 + y2) / (N + N2) = (202 * Tact + 900 000 * Tact) / 900 000 =
= Tact + 202 * Tact / 900 000 = ~Tact
So next is small table for few participants:
Participant | Large | XLarge | Scal | Tdet (for 800k) | (t1 + t2) / 2 | Rtime | Rscal | Rt+Rs |
---|---|---|---|---|---|---|---|---|
Roman Pletnev | 187 | 2125 | 1,42 | 3621 | 1156 | 1 | 1,775 | 2,775 |
Evgeny Zeyler | 219 | 1886 | 1,07 | 3638 | 1052,5 | 1,005 | 1,3375 | 2,3425 |
Yuri Kilochek | 281 | 1802 | 0,80 | 4050 | 1041,5 | 1,118 | 1 | 2,118 |
Andrew Kashta | 272 | 2453 | 1,13 | 4629 | 1362,5 | 1,278 | 1,4125 | 2,6905 |
As you can se my method has different result with yours but my method use scalable rating.
from challenge_mail_filter.
First, why do your formulas for y1 and y2 contain the same factors (Tact) for different things?
It should be:
y1 = time_per_message*N + time_per_rule*M + startup_time
y2 = time_per_message*N2 + time_per_rule*M + startup_time
Second, because we're not varying the number of rules, let's consider the terms containing M constant, so we'll include time_per_rule*M + startup_time into “C”. This produces the formulas I've shown previously:
y1 = C + time_per_message*N
y2 = C + time_per_message*N2
…and my reasoning stands valid.
from challenge_mail_filter.
@feldgendler, yes your formulas are right.
My main idea was to use both scalable and time criteria. I didn't want to rufute your formulas with constants:)
from challenge_mail_filter.
In real life, both C and time_per_message matter, and good engineering usually makes one or another trade-off between the two. As I have shown above, your proposal would shift thte balance of how much we relatively care about C and time_per_message, but any particular point of balance is a choice that is as good as any other.
from challenge_mail_filter.
@feldgendler , btw where is scalability factor in your formulas?
If use your formulas we'll get:
y1 = C + time_per_message * 1
y2 = C + time_per_message * 1000
Let's calculate scalability:
S = y2/(y1 * 1000) = (C + time_per_message * 1000)/(1000 * (C + time_per_message)) =
= (C + C * 1000 - C * 1000 + time_per_message * 1000) / (1000 * (C + time_per_message)) =>
S = 1 - 0,999 * C / (C + time_per_message)
If C > 0 and time_per_message > 0 than
that means that S is ALWAYS less than 1. But in real life scalability not linear and S could be more than 1.
Unfortinately it means formulas your suggested are wrong.
from challenge_mail_filter.
Please answer one question: in your model, is y
linear in N
? In other words, is y(N)
a linear function (assuming M
fixed)?
from challenge_mail_filter.
@feldgendler Of course not. If they were linear I wouldn't calculate Scal = S2 / S1
from challenge_mail_filter.
So your S() is some sort of nonlinear function? What do you think its graph looks like?
from challenge_mail_filter.
@feldgendler it's strange question. I'm not sure you understood S() meaning because S graph depends on filter.
If you want you can create more data sets and test filters on them.
Then calculate S1, S2...SN and draw it's graph.
from challenge_mail_filter.
Related Issues (4)
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from challenge_mail_filter.