| View previous topic :: View next topic |
| Author |
Message |
| gsf
| | Joined: 18 Aug 2005 | | Posts: 411 | | : | | Location: NJ USA |
Items |
|
 Posted: Wed Nov 05, 2008 6:52 am Post subject: |
 |
|
| Code: |
if (i == 81) printf ("º\nÈÍÍÏÍÍÏÍÍÊÍÍÏÍÍÏÍÍÊÍÍÏÍÍÏÍͼ\n");
else if ((i % 27) == 0) printf ("º\nÌÍÍØÍÍØÍÍÎÍÍØÍÍØÍÍÎÍÍØÍÍØÍ͹\n");
else if ((i % 9) == 0) printf ("º\nÇÄÄÅÄÄÅÄÄ×ÄÄÅÄÄÅÄÄ×ÄÄÅÄÄÅÄĶ\n");
|
so how are these printfs different from inline assembly? |
|
| Back to top |
|
 |
| briturner
| | Joined: 14 Oct 2008 | | Posts: 75 | | : | |
Items |
|
| Posted: Wed Nov 05, 2008 7:29 am Post subject: |
|
|
They are just printf statements, nothing special about them.
In my code, the odd characters show up as ascii characters for drawing full grids. They did not translate well putting them on the web page.
I will use a picture of the code and output so you can see what it looks like:
[img]http://tttarabians.com/sudoku/grid.bmp[/img]
brit |
|
| Back to top |
|
|
| gsf
| | Joined: 18 Aug 2005 | | Posts: 411 | | : | | Location: NJ USA |
Items |
|
| Posted: Wed Nov 05, 2008 7:44 am Post subject: |
|
|
| briturner wrote: | They are just printf statements, nothing special about them.
In my code, the odd characters show up as ascii characters for drawing full grids. They did not translate well putting them on the web page.
|
nothing against your code which I'm glad you posted
it looks to be the fastest right now
its just that those printfs are about as portable as inline asm
I jumped in because C portablility has many facets
inline asm being pretty obvious
printf using special characters being much more sublte
especially since the latter can easily escape compiler complaints |
|
| Back to top |
|
|
| briturner
| | Joined: 14 Oct 2008 | | Posts: 75 | | : | |
Items |
|
| Posted: Wed Nov 05, 2008 2:36 pm Post subject: |
|
|
Don't forget using nonstandard includes, which I also do for timings.
If anyone knows how to do high speed timers in linux, please let me know. I have the option of timing each puzzle, but clock ticks are way to slow (I don't have a single puzzle that takes 16 milliseconds, most take under 50 usec). On my laptop, I can measure in 0.27 usec increments, and my desktop, I am measuring in the nanoseconds.
The same is true for the other solvers, they use getopt, which is not a standard library, so I have to work around that when I compile the other solvers.
brit |
|
| Back to top |
|
|
| gsf
| | Joined: 18 Aug 2005 | | Posts: 411 | | : | | Location: NJ USA |
Items |
|
| Posted: Wed Nov 05, 2008 2:58 pm Post subject: |
|
|
| briturner wrote: | If anyone knows how to do high speed timers in linux, please let me know. I have the option of timing each puzzle, but clock ticks are way to slow (I don't have a single puzzle that takes 16 milliseconds, most take under 50 usec). On my laptop, I can measure in 0.27 usec increments, and my desktop, I am measuring in the nanoseconds.
The same is true for the other solvers, they use getopt, which is not a standard library, so I have to work around that when I compile the other solvers.
|
this is from my full-features solver which compiles on windows and unix
the function usr() returns the current user usage in microseconds
you can time a portion of code by
| Code: | t0 = usr();
...
t1 = usr();
usage_in_usec = t1 - t0;
|
here it is
it looks like you can improve on the _WIN32 code
| Code: | #define US 1000000L
#if _WIN32
#include <windows.h>
static uint64_t
usr(void)
{
uint64_t fs;
static uint64_t os;
fs = (US / 1000) * GetTickCount();
if (fs < os)
fs += 0xffffffffL + 1;
return os = fs;
}
#else
#include <sys/time.h>
#include <sys/resource.h>
static uint64_t
usr(void)
{
uint64_t us;
struct rusage ru;
getrusage(RUSAGE_SELF, &ru);
us = ru.ru_utime.tv_sec + ru.ru_stime.tv_sec;
return us * US + ru.ru_utime.tv_usec + ru.ru_stime.tv_usec;
}
#endif
|
|
|
| Back to top |
|
|
| m_b_metcalf
| | Joined: 13 Mar 2006 | | Posts: 210 | | : | | Location: Berlin |
Items |
|
| Posted: Thu Nov 06, 2008 4:38 pm Post subject: |
|
|
| briturner wrote: | | (I don't have a single puzzle that takes 16 milliseconds, ... |
Have you tried this one, from tarek?
| Code: |
. . 1 . . 4 . . .
. . . . 6 . 3 . 5
. . . 9 . . . . .
8 . . . . . 7 . 3
. . . . . . . 2 8
5 . . . 7 . 6 . .
3 . . . 8 . . . 6
. . 9 2 . . . . .
. 4 . . . 1 . . . |
Regards,
Mike Metcalf |
|
| Back to top |
|
|
| briturner
| | Joined: 14 Oct 2008 | | Posts: 75 | | : | |
Items |
|
| Posted: Fri Nov 07, 2008 4:14 am Post subject: |
|
|
Greetings,
That particular puzzle (tarek) takes 1516.60 usec.
Worst case puzzle was in the Top 1465, which took 4033.40 usec:
7..4......5....3........1..368..........2..5....7........5...7213...8...6........
so, worst case for me (1.83 ghz processor) is around 4 milliseconds.
brit |
|
| Back to top |
|
|
| zerothbase
| | Joined: 02 Nov 2008 | | Posts: 17 | | : | |
Items |
|
| Posted: Fri Nov 07, 2008 9:10 am Post subject: |
|
|
zerodoku_v2.c:
http://tinyurl.com/6krpwl
speed improvement based upon briturner's idea of caching all row/col/box groups - thanks
It actually shortened the code somewhat too. |
|
| Back to top |
|
|
| hobiwan
| | Joined: 11 Feb 2008 | | Posts: 83 | | : | |
Items |
|
| Posted: Fri Nov 07, 2008 10:13 am Post subject: |
|
|
| briturner wrote: | | so, worst case for me (1.83 ghz processor) is around 4 milliseconds. |
Two puzzles that are hard for brute force solvers (or at least for mine):
| Code: | .1.....2....8..6.......3........43....2.1....8......9.4...7.5.3...2...........4..
..15............32...............2.9.5...3......7..8..27.....4.3...9.......6..5.. |
|
|
| Back to top |
|
|
| m_b_metcalf
| | Joined: 13 Mar 2006 | | Posts: 210 | | : | | Location: Berlin |
Items |
|
| Posted: Fri Nov 07, 2008 10:38 am Post subject: |
|
|
| hobiwan wrote: | Two puzzles that are hard for brute force solvers (or at least for mine):
| Code: | .1.....2....8..6.......3........43....2.1....8......9.4...7.5.3...2...........4..
..15............32...............2.9.5...3......7..8..27.....4.3...9.......6..5.. |
|
But if you solve for singles before starting, there's almost nothing left for a brute-force solver to do.
Regards,
Mike Metcalf |
|
| Back to top |
|
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in
Log in to check your private messages
