Commits

Pierre Carbonnelle committed 548a7b6

improve speed of queens resolution by 15 to 20%

  • Participants
  • Parent commits 9f4ecfe

Comments (0)

Files changed (2)

pyDatalog/examples/queens.py

 import time
 
 pyDatalog.create_atoms('N,X0,X1,X2,X3,X4,X5,X6,X7')
-pyDatalog.create_atoms('ok,queens0,queens1,queens2,queens3,queens4,queens5,queens6,queens7')
+pyDatalog.create_atoms('ok,queens,next_queen')
 
 # when is it ok to have a queen in row X1 and another in row X2, separated by N columns
 # this is memoized !
-#ok(X1, N, X2) <= (X1!=X2) & (X1!= X2+N) & (X1!=X2-N)
-@pyDatalog.predicate()
-def ok3(X1, N, X2):
-    if (X1.id!=X2.id) and (X1.id!= X2.id+N.id) and (X1.id!=X2.id-N.id):
-        yield (X1.id, N.id, X2.id)
+ok(X1, N, X2) <= (X1 != X2) & (X1 != X2+N) & (X1 != X2-N)
 
-queens0(X0) <= (X0._in(range(8)))
-queens1(X0,X1) <= queens0(X0) & queens0(X1) & ok(X1,1,X0)
-queens2(X0,X1,X2) <= queens1(X0,X1) & queens1(X1,X2) & ok(X0,2,X2)
-queens3(X0,X1,X2,X3) <= queens2(X0,X1,X2) & queens2(X1,X2,X3) & ok(X0,3,X3)
-queens4(X0,X1,X2,X3,X4) <= queens3(X0,X1,X2,X3) & queens3(X1,X2,X3,X4) & ok(X0,4,X4)
-queens5(X0,X1,X2,X3,X4,X5) <= queens4(X0,X1,X2,X3,X4) & queens4(X1,X2,X3,X4,X5) & ok(X0,5,X5)
-queens6(X0,X1,X2,X3,X4,X5,X6) <= queens5(X0,X1,X2,X3,X4,X5) & queens5(X1,X2,X3,X4,X5,X6) & ok(X0,6,X6)
-queens7(X0,X1,X2,X3,X4,X5,X6,X7) <= queens6(X0,X1,X2,X3,X4,X5,X6) & queens6(X1,X2,X3,X4,X5,X6,X7) & ok(X0,7,X7)
+queens(X0)                      <= (X0._in(range(8)))
+queens(X0,X1)                   <= queens(X0)                   & next_queen(X0,X1)
+queens(X0,X1,X2)                <= queens(X0,X1)                & next_queen(X0,X1,X2)
+queens(X0,X1,X2,X3)             <= queens(X0,X1,X2)             & next_queen(X0,X1,X2,X3)
+queens(X0,X1,X2,X3,X4)          <= queens(X0,X1,X2,X3)          & next_queen(X0,X1,X2,X3,X4)
+queens(X0,X1,X2,X3,X4,X5)       <= queens(X0,X1,X2,X3,X4)       & next_queen(X0,X1,X2,X3,X4,X5)
+queens(X0,X1,X2,X3,X4,X5,X6)    <= queens(X0,X1,X2,X3,X4,X5)    & next_queen(X0,X1,X2,X3,X4,X5,X6)
+queens(X0,X1,X2,X3,X4,X5,X6,X7) <= queens(X0,X1,X2,X3,X4,X5,X6) & next_queen(X0,X1,X2,X3,X4,X5,X6,X7)
+
+next_queen(X0,X1)                   <= queens(X1)                       & ok(X0,1,X1)
+next_queen(X0,X1,X2)                <= next_queen(X1,X2)                & ok(X0,2,X2)
+next_queen(X0,X1,X2,X3)             <= next_queen(X1,X2,X3)             & ok(X0,3,X3)
+next_queen(X0,X1,X2,X3,X4)          <= next_queen(X1,X2,X3,X4)          & ok(X0,4,X4)
+next_queen(X0,X1,X2,X3,X4,X5)       <= next_queen(X1,X2,X3,X4,X5)       & ok(X0,5,X5)
+next_queen(X0,X1,X2,X3,X4,X5,X6)    <= next_queen(X1,X2,X3,X4,X5,X6)    & ok(X0,6,X6)
+next_queen(X0,X1,X2,X3,X4,X5,X6,X7) <= next_queen(X1,X2,X3,X4,X5,X6,X7) & ok(X0,7,X7)
 
 # counting is 0-based, so this is actually the 8-queens solution
 start_time = time.time()
