{"action":"created","issue":{"url":"https://api.github.com/repos/numpy/numpy/issues/6100","labels_url":"https://api.github.com/repos/numpy/numpy/issues/6100/labels{/name}","comments_url":"https://api.github.com/repos/numpy/numpy/issues/6100/comments","events_url":"https://api.github.com/repos/numpy/numpy/issues/6100/events","html_url":"https://github.com/numpy/numpy/pull/6100","id":96369147,"number":6100,"title":"ENH: Faster algorithm for computing histograms with equal-size bins","user":{"login":"astrofrog","id":314716,"avatar_url":"https://avatars.githubusercontent.com/u/314716?v=3","gravatar_id":"","url":"https://api.github.com/users/astrofrog","html_url":"https://github.com/astrofrog","followers_url":"https://api.github.com/users/astrofrog/followers","following_url":"https://api.github.com/users/astrofrog/following{/other_user}","gists_url":"https://api.github.com/users/astrofrog/gists{/gist_id}","starred_url":"https://api.github.com/users/astrofrog/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/astrofrog/subscriptions","organizations_url":"https://api.github.com/users/astrofrog/orgs","repos_url":"https://api.github.com/users/astrofrog/repos","events_url":"https://api.github.com/users/astrofrog/events{/privacy}","received_events_url":"https://api.github.com/users/astrofrog/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":11,"created_at":"2015-07-21T17:12:49Z","updated_at":"2015-07-22T15:31:26Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/numpy/numpy/pulls/6100","html_url":"https://github.com/numpy/numpy/pull/6100","diff_url":"https://github.com/numpy/numpy/pull/6100.diff","patch_url":"https://github.com/numpy/numpy/pull/6100.patch"},"body":"### About\r\n\r\nWhen bins are equal-sized, we don't have use ``searchsorted`` to find which bins values fall in, we can instead just scale and convert the values to the bin indices and use ``bincount``.\r\n\r\n### Results\r\n\r\nI carried out speed tests with arrays going from 1 to 10^8 elements. The values were randomly sampled with:\r\n\r\n```python\r\nx = np.random.uniform(-10., 100., N)\r\n```\r\n\r\nand the histogram was computed with:\r\n\r\n```python\r\nhist, edges = np.histogram(x, bins=45, range=[-5, 99.])\r\n```\r\n\r\nThe speed difference is as follows:\r\n\r\n![comparison](https://cloud.githubusercontent.com/assets/314716/8807304/caf3d498-2fdb-11e5-9484-2ece925e29dc.png)\r\n\r\nThe new method is always faster, and for more than 10^5 elements, the speedup is a factor of ~10x.\r\n\r\nI then checked that the memory usage is not increased, when binning an array with 10^9 values:\r\n\r\n![memory](https://cloud.githubusercontent.com/assets/314716/8807318/f307d420-2fdb-11e5-8942-a36c8104c3c6.png)\r\n\r\nThere is no memory penalty!\r\n\r\nNote that I originally implemented this without the iteration over blocks, and not only did it use more memory, it was 2x as slow as the version with looping over chunks (to my surprise).\r\n\r\n### Future work\r\n\r\nIf this PR is merged, we can also consider switching to using C or Cython for the part where the bin indices are computed. This could provide a further ~3x improvement in performance.\r\n\r\n### Notes\r\n\r\nThis partially addresses #6099 (np.histogram could be made even faster by switching to C in places)\r\n\r\nA similar speedup could be made for ``histogramdd``\r\n\r\nOf course, given how extensively this function is used, it would be great if people could subject to more rigorous testing (I will also do some more testing to see if I can find cases where there is a performance regression)"},"comment":{"url":"https://api.github.com/repos/numpy/numpy/issues/comments/123759447","html_url":"https://github.com/numpy/numpy/pull/6100#issuecomment-123759447","issue_url":"https://api.github.com/repos/numpy/numpy/issues/6100","id":123759447,"user":{"login":"jaimefrio","id":3343990,"avatar_url":"https://avatars.githubusercontent.com/u/3343990?v=3","gravatar_id":"","url":"https://api.github.com/users/jaimefrio","html_url":"https://github.com/jaimefrio","followers_url":"https://api.github.com/users/jaimefrio/followers","following_url":"https://api.github.com/users/jaimefrio/following{/other_user}","gists_url":"https://api.github.com/users/jaimefrio/gists{/gist_id}","starred_url":"https://api.github.com/users/jaimefrio/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jaimefrio/subscriptions","organizations_url":"https://api.github.com/users/jaimefrio/orgs","repos_url":"https://api.github.com/users/jaimefrio/repos","events_url":"https://api.github.com/users/jaimefrio/events{/privacy}","received_events_url":"https://api.github.com/users/jaimefrio/received_events","type":"User","site_admin":false},"created_at":"2015-07-22T15:31:26Z","updated_at":"2015-07-22T15:31:26Z","body":"I'll buy that 2x. Thanks for takinig the time to substantiate with measurements all my existential doubts,\r\n\r\nCorrect me if I am wrong, but it seems we both agree that, eventually, the right thing to do would be to rewrite at least this particular path in C, right?\r\n\r\nIf you could fix that int-that-should-be-an-intp, and get rid of some of the extraneous white space, I'll go ahead and merge it."}}