Time spent by an algorithm
in [Math]
|
Prev: Most *elementary* Q on quotient map of topological spaces
Next: On Coast to Coast AM this morning, the topic was the Shroud of Turin. ... bend, fold, staple, and mutilate.
From: Kaba on 5 Apr 2010 11:00 Hi, I am measuring the time spent by an algorithm. Let's assume it is a gaussian-distributed random variable. How many repetitions do I have to make to get a good estimate of the mean and standard deviation of this distribution? I'd like a cook-book answer this time, because I am in hurry with these measurements. I know it's 101.. Probability is one of my weaker sides. -- http://kaba.hilvi.org
From: Ludovicus on 5 Apr 2010 14:03 On Apr 5, 11:00 am, Kaba <n...(a)here.com> wrote: > Hi, > > I am measuring the time spent by an algorithm. Let's assume it is a > gaussian-distributed random variable. How many repetitions do I have to > make to get a good estimate of the mean and standard deviation of this > distribution? > > I'd like a cook-book answer this time, because I am in hurry with these > measurements. I know it's 101.. Probability is one of my weaker sides. > > --http://kaba.hilvi.org How can, the time spent by an algorith, be a random variable ? If it is run in the same computer the time is a constant. If it is run in different computers the values are not of the same genus.
From: Dirk Van de moortel on 5 Apr 2010 14:16 Kaba <none(a)here.com> wrote in message MPG.26242796a52f273c9898af(a)news.cc.tut.fi > Hi, > > I am measuring the time spent by an algorithm. Let's assume it is a > gaussian-distributed random variable. How many repetitions do I have to > make to get a good estimate of the mean and standard deviation of this > distribution? > > I'd like a cook-book answer this time, because I am in hurry with these > measurements. I know it's 101.. Probability is one of my weaker sides. > > -- > http://kaba.hilvi.org If you're in a hurry, then let it run and make it show the mean and standard deviation, together with the current repetition count, while it's running. Stop it when the mean and stddev values settle down. They are what you are looking for. If you're still interested in the number of repetitions, read it as wel; :-) Dirk Vdm
From: Kaba on 5 Apr 2010 14:16 Ludovicus wrote: > How can, the time spent by an algorith, be a random variable ? > If it is run in the same computer the time is a constant. > If it is run in different computers the values are not of the same > genus. There are at least these two reasons. First, I am feeding the algorithm with pseudo-random input. Second, computers do run programs at varying speeds, confirmed by repeating a measurement multiple times. I guess a gaussian variable would be a good model for this variation, but as suggested by my collegue, I'll first have to test this hypothesis with the Lilliefors test. -- http://kaba.hilvi.org
From: Kaba on 5 Apr 2010 14:27
Dirk Van de moortel wrote: > If you're in a hurry, then let it run and make it show the mean and standard > deviation, together with the current repetition count, while it's running. Stop > it when the mean and stddev values settle down. They are what you are > looking for. If you're still interested in the number of repetitions, read it > as wel; :-) > > Dirk Vdm Thanks, I'll consider whether this fits the situation. Let's put the question this way. Currently, using a sample of 10 realizations, I am having a sample standard deviation which is about 2% of the sample mean. What does this allow me to say about the quality of the sample mean (assuming gaussianity)? -- http://kaba.hilvi.org |