Last visit was: It is currently Thu Mar 28, 2024 6:49 pm


All times are UTC-05:00




Post new topic Reply to topic  [64 posts ] 
Author Message
 Post subject:
PostPosted:Wed Aug 29, 2007 6:48 pm 
 

Joined:Thu Aug 09, 2007 9:09 am
Posts:26
Quote:
I wasn't clear enough, transform is fine, the problem is it's use, if I haven't misread your code, if it's placing the queen on a given row, transform will be called on all the rows from that current row plus 1 up to N. This means that if you backtrack before the last row some calculation will have been made for nothing. Is it a huge impact? I honestly don't know.
That's a point I'll have to think about. Unfortunately, if we already knew we were going to backtrack before we transformed the array, we wouldn't need to transform the array. Furthermore, we don't save anything by not detecting that the very next row is completely threatened.

What we could do is insert code into the transform functor to determine whether there are any dominated rows already, starting two rows down, and if so stop copying. I'm doubtful this will improve performance, for two reasons: the vast majority of the time, there won't be any dominated rows that far below us, and this would probably inhibit the compiler from generating SIMD instructions for the loop. As an alternative, we could finish the loop and then scan for dominated rows over the horizon, but that would make the rest of the program do more work.
Quote:
I would also like to point out the other brillant idea you had to eliminate the need to try the middle row on odd N ;)
Thank you. That's actually the basis for my refactoring.


Top
Offline  
 Post subject:
PostPosted:Sun Sep 02, 2007 3:58 pm 
 

Joined:Thu Aug 09, 2007 9:09 am
Posts:26
Thought I'd give an update. I think the secret of your success, FrenchFrog, is that you did a much better job of writing loops the compiler can unroll. I've designed a new algorithm (or, at least, one I haven't heard of before) that I expect should improve performance considerably, but I've had limited time to implement it, and I don't want to make any guarantees until I've tested that it works.


Top
Offline  
 Post subject:
PostPosted:Tue Sep 04, 2007 9:23 am 
Sagely Amphibian
User avatar
 

Joined:Sun Jun 18, 2006 3:06 pm
Posts:69
Please post your idea even if it's not faster :) It's constructive to see what people can come up with.


Top
Offline  
 Post subject:
PostPosted:Thu Sep 06, 2007 12:05 am 
 

Joined:Thu Aug 09, 2007 9:09 am
Posts:26
Thanks. The reason I haven't been able to is that the program is very long and not finished. I did an almost-complete rewrite of the main procedure, and now that I'm sure its basic structure is correct, I'm trying to implement a different algorithm. Here are the benchmarks from the last version that ran correctly:
Code:
0 ms # of distinct solutions for 4 x 4 = 2 0 ms # of distinct solutions for 5 x 5 = 10 0 ms # of distinct solutions for 6 x 6 = 4 0 ms # of distinct solutions for 7 x 7 = 40 0 ms # of distinct solutions for 8 x 8 = 92 0 ms # of distinct solutions for 9 x 9 = 352 0 ms # of distinct solutions for 10 x 10 = 724 0 ms # of distinct solutions for 11 x 11 = 2680 16 ms # of distinct solutions for 12 x 12 = 14200 62 ms # of distinct solutions for 13 x 13 = 73712 406 ms # of distinct solutions for 14 x 14 = 365596 2182 ms # of distinct solutions for 15 x 15 = 2279184 16521 ms # of distinct solutions for 16 x 16 = 14772512 94623 ms # of distinct solutions for 17 x 17 = 95815104 Total time: 113810 ms.
That version uses a slower algorithm than the one I'm attempting to implement. This is still slower than your version for N < 18, but it's made up most of the difference, and I suspect that it catches up for higher values of N. Unfortunately, it's impractical for me to test N higher than 17 without running the program overnight.


Top
Offline  
Display posts from previous: Sort by 
Post new topic Reply to topic

All times are UTC-05:00


Who is online

Users browsing this forum: No registered users and 4 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
Theme created by Miah with assistance from hyprnova