ruby​​で再帰が遅すぎる

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があり、質問に答えるまで待つべきでしょう...

冗談を脇に置きます。最適化されたプログラムを作成したら、直接的なアプローチでは必ずしもカットされません。事前計算の時間を節約し、ルックアップテーブルを作成するので、内部ループ/再帰に必要な時間が短縮されます。

以下のコードは、約8msでロードして（ルックアップテーブルをあらかじめ計算しています）、私のマシン上で約2msで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 [ 4; 7; 5; 2; 6; 1; 3 |]

さて、私はRubyのは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; 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 [ 2; 4; 1; 8; 11; 9; 12; 3; 5; 7; 10; 6 |]