{"action":"created","issue":{"url":"https://api.github.com/repos/scipy/scipy/issues/6806","repository_url":"https://api.github.com/repos/scipy/scipy","labels_url":"https://api.github.com/repos/scipy/scipy/issues/6806/labels{/name}","comments_url":"https://api.github.com/repos/scipy/scipy/issues/6806/comments","events_url":"https://api.github.com/repos/scipy/scipy/issues/6806/events","html_url":"https://github.com/scipy/scipy/pull/6806","id":191031539,"number":6806,"title":"ENH: Faster linkage for 'centroid' and 'median' methods","user":{"login":"nmayorov","id":7074023,"avatar_url":"https://avatars.githubusercontent.com/u/7074023?v=3","gravatar_id":"","url":"https://api.github.com/users/nmayorov","html_url":"https://github.com/nmayorov","followers_url":"https://api.github.com/users/nmayorov/followers","following_url":"https://api.github.com/users/nmayorov/following{/other_user}","gists_url":"https://api.github.com/users/nmayorov/gists{/gist_id}","starred_url":"https://api.github.com/users/nmayorov/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/nmayorov/subscriptions","organizations_url":"https://api.github.com/users/nmayorov/orgs","repos_url":"https://api.github.com/users/nmayorov/repos","events_url":"https://api.github.com/users/nmayorov/events{/privacy}","received_events_url":"https://api.github.com/users/nmayorov/received_events","type":"User","site_admin":false},"labels":[{"id":37340735,"url":"https://api.github.com/repos/scipy/scipy/labels/enhancement","name":"enhancement","color":"bfe5bf","default":true},{"id":37342878,"url":"https://api.github.com/repos/scipy/scipy/labels/scipy.cluster","name":"scipy.cluster","color":"207de5","default":false}],"state":"closed","locked":false,"assignee":null,"assignees":[],"milestone":{"url":"https://api.github.com/repos/scipy/scipy/milestones/30","html_url":"https://github.com/scipy/scipy/milestones/0.19.0","labels_url":"https://api.github.com/repos/scipy/scipy/milestones/30/labels","id":1836547,"number":30,"title":"0.19.0","description":"","creator":{"login":"ev-br","id":2133832,"avatar_url":"https://avatars.githubusercontent.com/u/2133832?v=3","gravatar_id":"","url":"https://api.github.com/users/ev-br","html_url":"https://github.com/ev-br","followers_url":"https://api.github.com/users/ev-br/followers","following_url":"https://api.github.com/users/ev-br/following{/other_user}","gists_url":"https://api.github.com/users/ev-br/gists{/gist_id}","starred_url":"https://api.github.com/users/ev-br/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ev-br/subscriptions","organizations_url":"https://api.github.com/users/ev-br/orgs","repos_url":"https://api.github.com/users/ev-br/repos","events_url":"https://api.github.com/users/ev-br/events{/privacy}","received_events_url":"https://api.github.com/users/ev-br/received_events","type":"User","site_admin":false},"open_issues":18,"closed_issues":207,"state":"open","created_at":"2016-06-19T11:44:03Z","updated_at":"2016-11-27T18:18:58Z","due_on":"2017-01-20T00:00:00Z","closed_at":null},"comments":12,"created_at":"2016-11-22T15:05:20Z","updated_at":"2016-11-29T18:31:43Z","closed_at":"2016-11-27T18:18:58Z","pull_request":{"url":"https://api.github.com/repos/scipy/scipy/pulls/6806","html_url":"https://github.com/scipy/scipy/pull/6806","diff_url":"https://github.com/scipy/scipy/pull/6806.diff","patch_url":"https://github.com/scipy/scipy/pull/6806.patch"},"body":"As mentioned in #6802, the trivial algorithm can be improved significantly to run as O(N^2) in the best case, which often happens in practice.\r\n\r\nSo I implemented this modification, rather straightforward. But some more experimenting / reviewing will be useful.\r\n\r\nHere is a comparison example:\r\n\r\n```Python\r\nfrom time import time\r\nimport numpy as np\r\nfrom scipy.cluster.hierarchy import linkage\r\nfrom scipy.spatial.distance import pdist\r\nfrom fastcluster import linkage as linkage_fc\r\n\r\nnp.random.seed(0)\r\nX = np.random.randn(3000, 2)\r\nd = pdist(X)\r\n\r\n\r\ndef cluster_and_time(d, fun, method):\r\n    t1 = time()\r\n    Z = fun(d, method=method)\r\n    t2 = time()\r\n    return Z, t2 - t1\r\n\r\n\r\ncases = [\r\n    ('new', linkage, 'median'),\r\n    ('old', linkage, 'median_old'),\r\n    ('fc', linkage_fc, 'median')\r\n]\r\n\r\ndts = {}\r\nZs = {}\r\n\r\nfor name, fun, method in cases:\r\n    Z, dt = cluster_and_time(d, fun, method)\r\n    dts[name] = dt\r\n    Zs[name] = Z\r\n    \r\nfor name, dt in dts.items():\r\n    print(name, dt)\r\n    \r\nprint(np.allclose(Zs['new'], Zs['old']))\r\nprint(np.allclose(Zs['new'], Zs['fc']))\r\nprint(np.allclose(Zs['old'], Zs['fc']))\r\n```\r\n```\r\nold 11.613052129745483\r\nnew 0.2184290885925293\r\nfc 0.09301209449768066\r\nTrue\r\nTrue\r\nTrue\r\n```\r\n\r\nI think it's worth keeping the original `linkage` forever for reference and comparison.\r\n\r\n@rgommers @richardtsai "},"comment":{"url":"https://api.github.com/repos/scipy/scipy/issues/comments/263656419","html_url":"https://github.com/scipy/scipy/pull/6806#issuecomment-263656419","issue_url":"https://api.github.com/repos/scipy/scipy/issues/6806","id":263656419,"user":{"login":"nmayorov","id":7074023,"avatar_url":"https://avatars.githubusercontent.com/u/7074023?v=3","gravatar_id":"","url":"https://api.github.com/users/nmayorov","html_url":"https://github.com/nmayorov","followers_url":"https://api.github.com/users/nmayorov/followers","following_url":"https://api.github.com/users/nmayorov/following{/other_user}","gists_url":"https://api.github.com/users/nmayorov/gists{/gist_id}","starred_url":"https://api.github.com/users/nmayorov/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/nmayorov/subscriptions","organizations_url":"https://api.github.com/users/nmayorov/orgs","repos_url":"https://api.github.com/users/nmayorov/repos","events_url":"https://api.github.com/users/nmayorov/events{/privacy}","received_events_url":"https://api.github.com/users/nmayorov/received_events","type":"User","site_admin":false},"created_at":"2016-11-29T18:31:43Z","updated_at":"2016-11-29T18:31:43Z","body":"Some information for reference. \r\n\r\nWhen we use contiguous memoryviews, say `double[::1] D`, then the generated indexing code changes from something like `*(p + i * stride)` to `*(p + i)`. After I coded contiguous views everywhere, I got about 7% speed up. So such small improvement is possible, but it is not that useful."}}
{"actor":{"display_login":"nmayorov"}}