GitHub PushEvent at 2014-04-02 22:10:13
Repository: scipy
Actor: jaimefrio
Payload: {"shas":[["11bd10ed3eedb651d5d837ec55cf060c7bb7c1d2","7e3732bce533ff576018c16050ab6f7cda886861@gmail.com","ENH: speed-up ndimage.filters.min(max)imum_filter1d\n\nThe current implementation of min(max)imum_filter1d rescans the full filter\nwindow at every step, leading to an O(n*m) complexity, n being the size of\nthe image, and m of the filter.\nThis PR changes the computation algorithm, keeping track of the min(max)imum\nvalue, and its offset from the current position. This allows to compute the\nmin(max)imum by making a single compare of the next value in the image against\nthe min(max)imum, and checking that the min(max)imum is still within the filter\nwindow. This leads to an expected O(n) average performance, although the worst\ncase is still O(n*m).\n\nThe worst case happens for strictly inc(dec)reasing sequences of values, and in\nthis case the performance is actually worse than the original, because of the\noverhead of computing the min(max)imum offset.","jaimefrio",true],["bea2fd699bb35b25caa75d20c6ebbdeb5426eee4","22b9243c7c9f4b8e52e010f54a3e83553dd68030@users.noreply.github.com","Merge pull request #3517 from jaimefrio/minmax-filter\n\nENH: speed-up ndimage.filters.min(max)imum_filter1d","argriffing",true]],"size":2,"ref":"refs/heads/master","head":"bea2fd699bb35b25caa75d20c6ebbdeb5426eee4"}