{"action":"created","issue":{"url":"https://api.github.com/repos/JuliaLang/julia/issues/10803","labels_url":"https://api.github.com/repos/JuliaLang/julia/issues/10803/labels{/name}","comments_url":"https://api.github.com/repos/JuliaLang/julia/issues/10803/comments","events_url":"https://api.github.com/repos/JuliaLang/julia/issues/10803/events","html_url":"https://github.com/JuliaLang/julia/issues/10803","id":68168708,"number":10803,"title":"Slow sub2ind and ind2sub","user":{"login":"romanShekhtman","id":6709796,"avatar_url":"https://avatars.githubusercontent.com/u/6709796?v=3","gravatar_id":"","url":"https://api.github.com/users/romanShekhtman","html_url":"https://github.com/romanShekhtman","followers_url":"https://api.github.com/users/romanShekhtman/followers","following_url":"https://api.github.com/users/romanShekhtman/following{/other_user}","gists_url":"https://api.github.com/users/romanShekhtman/gists{/gist_id}","starred_url":"https://api.github.com/users/romanShekhtman/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/romanShekhtman/subscriptions","organizations_url":"https://api.github.com/users/romanShekhtman/orgs","repos_url":"https://api.github.com/users/romanShekhtman/repos","events_url":"https://api.github.com/users/romanShekhtman/events{/privacy}","received_events_url":"https://api.github.com/users/romanShekhtman/received_events","type":"User","site_admin":false},"labels":[],"state":"closed","locked":false,"assignee":null,"milestone":null,"comments":1,"created_at":"2015-04-13T19:01:02Z","updated_at":"2015-04-13T19:19:05Z","closed_at":"2015-04-13T19:19:05Z","body":"sub2ind and ind2sub are implemented in a very slow way. Checkout my implementation and compare run time to the julia built in implementation. I observed factors of up to 50 \r\n\r\njulia> include(\"test_sub2ind.jl\")\r\nJulia sub2ind 2D elapsed time: 3.071918131 seconds\r\nMy sub2ind 2D    elapsed time: 0.061298908 seconds\r\nJulia ind2sub 2D elapsed time: 1.626608852 seconds\r\nMy ind2sub 2D    elapsed time: 0.253709231 seconds\r\nJulia sub2ind 3D elapsed time: 4.206525844 seconds\r\nMy sub2ind 3D    elapsed time: 0.080784239 seconds\r\nJulia ind2sub 3D elapsed time: 2.85505408 seconds\r\nMy ind2sub 3D    elapsed time: 0.491045143 seconds\r\n\r\n\r\n```julia\r\nfunction mysub2ind( s::Vector{Int64}, \r\n                    ii::Vector{Int64},jj::Vector{Int64} )\r\n   # 2D sub2ind                 \r\n   const nn = length(ii)\r\n   \r\n   if length(jj) != nn\r\n      error(\"length(jj) != nn\")\r\n   elseif length(s) != 2\r\n      error(\"length(s) != 2\")\r\n   end\r\n   \r\n   idx = Array(Int64,nn)\r\n   \r\n   const m = s[1]\r\n   \r\n   for i = 1:nn\r\n      idx[i] = ii[i] + (jj[i]-1)*m\r\n   end\r\n   \r\n   return idx\r\nend  # function mysub2ind\r\n\r\n#----------------------------------------------------\r\n\r\nfunction mysub2ind( s::Vector{Int64},\r\n                    ii::Vector{Int64},jj::Vector{Int64},kk::Vector{Int64} )\r\n   # 3D sub2ind                 \r\n   const nn = length(ii)\r\n   \r\n   if length(jj) != nn || length(kk) != nn\r\n      error(\"length(jj) != nn\")\r\n   elseif length(s) != 3\r\n      error(\"length(s) != 3\")\r\n   end\r\n   \r\n   idx = Array(Int64,nn)\r\n   \r\n   const m = s[1]\r\n   const mn = s[1] * s[2]\r\n   \r\n   for i = 1:nn\r\n      idx[i] = ii[i] + (jj[i]-1)*m + (kk[i]-1)*mn\r\n   end\r\n   \r\n   return idx\r\nend  # function mysub2ind\r\n\r\n#-------------------------------------------------------\r\n#-------------------------------------------------------\r\n\r\nfunction myind2sub( s::Vector{Int64}, idx::Vector{Int64} )\r\n   const nn = length(idx)\r\n   \r\n   if length(s) == 2\r\n      ii = Array(Int64,nn)\r\n      jj = Array(Int64,nn)\r\n      \r\n      const s1 = s[1]\r\n   \r\n      for i = 1:nn\r\n      \r\n         it = idx[i]\r\n         ji = div(it - 1, s1) + 1\r\n         jj[i] = ji\r\n      \r\n         ii[i] = it - (ji - 1)*s1\r\n   \r\n      end  # i\r\n   \r\n      return ii,jj\r\n      \r\n   elseif length(s) == 3\r\n   \r\n      ii = Array(Int64,nn)\r\n      jj = Array(Int64,nn)\r\n      kk = Array(Int64,nn)\r\n      \r\n      const s1 = s[1]\r\n      const s12 = s[1] * s[2]\r\n   \r\n      for i = 1:nn\r\n         idxi = idx[i]\r\n         ki = div(idxi - 1, s12) + 1\r\n         kk[i] = ki\r\n      \r\n         it = idxi - (ki - 1)*s12\r\n      \r\n         ji = div(it - 1, s1) + 1\r\n         jj[i] = ji\r\n         ii[i] = it - (ji - 1)*s1\r\n   \r\n      end  # i\r\n   \r\n      return ii,jj,kk\r\n   \r\n   else\r\n      error(\"myind2sub only works for 2d or 3d arrays.\")\r\n   end\r\n   \r\nend # function myind2sub\r\n```\r\n\r\nNow the test\r\n```julia\r\n\r\ninclude(\"mysub2ind.jl\")\r\n\r\n# 2D test\r\nmrow = 10000\r\nncol = 20000\r\n\r\npfil = 0.1\r\nnz = trunc(Int64, mrow*ncol*pfil)  # # of non-zeros\r\n\r\nii = rand(1:mrow, nz)\r\njj = rand(1:ncol, nz)\r\n\r\n\r\nprint(\"Julia sub2ind 2D \")\r\ntic()\r\nidx = sub2ind( (mrow,ncol), ii,jj );\r\ntoc()\r\n\r\nprint(\"My sub2ind 2D    \")\r\ntic()\r\nidx2 = mysub2ind( [mrow,ncol], ii,jj );\r\ntoc()\r\n\r\n\r\ner = norm(idx - idx2)\r\nif er != 0\r\n   error(\"mysub2ind error\")\r\nend\r\n\r\nprint(\"Julia ind2sub 2D \")\r\n\r\ntic()\r\nii2,jj2 = ind2sub((mrow,ncol), idx)\r\ntoc()\r\ner = norm(ii2 - ii) + norm(jj2 - jj)\r\nif er != 0\r\n   error(\"ind2sub error\")\r\nend\r\n\r\nprint(\"My ind2sub 2D    \")\r\n\r\ntic()\r\nii3,jj3 = myind2sub([mrow,ncol], idx2)\r\ntoc()\r\n\r\ner = norm(ii3 - ii) + norm(jj3 - jj)\r\nif er != 0\r\n   error(\"myind2sub error\")\r\nend\r\n\r\n#------------------------------------------------\r\n\r\n# 3D test\r\n\r\nm1 = 1024\r\nm2 = 2048\r\nm3 = 512\r\n\r\npfil = 0.02\r\nnz = trunc(Int64, m1*m2*m3*pfil)  # # of non-zeros\r\n\r\nii = rand(1:m1, nz)\r\njj = rand(1:m2, nz)\r\nkk = rand(1:m3, nz)\r\n\r\nprint(\"Julia sub2ind 3D \")\r\n\r\ntic()\r\nidx = sub2ind( (m1,m2,m3), ii,jj,kk );\r\ntoc()\r\n\r\nprint(\"My sub2ind 3D    \")\r\n\r\ntic()\r\nidx2 = mysub2ind( [m1,m2,m3], ii,jj,kk );\r\ntoc()\r\n\r\ner = norm(idx - idx2)\r\nif er != 0\r\n   error(\"mysub2ind error\")\r\nend\r\n\r\nprint(\"Julia ind2sub 3D \")\r\n\r\ntic()\r\nii2,jj2,kk2 = ind2sub((m1,m2,m3), idx)\r\ntoc()\r\ner = norm(ii2 - ii) + norm(jj2 - jj) + norm(kk2 - kk)\r\nif er != 0\r\n   error(\"ind2sub error\")\r\nend\r\n\r\nprint(\"My ind2sub 3D    \")\r\n\r\ntic()\r\nii3,jj3,kk3 = myind2sub([m1,m2,m3], idx2)\r\ntoc()\r\n\r\ner = norm(ii3 - ii) + norm(jj3 - jj) + norm(kk3 - kk)\r\nif er != 0\r\n   error(\"myind2sub error\")\r\nend\r\n\r\n```"},"comment":{"url":"https://api.github.com/repos/JuliaLang/julia/issues/comments/92467823","html_url":"https://github.com/JuliaLang/julia/issues/10803#issuecomment-92467823","issue_url":"https://api.github.com/repos/JuliaLang/julia/issues/10803","id":92467823,"user":{"login":"pao","id":140497,"avatar_url":"https://avatars.githubusercontent.com/u/140497?v=3","gravatar_id":"","url":"https://api.github.com/users/pao","html_url":"https://github.com/pao","followers_url":"https://api.github.com/users/pao/followers","following_url":"https://api.github.com/users/pao/following{/other_user}","gists_url":"https://api.github.com/users/pao/gists{/gist_id}","starred_url":"https://api.github.com/users/pao/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/pao/subscriptions","organizations_url":"https://api.github.com/users/pao/orgs","repos_url":"https://api.github.com/users/pao/repos","events_url":"https://api.github.com/users/pao/events{/privacy}","received_events_url":"https://api.github.com/users/pao/received_events","type":"User","site_admin":false},"created_at":"2015-04-13T19:19:05Z","updated_at":"2015-04-13T19:19:05Z","body":"Closing as duplicate in favor of #10337--please take a look at the proposed replacement there and offer feedback! Thanks!"}}