{"action":"created","comment":{"url":"https://api.github.com/repos/scipy/scipy/pulls/comments/89368703","pull_request_review_id":9915044,"id":89368703,"diff_hunk":"@@ -682,8 +681,8 @@ def linkage(y, method='single', metric='euclidean'):\n         return _hierarchy.mst_single_linkage(y, n)\n     elif method in ['complete', 'average', 'weighted', 'ward']:\n         return _hierarchy.nn_chain(y, n, method_code)\n-    else:\n-        return _hierarchy.linkage(y, n, method_code)\n+    elif method in ['centroid', 'median']:","path":"scipy/cluster/hierarchy.py","position":14,"original_position":14,"commit_id":"84cf73aa30ec98e6d2c6a96da394b5f41267117e","original_commit_id":"84cf73aa30ec98e6d2c6a96da394b5f41267117e","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},"body":"I'm fine with the previous way too.","created_at":"2016-11-23T17:57:09Z","updated_at":"2016-11-23T17:57:09Z","html_url":"https://github.com/scipy/scipy/pull/6806#discussion_r89368703","pull_request_url":"https://api.github.com/repos/scipy/scipy/pulls/6806","_links":{"self":{"href":"https://api.github.com/repos/scipy/scipy/pulls/comments/89368703"},"html":{"href":"https://github.com/scipy/scipy/pull/6806#discussion_r89368703"},"pull_request":{"href":"https://api.github.com/repos/scipy/scipy/pulls/6806"}}},"pull_request":{"url":"https://api.github.com/repos/scipy/scipy/pulls/6806","id":94831334,"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","issue_url":"https://api.github.com/repos/scipy/scipy/issues/6806","number":6806,"state":"open","locked":false,"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},"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 ","created_at":"2016-11-22T15:05:20Z","updated_at":"2016-11-23T17:57:09Z","closed_at":null,"merged_at":null,"merge_commit_sha":"447c9e3ed23c2f07e751b985d88f6088a190d5b7","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":17,"closed_issues":204,"state":"open","created_at":"2016-06-19T11:44:03Z","updated_at":"2016-11-22T15:05:21Z","due_on":"2017-01-20T00:00:00Z","closed_at":null},"commits_url":"https://api.github.com/repos/scipy/scipy/pulls/6806/commits","review_comments_url":"https://api.github.com/repos/scipy/scipy/pulls/6806/comments","review_comment_url":"https://api.github.com/repos/scipy/scipy/pulls/comments{/number}","comments_url":"https://api.github.com/repos/scipy/scipy/issues/6806/comments","statuses_url":"https://api.github.com/repos/scipy/scipy/statuses/84cf73aa30ec98e6d2c6a96da394b5f41267117e","head":{"label":"nmayorov:fast_linkage","ref":"fast_linkage","sha":"84cf73aa30ec98e6d2c6a96da394b5f41267117e","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},"repo":{"id":31169507,"name":"scipy","full_name":"nmayorov/scipy","owner":{"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},"private":false,"html_url":"https://github.com/nmayorov/scipy","description":"Scipy library main repository","fork":true,"url":"https://api.github.com/repos/nmayorov/scipy","forks_url":"https://api.github.com/repos/nmayorov/scipy/forks","keys_url":"https://api.github.com/repos/nmayorov/scipy/keys{/key_id}","collaborators_url":"https://api.github.com/repos/nmayorov/scipy/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/nmayorov/scipy/teams","hooks_url":"https://api.github.com/repos/nmayorov/scipy/hooks","issue_events_url":"https://api.github.com/repos/nmayorov/scipy/issues/events{/number}","events_url":"https://api.github.com/repos/nmayorov/scipy/events","assignees_url":"https://api.github.com/repos/nmayorov/scipy/assignees{/user}","branches_url":"https://api.github.com/repos/nmayorov/scipy/branches{/branch}","tags_url":"https://api.github.com/repos/nmayorov/scipy/tags","blobs_url":"https://api.github.com/repos/nmayorov/scipy/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/nmayorov/scipy/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/nmayorov/scipy/git/refs{/sha}","trees_url":"https://api.github.com/repos/nmayorov/scipy/git/trees{/sha}","statuses_url":"https://api.github.com/repos/nmayorov/scipy/statuses/{sha}","languages_url":"https://api.github.com/repos/nmayorov/scipy/languages","stargazers_url":"https://api.github.com/repos/nmayorov/scipy/stargazers","contributors_url":"https://api.github.com/repos/nmayorov/scipy/contributors","subscribers_url":"https://api.github.com/repos/nmayorov/scipy/subscribers","subscription_url":"https://api.github.com/repos/nmayorov/scipy/subscription","commits_url":"https://api.github.com/repos/nmayorov/scipy/commits{/sha}","git_commits_url":"https://api.github.com/repos/nmayorov/scipy/git/commits{/sha}","comments_url":"https://api.github.com/repos/nmayorov/scipy/comments{/number}","issue_comment_url":"https://api.github.com/repos/nmayorov/scipy/issues/comments{/number}","contents_url":"https://api.github.com/repos/nmayorov/scipy/contents/{+path}","compare_url":"https://api.github.com/repos/nmayorov/scipy/compare/{base}...{head}","merges_url":"https://api.github.com/repos/nmayorov/scipy/merges","archive_url":"https://api.github.com/repos/nmayorov/scipy/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/nmayorov/scipy/downloads","issues_url":"https://api.github.com/repos/nmayorov/scipy/issues{/number}","pulls_url":"https://api.github.com/repos/nmayorov/scipy/pulls{/number}","milestones_url":"https://api.github.com/repos/nmayorov/scipy/milestones{/number}","notifications_url":"https://api.github.com/repos/nmayorov/scipy/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/nmayorov/scipy/labels{/name}","releases_url":"https://api.github.com/repos/nmayorov/scipy/releases{/id}","deployments_url":"https://api.github.com/repos/nmayorov/scipy/deployments","created_at":"2015-02-22T16:30:36Z","updated_at":"2016-01-25T21:59:34Z","pushed_at":"2016-11-22T21:38:01Z","git_url":"git://github.com/nmayorov/scipy.git","ssh_url":"git@github.com:nmayorov/scipy.git","clone_url":"https://github.com/nmayorov/scipy.git","svn_url":"https://github.com/nmayorov/scipy","homepage":"http://scipy.org/scipylib/","size":62745,"stargazers_count":0,"watchers_count":0,"language":"Python","has_issues":false,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":0,"mirror_url":null,"open_issues_count":0,"forks":0,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"scipy:master","ref":"master","sha":"28e2ee4d62ac07112c79f68818c435c197c7bd0e","user":{"login":"scipy","id":288277,"avatar_url":"https://avatars.githubusercontent.com/u/288277?v=3","gravatar_id":"","url":"https://api.github.com/users/scipy","html_url":"https://github.com/scipy","followers_url":"https://api.github.com/users/scipy/followers","following_url":"https://api.github.com/users/scipy/following{/other_user}","gists_url":"https://api.github.com/users/scipy/gists{/gist_id}","starred_url":"https://api.github.com/users/scipy/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/scipy/subscriptions","organizations_url":"https://api.github.com/users/scipy/orgs","repos_url":"https://api.github.com/users/scipy/repos","events_url":"https://api.github.com/users/scipy/events{/privacy}","received_events_url":"https://api.github.com/users/scipy/received_events","type":"Organization","site_admin":false},"repo":{"id":1460385,"name":"scipy","full_name":"scipy/scipy","owner":{"login":"scipy","id":288277,"avatar_url":"https://avatars.githubusercontent.com/u/288277?v=3","gravatar_id":"","url":"https://api.github.com/users/scipy","html_url":"https://github.com/scipy","followers_url":"https://api.github.com/users/scipy/followers","following_url":"https://api.github.com/users/scipy/following{/other_user}","gists_url":"https://api.github.com/users/scipy/gists{/gist_id}","starred_url":"https://api.github.com/users/scipy/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/scipy/subscriptions","organizations_url":"https://api.github.com/users/scipy/orgs","repos_url":"https://api.github.com/users/scipy/repos","events_url":"https://api.github.com/users/scipy/events{/privacy}","received_events_url":"https://api.github.com/users/scipy/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/scipy/scipy","description":"Scipy library main repository","fork":false,"url":"https://api.github.com/repos/scipy/scipy","forks_url":"https://api.github.com/repos/scipy/scipy/forks","keys_url":"https://api.github.com/repos/scipy/scipy/keys{/key_id}","collaborators_url":"https://api.github.com/repos/scipy/scipy/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/scipy/scipy/teams","hooks_url":"https://api.github.com/repos/scipy/scipy/hooks","issue_events_url":"https://api.github.com/repos/scipy/scipy/issues/events{/number}","events_url":"https://api.github.com/repos/scipy/scipy/events","assignees_url":"https://api.github.com/repos/scipy/scipy/assignees{/user}","branches_url":"https://api.github.com/repos/scipy/scipy/branches{/branch}","tags_url":"https://api.github.com/repos/scipy/scipy/tags","blobs_url":"https://api.github.com/repos/scipy/scipy/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/scipy/scipy/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/scipy/scipy/git/refs{/sha}","trees_url":"https://api.github.com/repos/scipy/scipy/git/trees{/sha}","statuses_url":"https://api.github.com/repos/scipy/scipy/statuses/{sha}","languages_url":"https://api.github.com/repos/scipy/scipy/languages","stargazers_url":"https://api.github.com/repos/scipy/scipy/stargazers","contributors_url":"https://api.github.com/repos/scipy/scipy/contributors","subscribers_url":"https://api.github.com/repos/scipy/scipy/subscribers","subscription_url":"https://api.github.com/repos/scipy/scipy/subscription","commits_url":"https://api.github.com/repos/scipy/scipy/commits{/sha}","git_commits_url":"https://api.github.com/repos/scipy/scipy/git/commits{/sha}","comments_url":"https://api.github.com/repos/scipy/scipy/comments{/number}","issue_comment_url":"https://api.github.com/repos/scipy/scipy/issues/comments{/number}","contents_url":"https://api.github.com/repos/scipy/scipy/contents/{+path}","compare_url":"https://api.github.com/repos/scipy/scipy/compare/{base}...{head}","merges_url":"https://api.github.com/repos/scipy/scipy/merges","archive_url":"https://api.github.com/repos/scipy/scipy/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/scipy/scipy/downloads","issues_url":"https://api.github.com/repos/scipy/scipy/issues{/number}","pulls_url":"https://api.github.com/repos/scipy/scipy/pulls{/number}","milestones_url":"https://api.github.com/repos/scipy/scipy/milestones{/number}","notifications_url":"https://api.github.com/repos/scipy/scipy/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/scipy/scipy/labels{/name}","releases_url":"https://api.github.com/repos/scipy/scipy/releases{/id}","deployments_url":"https://api.github.com/repos/scipy/scipy/deployments","created_at":"2011-03-09T18:52:03Z","updated_at":"2016-11-23T17:31:08Z","pushed_at":"2016-11-23T15:42:04Z","git_url":"git://github.com/scipy/scipy.git","ssh_url":"git@github.com:scipy/scipy.git","clone_url":"https://github.com/scipy/scipy.git","svn_url":"https://github.com/scipy/scipy","homepage":"http://scipy.org/scipylib/","size":80666,"stargazers_count":2714,"watchers_count":2714,"language":"Python","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":1572,"mirror_url":null,"open_issues_count":928,"forks":1572,"open_issues":928,"watchers":2714,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/scipy/scipy/pulls/6806"},"html":{"href":"https://github.com/scipy/scipy/pull/6806"},"issue":{"href":"https://api.github.com/repos/scipy/scipy/issues/6806"},"comments":{"href":"https://api.github.com/repos/scipy/scipy/issues/6806/comments"},"review_comments":{"href":"https://api.github.com/repos/scipy/scipy/pulls/6806/comments"},"review_comment":{"href":"https://api.github.com/repos/scipy/scipy/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/scipy/scipy/pulls/6806/commits"},"statuses":{"href":"https://api.github.com/repos/scipy/scipy/statuses/84cf73aa30ec98e6d2c6a96da394b5f41267117e"}}}}
{"actor":{"display_login":"nmayorov"}}