Am Montag 01 März 2010 19:29:45 schrieb Artyom Kazak: > 2010/3/1 Daniel Fischer <daniel.is.fisc...@web.de>: > > In the algorithm. You investigate far too many dead ends. Since for > > larger boards, the number of dead ends increases fast, larger boards > > take much much longer. > > With one little change, I get > > ... > > For a reason I don't understand, if the second dimension is 60 and the > > first is > 18, it takes much longer, > >... > > The magic change: > > > > e ((x, y), arr) p = [(t, arr // [(t, p)]) | t <- changes] > > where > > legit ps = [t | t <- allTurns ! ps, arr!t == 0] > > changes = map snd $ sort [(length $ legit t, t) | t <- > > allTurns ! (x, y), arr ! t == 0] > > > > investigate squares with fewer options first. > > Wow! Thanks you! > By the way, I didn't notice the difference between (59, 59) and (60, > 60) on my machine...
Strangely, $ echo "62 59" | time ./knights > /dev/null 0.10user 0.08system 0:00.17elapsed 101%CPU $ echo "65 59" | time ./knights > /dev/null 0.08user 0.07system 0:00.17elapsed 96%CPU , so it's a thing of the second dimension predominantly (the size plays a small role, too). As I said, I don't understand it, but looking at the allocation figures: 70*59: 97,970,072 bytes allocated in the heap 18*60: 12,230,296 bytes allocated in the heap 19*60: 2,374,148,320 bytes allocated in the heap 19*61: 13,139,688 bytes allocated in the heap 60*61: 71,771,324 bytes allocated in the heap 61*61: 72,965,428 bytes allocated in the heap it seems that something is kicked out of the registers when the second dimension is 60 and the first > 18. Very strange. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe