{"action":"created","issue":{"url":"https://api.github.com/repos/spotify/luigi/issues/1296","labels_url":"https://api.github.com/repos/spotify/luigi/issues/1296/labels{/name}","comments_url":"https://api.github.com/repos/spotify/luigi/issues/1296/comments","events_url":"https://api.github.com/repos/spotify/luigi/issues/1296/events","html_url":"https://github.com/spotify/luigi/pull/1296","id":110525173,"number":1296,"title":"Makes computeDepth take linear time","user":{"login":"daveFNbuck","id":2091885,"avatar_url":"https://avatars.githubusercontent.com/u/2091885?v=3","gravatar_id":"","url":"https://api.github.com/users/daveFNbuck","html_url":"https://github.com/daveFNbuck","followers_url":"https://api.github.com/users/daveFNbuck/followers","following_url":"https://api.github.com/users/daveFNbuck/following{/other_user}","gists_url":"https://api.github.com/users/daveFNbuck/gists{/gist_id}","starred_url":"https://api.github.com/users/daveFNbuck/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/daveFNbuck/subscriptions","organizations_url":"https://api.github.com/users/daveFNbuck/orgs","repos_url":"https://api.github.com/users/daveFNbuck/repos","events_url":"https://api.github.com/users/daveFNbuck/events{/privacy}","received_events_url":"https://api.github.com/users/daveFNbuck/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":3,"created_at":"2015-10-08T19:29:46Z","updated_at":"2015-10-08T20:20:22Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/spotify/luigi/pulls/1296","html_url":"https://github.com/spotify/luigi/pull/1296","diff_url":"https://github.com/spotify/luigi/pull/1296.diff","patch_url":"https://github.com/spotify/luigi/pull/1296.patch"},"body":"computeDepth takes quadratic time because it needs to find the maximum depth of\r\neach node and this can require repeated traversal as longer paths are found. In\r\norder to compute this in linear time, we instead compute the height of each node\r\nand then subtract this from the height of the root node. Heights can be computed\r\nin linear time by a straightforward recursive algorithm with memoization.\r\n\r\nUsing a test example with a 400-task dependency chain with each task in the\r\nchain depending on a task with 10000 dependencies the time necessary for\r\ncomputeDepth on my laptop was reduced from about 5 seconds to about 13ms. This\r\nis in line with the expected 400x speedup from removing quadratic behavior."},"comment":{"url":"https://api.github.com/repos/spotify/luigi/issues/comments/146674775","html_url":"https://github.com/spotify/luigi/pull/1296#issuecomment-146674775","issue_url":"https://api.github.com/repos/spotify/luigi/issues/1296","id":146674775,"user":{"login":"erikbern","id":1027979,"avatar_url":"https://avatars.githubusercontent.com/u/1027979?v=3","gravatar_id":"","url":"https://api.github.com/users/erikbern","html_url":"https://github.com/erikbern","followers_url":"https://api.github.com/users/erikbern/followers","following_url":"https://api.github.com/users/erikbern/following{/other_user}","gists_url":"https://api.github.com/users/erikbern/gists{/gist_id}","starred_url":"https://api.github.com/users/erikbern/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/erikbern/subscriptions","organizations_url":"https://api.github.com/users/erikbern/orgs","repos_url":"https://api.github.com/users/erikbern/repos","events_url":"https://api.github.com/users/erikbern/events{/privacy}","received_events_url":"https://api.github.com/users/erikbern/received_events","type":"User","site_admin":false},"created_at":"2015-10-08T20:20:22Z","updated_at":"2015-10-08T20:20:22Z","body":"awesome!"}}