Speed problem

[Andreas Schmitt]

Hi,

I have a small problem here. I put in a paper today, which was basically a
programming project for a
sudoku solver.

I got the programm working without a problem, but somehow the algorithm
isn't running as fast as I thought it would.
I talked to some of my colleagues and they basically told me that their
algorithms were mostly not more complex than
mine. Mostly even more simply, yet their programs solved a certain set of
100 sudokus in under 2 minutes, where
mine needed 15 minutes.
I activated all optimization options, used /O2 in Visual C++ but that only
gave me like 2 seconds less computing time.

I went throught the algorithm over and over and I am sure that it does work
correctly, I put it on 20000 different sudokus
in a file I found and it solved them all in a time of about 1.6 seconds per
sudoku, which is simply not fast enough.

Problem is I don't have any idea why it is so slow, while other programs
which do basically do exactly the same are
doing it so much faster.

Don't missunderstand me, I don't want to get you to help me get more points,
I put the project in already anyway.
It's just that I will only get a score for the project, but no explanation
on why it was so slow and since I am simply
curious on what I did wrong I would appreciate if anyone her could give me a
hint or two.
I will upload the code under the following link so I don't have to put it in
here, since even just writing the functions which
actually do compute the algorithm would still be too much for a post here.
I don't want to short it down though, since I want to show you the actual
code as is so you can find anything
that might be slowing it down too much.
I know looking through all that code is a little work, but I would really
appreciate any help.
Again, my problem is not correctness or how to do it, but how to do it
faster, a lot faster.

Thanks in advance... here's the link:

http://www.wcrevival.de/joker/CSudokuRiddle_cpp.txt

 

[Victor Bazarov]

I have a small problem here. I put in a paper today, which was
basically a programming project for a
sudoku solver.

I got the programm working without a problem, but somehow the
algorithm isn't running as fast as I thought it would.
[...]

Thanks in advance... here's the link:

http://www.wcrevival.de/joker/CSudokuRiddle_cpp.txt

Functionality is missing there. No 'Init', no c-tor, no d-tor (if
it's needed at all, that is), no 'main'. No source data either.
What should we be looking at? How should we figure out what makes
it slow?

In any case, have you tried using a profiler? You may need to learn
what they are and how to use them.

V

 

[Andreas Schmitt]

Functionality is missing there. No 'Init', no c-tor, no d-tor (if

it's needed at all, that is), no 'main'. No source data either.
What should we be looking at? How should we figure out what makes
it slow?

Alright, I uploaded the entire code:

http://www.wcrevival.de/joker/Sudoku_cpp.txt
http://www.wcrevival.de/joker/CSudokuRiddle_cpp.txt
http://www.wcrevival.de/joker/CSudokuRiddle_h.txt

 

[Andreas Schmitt]

Alright, I uploaded the entire code:

http://www.wcrevival.de/joker/Sudoku_cpp.txt
http://www.wcrevival.de/joker/CSudokuRiddle_cpp.txt
http://www.wcrevival.de/joker/CSudokuRiddle_h.txt

And the source data, in case you need it:

http://www.wcrevival.de/joker/input.txt

 

[=?iso-8859-1?q?Kirit_S=E6lensminde?=]

And the source data, in case you need it:

http://www.wcrevival.de/joker/input.txt

* Only use all caps for #define macros - don't use them for typedefs,
structs or class names.
* Init() - You should do the initialisation in the constructor so that
it isn't possible to forget to do it.
* Using new is often acceptable, but if you find you're using delete
then think very carefully. Normally you should try to find a smart
pointer that has the right semantics. For many of your uses I think
boost::scoped_ptr should be fine. Better yet get rid of the pointers
all together.
* Don't use hungarian notation - it's ugly and doesn't really buy you
anything.

I can't really tell how it is solving the puzzles, but it looks like
you're doing a lot of manipulation building and rebuilding data
structures. I would guess that this is a likely place to look for speed
improvements.

You don't seem to be using iterators or any of the algorithms from the
standard library. It may be that restructuring in terms of those would
also help.

You really need a profiler though to get anywhere properly - everything
else is just guess work.

K

 

[Earl Purple]

typedef std::vector<std::vector<ENTRY>> ENTRIES;

won't compile. Needs a space between the two > symbols. And
vector<vector< > > is not usually a good idea anyway although I haven't
looked to see what it is used for here.

std::list is rarely correct to use either. For a small collection of
numbers, if you want an ordered list then use vector<int> or even
std::string if all the ints will fit into char, or std::wstring if they
don't but fit into wchar_t. If you don't need ordering then std::bitset
if you know the size you need, vector<bool> acts like bitset but is
resizable and vector<int> is an alternative but unlike the above
vector<int> here you size it to the number of possibly values you are
looking up and have a 0 or 1 in each slot (but unlike vector<bool> you
can use it with algorithms safely)

Now I mention algorithms - they are obviously key to what you are
doing. Check the complexity of them.

 

[Andreas Schmitt]

won't compile. Needs a space between the two > symbols.

Uh? Compiles without problems on my Visual C++ 2005, never read
anywhere that a space is needed there either. Is that fixed in the C++
Standard?
Never heard of that necessity

 

[red floyd]

Uh? Compiles without problems on my Visual C++ 2005, never read
anywhere that a space is needed there either. Is that fixed in the C++
Standard?
Never heard of that necessity

It's supposed to be fixed in C++0x, but in C++98 TC1 2.4/3:

"If the input stream has been pared into preprocessing token up to a
given character, the next preprocessing token is hte longest sequence of
characters that could constitute a preprocessing token, even if that
would cause further lexical analysis to fail."

Thus the >> would be tokenized as the right shift operator, rather than
two separate > tokens. Try compiling with /Za. What you're seeing is a
language extension in VC2005.