>write awesome but buggy as hell C program to kick ass at minesweeper
>1 second top score on expert mode. .47 seconds if I use a clone that keeps track of decimals.
>nagging feeling that I'm being a noob by writing in C and not C++
>learn C++ and rewrite program using classes and maps and vectors and lists and that kind of shit instead of just arrays.
>program works perfectly now, code is much cleaner, but it can't solve an expert board in under 10 seconds
>switch on every speed optimization I can find in Visual Studio
>times down to 6-7 seconds
>decide to rewrite the whole thing in C again from scratch so maybe it can be fast AND reliable at the same time
>change mind and decide to bitch to /prog/ instead and then take a nap
the main difference is that instead of looping over a 16x30 array of 10-15 byte structs defining the state of a board square, it's looping over a map<,> with user-defined classes for both entries.
also, i use set_difference and set_intersection to pick out sections of the board to analyze instead of picking elements out of an array.
Name:
Anonymous2011-04-06 10:23
I have 20 years programming experience writing HUGE windows games solvers that you couldnt even comprehend. I wrote an ANSI minesweeper solver when I was 12 years old.
You should just accept everything I say, I dont HAVE to give any reasons for my arguments because I am an EXPERT PROGRAMMER.
>>7 the main difference is that instead of looping over a 16x30array of 10-15 byte structs defining the state of a board square, it's looping over a map<,>
I literally slapped my forehead with my right hand and held it there for a couple of seconds, as if shielding myself from the idiocy emanated by the image of your statement on my computer screen.
Go suck a dick, faggot, you are not born for programming.
Wait, before you go, C++ has a lot of data structures, why did you choose a map specifically, why not an std::priority_queue? Or an std::stack of std::deques of std::priority_queues? If you don't give a fuck, why not go full retard, you should use every single of them, it's C++ motherfucker!
Now go, those dicks aren't going to suck themselves.
Name:
Anonymous2011-04-06 10:36
When I was 8-years-young, I wrote Turing machine in a single line of C
std::map can be slow, lookups are O(log n) in time complexity as it is implemented with a red-black tree or avl tree.
OP should be using std::unordered_map (available in C++11/C++0x--so MSVC++ 2010), or std::tr1::unordered_map (available in TR1--so MSVC++ 2005/2008), or boost::unordered_map. unordered_map has O(n) time complexity for lookups, as it's implemented as an associative hash-map with chained addressing.
>>9,13
Not just that, but I probably wouldn't use a C++ Standard Library template container for that at all. I'd still continue on using a 16x30 C style array in C++ for this because it's the fucking best data structure for the use case. It's a statically-sized array, you don't need any features of a dynamic data structure.
And before some faggot says ``Well, it's not Sepples enough if you don't use C++SL template containers,'' let me state that that is fucking bullshit. C++ is a superset of C. You can still use C style arrays where it fucking makes sense. Don't be a retard and force template containers just so that you can use template containers.
>>20
Your enterprise grade language has toy features like LAMBDAS and GARBAGE COLLECTOR(optional), don't you feel kind of bad about it?
Name:
nambla_dot_org_rules you2011-04-06 12:46
<a bit off topic>
Lisp has a strong garbage collector when compared with the shit that gets implemented in your loser languages like Python and Perl 5.
</a bit off topic
>>21
It doesn't have a garbage collector per se, the standard does not discuss any constraints about GC--it's implementation defined. Neither GCC, MSVC++, Intel C++, Clang, or any other C++ compiler that I know of has support for GC out of the box. There's a 3rd party Boehm-Demers-Weiser GC library you can plug in and use which overrides operator new and delete, but it doesn't specifically require compiler support, and it doesn't work well with multi-threaded C++ software. In other words, C++ GC is a crutch for Java/C# programmers who are trying to learn C++.
>keep c++ framework
>replace the code that actually does stuff and needs to be fast with the old c code
>tweak code to work in new environment, make a couple improvements to algorithm
>average solving time ~.3 seconds, new record is .25 seconds
>program locks up half the time in vista for some unknown reason, though >:I
Name:
（ ≖‿≖）2011-04-11 23:10
>>42 >program locks up half the time in vista for some unknown reason, though >:I
>mfw i read that
Name:
Anonymous2011-04-11 23:56
>>43
it's because the program tries to read a square before it's redrawn on the screen, but somewhere in the middle of 5 GetPixel calls it finally updates, and tricks the program into thinking it's a different type of square than it is. apparently XP has always been updating the screen faster than my program could read it, so it wasn't an issue.
trying to figure out a workaround that won't slow things down.
>>47
Oh wow. This poster posts as though he is straight out of /b/! We have a standard for posting just so you know.
Name:
Anonymous2011-04-12 1:20
>>48
When the program calculates that a square is safe to click, it sends the click and immediately starts trying to read its new state from the screen. Sometimes the game doesn't update fast enough, and the program will loop until it gets a valid read, but sometimes it'd get a mix of the old state (an unclicked square) and the new state (a "3", for instance), and the program would get confused since the mix of data actually corresponded to a completely different state.
I fixed it by just choosing a different (and actually smaller) set of pixels to poll, where that kind of thing won't happen.
Record's down to .23 seconds already thanks to the speed improvement from not needing to poll as many pixels.
>>42
Sounds like you figured out how to use C++ correctly. I use classes for higher-level components, but underneath, I'm using C style arrays for constant-time lookups where possible. Just because the standard library has associative key-value data structures doesn't mean they're going to be faster than straight memory offset calculations. You'd have to be retarded to think that.
Associative data structures are more useful for when your key data type has a non-trivial representation that can't be easily mapped to a unique array offset. Like strings for example.
>>61
No, not cache misses per se. OP was using the wrong data structures. Instead of using 2-dimensional arrays with O(1) lookup complexity like he was in C, he thought it was a good idea to use std::map, which is usually a red-black tree or avl tree with O(log n) lookup complexity, simply because he wanted to ``make it look more like C++,'' whatever that means. He has since corrected his mistake. Yes, using std::map does stress the cache more by nature of nodes not being local to one another using the default allocator, as well as link and allocation overhead. However, using a std::map for something that can easily be implementing as a memory offset calculation for indexing into an array is the real meat of the problem.