payload: {"action":"created","issue":{"url":"https://api.github.com/repos/JuliaStats/Clustering.jl/issues/156","repository_url":"https://api.github.com/repos/JuliaStats/Clustering.jl","labels_url":"https://api.github.com/repos/JuliaStats/Clustering.jl/issues/156/labels{/name}","comments_url":"https://api.github.com/repos/JuliaStats/Clustering.jl/issues/156/comments","events_url":"https://api.github.com/repos/JuliaStats/Clustering.jl/issues/156/events","html_url":"https://github.com/JuliaStats/Clustering.jl/pull/156","id":426596010,"node_id":"MDExOlB1bGxSZXF1ZXN0MjY1NDE0MDM3","number":156,"title":"Specialize MCL functions for Sparse Matrices","user":{"login":"altre","id":4160707,"node_id":"MDQ6VXNlcjQxNjA3MDc=","avatar_url":"https://avatars3.githubusercontent.com/u/4160707?v=4","gravatar_id":"","url":"https://api.github.com/users/altre","html_url":"https://github.com/altre","followers_url":"https://api.github.com/users/altre/followers","following_url":"https://api.github.com/users/altre/following{/other_user}","gists_url":"https://api.github.com/users/altre/gists{/gist_id}","starred_url":"https://api.github.com/users/altre/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/altre/subscriptions","organizations_url":"https://api.github.com/users/altre/orgs","repos_url":"https://api.github.com/users/altre/repos","events_url":"https://api.github.com/users/altre/events{/privacy}","received_events_url":"https://api.github.com/users/altre/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":1,"created_at":"2019-03-28T16:39:14Z","updated_at":"2019-03-28T17:27:38Z","closed_at":null,"author_association":"NONE","pull_request":{"url":"https://api.github.com/repos/JuliaStats/Clustering.jl/pulls/156","html_url":"https://github.com/JuliaStats/Clustering.jl/pull/156","diff_url":"https://github.com/JuliaStats/Clustering.jl/pull/156.diff","patch_url":"https://github.com/JuliaStats/Clustering.jl/pull/156.patch"},"body":"I've needed to add some specialized functions for Sparse Matrices in the mcl implementation  to make it feasible for use on larger Matrices.\r\nBenchmarking the old vs the new using:\r\n```\r\nusing SparseArrays\r\nusing Clustering\r\nusing BenchmarkTools\r\nusing Random\r\nRandom.seed!(1)\r\nadj = sprand(1000, 1000, 0.1)\r\n@benchmark mcl(adj)\r\n```\r\nOld:\r\n```julia> @benchmark mcl(adj)\r\nBenchmarkTools.Trial: \r\n  memory estimate:  251.94 MiB\r\n  allocs estimate:  103199\r\n  --------------\r\n  minimum time:     54.339 s (0.35% GC)\r\n  median time:      54.339 s (0.35% GC)\r\n  mean time:        54.339 s (0.35% GC)\r\n  maximum time:     54.339 s (0.35% GC)\r\n  --------------\r\n  samples:          1\r\n  evals/sample:     1\r\n```\r\nNew:\r\n```\r\njulia> @benchmark mcl(adj)\r\nBenchmarkTools.Trial: \r\n  memory estimate:  48.41 MiB\r\n  allocs estimate:  20675\r\n  --------------\r\n  minimum time:     144.370 ms (5.11% GC)\r\n  median time:      228.582 ms (9.42% GC)\r\n  mean time:        279.637 ms (16.85% GC)\r\n  maximum time:     578.249 ms (26.47% GC)\r\n  --------------\r\n  samples:          18\r\n  evals/sample:     1\r\n```\r\n\r\nNote that this is a contrived example, using a dense matrix of size (1000,1000) is faster. Using this only makes sense for larger sparse matrices which don't fit into memory."},"comment":{"url":"https://api.github.com/repos/JuliaStats/Clustering.jl/issues/comments/477694911","html_url":"https://github.com/JuliaStats/Clustering.jl/pull/156#issuecomment-477694911","issue_url":"https://api.github.com/repos/JuliaStats/Clustering.jl/issues/156","id":477694911,"node_id":"MDEyOklzc3VlQ29tbWVudDQ3NzY5NDkxMQ==","user":{"login":"alyst","id":348591,"node_id":"MDQ6VXNlcjM0ODU5MQ==","avatar_url":"https://avatars2.githubusercontent.com/u/348591?v=4","gravatar_id":"","url":"https://api.github.com/users/alyst","html_url":"https://github.com/alyst","followers_url":"https://api.github.com/users/alyst/followers","following_url":"https://api.github.com/users/alyst/following{/other_user}","gists_url":"https://api.github.com/users/alyst/gists{/gist_id}","starred_url":"https://api.github.com/users/alyst/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/alyst/subscriptions","organizations_url":"https://api.github.com/users/alyst/orgs","repos_url":"https://api.github.com/users/alyst/repos","events_url":"https://api.github.com/users/alyst/events{/privacy}","received_events_url":"https://api.github.com/users/alyst/received_events","type":"User","site_admin":false},"created_at":"2019-03-28T17:27:38Z","updated_at":"2019-03-28T17:27:38Z","author_association":"CONTRIBUTOR","body":"If it's possible to speed up MCL in the sparse case, that would be nice! I was worried that expansion will generate too many nonzeros for any sparse matrix and outweigh any performance gains, but I might be wrong. Could you please add tests checking that a) sparse case works (doesn't crash), b) the results of sparse and dense implementations are identical (for some reasonable nontrivial case)? We will need that to accept the PR, but it would also help you to shape the changes in the MCL code."}}
other: {"actor":{"display_login":"alyst"}}