为什么翻译的Sudoku求解器比原始的慢? [英] Why is translated Sudoku solver slower than original?
问题描述
我将Java Sudoku求解器转录为python.一切正常，但是解决过程最多需要2分钟，而在Java中，相同的难题仅需几秒钟.同样，所需的迭代次数完全相同.我想念什么吗?
I transcribed my Java Sudoku solver into python. Everything works, however solving takes up to 2mins, while the identical puzzle takes only a few seconds in Java. Also the iterations needed amount to the exact same number. Am I missing something?
import numpy as np
def solve_recursive(puzzle, pos):
if(pos == 81):
print puzzle
return True
if(puzzle[pos] != 0):
if (not solve_recursive(puzzle, pos+1)):
return False
else:
return True
row = np.copy(puzzle[pos//9*9:pos//9*9+9])
col = np.copy(puzzle[pos%9::9])
short = (pos%9)//3*3 + pos//27*27
square = np.concatenate((puzzle[short:short+3],puzzle[short+9:short+12],puzzle[short+18:short+21]))
for i in range(1,10):
puzzle[pos] = i
if(i not in row and i not in col and i not in square and solve_recursive(puzzle, pos+1)):
return True
puzzle[pos] = 0
return False
puzzle = np.array([[0,0,0,0,0,0,0,8,3],
[0,2,0,1,0,0,0,0,0],
[0,0,0,0,0,0,0,4,0],
[0,0,0,6,1,0,2,0,0],
[8,0,0,0,0,0,9,0,0],
[0,0,4,0,0,0,0,0,0],
[0,6,0,3,0,0,5,0,0],
[1,0,0,0,0,0,0,7,0],
[0,0,0,0,0,8,0,0,0]])
solve_recursive(puzzle.ravel(), 0)
按照@hpaulj的建议，我重新编写了代码以使用numpy的2D数组:
As suggested by @hpaulj I reworked my code to work with numpy´s 2D arrays:
import numpy as np
def solve_recursive(puzzle, pos):
if pos == (0,9):
print puzzle
raise Exception("Solution")
if(puzzle[pos] != 0):
if(pos[0] == 8):
solve_recursive(puzzle, (0,pos[1]+1))
return
elif pos[0] < 8:
solve_recursive(puzzle, (pos[0]+1, pos[1]))
return
for i in range(1,10):
if(i not in puzzle[pos[0]] and i not in puzzle[:,pos[1]] and i not in puzzle[pos[0]//3*3:pos[0]//3*3+3,pos[1]//3*3:pos[1]//3*3+3]):
puzzle[pos] = i
if(pos[0] == 8):
solve_recursive(puzzle, (0,pos[1]+1))
elif pos[0] < 8:
solve_recursive(puzzle, (pos[0]+1, pos[1]))
puzzle[pos] = 0
puzzle = np.array([[0,0,0,0,0,0,0,8,3],
[0,2,0,1,0,0,0,0,0],
[0,0,0,0,0,0,0,4,0],
[0,0,0,6,1,0,2,0,0],
[8,0,0,0,0,0,9,0,0],
[0,0,4,0,0,0,0,0,0],
[0,6,0,3,0,0,5,0,0],
[1,0,0,0,0,0,0,7,0],
[0,0,0,0,0,8,0,0,0]])
solve_recursive(puzzle, (0,0))
忽略以下事实:在递归调用的底部抛出异常非常微不足道，这仅比我原来的解决方案快得多.使用像链接的Norvig求解器这样的字典是否是一种合理的选择?
Ignoring the fact that throwing an exception at the bottom of the recursive calls is rather inelegant, this is just inconsiderably faster than my original solution. Would using dictionaries like the linked Norvig solver be a reasonable alternative?
推荐答案
我修改了函数以打印pos并保持调用次数的运行计数.而且我早点停止了.
I modified your function to print the pos and to maintain a running count of the times it's been called. And I stop it early.
在pos==46处停止会导致1190次呼叫，仅有轻微的可见延迟.但是，对于47，该数字是416621，运行了一分钟或更长时间.
Stopping at pos==46 results in 1190 calls, with just a slight visible delay. But for 47 the count is 416621, with a minute or more run.
假设它正在进行某种递归搜索，则该问题的难度在46到47之间发生了量子跃变.
Assuming it's doing some sort of recursive search, the problem had a quantum jump in difficulty between 46 and 47.
是的，Python作为一种解释型语言，其运行速度将比Java慢.可能的解决方案包括弄清楚为什么递归调用中会有这种跳跃.或提高每次通话的速度.
Yes, Python as an interpreted language will run slower than Java. Possible solutions include figuring out why there's this kind of jump in recursion calls. Or improving the speed of each call.
您设置了9x9的numpy数组，但随后立即对其进行了整理.然后，函数本身会将开发板视为81个值的列表.这意味着选择行，列和子矩阵要比数组仍为2d要复杂得多.实际上，数组只是一个列表.
You set up 9x9 numpy array, but then immediately ravel it. The function itself then treats the board as a list of 81 values. That means selecting rows and columns and submatrices is much more complicated than if the array were still 2d. In effect the array is just a list.
我可以想象两种加快通话速度的方法.一种是重新编码以使用列表板.对于小型数组和迭代操作列表，其开销比数组少，因此通常更快.一种替代方法是对其进行编码，以真正利用数组的2d性质. numpy解决方案只有在它们允许numpy使用编译代码执行大多数操作的情况下才是好的.数组上的迭代速度很慢.
I can imagine 2 ways of speeding up the calls. One is to recode it to use a list board. For small arrays and iterative actions lists have less overhead than arrays, so often are faster. An alternative is to code it to really take advantage of the 2d nature of the array. numpy solutions are good only if they let numpy use compiled code to perform most actions. Iteration over an array is slow.
==================
==================
更改函数，使其与平面列表而不是混乱的数组一起运行，运行速度要快得多.最高排名为47，它的运行时间为15秒，而原始版本(相同的电路板和迭代次数)则为1m 15s.
Changing your function so that it works with a flat list instead of the raveled array, runs much faster. For a max pos of 47, it runs in 15sec, versus 1m 15s for your original (same board and iteration count).
我正在清理2d numpy数组版本，但没有使其更快.
I'm cleaning up a 2d numpy array version, but not making it any faster.
纯列表版本也是在pypy上运行速度更快的理想选择.
A pure list version is also a good candidate for running faster on pypy.
与2d数组一起使用的部分代码
A portion of the code that works with a 2d array
r,c = np.unravel_index(pos, (9,9))
if(puzzle[r,c] != 0):
return solve_numpy(puzzle, pos+1)
row = puzzle[r,:].copy()
col = puzzle[:,c].copy()
r1, c1 = 3*(r//3), 3*(c//3)
square = puzzle[r1:r1+3, c1:c1+3].flatten()
for i in range(1,10):
puzzle[r,c] = i
if(i not in row and i not in col and i not in square):
if solve_numpy(puzzle, pos+1):
return True
puzzle[r,c] = 0
索引更清晰，但是速度没有提高.除了更简单的索引编制之外，它并没有过多地使用整个数组操作.
Indexing is clearer, but there isn't a speed improvement. Other than simpler indexing, it doesn't make much use of whole array operations.
list版本看起来与原始版本没有太大区别，但是速度更快:
The list version doesn't look that much different from the original, but is much faster:
row = puzzle[pos//9*9:pos//9*9+9]
col = puzzle[pos%9::9]
short = (pos%9)//3*3 + pos//27*27
square = puzzle[short:short+3] + \
puzzle[short+9:short+12] + \
puzzle[short+18:short+21]
http://norvig.com/sudoku.html 通过pythoN讨论数独解决方案的方法-by AI专家.
http://norvig.com/sudoku.html Discusses sudoku solution methods, with pythoN - by an AI expert.
使用此Norvig求解器，您的网格解决方案将花费0.01秒.信息主要存储在词典中.您的案例很简单，用他的两种基本分配策略即可解决.不搜索解决方案就非常快.
With this Norvig solver, your grid solution takes 0.01 sec. Information is stored primarily in dictionaries. Your case is an easy one, than can be solved with his 2 basic assignment strategies. Without searching the solution is very fast.
这篇关于为什么翻译的Sudoku求解器比原始的慢?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
