More specifically, are there any rules of thumb to say whether a function is n^2 or nlogn or any of the others?
I was reading a coding horror post about having too small of a data set and realised that, on this machine at least, it takes a non trivial amount of time to load just my 2048x2048 pixel testing texture file and this pales in comparison to the size of real world textures. Clearly the way I'm doing it now isn't going to suffice, but I have no idea how to estimate whether another method will be quicker or more of the same or even what to look for.
How do you estimate the time a function will take?
Moderator: Moderators
Re: How do you estimate the time a function will take?
Put it inside a for loop that loops like a thousand or million time. Basically, loop it enough time that it takes several seconds to run.
Measure time with Spring.GetTimer and Spring.DiffTimers (do NOT use os.time, it has a precision of many seconds due to Lua rounding error).
Divide measured time by number of loop.
Measure time with Spring.GetTimer and Spring.DiffTimers (do NOT use os.time, it has a precision of many seconds due to Lua rounding error).
Divide measured time by number of loop.
Re: How do you estimate the time a function will take?
I was thinking more in general.
Re: How do you estimate the time a function will take?
doing this is a branch of science called computational complexity. read up on it, e.g. here: http://en.wikipedia.org/wiki/Computatio ... ity_theory. A rough approximation is to count nested loops in your algorithm - if it's not smart in any way, the maximum amount of nesting (let it be k) will give you a complexity of n^k. this is NOT always true.
Re: How do you estimate the time a function will take?
Post the code!
Are you running visual studio?
Are you running visual studio?
Re: How do you estimate the time a function will take?
It's the LoadFile function in wxImage, I'll try and find it. *I tried and failed, it's a hideous rabbit warren*
No, I'm using code::blocks.
No, I'm using code::blocks.
Last edited by Das Bruce on 28 Jan 2010, 11:22, edited 1 time in total.
Re: How do you estimate the time a function will take?
When dealing with optimisation and code efficiency, in general you'll get it wrong if you try to guess what's best based on theory alone.Das Bruce wrote:I was thinking more in general.
Running an actual test and measure performance will in general show whatever initial assumption you have to be completly misleaded.
Re: How do you estimate the time a function will take?
O notation would help here, what you want is to improve your algorithm, not the number of instructions
Re: How do you estimate the time a function will take?
the O(bla) thing is something you can only find out by looking at the code/algorithm instructions. you can not find this out by doing measurements.
so...
what exactly do you want to know, and what for?
you really need to know the O thing, or you need to compare your codes wall-clock-time to the one of an other?
(WCT -> about: the time it really takes to run)
so...
what exactly do you want to know, and what for?
you really need to know the O thing, or you need to compare your codes wall-clock-time to the one of an other?
(WCT -> about: the time it really takes to run)
Re: How do you estimate the time a function will take?
Measure for different N, plot the curve, see how it's shaped....hoijui wrote:the O(bla) thing is something you can only find out by looking at the code/algorithm instructions. you can not find this out by doing measurements.
Anyway, what I meant is that O(n) has its uses, but Das Bruce problem seemed very practical (loading a texture), and I'm not sure theorical algorithm analysis would really indicate how to speed that up.
Re: How do you estimate the time a function will take?
yeah, right, forgot about that :D
still, it is not really clean/will not always work.
consider:
compiler optimizations kicking in (compile or runtime) -> code and measurement might suggest different O()'s
hardware kicking in (eg. once reading from memory only, the other time from HD)
...
still, it is not really clean/will not always work.
consider:
compiler optimizations kicking in (compile or runtime) -> code and measurement might suggest different O()'s
hardware kicking in (eg. once reading from memory only, the other time from HD)
...
Re: How do you estimate the time a function will take?
Never guess. Either test, or don't care.
My old code is littered with endless overuse of hashtables, when using built-in linear search functions would have been cleaner, more legible, and often even faster - even though hash-access is faster for large sets, most of the time it's not a large set.
My old code is littered with endless overuse of hashtables, when using built-in linear search functions would have been cleaner, more legible, and often even faster - even though hash-access is faster for large sets, most of the time it's not a large set.
Re: How do you estimate the time a function will take?
Hoiju:
Yeah, sure, any mathematician would cringe at the idea, and would on the spot construct me a counter exemple function.
But then it would be pretty hard as well to determine from source reading alone the moment an algorithm start using virtual memory, or that the compiler optimisation cleverified your code.
Yeah, sure, any mathematician would cringe at the idea, and would on the spot construct me a counter exemple function.
But then it would be pretty hard as well to determine from source reading alone the moment an algorithm start using virtual memory, or that the compiler optimisation cleverified your code.
Re: How do you estimate the time a function will take?
yeah true, that is hard to see from code, or even impossible (eg, if you do not know which compiler will be used). but that is not needed either.
when looking at the code, you can say, this algorithm is O(x), and you can say this for sure. If, in the end, it will be executed like this, is an other thing.
This is useful, as this O(x) will stay the same, no matter where the algorithm is used. eg, we can take some pathing algorithm from a game engine written in Java, and use it in spring C++ code. what we are interested in is the O(x) you get by only looking at the code, and compare it to what we have.
In theory, you could also try to estimate the final O(X) at runtime in GCC for both algorithms, by just looking at the two codes, but usually that will not lead to a different result (eg, the same algorithm will be the superior in both comparison methods). plus, it is much harder and more error thrown, as you already said.
when looking at the code, you can say, this algorithm is O(x), and you can say this for sure. If, in the end, it will be executed like this, is an other thing.
This is useful, as this O(x) will stay the same, no matter where the algorithm is used. eg, we can take some pathing algorithm from a game engine written in Java, and use it in spring C++ code. what we are interested in is the O(x) you get by only looking at the code, and compare it to what we have.
In theory, you could also try to estimate the final O(X) at runtime in GCC for both algorithms, by just looking at the two codes, but usually that will not lead to a different result (eg, the same algorithm will be the superior in both comparison methods). plus, it is much harder and more error thrown, as you already said.