{"action":"created","issue":{"url":"https://api.github.com/repos/numpy/numpy/issues/5594","labels_url":"https://api.github.com/repos/numpy/numpy/issues/5594/labels{/name}","comments_url":"https://api.github.com/repos/numpy/numpy/issues/5594/comments","events_url":"https://api.github.com/repos/numpy/numpy/issues/5594/events","html_url":"https://github.com/numpy/numpy/pull/5594","id":58539015,"number":5594,"title":"interp(): add storage of previous value for next index lookup","user":{"login":"newville","id":304251,"avatar_url":"https://avatars.githubusercontent.com/u/304251?v=3","gravatar_id":"","url":"https://api.github.com/users/newville","html_url":"https://github.com/newville","followers_url":"https://api.github.com/users/newville/followers","following_url":"https://api.github.com/users/newville/following{/other_user}","gists_url":"https://api.github.com/users/newville/gists{/gist_id}","starred_url":"https://api.github.com/users/newville/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/newville/subscriptions","organizations_url":"https://api.github.com/users/newville/orgs","repos_url":"https://api.github.com/users/newville/repos","events_url":"https://api.github.com/users/newville/events{/privacy}","received_events_url":"https://api.github.com/users/newville/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/numpy/numpy/labels/component:%20numpy.core","name":"component: numpy.core","color":"ff0000"},{"url":"https://api.github.com/repos/numpy/numpy/labels/Maintenance","name":"Maintenance","color":"02e10c"}],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":18,"created_at":"2015-02-23T03:36:13Z","updated_at":"2015-03-09T14:40:22Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/numpy/numpy/pulls/5594","html_url":"https://github.com/numpy/numpy/pull/5594","diff_url":"https://github.com/numpy/numpy/pull/5594.diff","patch_url":"https://github.com/numpy/numpy/pull/5594.patch"},"body":"This PR addresses #5593  by changing `binary_search()` to `binary_search_with_guess()` with an added `guess` parameter that is used as a first guess (including +/- 1 indices)  as the correct index.   The calls `binary_search_with_guess()` in `arr_interp()` store the index found for the array element i as the guess for element i+1.\r\n\r\nFor very many cases, this guess will be close enough (+/-1) to completely avoid the binary search of the array.   Though binary search is fast, using the previous index and testing values in its immediate vicinity (and likely to still be in active memory)  can give a substantial speedup in many common cases, and nearly no penalty in pathologically cases (say, randomly ordered values of `x`).\r\n\r\nIn a test case using scikits-image's iradon transform, linear interpolation of ~85M well- (but not perfectly-) ordered values was sped up by more than a factor of 3 with this change.\r\n"},"comment":{"url":"https://api.github.com/repos/numpy/numpy/issues/comments/77865298","html_url":"https://github.com/numpy/numpy/pull/5594#issuecomment-77865298","issue_url":"https://api.github.com/repos/numpy/numpy/issues/5594","id":77865298,"user":{"login":"charris","id":77272,"avatar_url":"https://avatars.githubusercontent.com/u/77272?v=3","gravatar_id":"","url":"https://api.github.com/users/charris","html_url":"https://github.com/charris","followers_url":"https://api.github.com/users/charris/followers","following_url":"https://api.github.com/users/charris/following{/other_user}","gists_url":"https://api.github.com/users/charris/gists{/gist_id}","starred_url":"https://api.github.com/users/charris/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/charris/subscriptions","organizations_url":"https://api.github.com/users/charris/orgs","repos_url":"https://api.github.com/users/charris/repos","events_url":"https://api.github.com/users/charris/events{/privacy}","received_events_url":"https://api.github.com/users/charris/received_events","type":"User","site_admin":false},"created_at":"2015-03-09T14:40:22Z","updated_at":"2015-03-09T14:40:22Z","body":"What is bothering me about this is the number of checks that are made, together with a fair amount of index arithmetic. For searches into a big array, that probably doesn't matter, but for smaller searches it might make a difference. I wonder if it might not be faster to just check a smaller range, or do the method that starts with a guess and increments by an offset in the right direction, the offset doubling on each falure, and do that maybe two, three times before falling back on binary search.\r\n\r\nSome timing numbers would be useful here.  "}}