{"action":"closed","number":261,"pull_request":{"url":"https://api.github.com/repos/stefankroes/ancestry/pulls/261","id":58509671,"html_url":"https://github.com/stefankroes/ancestry/pull/261","diff_url":"https://github.com/stefankroes/ancestry/pull/261.diff","patch_url":"https://github.com/stefankroes/ancestry/pull/261.patch","issue_url":"https://api.github.com/repos/stefankroes/ancestry/issues/261","number":261,"state":"closed","locked":false,"title":"Improve performance of arrange_nodes.","user":{"login":"Fryguy","id":52120,"avatar_url":"https://avatars.githubusercontent.com/u/52120?v=3","gravatar_id":"","url":"https://api.github.com/users/Fryguy","html_url":"https://github.com/Fryguy","followers_url":"https://api.github.com/users/Fryguy/followers","following_url":"https://api.github.com/users/Fryguy/following{/other_user}","gists_url":"https://api.github.com/users/Fryguy/gists{/gist_id}","starred_url":"https://api.github.com/users/Fryguy/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Fryguy/subscriptions","organizations_url":"https://api.github.com/users/Fryguy/orgs","repos_url":"https://api.github.com/users/Fryguy/repos","events_url":"https://api.github.com/users/Fryguy/events{/privacy}","received_events_url":"https://api.github.com/users/Fryguy/received_events","type":"User","site_admin":false},"body":"The old code is essentially an insertion algorithm that walks the tree\r\nfrom the root for each node and inserts itself in the right spot.\r\nInserting a node is roughly O(depth); best case O(1), but worst case\r\nO(n).  Thus, the tree building is roughly O(n * depth); best case O(n),\r\nbut worst case O(n^2).\r\n\r\nThe new code maintains an index of a node's children by node id.  Each\r\nnodes is placed into the children of the parent id. Thus, inserting a\r\nnode is an O(1) lookup, making the tree building O(n).\r\n\r\nThe operation only has to look at the parent, and does not have to go\r\nthrough all of the ancestry ids, because eventually the parent node\r\nwill go through the same insertion process itself.\r\n\r\nNote that the old algorithm used a pre-sorting of nodes in order to\r\nmore efficiently arrange them.  The new algorithm doesn't care about\r\norder, and thus that sorting can probably be removed in future PRs.","created_at":"2016-02-06T03:06:24Z","updated_at":"2016-02-09T13:37:53Z","closed_at":"2016-02-09T13:37:53Z","merged_at":"2016-02-09T13:37:53Z","merge_commit_sha":"956af3206781755ab8d8559571131246d8615121","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/stefankroes/ancestry/pulls/261/commits","review_comments_url":"https://api.github.com/repos/stefankroes/ancestry/pulls/261/comments","review_comment_url":"https://api.github.com/repos/stefankroes/ancestry/pulls/comments{/number}","comments_url":"https://api.github.com/repos/stefankroes/ancestry/issues/261/comments","statuses_url":"https://api.github.com/repos/stefankroes/ancestry/statuses/8a4fb0083db246ca8e3462db148bba202b5c8b4c","head":{"label":"Fryguy:better_arrange_nodes","ref":"better_arrange_nodes","sha":"8a4fb0083db246ca8e3462db148bba202b5c8b4c","user":{"login":"Fryguy","id":52120,"avatar_url":"https://avatars.githubusercontent.com/u/52120?v=3","gravatar_id":"","url":"https://api.github.com/users/Fryguy","html_url":"https://github.com/Fryguy","followers_url":"https://api.github.com/users/Fryguy/followers","following_url":"https://api.github.com/users/Fryguy/following{/other_user}","gists_url":"https://api.github.com/users/Fryguy/gists{/gist_id}","starred_url":"https://api.github.com/users/Fryguy/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Fryguy/subscriptions","organizations_url":"https://api.github.com/users/Fryguy/orgs","repos_url":"https://api.github.com/users/Fryguy/repos","events_url":"https://api.github.com/users/Fryguy/events{/privacy}","received_events_url":"https://api.github.com/users/Fryguy/received_events","type":"User","site_admin":false},"repo":{"id":749404,"name":"ancestry","full_name":"Fryguy/ancestry","owner":{"login":"Fryguy","id":52120,"avatar_url":"https://avatars.githubusercontent.com/u/52120?v=3","gravatar_id":"","url":"https://api.github.com/users/Fryguy","html_url":"https://github.com/Fryguy","followers_url":"https://api.github.com/users/Fryguy/followers","following_url":"https://api.github.com/users/Fryguy/following{/other_user}","gists_url":"https://api.github.com/users/Fryguy/gists{/gist_id}","starred_url":"https://api.github.com/users/Fryguy/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Fryguy/subscriptions","organizations_url":"https://api.github.com/users/Fryguy/orgs","repos_url":"https://api.github.com/users/Fryguy/repos","events_url":"https://api.github.com/users/Fryguy/events{/privacy}","received_events_url":"https://api.github.com/users/Fryguy/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/Fryguy/ancestry","description":"Organise ActiveRecord model into a tree structure","fork":true,"url":"https://api.github.com/repos/Fryguy/ancestry","forks_url":"https://api.github.com/repos/Fryguy/ancestry/forks","keys_url":"https://api.github.com/repos/Fryguy/ancestry/keys{/key_id}","collaborators_url":"https://api.github.com/repos/Fryguy/ancestry/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/Fryguy/ancestry/teams","hooks_url":"https://api.github.com/repos/Fryguy/ancestry/hooks","issue_events_url":"https://api.github.com/repos/Fryguy/ancestry/issues/events{/number}","events_url":"https://api.github.com/repos/Fryguy/ancestry/events","assignees_url":"https://api.github.com/repos/Fryguy/ancestry/assignees{/user}","branches_url":"https://api.github.com/repos/Fryguy/ancestry/branches{/branch}","tags_url":"https://api.github.com/repos/Fryguy/ancestry/tags","blobs_url":"https://api.github.com/repos/Fryguy/ancestry/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/Fryguy/ancestry/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/Fryguy/ancestry/git/refs{/sha}","trees_url":"https://api.github.com/repos/Fryguy/ancestry/git/trees{/sha}","statuses_url":"https://api.github.com/repos/Fryguy/ancestry/statuses/{sha}","languages_url":"https://api.github.com/repos/Fryguy/ancestry/languages","stargazers_url":"https://api.github.com/repos/Fryguy/ancestry/stargazers","contributors_url":"https://api.github.com/repos/Fryguy/ancestry/contributors","subscribers_url":"https://api.github.com/repos/Fryguy/ancestry/subscribers","subscription_url":"https://api.github.com/repos/Fryguy/ancestry/subscription","commits_url":"https://api.github.com/repos/Fryguy/ancestry/commits{/sha}","git_commits_url":"https://api.github.com/repos/Fryguy/ancestry/git/commits{/sha}","comments_url":"https://api.github.com/repos/Fryguy/ancestry/comments{/number}","issue_comment_url":"https://api.github.com/repos/Fryguy/ancestry/issues/comments{/number}","contents_url":"https://api.github.com/repos/Fryguy/ancestry/contents/{+path}","compare_url":"https://api.github.com/repos/Fryguy/ancestry/compare/{base}...{head}","merges_url":"https://api.github.com/repos/Fryguy/ancestry/merges","archive_url":"https://api.github.com/repos/Fryguy/ancestry/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/Fryguy/ancestry/downloads","issues_url":"https://api.github.com/repos/Fryguy/ancestry/issues{/number}","pulls_url":"https://api.github.com/repos/Fryguy/ancestry/pulls{/number}","milestones_url":"https://api.github.com/repos/Fryguy/ancestry/milestones{/number}","notifications_url":"https://api.github.com/repos/Fryguy/ancestry/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/Fryguy/ancestry/labels{/name}","releases_url":"https://api.github.com/repos/Fryguy/ancestry/releases{/id}","deployments_url":"https://api.github.com/repos/Fryguy/ancestry/deployments","created_at":"2010-06-30T16:24:11Z","updated_at":"2014-07-23T21:52:39Z","pushed_at":"2016-02-09T05:00:14Z","git_url":"git://github.com/Fryguy/ancestry.git","ssh_url":"git@github.com:Fryguy/ancestry.git","clone_url":"https://github.com/Fryguy/ancestry.git","svn_url":"https://github.com/Fryguy/ancestry","homepage":"","size":8684,"stargazers_count":0,"watchers_count":0,"language":"Ruby","has_issues":false,"has_downloads":false,"has_wiki":true,"has_pages":false,"forks_count":1,"mirror_url":null,"open_issues_count":0,"forks":1,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"stefankroes:master","ref":"master","sha":"2cfab656578ba8041ffc0acf663890a3811aad10","user":{"login":"stefankroes","id":37841,"avatar_url":"https://avatars.githubusercontent.com/u/37841?v=3","gravatar_id":"","url":"https://api.github.com/users/stefankroes","html_url":"https://github.com/stefankroes","followers_url":"https://api.github.com/users/stefankroes/followers","following_url":"https://api.github.com/users/stefankroes/following{/other_user}","gists_url":"https://api.github.com/users/stefankroes/gists{/gist_id}","starred_url":"https://api.github.com/users/stefankroes/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/stefankroes/subscriptions","organizations_url":"https://api.github.com/users/stefankroes/orgs","repos_url":"https://api.github.com/users/stefankroes/repos","events_url":"https://api.github.com/users/stefankroes/events{/privacy}","received_events_url":"https://api.github.com/users/stefankroes/received_events","type":"User","site_admin":false},"repo":{"id":339567,"name":"ancestry","full_name":"stefankroes/ancestry","owner":{"login":"stefankroes","id":37841,"avatar_url":"https://avatars.githubusercontent.com/u/37841?v=3","gravatar_id":"","url":"https://api.github.com/users/stefankroes","html_url":"https://github.com/stefankroes","followers_url":"https://api.github.com/users/stefankroes/followers","following_url":"https://api.github.com/users/stefankroes/following{/other_user}","gists_url":"https://api.github.com/users/stefankroes/gists{/gist_id}","starred_url":"https://api.github.com/users/stefankroes/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/stefankroes/subscriptions","organizations_url":"https://api.github.com/users/stefankroes/orgs","repos_url":"https://api.github.com/users/stefankroes/repos","events_url":"https://api.github.com/users/stefankroes/events{/privacy}","received_events_url":"https://api.github.com/users/stefankroes/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/stefankroes/ancestry","description":"Organise ActiveRecord model into a tree structure","fork":false,"url":"https://api.github.com/repos/stefankroes/ancestry","forks_url":"https://api.github.com/repos/stefankroes/ancestry/forks","keys_url":"https://api.github.com/repos/stefankroes/ancestry/keys{/key_id}","collaborators_url":"https://api.github.com/repos/stefankroes/ancestry/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/stefankroes/ancestry/teams","hooks_url":"https://api.github.com/repos/stefankroes/ancestry/hooks","issue_events_url":"https://api.github.com/repos/stefankroes/ancestry/issues/events{/number}","events_url":"https://api.github.com/repos/stefankroes/ancestry/events","assignees_url":"https://api.github.com/repos/stefankroes/ancestry/assignees{/user}","branches_url":"https://api.github.com/repos/stefankroes/ancestry/branches{/branch}","tags_url":"https://api.github.com/repos/stefankroes/ancestry/tags","blobs_url":"https://api.github.com/repos/stefankroes/ancestry/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/stefankroes/ancestry/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/stefankroes/ancestry/git/refs{/sha}","trees_url":"https://api.github.com/repos/stefankroes/ancestry/git/trees{/sha}","statuses_url":"https://api.github.com/repos/stefankroes/ancestry/statuses/{sha}","languages_url":"https://api.github.com/repos/stefankroes/ancestry/languages","stargazers_url":"https://api.github.com/repos/stefankroes/ancestry/stargazers","contributors_url":"https://api.github.com/repos/stefankroes/ancestry/contributors","subscribers_url":"https://api.github.com/repos/stefankroes/ancestry/subscribers","subscription_url":"https://api.github.com/repos/stefankroes/ancestry/subscription","commits_url":"https://api.github.com/repos/stefankroes/ancestry/commits{/sha}","git_commits_url":"https://api.github.com/repos/stefankroes/ancestry/git/commits{/sha}","comments_url":"https://api.github.com/repos/stefankroes/ancestry/comments{/number}","issue_comment_url":"https://api.github.com/repos/stefankroes/ancestry/issues/comments{/number}","contents_url":"https://api.github.com/repos/stefankroes/ancestry/contents/{+path}","compare_url":"https://api.github.com/repos/stefankroes/ancestry/compare/{base}...{head}","merges_url":"https://api.github.com/repos/stefankroes/ancestry/merges","archive_url":"https://api.github.com/repos/stefankroes/ancestry/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/stefankroes/ancestry/downloads","issues_url":"https://api.github.com/repos/stefankroes/ancestry/issues{/number}","pulls_url":"https://api.github.com/repos/stefankroes/ancestry/pulls{/number}","milestones_url":"https://api.github.com/repos/stefankroes/ancestry/milestones{/number}","notifications_url":"https://api.github.com/repos/stefankroes/ancestry/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/stefankroes/ancestry/labels{/name}","releases_url":"https://api.github.com/repos/stefankroes/ancestry/releases{/id}","deployments_url":"https://api.github.com/repos/stefankroes/ancestry/deployments","created_at":"2009-10-16T13:37:09Z","updated_at":"2016-02-09T02:03:12Z","pushed_at":"2016-02-09T13:37:53Z","git_url":"git://github.com/stefankroes/ancestry.git","ssh_url":"git@github.com:stefankroes/ancestry.git","clone_url":"https://github.com/stefankroes/ancestry.git","svn_url":"https://github.com/stefankroes/ancestry","homepage":"","size":8846,"stargazers_count":2072,"watchers_count":2072,"language":"Ruby","has_issues":true,"has_downloads":false,"has_wiki":true,"has_pages":true,"forks_count":292,"mirror_url":null,"open_issues_count":89,"forks":292,"open_issues":89,"watchers":2072,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/stefankroes/ancestry/pulls/261"},"html":{"href":"https://github.com/stefankroes/ancestry/pull/261"},"issue":{"href":"https://api.github.com/repos/stefankroes/ancestry/issues/261"},"comments":{"href":"https://api.github.com/repos/stefankroes/ancestry/issues/261/comments"},"review_comments":{"href":"https://api.github.com/repos/stefankroes/ancestry/pulls/261/comments"},"review_comment":{"href":"https://api.github.com/repos/stefankroes/ancestry/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/stefankroes/ancestry/pulls/261/commits"},"statuses":{"href":"https://api.github.com/repos/stefankroes/ancestry/statuses/8a4fb0083db246ca8e3462db148bba202b5c8b4c"}},"merged":true,"mergeable":null,"mergeable_state":"unknown","merged_by":{"login":"kbrock","id":1930,"avatar_url":"https://avatars.githubusercontent.com/u/1930?v=3","gravatar_id":"","url":"https://api.github.com/users/kbrock","html_url":"https://github.com/kbrock","followers_url":"https://api.github.com/users/kbrock/followers","following_url":"https://api.github.com/users/kbrock/following{/other_user}","gists_url":"https://api.github.com/users/kbrock/gists{/gist_id}","starred_url":"https://api.github.com/users/kbrock/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/kbrock/subscriptions","organizations_url":"https://api.github.com/users/kbrock/orgs","repos_url":"https://api.github.com/users/kbrock/repos","events_url":"https://api.github.com/users/kbrock/events{/privacy}","received_events_url":"https://api.github.com/users/kbrock/received_events","type":"User","site_admin":false},"comments":6,"review_comments":0,"commits":1,"additions":137,"deletions":23,"changed_files":2}}