August 24, 2012 Re: Sudoku Py / C++11 / D? | ||||
---|---|---|---|---|
| ||||
Posted in reply to maarten van damme | maarten van damme: > http://dpaste.dzfl.pl/8a2aef5b Some suggestions about the code: - Put a space before and after operators, after a commas and semicolon, around "..", etc. - Compile with "-wi -property"; - Try to add pure/const/nothrow/immutable where possible; - Minimize the need of cast(); - Sometimes it's useful to localize the imports (stdio e datetime are used just by the main); - Minimize the usage of magical constants like 0b10_0000_0000, possibly define it only once. And often adding underscores inside long numbers is handy (here I have put them every 4 digits because it's binary); - Repeating things like "short[81]" in many function signatures is quite bad. Better to define a global type with alias (or someday better with std.typecons.Typedef when it will work), and then use it; - Generally it's better to use unsigned values for array indexes; - If you look for performance and your program is single thread, then it's better to annotate global variables with __gshared; - This: ubyte[81] taken = false; is better than this: ubyte[81] taken; taken[] = false; This is your code modified, it's also a little faster: http://dpaste.dzfl.pl/06510dcd I will try to replace the int[] of cachedBitsetToRange with something more static, to reduce indirection. Bye, bearophile |
August 24, 2012 Re: Sudoku Py / C++11 / D? | ||||
---|---|---|---|---|
| ||||
Posted in reply to bearophile | > I will try to replace the int[] of cachedBitsetToRange with something more static, to reduce indirection. Yeah, it's a bit faster, but not a lot: http://dpaste.dzfl.pl/b04a0127 Bye, bearophile |
August 24, 2012 Re: Sudoku Py / C++11 / D? | ||||
---|---|---|---|---|
| ||||
Posted in reply to bearophile | > Some suggestions about the code: Thank you very much for your criticism, there are indeed a lot of points where I have to improve on. > - Put a space before and after operators, after a commas and semicolon, > around "..", etc. > - Compile with "-wi -property"; > - Try to add pure/const/nothrow/immutable where possible; I realize the usefullness of keywords like these but having to type them over and over again tends to become rather annoying. There are functions where the implementation is shorter than it's declaration... Is there a special reason I should use them in little programs like these? > - Minimize the need of cast(); > - Sometimes it's useful to localize the imports (stdio e datetime are used > just by the main); > - Minimize the usage of magical constants like 0b10_0000_0000, possibly > define it only once. And often adding underscores inside long numbers is > handy (here I have put them every 4 digits because it's binary); > - Repeating things like "short[81]" in many function signatures is quite > bad. Better to define a global type with alias (or someday better with > std.typecons.Typedef when it will work), and then use it; > - Generally it's better to use unsigned values for array indexes; > - If you look for performance and your program is single thread, then it's > better to annotate global variables with __gshared; I'm not all that familiar with __gshared, why does it increase performance? > > - This: > ubyte[81] taken = false; > is better than this: > ubyte[81] taken; > taken[] = false; I know and I think I can even leave false out because the default value of ubyte is 0 => false. I had a big in my code and it took me a long time to find it. That line is a leftover of a desperate attempt at finding it :) (as is line 101) I even tried using array!bool but even instantiating failed so I gave up. Would performance increase be noticeable? I guess not. > > > This is your code modified, it's also a little faster: http://dpaste.dzfl.pl/06510dcd > Thank you. I see you also used contracts, looks better now :) (using contracts is really something I should start doing...) > I will try to replace the int[] of cachedBitsetToRange with something more static, to reduce indirection. > > Bye, > bearophile I should also add a little check to see if every value I put is indeed numerical. |
August 24, 2012 Re: Sudoku Py / C++11 / D? | ||||
---|---|---|---|---|
| ||||
Posted in reply to maarten van damme | On 08/24/2012 09:32 PM, maarten van damme wrote:
> I've distiled what I understood from your source and the resulting
> executable managed to solve the impossible one in 27 seconds while
> your source takes 41 seconds.
>
It is 10s vs 13s with GDC on my machine.
|
August 24, 2012 Re: Sudoku Py / C++11 / D? | ||||
---|---|---|---|---|
| ||||
and everythingPossible should also be changed to something ala 2 ^(side) -1 |
August 24, 2012 Re: Sudoku Py / C++11 / D? | ||||
---|---|---|---|---|
| ||||
Posted in reply to Timon Gehr | 2012/8/25 Timon Gehr <timon.gehr@gmx.ch>: > On 08/24/2012 09:32 PM, maarten van damme wrote: >> >> I've distiled what I understood from your source and the resulting executable managed to solve the impossible one in 27 seconds while your source takes 41 seconds. >> > > It is 10s vs 13s with GDC on my machine. > I've only tried dmd but I'm installing gdc on this laptop too. When that's done I'm going to see how they both perform on this puzzle : http://en.wikipedia.org/wiki/File:Sudoku_puzzle_hard_for_brute_force.jpg |
August 25, 2012 Re: Sudoku Py / C++11 / D? | ||||
---|---|---|---|---|
| ||||
Posted in reply to maarten van damme | maarten van damme: > Is there a special reason I should use them in little programs like these? In my experience small programs contain lot of the issues and ideas contained in large programs. Using things like "pure" and "const/immutable" helps avoid/catch some bugs even in small programs. Generally try to make your code as strong as possible, to avoid chances of introducing bugs. > I'm not all that familiar with __gshared, why does it increase performance? That implements global variables as in C. Take a look at the D docs, about thread-local memory, etc. > Would performance increase be noticeable? I guess not. In your code I have seen performance increase replacing ubyte[] with bool[]. > (using contracts is really something I should start doing...) Yep. It's a matter of self-training. > I should also add a little check to see if every value I put is indeed numerical. That's very easy to do: if (args[1].length != size || args[1].countchars("0-9") != args[1].length) { writeln("A sudoku is 81 0-9 digits, not ", args[1].length, " digits"); return; } Bye, bearophile |
August 25, 2012 Re: Sudoku Py / C++11 / D? | ||||
---|---|---|---|---|
| ||||
Posted in reply to Timon Gehr | On 08/25/2012 01:01 AM, Timon Gehr wrote: > On 08/24/2012 09:32 PM, maarten van damme wrote: >> I've distiled what I understood from your source and the resulting >> executable managed to solve the impossible one in 27 seconds while >> your source takes 41 seconds. >> > > It is 10s vs 13s with GDC on my machine. > I have inlined some ranges. http://dpaste.dzfl.pl/4a7e4038 I now measure 10.5s vs 6.7s (GDC) and 20s vs 12s (DMD). |
August 25, 2012 Re: Sudoku Py / C++11 / D? | ||||
---|---|---|---|---|
| ||||
Posted in reply to Timon Gehr | On 08/25/2012 02:38 AM, Timon Gehr wrote: > On 08/25/2012 01:01 AM, Timon Gehr wrote: >> On 08/24/2012 09:32 PM, maarten van damme wrote: >>> I've distiled what I understood from your source and the resulting >>> executable managed to solve the impossible one in 27 seconds while >>> your source takes 41 seconds. >>> >> >> It is 10s vs 13s with GDC on my machine. >> > > I have inlined some ranges. > > http://dpaste.dzfl.pl/4a7e4038 > > I now measure 10.5s vs 6.7s (GDC) and 20s vs 12s (DMD). I meant to paste this: http://dpaste.dzfl.pl/8fa23a97 |
August 25, 2012 Re: Sudoku Py / C++11 / D? | ||||
---|---|---|---|---|
| ||||
Posted in reply to maarten van damme | On Friday, 24 August 2012 at 23:14:02 UTC, maarten van damme wrote:
> http://en.wikipedia.org/wiki/File:Sudoku_puzzle_hard_for_brute_force.jpg
It occurs to me that one of the main reasons why this particular puzzle would be hard for brute force is that the first line is blank and more than half of the second line is blank, and it seems like it is designed to have as many choices as possible before a set square is encountered.
I bet it could be solved much quicker by a computer by doing it in reverse.
I've got some ideas, maybe I'll write a solution to this myself. :)
|
Copyright © 1999-2021 by the D Language Foundation