Juliaのラスタマージンシャッフル - より良い実装

Question

ランダムな2x2サブ行列を取り、それらのcolsumsとrowsumsが等しい場合にのみ、0と1の行列のシャッフル方法を実装したいと思います。 1 0]または[1 0; 0 1]となる。

EDIT：FYIこれは、両方の

sum(matrix,1) == sum(shuffledmatrix,1) && 
sum(matrix,2) == sum(shuffledmatrix,2) 

==>真

以下のコードは正しいですが、基本的には十分な速さではないことを意味する必要があります。誰でもここで目障りなエラーを見ることができますか？ （私はジュリアにかなり新しいよ！）

function rastershuffle!(shuffledmatrix::Array{Int32,2},minchanges::Int) 
    @inbounds begin 
     numchanges = 0 
     numcols = size(shuffledmatrix,2) 
     numrows = size(shuffledmatrix,1) 
     while numchanges < minchanges 
      a = findmargeflip!(shuffledmatrix,numcols::Int, numrows::Int) 
      numchanges = numchanges + sum(a) 
     end 
    end 
    return shuffledmatrix 
end 

function findmargeflip!(shuffledmatrix::Array{Int32,2},numcols::Int, numrows::Int) 
    change = false 
    cols = EPhys.random_generator(2,numcols) 
    rows = EPhys.random_generator(2,numrows) 
    vall = sub(shuffledmatrix, [rows[1]; rows[2]],[cols[1]; cols[2]]) 
    if vall == [0 1; 1 0] || vall == [1 0; 0 1] 
     flipvall!(vall) 
     #numchanges += 1 
     change = true 
    end 
    change 
end 

function flipvall!(vall) 
    if vall[1] == 1 
     vall[:] = [0 1 1 0]  
    else 
     vall[:] = [1 0 0 1] 
    end 
    nothing 
end 

私は、ドキュメント内の情報に基づいて、これまでに試した：

• 代わりのInt32のBitArraysを使用すると、 - あまりしませんでした私はこれをとにかく変更することができます違いは、関数flipvall！また、フリップビットで置き換えることもできます！

• 変化とは対照的に、反復回数を設定するコンパイラの余分なタイプの情報

• を与え、その後、

@simdは私がメインのボトルネックがいると思う使用してvectoriseしようとして再生成SubArrayはメモリの再割り当て/ガベージコレクションを必要とする反復ですが、これをどのようにして取得するのかは完全にはわかりません。

追加情報：

shuffledspikematrix3 = copy(spikematrixnonoise) 
@time rastershuffle!(shuffledspikematrix3, 100); 
@profile rastershuffle!(shuffledspikematrix3, 100); 
Profile.print() 

===> OUTPUT：

8.776213 seconds (153.35 M allocations: 7.835 GB, 15.94% gc time) 
    1 abstractarray.jl; ==; line: 1060 
    1 abstractarray.jl; hvcat; line: 974 
    2 abstractarray.jl; vcat; line: 733 
    2 array.jl; getindex; line: 282 
    2 multidimensional.jl; start; line: 99 
    800 task.jl; anonymous; line: 447 
    800 .../IJulia/src/IJulia.jl; eventloop; line: 143 
     800 ...rc/execute_request.jl; execute_request_0x535c5df2; line: 183 
     800 loading.jl; include_string; line: 266 
     800 profile.jl; anonymous; line: 16 
     800 In[174]; rastershuffle!; line: 7 
      1 ...devel/src/helper.jl; random_generator; line: 52 
      1 In[174]; findmargeflip!; line: 15 
      77 In[174]; findmargeflip!; line: 16 
      13 ....devel/src/helper.jl; random_generator; line: 44 
      7 random.jl; rand; line: 255 
      5 random.jl; gen_rand; line: 88 
       1 dSFMT.jl; dsfmt_fill_array_close1_open2!; line: 66 
       4 dSFMT.jl; dsfmt_fill_array_close1_open2!; line: 67 
      2 random.jl; rand; line: 256 
      47 ....devel/src/helper.jl; random_generator; line: 47 
      1 ....devel/src/helper.jl; random_generator; line: 48 
      13 ....devel/src/helper.jl; random_generator; line: 49 
      1 ....devel/src/helper.jl; random_generator; line: 52 
      86 In[174]; findmargeflip!; line: 17 
      9 ....devel/src/helper.jl; random_generator; line: 44 
      5 random.jl; rand; line: 255 
      4 random.jl; gen_rand; line: 88 
       4 dSFMT.jl; dsfmt_fill_array_close1_open2!; line: 67 
      1 random.jl; rand; line: 256 
      53 ....devel/src/helper.jl; random_generator; line: 47 
      1 ....devel/src/helper.jl; random_generator; line: 48 
      13 ....devel/src/helper.jl; random_generator; line: 49 
      2 ....devel/src/helper.jl; random_generator; line: 52 
      211 In[174]; findmargeflip!; line: 19 
      87 abstractarray.jl; vcat; line: 733 
      9 subarray.jl; _sub; line: 90 
      35 subarray.jl; _sub; line: 91 
      1 subarray.jl; _sub_unsafe; line: 96 
      21 subarray.jl; _sub_unsafe; line: 125 
      1 subarray.jl; _sub_unsafe; line: 437 
      1 subarray.jl; _sub_unsafe; line: 440 
      411 In[174]; findmargeflip!; line: 20 
      5 abstractarray.jl; ==; line: 1060 
      4 abstractarray.jl; ==; line: 1066 
      258 abstractarray.jl; ==; line: 1067 
      4 abstractarray.jl; ==; line: 1068 
      2 abstractarray.jl; hvcat; line: 957 
      87 abstractarray.jl; hvcat; line: 960 
      1 abstractarray.jl; hvcat; line: 961 
      2 abstractarray.jl; hvcat; line: 969 
      3 abstractarray.jl; hvcat; line: 970 
      11 abstractarray.jl; hvcat; line: 971 
      1 abstractarray.jl; hvcat; line: 974 
      4 In[174]; findmargeflip!; line: 25 
      1 abstractarray.jl; ==; line: 1060 
      2 abstractarray.jl; hvcat; line: 960 
      1 abstractarray.jl; vcat; line: 733 
    1 tuple.jl; ==; line: 95 
    3 tuple.jl; ==; line: 96 

