루비로 재귀가 너무 느림

Question

나는 프로그래밍에 초보자입니다. 나는 루비를 배우고 나는 hackerearth 문제에 빠져있다 : 전체 솔루션이 아니라 내 프로그램의 속도만으로 ... 문제는 재귀가있는 n * n 보드에 n (umber)의 왕비를 배치하는 것이다. 여기에 내가 제출 한 솔루션입니다 : 내가 당신을 도울 수 있다면 ... 이 조금 더 빨랐다 읽을 수 있지만 때문에 나는 잠시 대신 각각의 사용

def is_attacked(x,y,n,chess_board) 
    return true if chess_board[x].include?(1) 
    sum=x+y 
    diff=x-y 
    p=0 
    while p<=n-1 
     return true if p!=x && chess_board[p][y]==1 
     q=0 

     while q<=n-1 
      (((p+q==sum)||(p-q==diff)) && chess_board[p][q]==1) ? (return true) : q+=1 
     end 
    p+=1 
    end 
    return false 
end 

def n_Queens(n,n_fix,chess_board) 
    return true if n==0 
    i=0 
    while i<=n_fix-1 
     j=0 
     while j<=n_fix-1 
      if is_attacked(i,j,n_fix,chess_board) 
       j+=1 
       next 
      else 
       chess_board[i][j]=1 
       n_Queens(n-1,n_fix,chess_board) ? (return true) : chess_board[i][j]=0 
      end 
      j+=1 
     end 
     i+=1 
    end 
    return false 
end 

n=gets.chomp.to_i 
n_fix=n 
chess_board=Array.new(n) {Array.new(n,0)} 
if n_Queens(n,n_fix,chess_board) 
    chess_board.each do |line| 
     puts line.join(" ") 
    end 
else 
    puts "Not possible" 
end 

이, 내가 감사하고 확실히에서 내 능력을 둘 것이다 더 나은 수준. 감사합니다.

Answer 1

이제 우리는 64 비트 부호없는 정수와 64 비트 운영 체제를 자랑스럽게 생각합니다. N> 8은 정말 짜증납니다. 어쩌면 나는 x128 플랫폼에있을 때까지 기다려야하고 F #은 uint128을 가지고있다가 질문에 답할 수 있습니다 ...

농담은 제쳐두고. 일단 당신이 최적화 된 프로그램을 작성하면, 직접적인 접근은 항상 상처를 줄 수는 없습니다. 사전 계산 시간을 절약하고 조회 테이블을 생성하므로 내부 루프/재귀에 필요한 시간을 줄일 수 있습니다.

아래의 코드는 내 컴퓨터에서 약 8ms 내에로드하고 (그리고 룩업 테이블을 미리 계산 함) N = 8에 대해 nqueens를 해결합니다. 그리고 그것은 네이티브 코드가 아닌 .NET 언어입니다. 그리고 그것은 fsi (대화식 셸)에서 실행됩니다.

비트 보드를 사용합니다 (uint64로 N = 8까지 잘 작동 함).

트릭은 k 열에 k 열 여왕을 배치하면 이전에 배치 된 k 열 여왕이 위협받지 않는 행에 대해 (k + 1) 회귀를 필터링 할 수 있다는 것입니다. 따라서 깊이가 깊을수록 검색에서 실제로 고려해야하는 행이 적어지고 (알고리즘의 복잡성이 어느 정도 향상됩니다).

N> 8의 경우 보드 2의 uint64 값 (10 * 10 = 100 < 128)을 사용해도됩니다. 32 비트 머신을 프로그래밍 한 옛 체스와 마찬가지로 사람들은 비트 보드에 2 uint32를 사용했습니다 ...

nqueens 8 ;;
실수 : 00 : 00 : 00.002, CPU : 00 : 00 : 00.000, GC gen0 : 0, gen1 : 0, gen2 : 0
val it : int [] option = Some [| 0; 4; 7; 5; 2; 6; 1; 3 | 지금]

, 당신은 덜 효율적 뭔가를해야 할 경우에도, 나는 루비는 F 번호에 비해 얼마나 빨리 아무 생각이 없다,하지만 난 당신이 솔루션 회의와 그 해커 사이트의 타이밍 요구 사항을 올 수없는 의심 내 코드가 사용하는 비트 보드보다.

그래서 아래 코드는 Ruby 코드를 최적화 할 때 어디에서 아이디어를 얻을 수 있는지 알려줍니다.

let binary (v : uint64) (tw : System.IO.TextWriter) = 
    let mask : uint64 = 0x1UL <<< 63 
    let rec printDigit m c = 
     if c % 8 = 0 then tw.WriteLine() 
     match m with 
     | 0UL ->() 
     | _ -> 
      if m &&& v <> 0UL then 
       tw.Write("1") 
      else 
       tw.Write("0") 
      printDigit (m >>> 1) (c+1) 
    printDigit mask 0 

let showMask (m : uint64) = 
    printfn "%t" (binary m) 

let squareIndexBig n col row = row * n + col 

let squareIndex col row = row * 8 + col 

let squareMaskBig n col row = 
    bigint.One <<< squareIndexBig n col row 

let squareMask col row = 1UL <<< squareIndex col row 

