{"action":"created","issue":{"url":"https://api.github.com/repos/praw-dev/praw/issues/514","labels_url":"https://api.github.com/repos/praw-dev/praw/issues/514/labels{/name}","comments_url":"https://api.github.com/repos/praw-dev/praw/issues/514/comments","events_url":"https://api.github.com/repos/praw-dev/praw/issues/514/events","html_url":"https://github.com/praw-dev/praw/pull/514","id":103899353,"number":514,"title":"Use deque instead of list","user":{"login":"eugene-eeo","id":3669236,"avatar_url":"https://avatars.githubusercontent.com/u/3669236?v=3","gravatar_id":"","url":"https://api.github.com/users/eugene-eeo","html_url":"https://github.com/eugene-eeo","followers_url":"https://api.github.com/users/eugene-eeo/followers","following_url":"https://api.github.com/users/eugene-eeo/following{/other_user}","gists_url":"https://api.github.com/users/eugene-eeo/gists{/gist_id}","starred_url":"https://api.github.com/users/eugene-eeo/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/eugene-eeo/subscriptions","organizations_url":"https://api.github.com/users/eugene-eeo/orgs","repos_url":"https://api.github.com/users/eugene-eeo/repos","events_url":"https://api.github.com/users/eugene-eeo/events{/privacy}","received_events_url":"https://api.github.com/users/eugene-eeo/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":1,"created_at":"2015-08-30T03:42:50Z","updated_at":"2015-08-30T05:29:13Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/praw-dev/praw/pulls/514","html_url":"https://github.com/praw-dev/praw/pull/514","diff_url":"https://github.com/praw-dev/praw/pull/514.diff","patch_url":"https://github.com/praw-dev/praw/pull/514.patch"},"body":"Reason being that [deques](https://docs.python.org/2/library/collections.html#collections.deque) offer O(1) insert on *both* ends of the stack instead of just the end. Previously, using a list and appending to the 'head' is an O(n) operation.\r\n\r\nA simple demonstration/benchmark: https://gist.github.com/eugene-eeo/549b5b5c5b72a882bc02"},"comment":{"url":"https://api.github.com/repos/praw-dev/praw/issues/comments/136086608","html_url":"https://github.com/praw-dev/praw/pull/514#issuecomment-136086608","issue_url":"https://api.github.com/repos/praw-dev/praw/issues/514","id":136086608,"user":{"login":"bboe","id":48100,"avatar_url":"https://avatars.githubusercontent.com/u/48100?v=3","gravatar_id":"","url":"https://api.github.com/users/bboe","html_url":"https://github.com/bboe","followers_url":"https://api.github.com/users/bboe/followers","following_url":"https://api.github.com/users/bboe/following{/other_user}","gists_url":"https://api.github.com/users/bboe/gists{/gist_id}","starred_url":"https://api.github.com/users/bboe/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/bboe/subscriptions","organizations_url":"https://api.github.com/users/bboe/orgs","repos_url":"https://api.github.com/users/bboe/repos","events_url":"https://api.github.com/users/bboe/events{/privacy}","received_events_url":"https://api.github.com/users/bboe/received_events","type":"User","site_admin":false},"created_at":"2015-08-30T05:29:13Z","updated_at":"2015-08-30T05:29:13Z","body":"Thanks for the PR! Your gist doesn't exactly provide the comparison I was hoping for but this does:\r\n\r\n```python\r\nfrom timeit import timeit\r\ntimes = 100000\r\nprint(timeit('x.insert(0, 1)', setup='x = []', number = 100000))\r\nprint(timeit('x.appendleft(1)', number=times,\r\n             setup='from collections import deque; x = deque()'))\r\n```\r\n\r\n    1.92158889771\r\n    0.00701308250427\r\n\r\nI admit I'm shocked. I would have assumed as with many list implementations that adding to either end would be O(1). It looks like the deque is precisely the data structure I was thinking of. Thanks!"}}