-print(queens7(X0,X1,X2,X3,X4,X5,X6,X7))
+print(queens(X0,X1,X2,X3,X4,X5,X6,X7))
 print("First datalog run in %f seconds" % (time.time() - start_time))
 
 start = time.time()
 for i in range(20):  
     # there is a warm-up period for the JIT --> let's compute it again
     start_time = time.time()
-    datalog_count = len(queens7(X0,X1,X2,X3,X4,X5,X6,X7))
+    datalog_count = len(queens(X0,X1,X2,X3,X4,X5,X6,X7))
     datalog_time = (time.time() - start_time)
     print(datalog_time)
 print("Average : %s" % ((time.time() - start)/20))
 print("python : %f seconds" % python_time)
 
 # results with pypy 1.9 on Intel Core i7-2820 QM CPU @ 2.3 GHz (run from Command prompt):
-# 0.17..0.24 sec for Datalog
+# 0.22 sec for Datalog in average
 # 0.11 sec for python

pyDatalog/examples/queens_N.py

 from pyDatalog import pyEngine
 
 pyDatalog.create_atoms('N,N1, X,Y, X0,X1,X2,X3,X4,X5,X6,X7')
-pyDatalog.create_atoms('ok,queens, pred')
+pyDatalog.create_atoms('ok,queens, next_queen, pred, pred2')
 
 size=8
 
 # when is it ok to have a queen in row X1 and another in row X2, separated by N columns
 # this is memoized !
-#ok(X1, N, X2) <= (X1!=X2) & (X1!= X2+N) & (X1!=X2-N)
-@pyDatalog.predicate()
-def ok3(X1, N, X2):
-    if (X1.id!=X2.id) and (X1.id!= X2.id+N.id) and (X1.id!=X2.id-N.id):
-        yield (X1.id, N.id, X2.id)
+ok(X1, N, X2) <= (X1 != X2) & (X1 != X2+N) & (X1 != X2-N)
 
-pred(N, N1) <= (N>1) & (N1==N-1)
-queens(1, X) <= (X1._in(range(size))) & (X1==X[0])
-queens(N, X) <= pred(N, N1) & queens(N1, X[:-1]) & queens(N1, X[1:]) & ok(X[0], N1, X[-1])
+pred(N, N1)     <= (N > 1) & (N1 == N-1)
+queens(1, X)    <= (X1._in(range(size))) & (X1 == X[0])
+queens(N, X)    <= pred(N, N1) & queens(N1, X[:-1]) & next_queen(N, X)
+
+pred2(N, N1)     <= (N >2) & (N1 == N-1)
+next_queen(2, X) <= (X1._in(range(8))) & ok(X[0], 1, X1) & (X1 == X[1])
+next_queen(N, X) <= pred2(N, N1) & next_queen(N1, X[1:]) & ok(X[0], N1, X[-1]) 
 
 start_time = time.time()
 print(queens(size, (X0,X1,X2,X3,X4,X5,X6,X7)))
 print("First datalog run in %f seconds" % (time.time() - start_time))
 
+start = time.time()
 for i in range(20):
     # there is a warm-up period for the JIT --> let's compute it again
     start_time = time.time()
     datalog_count = len(queens(size, (X0,X1,X2,X3,X4,X5,X6,X7)).data)
     datalog_time = (time.time() - start_time)
     print(datalog_time)
+print("Average : %s" % ((time.time() - start)/20))
 
 # pure python solution found on http://rosettacode.org/wiki/N-Queens#Python, for comparison purposes