let diagMovesBig n col row = 
    let mutable c = col 
    let mutable r = row 
    let mutable b = bigint.Zero 
    while c > -1 && row > -1 do 
     b <- b ||| squareMaskBig n c r 
     c <- c - 1 
     r <- r - 1 
    c <- col 
    r <- row 
    while c < n && r < n do 
     b <- b ||| squareMaskBig n c r 
     c <- c + 1 
     r <- r + 1 
    c <- col 
    r <- row 
    while c > -1 && r < n do 
     b <- b ||| squareMaskBig n c r 
     c <- c - 1 
     r <- r + 1 
    c <- col 
    r <- row 
    while c < n && r > -1 do 
     b <- b ||| squareMaskBig n c r 
     c <- c + 1 
     r <- r - 1 
    b 

let diagMoves col row = 
    let mutable c = col 
    let mutable r = row 
    let mutable b = 0UL 
    while c > -1 && row > -1 do 
     b <- b ||| squareMask c r 
     c <- c - 1 
     r <- r - 1 
    c <- col 
    r <- row 
    while c < 8 && r < 8 do 
     b <- b ||| squareMask c r 
     c <- c + 1 
     r <- r + 1 
    c <- col 
    r <- row 
    while c > -1 && r < 8 do 
     b <- b ||| squareMask c r 
     c <- c - 1 
     r <- r + 1 
    c <- col 
    r <- row 
    while c < 8 && r > -1 do 
     b <- b ||| squareMask c r 
     c <- c + 1 
     r <- r - 1 
    b 

let nlowerbits n = 
    let mutable v = 0x01UL 
    for i in [1..n] do 
     v <- (v <<< 1) ||| 1UL 
    bigint v 

let nbitswideOne n = 
    let mutable v = bigint.One 
    for i in [1..n] do 
     v <- (v <<< n) ||| bigint.One 
    v 


let row0CodeBig n = 
    [| 
     for r in 0..n-1 do 
      yield (nlowerbits n) <<< (n * r) 
    |] 


let row0Code = 
    [| 
     for r in 0..7 do 
      yield 0b11111111UL <<< (8 * r) 
    |] 

let col0CodeBig n = 
    [| 
     for c in 0..n-1 do 
      yield nbitswideOne n <<< c 
    |] 

let col0Code = 
    [| 
     for c in 0..7 do 
      yield 0b0000000100000001000000010000000100000001000000010000000100000001UL <<< c 
    |] 

let diagCodeBig n = 
    [| 
     for col in 0..n-1 do 
      yield 
       [| 
        for row in 0..n-1 do 
         yield diagMovesBig n col row 
       |] 
    |] 


let diagCode = 
    [| 
     for col in 0..7 do 
      yield 
       [| 
        for row in 0..7 do 
         yield diagMoves col row 
       |] 
    |] 

let placeQueenBig n col row = 
    (row0CodeBig n).[row] ||| (col0CodeBig n).[col] ||| (diagCodeBig n).[col].[row] 

let placeQueen col row = 
    row0Code.[row] ||| (col0Code.[col]) ||| (diagCode.[col].[row]) 

let squareSafeBig n board col row = 
    bigint.Zero = (board &&& squareMaskBig n col row) 

let squareSafe board col row = 
    0UL = (board &&& squareMask col row) 

let nqueensBig n = 
    let queenRows : int[] = Array.zeroCreate n 
    let assign col row = queenRows.[col] <- row 

    let rec place board col = 
     //showMask board 
     match col with 
     | x when x = n -> true 
     | _ -> 
      [0..n-1] 
      |> List.filter (fun row -> squareSafeBig n board col row) 
      |> List.tryFind (fun row -> place (board ||| placeQueenBig n col row) (col+1)) 
      |> fun row -> 
        match row with 
        | None -> false 
        | Some r -> 
         assign col r 
         true 

    if place (bigint.Zero) 0 
    then 
     Some queenRows 
    else 
     None 


let nqueens n = 
    let queenRows : int[] = Array.zeroCreate n 
    let assign col row = queenRows.[col] <- row 

    let rec place board col = 
     //showMask board 
     match col with 
     | x when x = n -> true 
     | _ -> 
      [0..n-1] 
      |> List.filter (fun row -> squareSafe board col row) 
      |> List.tryFind (fun row -> place (board ||| placeQueen col row) (col+1)) 
      |> fun row -> 
        match row with 
        | None -> false 
        | Some r -> 
         assign col r 
         true 

    if place 0UL 0 
    then 
     Some queenRows 
    else 
     None 

업데이트

또한 F #으로 bigint로 알려진 System.Math.BigInteger를 사용하여 - (미안 ... 루비에 대해 아무것도 몰라), 또한 N에 대한 문제를 해결하는 nqueensBig n 기능을 가진 코드를 확장 > 8. 성능은 nqueens n과 비슷하지만 힙 연산은 무료가 아니지만 충분히 빠르다고 생각합니다.

nqueensBig 10 ;;
실수 : 00 : 00 : 00.071, CPU : 00 : 00 : 00.078, GC gen0 : 10, gen1 : 1, gen2 : 0
val it : int [] option = Some [ 2; 5; 7; 9; 4; 8; 1; 삼; 6 |]

nqueensBig 13 ;;
실수 : 00 : 00 : 00.167, CPU : 00 : 00 : 00.171, GC gen0 : 23, gen1 : 0, gen2 : 0
val it : int [] option = Some [| 0; 2; 4; 1; 8; 11; 9; 12; 삼; 5; 7; 10; 6 |]