Answer 1

これは同じ機能の別の実装です（正しく動作するかどうかわかっている場合）。より速く動作する可能性は高いですが、OPと同じランダムソースは使用しません。それを見て、最適化の提案をするかもしれません。

これが役に立ちます。Mは行列であり、nflipit!(M,n)と

function flipit!(m, flipcount) 
    zeroinds = map(x->ind2sub(m,x),find(m .== 0)) # find 0 locations 
    zerorows = Set{Int}(map(first,zeroinds))  # find rows with 0s 
    zerocols = Set{Int}(map(last,zeroinds))  # find cols with 0s 
    oneinds = map(x->ind2sub(m,x),find(m .== 1)) # find 1 locations 
    filter!(x->x[1] in zerorows && x[2] in zerocols,oneinds) # must satisfy trivially 
    n = length(oneinds) 
    numflips = 0 
    badcount = 0         
    badcorners = Set{Tuple{Int,Int}}()  # track bad rectangles 
    maxbad = binomial(length(oneinds),2) # num candidate rectangles 
    maxbad == 0 && error("Can't find candidate rectangle") 
    randbuf = rand(1:n,2*flipcount)  # make some rands to use later 
    while numflips < flipcount 
    if length(randbuf)==0 
     randbuf = rand(1:n,2*flipcount) # refresh rands 
    end 
    cornersinds = minmax(pop!(randbuf),pop!(randbuf)) 
    if first(cornersinds)==last(cornersinds) continue ; end 
    if cornersinds in badcorners        
     continue         # bad candidate 
    end 
    corners = (oneinds[cornersinds[1]],oneinds[cornersinds[2]]) 
    if m[corners[1][1],corners[2][2]] == 0 &&  # check 0s 
     m[corners[2][1],corners[1][2]] == 0   
     m[corners[1]...] = 0      # flip 
     m[corners[2]...] = 0 
     m[corners[1][1],corners[2][2]] = 1 
     m[corners[2][1],corners[1][2]] = 1 
     oneinds[cornersinds[1]] = (corners[1][1],corners[2][2]) # flip corner list 
     oneinds[cornersinds[2]] = (corners[2][1],corners[1][2]) 
     numflips += 1 
     if badcount>0 
     badcount = 0 
     empty!(badcorners) 
     end 
    else 
     push!(badcorners,cornersinds)  # remember bad candidate 
     badcount += 1 
     if badcount == maxbad    # if candidates exhausted 
     error("No flippable rectangle") 
     end 
    end 
    end 
end 

使用は、所望のフリップの数です。これは、コンパクトさを明確にするために、最もクリーンなコードではありません。

Answer 2

プロファイリングが明確に最も時間が

ある

211 In[174]; findmargeflip!; line: 19 
411 In[174]; findmargeflip!; line: 20 

に費やされていることを言いました

vall = sub(shuffledmatrix, [rows[1]; rows[2]],[cols[1]; cols[2]]) 
    if vall == [0 1; 1 0] || vall == [1 0; 0 1] 

あなたは場所全体に新しい配列を割り当てています。

あなたはInt32 & Int64を混入していない理由ちなみに

size(val1) == (2,2) && val1[1,1] == 0 && 
    val1[1,2] == 1 && val1[2,1] == 1 && val1[2,2] == 0 

ようなものでvall == [0 1; 1 0]を交換してみてください？行列にメモリを節約するには？