OpenEuphoria

Re: [clickbait] Slowest Python program?

• Posted by petelomax Jun 04, 2020
• 1084 views

The python code is recursively taking smaller and smaller slices, which is a fair bit of copying, whereas the phix routine iteratively reduces hi/lo indexes, no copying.

If would probably be fairer to compare against a couple of entries from https://rosettacode.org/wiki/Binary_search#Python :

Closest match to the Phix code

def binary_search(l, value): 
    low = 0 
    high = len(l)-1 
    while low <= high:  
        mid = (low+high)//2 
        if l[mid] > value: high = mid-1 
        elif l[mid] < value: low = mid+1 
        else: return mid 
    return -1 

Using Python builtin methods:

from bisect import bisect_left 
  
def binary_search(a, x, lo=0, hi=None):   # can't use a to specify default for hi 
    hi = hi if hi is not None else len(a) # hi defaults to len(a)    
    pos = bisect_left(a,x,lo,hi)          # find insertion position 
    return (pos if pos != hi and a[pos] == x else -1) # don't walk off the end