View mode: basic / threaded / horizontal-split · Log in · Help
August 24, 2012
Re: Sudoku Py / C++11 / D?
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?
> 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?
> 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?
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?
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?
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?
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?
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?
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. 
:)
2 3 4 5 6 7 8
Top | Discussion index | About this forum | D home