Efficient way to keep tallies?
Pages: 12
g++4.6 complains about your Counter class needs some extra typenames so I fixed that. I also replaced your timer with a high resolution one.
When I run the optimized version, the times in micro (10^-6) seconds for each trial are like this
This gives a total runtime for all trials of about 5 seconds.
For the non optimized version I get:
So even for the one with no optimization you are getting < 0.15 seconds per trial.
This would make me think if you are hitting 2-3s per trial then there is a problem with your computer/compiler.
To give you an idea about calls. The heaviest used function is std::less<int>, which the map uses internally to find elements. It is called 158526324 times (but will almost certainly be inlined in the optimized version). The next culprit is operator[] of the map, there are 66240010 calls. These two functions count for 33.25% of the runtime.
When I run the optimized version, the times in micro (10^-6) seconds for each trial are like this
|
|
This gives a total runtime for all trials of about 5 seconds.
For the non optimized version I get:
|
|
So even for the one with no optimization you are getting < 0.15 seconds per trial.
This would make me think if you are hitting 2-3s per trial then there is a problem with your computer/compiler.
To give you an idea about calls. The heaviest used function is std::less<int>, which the map uses internally to find elements. It is called 158526324 times (but will almost certainly be inlined in the optimized version). The next culprit is operator[] of the map, there are 66240010 calls. These two functions count for 33.25% of the runtime.
Please fix the memory leaks. In fact you shouldn't be using
The dynamic arrays could be replaced by std::vector
Just call srand once in the whole program
You don't need maps, arrays are enough. Just convert those strings to integers (and operate them in that way).
The pixels could be represented by an integer in a fixed range.
Bayes.h Line 109:
¡¿?! I've got ~8s with O3 optimization level.
Change the maps for arrays and tell us the results.
Regards.
newThe dynamic arrays could be replaced by std::vector
Just call srand once in the whole program
You don't need maps, arrays are enough. Just convert those strings to integers (and operate them in that way).
The pixels could be represented by an integer in a fixed range.
Bayes.h Line 109:
cprob[x][y][i].increment_count(0,0); that doesn't do anything.| the time delay is still around 3 seconds. |
Change the maps for arrays and tell us the results.
Regards.
Thanks kev82! But I'm a bit surprised as to how low your runtimes are. My computer is pretty powerful and I don't think my compiler has acted up anywhere else. ne555 seems to also get large runtimes when running my code.
Sorry about the leaks! Now that I'm using vectors, they'll automatically deallocate the memory when finished, right? Also, is there any other place where I'm causing memory leaks?
I don't see how I can use arrays though. I mean now since I'm only checking whether a pixel is on or off, I could easily create a counter that just deals with an on or off count, but I'd like a general counter where I can keep giving it new categories and the counter will work fine. How would I convert strings to integers without using a map to pair each string to an integer?
That was just crappy programming on my part-- I needed to add that line in because if a pixel encountered exclusively one type of signal (either on or off), then increment_all would not add the other pixel type in, so ultimately I'd end up taking the log of 0 which obviously wrecks the whole recognition.
When should maps be used then, out of curiosity? From the description it seemed they were geared toward this task of rapid access for keyed values rather than indexed ones.
Sorry about the leaks! Now that I'm using vectors, they'll automatically deallocate the memory when finished, right? Also, is there any other place where I'm causing memory leaks?
I don't see how I can use arrays though. I mean now since I'm only checking whether a pixel is on or off, I could easily create a counter that just deals with an on or off count, but I'd like a general counter where I can keep giving it new categories and the counter will work fine. How would I convert strings to integers without using a map to pair each string to an integer?
| Bayes.h Line 109: cprob[x][y][i].increment_count(0,0); that doesn't do anything. |
That was just crappy programming on my part-- I needed to add that line in because if a pixel encountered exclusively one type of signal (either on or off), then increment_all would not add the other pixel type in, so ultimately I'd end up taking the log of 0 which obviously wrecks the whole recognition.
When should maps be used then, out of curiosity? From the description it seemed they were geared toward this task of rapid access for keyed values rather than indexed ones.
Last edited on
For converting strings to and from integers, the standard library's stringstream class is excellent for this kind of stuff. By putting numbers in the stream and then getting the stream as a string, you can convert numbers to strings. Vice-versa, you can construct a stream from a string, and then extract a number from the stream to convert a string to a number.
Last edited on
Well my biggest question is this: I have no idea how to create the kind of counter I have in mind using a vector because now I need to use the vector indices to point to some count. But if I want to do something like
That's what I liked about the map-- the associating of a key and a value rather than an index and a value. But since the map's performance isn't exactly up to par, I'm wondering how I could achieve something similar using vectors.
Sorry for asking so many questions, but I really, really appreciate all the help you guys have been giving me so far!
** I got it to work using vectors but I have no idea how clean my solution is. Performance went way up. Delay under a second. So that begs the question, when is it worth using a map over a vector if the performance gap is so noticeable?
counter.increment_count("red", 1) how can I get the "red" to map to an index in the vector? How do I get "red" to point to that index every time, without using a map? And then when I want to add in "blue" how do I get "blue" to point to the new index every time? That's what I liked about the map-- the associating of a key and a value rather than an index and a value. But since the map's performance isn't exactly up to par, I'm wondering how I could achieve something similar using vectors.
Sorry for asking so many questions, but I really, really appreciate all the help you guys have been giving me so far!
** I got it to work using vectors but I have no idea how clean my solution is. Performance went way up. Delay under a second. So that begs the question, when is it worth using a map over a vector if the performance gap is so noticeable?
Last edited on
| Thanks kev82! But I'm a bit surprised as to how low your runtimes are. My computer is pretty powerful and I don't think my compiler has acted up anywhere else. ne555 seems to also get large runtimes when running my code. |
Those runtimes were per trial, of which you did 100. That gave me a total runtime of about 5s. Just did it again to get 4.503s (total). ne555's time of 8s for all trials is a bit slower than mine, but not miles off. Are you saying 2-3s per trial or 2-3s in total?
It's about 2-3 seconds PER TRIAL, which I just can't understand. Using arrays I get it down a a little under a second per trial, but I'd like to stick with the map if possible, because if it really is 8s or 5s for 100 trials, that performance more than adequate for my needs.
Well then it's a compiler/computer problem.
Make sure you have turned optimization on.
If it's relevant, I'm compiling with g++4.6 and icpc 11 (icpc gets it down to about 4.1s with -O2). The system is Debian testing running as the guest os inside VirtualBox on a 4 year old Macbook.
Make sure you have turned optimization on.
If it's relevant, I'm compiling with g++4.6 and icpc 11 (icpc gets it down to about 4.1s with -O2). The system is Debian testing running as the guest os inside VirtualBox on a 4 year old Macbook.
Last edited on
Ah, ok that makes sense! Sorry, I'm still new to this whole process. With optimization I get around 4 seconds for the whole program. Cool!
Thanks so much for the help!
BTW- what were you using for the higher res timer? I'm not a big fan of this "0.00" accuracy.
Thanks so much for the help!
BTW- what were you using for the higher res timer? I'm not a big fan of this "0.00" accuracy.
You would not believe the number of people who don't know to turn optimization on. You are not alone.
I used boost to do the timing, as I like to stay platform independent. If you want to avoid boost, the *nix way would be gettimeofday, there will be a Windows equivalent, but I have no idae what it is.
I have imported the boost::posix_time namespace, start and end are of type ptime.
I used boost to do the timing, as I like to stay platform independent. If you want to avoid boost, the *nix way would be gettimeofday, there will be a Windows equivalent, but I have no idae what it is.
I have imported the boost::posix_time namespace, start and end are of type ptime.
|
|
Topic archived. No new replies allowed.
Pages: 12