soduko1.sql and soduko2.sql are the two originals. soduko3.sql removes the
digits view to an actual table (from soduko2.sql) and soduko3.sql puts digits
back in as a CTE but is a select from the wholenumber module rather than
generating the digits recursively.
So, the fastest one uses digits pregenerated as a table with both text and
integer columns used in the appropriate places dictated by the format
requirement in order to avoid conversions. All run one after the other on a
3Ghz core, single threaded, solving the same problem.
The main determinants are whether or not the digits is a CTE thus regenerated
each time needed, and whether the digits table contains both text and integer
values so that conversions can be avoided. The former (CTE regeneration) may
be able to be fixed in the optimizer. The latter (conversions) is pretty much
expected and why we have datatypes.
>timethis sqlite < soduko1.sql
TimeThis : Command Line : sqlite
TimeThis : Start Time : Sun Jan 19 11:43:39 2014
812753649943682175675491283154237896369845721287169534521974368438526917796318452
TimeThis : Command Line : sqlite
TimeThis : Start Time : Sun Jan 19 11:43:39 2014
TimeThis : End Time : Sun Jan 19 11:45:27 2014
TimeThis : Elapsed Time : 00:01:47.919
>timethis sqlite < soduko2.sql
TimeThis : Command Line : sqlite
TimeThis : Start Time : Sun Jan 19 11:46:39 2014
812753649943682175675491283154237896369845721287169534521974368438526917796318452
TimeThis : Command Line : sqlite
TimeThis : Start Time : Sun Jan 19 11:46:39 2014
TimeThis : End Time : Sun Jan 19 11:50:42 2014
TimeThis : Elapsed Time : 00:04:02.752
>timethis sqlite < soduko3.sql
TimeThis : Command Line : sqlite
TimeThis : Start Time : Sun Jan 19 11:50:50 2014
812753649943682175675491283154237896369845721287169534521974368438526917796318452
TimeThis : Command Line : sqlite
TimeThis : Start Time : Sun Jan 19 11:50:50 2014
TimeThis : End Time : Sun Jan 19 11:52:10 2014
TimeThis : Elapsed Time : 00:01:19.912
>timethis sqlite < soduko4.sql
TimeThis : Command Line : sqlite
TimeThis : Start Time : Sun Jan 19 11:52:17 2014
812753649943682175675491283154237896369845721287169534521974368438526917796318452
TimeThis : Command Line : sqlite
TimeThis : Start Time : Sun Jan 19 11:52:17 2014
TimeThis : End Time : Sun Jan 19 11:54:14 2014
TimeThis : Elapsed Time : 00:01:56.807
soduko1 uses:
drop table if exists gen9;
create table gen9(z);
insert into gen9 values ('1'),('2'),('3'),('4'),('5'),('6'),('7'),('8'),('9');
drop table if exists initial;
create table initial (s, ind);
insert into initial
select sud, instr( sud, ' ')
from (SELECT
--- '53 7 6 195 98 6 8 6 34 8 3 17 2 6 6
28 419 5 8 79'
'8 36 7 9 2 5 7 457 1 3 1
68 85 1 9 4 '
as sud) as q;
soduko2:
WITH RECURSIVE input(sud) AS (
VALUES(
'8..........36......7..9.2...5...7.......457.....1...3...1....68..85...1..9....4..'
---
'53..7....6..195....98....6.8...6...34..8.3..17...2...6.6....28....419..5....8..79'
)
),
/* A table filled with digits 1..9, inclusive. */
digits(z, lp) AS (
VALUES('1', 1)
UNION ALL SELECT
CAST(lp+1 AS TEXT), lp+1 FROM digits WHERE lp<9
),
soduko3:
create table digits(lp integer primary key, z text);
create virtual table w using wholenumber;
insert into digits (lp, z) select value, cast(value as text) from w where value
between 1 and 9;
WITH RECURSIVE input(sud) AS (
VALUES(
'8..........36......7..9.2...5...7.......457.....1...3...1....68..85...1..9....4..'
---
'53..7....6..195....98....6.8...6...34..8.3..17...2...6.6....28....419..5....8..79'
)
),
and soduko4:
create virtual table w using wholenumber;
WITH RECURSIVE input(sud) AS (
VALUES(
'8..........36......7..9.2...5...7.......457.....1...3...1....68..85...1..9....4..'
---
'53..7....6..195....98....6.8...6...34..8.3..17...2...6.6....28....419..5....8..79'
)
),
/* A table filled with digits 1..9, inclusive. */
digits(z, lp) AS (
select cast(value as text), value from w where value between 1 and 9
-- VALUES('1', 1)
-- UNION ALL SELECT
-- CAST(lp+1 AS TEXT), lp+1 FROM digits WHERE lp<9
),
>-----Original Message-----
>From: sqlite-users-boun...@sqlite.org [mailto:sqlite-users-
>boun...@sqlite.org] On Behalf Of big stone
>Sent: Sunday, 19 January, 2014 04:54
>To: sqlite-users@sqlite.org
>Subject: Re: [sqlite] Solving the Sudoku with SQlite 3.8.3 trunk
>
>Hi Keith,
>
>Indeed just removing the CTE creation of the DIGITS makes Dan's version
>up
>to speed.
>
>Would the "wholenumber" external SQLite module help :
>- to make SQLite code cleaner ? (like "generate_series" of Postgresql, or
>"dual" of Oracle)
>- still provide the same speed-up ?
>
>
>Portfolio of typical Sudokus
>-- easy (0 sec)
>'53..7....6..195....98....6.8...6...34..8.3..17...2...6.6....28....419..5
>....8..79'
>-- medium (2 sec)
>'1....7.9..3..2...8..96..5....53..9...1..8...26....4...3......1..4......7
>..7...3..'
>-- hard (200 s)
>'8..........36......7..9.2...5...7.......457.....1...3...1....68..85...1.
>.9....4..'
>
>WITH RECURSIVE input(sud) AS (
> VALUES(
>'53..7....6..195....98....6.8...6...34..8.3..17...2...6.6....28....419..5
>....8..79'
> )
>),
>
>/* A table filled with digits 1..9, inclusive. */
>digits(z, lp) AS (
> VALUES('1', 1),('2', 2) ,('3', 3),('4', 4),('5', 5),('6', 6),('7',
>7),('8', 8),('9', 9)
> ),
>
>/* The tricky bit. */
>x(s, ind) AS (
> SELECT sud, instr(sud, '.') FROM input
> UNION ALL
> SELECT
> substr(s, 1, ind-1) || z || substr(s, ind+1),
> instr( substr(s, 1, ind-1) || z || substr(s, ind+1), '.' )
> FROM x, digits AS z
> WHERE ind>0
> AND NOT EXISTS (
> SELECT 1 FROM digits AS lp
> WHERE z.z = substr(s, ((ind-1)/9)*9 + lp, 1)
> OR z.z = substr(s, ((ind-1)%9) + (lp-1)*9 + 1, 1)
> OR z.z = substr(s, (((ind-1)/3) % 3) * 3
> + ((ind-1)/27) * 27 + lp
> + ((lp-1) / 3) * 6
> , 1)
> )
>)
>
>SELECT s FROM x WHERE ind=0;
>_______________________________________________
>sqlite-users mailing list
>sqlite-users@sqlite.org
>http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
_______________________________________________
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
