рекурсия слишком медленная с рубином

Question

Я новичок в программировании. Я изучаю рубин, и я застрял в проблеме с хакерами: не все решение, но только со скоростью моей программы ... проблема состоит в том, чтобы разместить n (umber) ферзей на доске n * n с рекурсией. вот решение я представил:

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, а затем ответьте на вопрос ...

Шутки в сторону. Когда вы пишете оптимизированную программу, простой подход не всегда делает разрез. Вы можете сэкономить время на предварительные вычисления и создать таблицы поиска и, как таковые, сократить время, требуемое внутренним циклом/рекурсией.

Код ниже загружает (и предварительно вычисляет таблицы поиска) примерно в 8 мс и решает nqueens для N = 8 около 2 мс на моей машине. И это язык .NET, а не некоторый собственный код. И он запускается в fsi (интерактивная оболочка).

Он использует биты (которые хорошо работают до N = 8 с uint64).

Фокус в том, что если вы поместили k королей на k столбцов, вы можете отфильтровать рекурсию (k + 1) для строк, которым не угрожают ранее размещенные k королев. Таким образом, чем глубже вы получаете, тем меньше строк вы должны учитывать в своем поиске (несколько улучшая алгоритмическую сложность).

Для 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 

Update

Используя System.Math.BigInteger также известный как bigint в F #, я продлил код с nqueensBig n функцией, которая также решает проблемы для 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 [| 0; 2; 5; 7; 9; 4; 8; 1; 3; 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; 3; 5; 7; 10; 6 |]