### 1. [clickbait] Slowest Python program?

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

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

"""

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

"""

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

### 2. Re: [clickbait] Slowest Python program?

Why is Python so slow?! Yikes!

### 3. Re: [clickbait] Slowest Python program?

euphoric said...

Why is Python so slow?! Yikes!

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
```