Re: [racket-users] Sequential vs. Parallel 13-Queens program
This is a bit off-topic (though it is about N-queens) but I've long wanted to ask people if an idea I had once is a well-known one. It once occurred to me that solutions to N-rooks can be viewed as linear transformations that correspond to permutations of a vector. So, then I wondered to what sort of transformations solutions to N-queens correspond. I'll leave a gap in case anyone wants to think about it... Okay, N-queens solutions correspond to transformations in which no two entries in the permuted vector are the same distance apart as they were before. This leads to a simple algorithm for finding solutions. Fill a vector with the digits 1 to veclen, generate permutations, and see if the difference between any two element indices is the same as the difference between their contents. You can then easily reverse engineer the board. Is this well known? Thanks, --Jerry Jackson -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: [racket-users] Sequential vs. Parallel 13-Queens program
My program does represent a solution by a list of length N (one queen per file), so each element of the list is a file and stores the rank. The reason I also store the second coordinate (the file) is for ease of knowing the file when backtracking. If I used vectors instead, I could get by with just storing one number, the rank, since the index of the vector would be the file. Using vectors won't change big-O but might reduce the constant factor. My main goal was really just to compare sequential vs. parallel though, I'm sure there are other heuristics that could be applied to make the algorithm less naive. > On Mar 12, 2016, at 7:05 PM, Jos Koot <jos.k...@gmail.com> wrote: > > I addition to my previous post: > > If I understand well you are using posn-s. > A solution of the N-queens can be represented by a list or vector of lenhgth > N that for each row (or column) records the position of a queen in the > column (or row). This reduces the computation of time O(f(N^2)) to O(f(N)), > because only rows (or cullums) are considered, not all N^2 squares of the > board. > Jos > > -Original Message- > From: Brian Adkins [mailto:lojicdot...@gmail.com] > Sent: sábado, 12 de marzo de 2016 23:33 > To: Jos Koot > Cc: Racket Users > Subject: Re: [racket-users] Sequential vs. Parallel 13-Queens program > > The code is a little difficult for me to read. It doesn't seem to collect > *all* solutions for a given N. If that's the case, would you be able to > modify it to do so to allow a more direct comparison? > >> On Mar 12, 2016, at 1:19 PM, Jos Koot <jos.k...@gmail.com> wrote: >> >> See https://en.wikipedia.org/wiki/Eight_queens_puzzle >> For a non recursive non-back-tracking algorithm. >> It is a loop that (when using a vector) can easily be unrolled in > parallelly >> executed loops. >> I implemented it as follows running on 2 processors: >> >> #lang racket >> #| >> The following text is copied from article n queens of wikipedia: >> >> This heuristic solves N queens for any N ≥ 4. It forms the list of > numbers >> for vertical positions (rows) of queens with horizontal position (column) >> simply increasing. N is 8 for eight queens puzzle. >> >> 1. If the remainder from dividing N by 6 is not 2 or 3 then the list is >> simply all even numbers followed by all odd numbers ≤ N >> 2. Otherwise, write separate lists of even and odd numbers (i.e. 2,4,6,8 - >> 1,3,5,7) >> 3. If the remainder is 2, swap 1 and 3 in odd list and move 5 to the end > (i. >> e. 3,1,7,5) >> 4. If the remainder is 3, move 2 to the end of even list and 1,3 to the > end >> of odd list (i.e. 4,6,8,2 - 5,7,9,1,3) >> 5. Append odd list to the even list and place queens in the rows given by >> these numbers, from left to right (i.e. a2, b4, c6, d8, e3, f1, g7, h5) >> >> In the following procedure I use a vector with as many elements as the > chess >> board has rows. Every element is assigned exactly once. Rows and columns > are >> counted from 0 (in the wikipedia article they are counted from 1) >> >> Futures allow two or more loops to run simulanuously on two or more >> processors. If you don't have futures, replace (define f (future odd)) by >> (odd) and remove the touch. >> |# >> >> (require racket/future) >> >> (define (queens n) >> (define v (make-vector n)) >> (define n-odd (quotient n 2)) >> (define r (remainder n 6)) >> (define (odd) >> (case r >> ((3) >> (for ((k (in-range 0 (sub1 n-odd (vector-set! v k (+ 3 (* 2 k >> (vector-set! v (sub1 n-odd) 1)) >> (else >> (for ((k (in-range 0 n-odd))) (vector-set! v k (add1 (* 2 k))) >> (define (even) >> (case r >> ((2) >> (vector-set! v n-odd 2) >> (vector-set! v (add1 n-odd) 0) >> (for ((k (in-range (+ 2 n-odd) n))) >>(vector-set! v k (+ 6 (* 2 (- k n-odd 2) >> (vector-set! v (sub1 n) 4)) >> ((3) >> (for ((k (in-range n-odd (- n 2 >>(vector-set! v k (+ 4 (* 2 (- k n-odd) >> (vector-set! v (- n 2) 0) >> (vector-set! v (- n 1) 2)) >> (else >> (for ((k (in-range n-odd n))) >>(vector-set! v k (* 2 (- k n-odd))) >> (define f (future odd)) >> (even) >> (touch f) >> v) >> >> (define (check v) >> (let ((n (vector-length v))) >> (for/and ((x1 (in-range 0 n))) >> (let ((y1 (vector-ref v x1))) >> (for/and ((x2 (in-range (add1 x1) n))) >>(let ((y2 (vector-ref v x2))) >> (not >> (or >> (= y1 y2) >> (= (abs (- x1 x2)) (abs (-
RE: [racket-users] Sequential vs. Parallel 13-Queens program
I addition to my previous post: If I understand well you are using posn-s. A solution of the N-queens can be represented by a list or vector of lenhgth N that for each row (or column) records the position of a queen in the column (or row). This reduces the computation of time O(f(N^2)) to O(f(N)), because only rows (or cullums) are considered, not all N^2 squares of the board. Jos -Original Message- From: Brian Adkins [mailto:lojicdot...@gmail.com] Sent: sábado, 12 de marzo de 2016 23:33 To: Jos Koot Cc: Racket Users Subject: Re: [racket-users] Sequential vs. Parallel 13-Queens program The code is a little difficult for me to read. It doesn't seem to collect *all* solutions for a given N. If that's the case, would you be able to modify it to do so to allow a more direct comparison? > On Mar 12, 2016, at 1:19 PM, Jos Koot <jos.k...@gmail.com> wrote: > > See https://en.wikipedia.org/wiki/Eight_queens_puzzle > For a non recursive non-back-tracking algorithm. > It is a loop that (when using a vector) can easily be unrolled in parallelly > executed loops. > I implemented it as follows running on 2 processors: > > #lang racket > #| > The following text is copied from article n queens of wikipedia: > > This heuristic solves N queens for any N ≥ 4. It forms the list of numbers > for vertical positions (rows) of queens with horizontal position (column) > simply increasing. N is 8 for eight queens puzzle. > > 1. If the remainder from dividing N by 6 is not 2 or 3 then the list is > simply all even numbers followed by all odd numbers ≤ N > 2. Otherwise, write separate lists of even and odd numbers (i.e. 2,4,6,8 - > 1,3,5,7) > 3. If the remainder is 2, swap 1 and 3 in odd list and move 5 to the end (i. > e. 3,1,7,5) > 4. If the remainder is 3, move 2 to the end of even list and 1,3 to the end > of odd list (i.e. 4,6,8,2 - 5,7,9,1,3) > 5. Append odd list to the even list and place queens in the rows given by > these numbers, from left to right (i.e. a2, b4, c6, d8, e3, f1, g7, h5) > > In the following procedure I use a vector with as many elements as the chess > board has rows. Every element is assigned exactly once. Rows and columns are > counted from 0 (in the wikipedia article they are counted from 1) > > Futures allow two or more loops to run simulanuously on two or more > processors. If you don't have futures, replace (define f (future odd)) by > (odd) and remove the touch. > |# > > (require racket/future) > > (define (queens n) > (define v (make-vector n)) > (define n-odd (quotient n 2)) > (define r (remainder n 6)) > (define (odd) > (case r > ((3) >(for ((k (in-range 0 (sub1 n-odd (vector-set! v k (+ 3 (* 2 k >(vector-set! v (sub1 n-odd) 1)) > (else >(for ((k (in-range 0 n-odd))) (vector-set! v k (add1 (* 2 k))) > (define (even) > (case r > ((2) >(vector-set! v n-odd 2) >(vector-set! v (add1 n-odd) 0) >(for ((k (in-range (+ 2 n-odd) n))) > (vector-set! v k (+ 6 (* 2 (- k n-odd 2) >(vector-set! v (sub1 n) 4)) > ((3) >(for ((k (in-range n-odd (- n 2 > (vector-set! v k (+ 4 (* 2 (- k n-odd) >(vector-set! v (- n 2) 0) >(vector-set! v (- n 1) 2)) > (else >(for ((k (in-range n-odd n))) > (vector-set! v k (* 2 (- k n-odd))) > (define f (future odd)) > (even) > (touch f) > v) > > (define (check v) > (let ((n (vector-length v))) > (for/and ((x1 (in-range 0 n))) > (let ((y1 (vector-ref v x1))) >(for/and ((x2 (in-range (add1 x1) n))) > (let ((y2 (vector-ref v x2))) > (not > (or >(= y1 y2) >(= (abs (- x1 x2)) (abs (- y1 y2))) > > (for/and ((n (in-range 4 100))) (check (queens n))) > > (for ((k (in-range 2 9))) > (printf "(expt 10 ~s) : " k) > (let ((n (expt 10 k))) > (time (queens n > > Runs fast: > > (expt 10 2) : cpu time: 0 real time: 0 gc time: 0 > (expt 10 3) : cpu time: 0 real time: 0 gc time: 0 > (expt 10 4) : cpu time: 0 real time: 0 gc time: 0 > (expt 10 5) : cpu time: 0 real time: 0 gc time: 0 > (expt 10 6) : cpu time: 63 real time: 47 gc time: 32 > (expt 10 7) : cpu time: 203 real time: 140 gc time: 15 > (expt 10 8) : cpu time: 3183 real time: 2543 gc time: 1123 > > Times measured with DrRacket > > Jos > > > -Original Message- > From: racket-users@googlegroups.com [mailto:racket-users@googlegroups.com] > On Behalf Of Brian Adkins > Sent: sábado, 12 de marzo de 2016 1:42 > To: Racket Users > Subject: [racket-users] Sequential vs. Parallel 13-Queens program > > I coded up a sequential and parallel version of N-Queens, then did a ton of > benchmark runs of 13-Queens to compare the tim
RE: [racket-users] Sequential vs. Parallel 13-Queens program
You are right. The algorithm shown in https://en.wikipedia.org/wiki/Eight_queens_puzzle gives one solution only. I did not realize that you want all solutions. Sorry for that. In order to find all solutions you indeeed need a backtracking algorithm, I think, which requires much more computation. In that respect the times you report seem very reasonably to me. As you have shown it is not too difficult to compute all solutions, but the question which algorithm would be the fastest one remains an open question for me too. My advice: first look at the efficiency of the algorithm you want to use. In the past I have run into problems by not doing so, producing programs running parallelly on many processors, but not faster than when running on one processor only. First consider the algorithm, then the implementation. A simple example where the implementation may go wrong in respect to computing time, is in computing binomial coefficients. I am sure there are much more examples. May be a define-with-hash may help, producing functions that use a hash to remember previous calls with the same arguments. It may be necessary to define the hash such as to recognize distinct, but computationaly symmetrical problems. Best wishes, Jos -Original Message- From: Brian Adkins [mailto:lojicdot...@gmail.com] Sent: sábado, 12 de marzo de 2016 23:33 To: Jos Koot Cc: Racket Users Subject: Re: [racket-users] Sequential vs. Parallel 13-Queens program The code is a little difficult for me to read. It doesn't seem to collect *all* solutions for a given N. If that's the case, would you be able to modify it to do so to allow a more direct comparison? > On Mar 12, 2016, at 1:19 PM, Jos Koot <jos.k...@gmail.com> wrote: > snip -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
RE: [racket-users] Sequential vs. Parallel 13-Queens program
You are right. The algorithm shown in https://en.wikipedia.org/wiki/Eight_queens_puzzle gives one solution only. I did not realize that you want all solutions. Sorry for that. In order to find all solutions you indeeed need a backtracking algorithm, I think, which requires much more computation. In that respect the times you report seem very reasonably to me. As you have shown it is not too difficult to compute all solutions, but the question which algorithm would be the fast one remains an open question for me too. My advice: first look at the efficiency of the algorithm you want to use. In the past I have run into problems by not doing so, producing programs running parallelly on many processors, but not faster than when running on one processor only. First consider the algorithm, then the implementation. A simple example where the implementation may go wrong in respect to computing time, is in computing binomial coefficients. I am sure there are much more examples. May be a define-with-hash may help, producing functions that use a hash to remember previous calls with the same arguments. It may be necessary to define the hash such as to recognize distinct, but computationaly symmetrical problems. Best wishes, Jos -Original Message- From: Brian Adkins [mailto:lojicdot...@gmail.com] Sent: sábado, 12 de marzo de 2016 23:33 To: Jos Koot Cc: Racket Users Subject: Re: [racket-users] Sequential vs. Parallel 13-Queens program The code is a little difficult for me to read. It doesn't seem to collect *all* solutions for a given N. If that's the case, would you be able to modify it to do so to allow a more direct comparison? > On Mar 12, 2016, at 1:19 PM, Jos Koot <jos.k...@gmail.com> wrote: > > See https://en.wikipedia.org/wiki/Eight_queens_puzzle > For a non recursive non-back-tracking algorithm. > It is a loop that (when using a vector) can easily be unrolled in parallelly > executed loops. > I implemented it as follows running on 2 processors: > snip > > Jos > > > -Original Message- > From: racket-users@googlegroups.com [mailto:racket-users@googlegroups.com] > On Behalf Of Brian Adkins > Sent: sábado, 12 de marzo de 2016 1:42 > To: Racket Users > Subject: [racket-users] Sequential vs. Parallel 13-Queens program > > I coded up a sequential and parallel version of N-Queens, then did a ton of > benchmark runs of 13-Queens to compare the time. For each configuration > (sequential or parallel w/ M workers), I ran the programs 6 times, threw out > the high two & low two and averaged the middle two numbers. > > The spreadsheet with timings is here: > > https://docs.google.com/spreadsheets/d/1LFwdZbBveaARY_AquGXY9jgaSJlOA03NQCV9 > TeYQ-l8/edit?usp=sharing > > The code is here: > > https://gist.github.com/lojic/aef0aec491d3dc9cb40b > > I didn't spend any time refining/optimizing, so it's fairly crude, but > informative nonetheless. > > The executive summary of timings for the parallel version: > > # Places Time > 1 34.9 > 2 19.7 > 3 13.8 > 4 12.3 > 5 11.9 > 6 12.9 > 7 12.1 > 8 12.2 > > The sequential version took 31.3 seconds. > > The basic idea for the parallel version is to place the first 13 starting > positions in a queue that the place workers will pull from and produce a set > of solutions with that starting position. Both the parallel and sequential > versions collect all 73,712 solutions in a list and compute the length of > it. I hardcoded the number of solutions as a quick & dirty way of > determining completion in the parallel version just to allow me to get the > timings easily. > > It was great to finally write some Racket code that got all my cores heated > up :) > > Brian > > -- > You received this message because you are subscribed to the Google Groups > "Racket Users" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to racket-users+unsubscr...@googlegroups.com. > For more options, visit https://groups.google.com/d/optout. > -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: [racket-users] Sequential vs. Parallel 13-Queens program
The code is a little difficult for me to read. It doesn't seem to collect *all* solutions for a given N. If that's the case, would you be able to modify it to do so to allow a more direct comparison? > On Mar 12, 2016, at 1:19 PM, Jos Koot <jos.k...@gmail.com> wrote: > > See https://en.wikipedia.org/wiki/Eight_queens_puzzle > For a non recursive non-back-tracking algorithm. > It is a loop that (when using a vector) can easily be unrolled in parallelly > executed loops. > I implemented it as follows running on 2 processors: > > #lang racket > #| > The following text is copied from article n queens of wikipedia: > > This heuristic solves N queens for any N ≥ 4. It forms the list of numbers > for vertical positions (rows) of queens with horizontal position (column) > simply increasing. N is 8 for eight queens puzzle. > > 1. If the remainder from dividing N by 6 is not 2 or 3 then the list is > simply all even numbers followed by all odd numbers ≤ N > 2. Otherwise, write separate lists of even and odd numbers (i.e. 2,4,6,8 - > 1,3,5,7) > 3. If the remainder is 2, swap 1 and 3 in odd list and move 5 to the end (i. > e. 3,1,7,5) > 4. If the remainder is 3, move 2 to the end of even list and 1,3 to the end > of odd list (i.e. 4,6,8,2 - 5,7,9,1,3) > 5. Append odd list to the even list and place queens in the rows given by > these numbers, from left to right (i.e. a2, b4, c6, d8, e3, f1, g7, h5) > > In the following procedure I use a vector with as many elements as the chess > board has rows. Every element is assigned exactly once. Rows and columns are > counted from 0 (in the wikipedia article they are counted from 1) > > Futures allow two or more loops to run simulanuously on two or more > processors. If you don't have futures, replace (define f (future odd)) by > (odd) and remove the touch. > |# > > (require racket/future) > > (define (queens n) > (define v (make-vector n)) > (define n-odd (quotient n 2)) > (define r (remainder n 6)) > (define (odd) > (case r > ((3) >(for ((k (in-range 0 (sub1 n-odd (vector-set! v k (+ 3 (* 2 k >(vector-set! v (sub1 n-odd) 1)) > (else >(for ((k (in-range 0 n-odd))) (vector-set! v k (add1 (* 2 k))) > (define (even) > (case r > ((2) >(vector-set! v n-odd 2) >(vector-set! v (add1 n-odd) 0) >(for ((k (in-range (+ 2 n-odd) n))) > (vector-set! v k (+ 6 (* 2 (- k n-odd 2) >(vector-set! v (sub1 n) 4)) > ((3) >(for ((k (in-range n-odd (- n 2 > (vector-set! v k (+ 4 (* 2 (- k n-odd) >(vector-set! v (- n 2) 0) >(vector-set! v (- n 1) 2)) > (else >(for ((k (in-range n-odd n))) > (vector-set! v k (* 2 (- k n-odd))) > (define f (future odd)) > (even) > (touch f) > v) > > (define (check v) > (let ((n (vector-length v))) > (for/and ((x1 (in-range 0 n))) > (let ((y1 (vector-ref v x1))) >(for/and ((x2 (in-range (add1 x1) n))) > (let ((y2 (vector-ref v x2))) > (not > (or >(= y1 y2) >(= (abs (- x1 x2)) (abs (- y1 y2))) > > (for/and ((n (in-range 4 100))) (check (queens n))) > > (for ((k (in-range 2 9))) > (printf "(expt 10 ~s) : " k) > (let ((n (expt 10 k))) > (time (queens n > > Runs fast: > > (expt 10 2) : cpu time: 0 real time: 0 gc time: 0 > (expt 10 3) : cpu time: 0 real time: 0 gc time: 0 > (expt 10 4) : cpu time: 0 real time: 0 gc time: 0 > (expt 10 5) : cpu time: 0 real time: 0 gc time: 0 > (expt 10 6) : cpu time: 63 real time: 47 gc time: 32 > (expt 10 7) : cpu time: 203 real time: 140 gc time: 15 > (expt 10 8) : cpu time: 3183 real time: 2543 gc time: 1123 > > Times measured with DrRacket > > Jos > > > -Original Message- > From: racket-users@googlegroups.com [mailto:racket-users@googlegroups.com] > On Behalf Of Brian Adkins > Sent: sábado, 12 de marzo de 2016 1:42 > To: Racket Users > Subject: [racket-users] Sequential vs. Parallel 13-Queens program > > I coded up a sequential and parallel version of N-Queens, then did a ton of > benchmark runs of 13-Queens to compare the time. For each configuration > (sequential or parallel w/ M workers), I ran the programs 6 times, threw out > the high two & low two and averaged the middle two numbers. > > The spreadsheet with timings is here: > > https://docs.google.com/spreadsheets/d/1LFwdZbBveaARY_AquGXY9jgaSJlOA03NQCV9 > TeYQ-l8/edit?usp=sharing > > The code is here: > > https://gist.github.com/lojic/aef0aec491d3dc9cb40b > > I didn't spend any time refining/optimizing, so it's fairly crude, but > informative nonetheless. > > The executive summary of timings for
RE: [racket-users] Sequential vs. Parallel 13-Queens program
See https://en.wikipedia.org/wiki/Eight_queens_puzzle For a non recursive non-back-tracking algorithm. It is a loop that (when using a vector) can easily be unrolled in parallelly executed loops. I implemented it as follows running on 2 processors: #lang racket #| The following text is copied from article n queens of wikipedia: This heuristic solves N queens for any N ≥ 4. It forms the list of numbers for vertical positions (rows) of queens with horizontal position (column) simply increasing. N is 8 for eight queens puzzle. 1. If the remainder from dividing N by 6 is not 2 or 3 then the list is simply all even numbers followed by all odd numbers ≤ N 2. Otherwise, write separate lists of even and odd numbers (i.e. 2,4,6,8 - 1,3,5,7) 3. If the remainder is 2, swap 1 and 3 in odd list and move 5 to the end (i. e. 3,1,7,5) 4. If the remainder is 3, move 2 to the end of even list and 1,3 to the end of odd list (i.e. 4,6,8,2 - 5,7,9,1,3) 5. Append odd list to the even list and place queens in the rows given by these numbers, from left to right (i.e. a2, b4, c6, d8, e3, f1, g7, h5) In the following procedure I use a vector with as many elements as the chess board has rows. Every element is assigned exactly once. Rows and columns are counted from 0 (in the wikipedia article they are counted from 1) Futures allow two or more loops to run simulanuously on two or more processors. If you don't have futures, replace (define f (future odd)) by (odd) and remove the touch. |# (require racket/future) (define (queens n) (define v (make-vector n)) (define n-odd (quotient n 2)) (define r (remainder n 6)) (define (odd) (case r ((3) (for ((k (in-range 0 (sub1 n-odd (vector-set! v k (+ 3 (* 2 k (vector-set! v (sub1 n-odd) 1)) (else (for ((k (in-range 0 n-odd))) (vector-set! v k (add1 (* 2 k))) (define (even) (case r ((2) (vector-set! v n-odd 2) (vector-set! v (add1 n-odd) 0) (for ((k (in-range (+ 2 n-odd) n))) (vector-set! v k (+ 6 (* 2 (- k n-odd 2) (vector-set! v (sub1 n) 4)) ((3) (for ((k (in-range n-odd (- n 2 (vector-set! v k (+ 4 (* 2 (- k n-odd) (vector-set! v (- n 2) 0) (vector-set! v (- n 1) 2)) (else (for ((k (in-range n-odd n))) (vector-set! v k (* 2 (- k n-odd))) (define f (future odd)) (even) (touch f) v) (define (check v) (let ((n (vector-length v))) (for/and ((x1 (in-range 0 n))) (let ((y1 (vector-ref v x1))) (for/and ((x2 (in-range (add1 x1) n))) (let ((y2 (vector-ref v x2))) (not (or (= y1 y2) (= (abs (- x1 x2)) (abs (- y1 y2))) (for/and ((n (in-range 4 100))) (check (queens n))) (for ((k (in-range 2 9))) (printf "(expt 10 ~s) : " k) (let ((n (expt 10 k))) (time (queens n Runs fast: (expt 10 2) : cpu time: 0 real time: 0 gc time: 0 (expt 10 3) : cpu time: 0 real time: 0 gc time: 0 (expt 10 4) : cpu time: 0 real time: 0 gc time: 0 (expt 10 5) : cpu time: 0 real time: 0 gc time: 0 (expt 10 6) : cpu time: 63 real time: 47 gc time: 32 (expt 10 7) : cpu time: 203 real time: 140 gc time: 15 (expt 10 8) : cpu time: 3183 real time: 2543 gc time: 1123 Times measured with DrRacket Jos -Original Message- From: racket-users@googlegroups.com [mailto:racket-users@googlegroups.com] On Behalf Of Brian Adkins Sent: sábado, 12 de marzo de 2016 1:42 To: Racket Users Subject: [racket-users] Sequential vs. Parallel 13-Queens program I coded up a sequential and parallel version of N-Queens, then did a ton of benchmark runs of 13-Queens to compare the time. For each configuration (sequential or parallel w/ M workers), I ran the programs 6 times, threw out the high two & low two and averaged the middle two numbers. The spreadsheet with timings is here: https://docs.google.com/spreadsheets/d/1LFwdZbBveaARY_AquGXY9jgaSJlOA03NQCV9 TeYQ-l8/edit?usp=sharing The code is here: https://gist.github.com/lojic/aef0aec491d3dc9cb40b I didn't spend any time refining/optimizing, so it's fairly crude, but informative nonetheless. The executive summary of timings for the parallel version: # PlacesTime 1 34.9 2 19.7 3 13.8 4 12.3 5 11.9 6 12.9 7 12.1 8 12.2 The sequential version took 31.3 seconds. The basic idea for the parallel version is to place the first 13 starting positions in a queue that the place workers will pull from and produce a set of solutions with that starting position. Both the parallel and sequential versions collect all 73,712 solutions in a list and compute the length of it. I hardcoded the number of solutions as a quick & dirty way of determining completion in the parallel version just to allow me to get the timings easily. It was great to finally write some Racket code that got all my cores heated up :) Brian -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this gro
[racket-users] Sequential vs. Parallel 13-Queens program
I coded up a sequential and parallel version of N-Queens, then did a ton of benchmark runs of 13-Queens to compare the time. For each configuration (sequential or parallel w/ M workers), I ran the programs 6 times, threw out the high two & low two and averaged the middle two numbers. The spreadsheet with timings is here: https://docs.google.com/spreadsheets/d/1LFwdZbBveaARY_AquGXY9jgaSJlOA03NQCV9TeYQ-l8/edit?usp=sharing The code is here: https://gist.github.com/lojic/aef0aec491d3dc9cb40b I didn't spend any time refining/optimizing, so it's fairly crude, but informative nonetheless. The executive summary of timings for the parallel version: # PlacesTime 1 34.9 2 19.7 3 13.8 4 12.3 5 11.9 6 12.9 7 12.1 8 12.2 The sequential version took 31.3 seconds. The basic idea for the parallel version is to place the first 13 starting positions in a queue that the place workers will pull from and produce a set of solutions with that starting position. Both the parallel and sequential versions collect all 73,712 solutions in a list and compute the length of it. I hardcoded the number of solutions as a quick & dirty way of determining completion in the parallel version just to allow me to get the timings easily. It was great to finally write some Racket code that got all my cores heated up :) Brian -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
