Author: Brian Kearns <bdkea...@gmail.com>
Branch:
Changeset: r73869:0e32a2a7d77c
Date: 2014-10-09 15:38 -0400
http://bitbucket.org/pypy/pypy/changeset/0e32a2a7d77c/
Log: optimize searchsorted for case of sorted keys
diff --git a/pypy/module/micronumpy/selection.py
b/pypy/module/micronumpy/selection.py
--- a/pypy/module/micronumpy/selection.py
+++ b/pypy/module/micronumpy/selection.py
@@ -359,24 +359,31 @@
app_searchsort = applevel(r"""
import operator
- def _searchsort(a, op, val):
- imin = 0
- imax = a.size
- while imin < imax:
- imid = imin + ((imax - imin) >> 1)
- if op(a[imid], val):
- imin = imid + 1
- else:
- imax = imid
- return imin
-
- def searchsort(a, v, side, result):
+ def searchsort(arr, val, side, res):
+ val = val.flat
+ res = res.flat
if side == 0:
op = operator.lt
else:
op = operator.le
- v = v.flat
- result = result.flat
- for i in xrange(len(v)):
- result[i] = _searchsort(a, op, v[i])
+
+ size = arr.size
+ imin = 0
+ imax = size
+ last = val[0]
+ for i in xrange(len(val)):
+ key = val[i]
+ if last < key:
+ imax = size
+ else:
+ imin = 0
+ imax = imax + 1 if imax < size else size
+ last = key
+ while imin < imax:
+ imid = imin + ((imax - imin) >> 1)
+ if op(arr[imid], key):
+ imin = imid + 1
+ else:
+ imax = imid
+ res[i] = imin
""", filename=__file__).interphook('searchsort')
_______________________________________________
pypy-commit mailing list
pypy-commit@python.org
https://mail.python.org/mailman/listinfo/pypy-commit
