0
\$\begingroup\$

I have the following code for the n queens problem described here: https://leetcode.com/problems/n-queens/

;; depth first permutations + early pruning

(define (left-diagonal-attack pos perm index n)
  (if (empty? perm) #f
      (if (= (car perm) index) #t
          (left-diagonal-attack pos (cdr perm) (+ 1 index) n))))

(define (right-diagonal-attack pos perm index n)
  (if (empty? perm) #f
      (if  (= (car perm) (- (- n 1) index)) #t
           (right-diagonal-attack pos (cdr perm) (+ index 1) n))))

(define (place-next-queen-perm perm n)
  (for/list ([pos (in-range n)]
             #:unless (or (member pos perm)
                          (left-diagonal-attack pos (drop perm (max 0 (- (length perm) pos))) (max (- pos (length perm)) 0) n)

                          (right-diagonal-attack pos (drop perm (max 0 (- (+ (length perm) pos) (- n 1)))) (max (- (- n 1) (+ (length perm) pos)) 0) n)))
            (append perm (list pos))))

(define (place-next-queen perms n)
  (if (= (length (car perms)) n)
      perms
      (place-next-queen 
       (apply append (map (lambda (perm) (place-next-queen-perm perm n)) perms)) n)))

(define (to-queen-strings placements)
  (map (lambda (placement) 
         (map (lambda (pos) (list->string (list-set (build-list (length (car placements)) (lambda (_) #\.)) pos #\Q))) placement))
       placements))

(define/contract (solve-n-queens n)
                 (-> exact-integer? (listof (listof string?)))
                 (case n
                       [(1) (list (list "Q"))]
                       [(2 3) '()]
                       [else (to-queen-strings
                              (place-next-queen (map (lambda (placement) (list placement)) 
                                                     (stream->list (in-range n))) n))]))

This code works and all the test pass. I even got a 100% time and memory score for racket on leetcode for this. But I copied someone else's C++ submission and submitted that, and found that it takes 7 mb of memory and 4 ms to run it whereas my submission takes 216 ms and 100.2 mb. Is there a way to make the performance of this code comparable to the C++ code?

C++ code:

class Solution {
public:

 bool isSafe(int row,int col,int n,vector<int>& leftRow,vector<int>& upperDiagonal,vector<int>& lowerDiagonal)
    {
        if(leftRow[row]==0 and upperDiagonal[row+col]==0 and lowerDiagonal[n-1+col-row]==0) return true;
        return false;
    }
    void solveBoard(int col,int n,vector<string>& board,vector<vector<string>>& ans,vector<int>& leftRow,vector<int>& upperDiagonal,vector<int>& lowerDiagonal)
    {
        //base
        if(col==n)
        {
            ans.push_back(board);
            return;
        }
        //
        for(int row=0;row<n;row++)
        {
            if(isSafe(row,col,n,leftRow,upperDiagonal,lowerDiagonal))
            {
                board[row][col]='Q';
                leftRow[row]=1;
                upperDiagonal[row+col]=1;
                lowerDiagonal[n-1+col-row]=1;
                solveBoard(col+1,n,board,ans,leftRow,upperDiagonal,lowerDiagonal);
                board[row][col]='.';
                leftRow[row]=0;
                upperDiagonal[row+col]=0;
                lowerDiagonal[n-1+col-row]=0;
            }
        }
    }
        
    
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> ans;
        vector<string> board(n);
        string s(n,'.');
        for(int i=0;i<n;i++)
        {
            board[i]=s;                
        }
        vector<int> leftRow(n,0), upperDiagonal(2*n-1,0) ,lowerDiagonal(2*n-1,0);
        solveBoard(0,n,board,ans,leftRow,upperDiagonal,lowerDiagonal);
        return ans;
    }
};

```
\$\endgroup\$
2
  • \$\begingroup\$ memory-wise seems hard to improve, most of the memory is being used to store the actual solutions right? \$\endgroup\$
    – user62030
    Jun 18 at 18:43
  • \$\begingroup\$ Incidentaly, I submitted the c++ code and it gave me only 0ms of runtime. \$\endgroup\$
    – user62030
    Jun 18 at 18:49
1
\$\begingroup\$

Probably not. C++ is known for its raw performance. It can work with data that is close to the machine's underlying representation, and easily compiles down fairly directly to machine code. Not only that, but the code you copied could probably optimize even better (run faster) if it used const appropriately.

With the LISP code, even if the algorithm itself can be distilled down to efficient machine code, the data is represented as lists and other high-level structures. In C++, both vector and string use a single contiguous memory block for the element storage and this is exposed to the compiler so the code using them can inline and optimize the functions that manipulate the container, stripping away the abstractions at compile time and generating code to directly scan through memory.

Note that on modern architectures, memory access is a major bottleneck. Having containers that work like vector is orders of magnitude faster than a linked indirect data structure.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.