1. [clickbait] Slowest Python program?

• Posted by _tom (admin) Jun 04, 2020
• 1309 views

The challenge is to find the slowest Python program. This is the largest difference between Phix and Python I have discovered so far.

---

A feature of Python is that it is slow. They say "you can always buy a faster computer." But, Python is productive.

---

The Puzzle from "Think Python"

Two words "interlock" if taking alternating letters from each forms a new word. For example, "shoe" and "cold" interlock to form "schooled".

Credit: This exercise is inspired by an example at http://puzzlers.org.

• Write a program that finds all pairs of words that interlock. Hint: don't enumerate all pairs!

Python solution

• Download the wordlist:

https://www.gutenberg.org/files/3201/3201.txt

renamed to "words.txt"

• The Python include file: inlist.py

"""This module contains a code example related to 

 
Think Python, 2nd Edition 
by Allen Downey 
http://thinkpython2.com 
 
Copyright 2015 Allen Downey 
 
License: http://creativecommons.org/licenses/by/4.0/ 
""" 

 
from __future__ import print_function, division 
 
import bisect 
 
 
def make_word_list(): 
    """Reads lines from a file and builds a list using append. 

 
    returns: list of strings 
    """ 

    word_list = [] 
    fin = open('words.txt') 
    for line in fin: 
        word = line.strip() 
        word_list.append(word) 
    return word_list 
 
 
def in_bisect(word_list, word): 
    """Checks whether a word is in a list using bisection search. 

 
    Precondition: the words in the list are sorted 
 
    word_list: list of strings 
    word: string 
 
    returns: True if the word is in the list; False otherwise 
    """ 

    if len(word_list) == 0: 
        return False 
 
    i = len(word_list) // 2 
    if word_list[i] == word: 
        return True 
 
    if word_list[i] > word: 
        # search the first half 
        return in_bisect(word_list[:i], word) 
    else: 
        # search the second half 
        return in_bisect(word_list[i+1:], word) 
 
 
def in_bisect_cheat(word_list, word): 
    """Checks whether a word is in a list using bisection search. 

 
    Precondition: the words in the list are sorted 
 
    word_list: list of strings 
    word: string 
    """ 

    i = bisect.bisect_left(word_list, word) 
    if i == len(word_list): 
        return False 
 
    return word_list[i] == word 
 
 
if __name__ == '__main__': 
    word_list = make_word_list() 
 
    for word in ['aa', 'alien', 'allen', 'zymurgy']: 
        print(word, 'in list', in_bisect(word_list, word)) 
 
    for word in ['aa', 'alien', 'allen', 'zymurgy']: 
        print(word, 'in list', in_bisect_cheat(word_list, word)) 

• The Python main file: interlock_python.py

"""This module contains a code example related to 

 
Think Python, 2nd Edition 
by Allen Downey 
http://thinkpython2.com 
 
Copyright 2015 Allen Downey 
 
License: http://creativecommons.org/licenses/by/4.0/ 
""" 

 
from __future__ import print_function, division 
 
from inlist import make_word_list, in_bisect 
 
 
def interlock(word_list, word): 
    """Checks whether a word contains two interleaved words. 

 
    word_list: list of strings 
    word: string 
    """ 

    evens = word[::2] 
    odds = word[1::2] 
    return in_bisect(word_list, evens) and in_bisect(word_list, odds) 
 
if __name__ == '__main__': 
    word_list = make_word_list() 
 
    for word in word_list: 
        if interlock(word_list, word): 
            print(word, word[::2], word[1::2]) 

The Phix Solution

• Use the same wordlist as for Python

• The Phix file: interlock_phix.exw

-- download the wordlist 
-- https://www.gutenberg.org/files/3201/3201.txt 
-- renamed to "words.txt" 
 
 
atom fn = open( "words.txt", "r" ) 
sequence words = get_text(fn, 1 ) 
 
procedure interlock( string w ) 
    sequence wo = "", we = ""               -- odd start, even start 
 
    for i=1 to length(w) by 2 do            -- interleave by two 
        wo = append(wo, w[i] ) 
    end for 
 
    for i=2 to length(w) by 2 do 
        we = append(we, w[i] ) 
    end for 
 
 
    if binary_search( wo, words ) > 0           -- lookup the words 
    and binary_search( we, words ) > 0 then 
        printf(1, "%s %s %s\n", {w, wo, we } ) 
    end if 
end procedure 
 
---------------------- 
 
for i=1 to length(words) do 
    interlock( words[i] ) 
end for 

Benchmark Results

atom t 
t = time() 
{} = system_exec( "python3 interlock_python.py" ) 
? time() - t 

atom t 
t = time() 
{} = system_exec( "p64 interlock_phix.exw" ) 
? time() - t 

Linux Mint 64bit. Fewer seconds is better.

	i5	i0
Python	156	1_270
Phix	0.5	1.7

be well
_tom

3. Re: [clickbait] Slowest Python program?

• Posted by petelomax Jun 04, 2020
• 1266 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