Numeric List Closest Pairs (Python)

Comparing a number of different approaches to finding the closest pair of numeric elements in a list. The timing is done with the mpmath module, but you can also use Python module timeit.

Gribouillis commented: interesting test +13
snippsat commented: Thx for making a snippets with different approaches. +10
``````''' list_closest_pair3.py
find the closest pair of numeric elements in a list

various functions timed with module mpmath
mpmath-0.17.win32.exe
from

tested with Python27 and Python33  by  vegaseat  07dec2012
'''

import mpmath as mpm

def closest_pair1(mylist):
'''
return the closest pair of numeric elements in mylist
original by snippsat
'''
# make elements unique and sort
lst = sorted(set(mylist))
# shift second list by 1 to avoid matches
# list() needed for Python3
number_par = list(zip(lst, lst[1:]))
lowest_par_result = [abs(y-x) for x, y in number_par]
lowest_par_index = lowest_par_result.index(min(lowest_par_result))
return number_par[lowest_par_index]

def closest_pair2(mylist):
'''return the closest pair of numeric elements in mylist'''
# make a copy of mylist to avoid feedback
slist = mylist[:]
# put initial closest pair values far apart
cpair = (10000, 0)
for n in slist:
for y in slist:
# avoid matches and pick the smallest difference
if 0 < abs(n - y) < abs(cpair[0] - cpair[1]):
# update closest pair values
cpair = (n, y)
return cpair

def closest_pair3(mylist):
'''return the closest pair of numeric elements in mylist'''
# create only unique elements
myset = set(mylist)
# put initial closest pair values far apart
cpair = (10000, 0)
for n in myset:
for y in myset:
# avoid matches and pick the smallest difference
if 0 < abs(n - y) < abs(cpair[0] - cpair[1]):
# update closest pair values
cpair = (n, y)
return cpair

def closest_pair4(mylist):
'''return the closest pair of numeric elements in mylist'''
# make unique elements and sort
slist = sorted(set(mylist))
# put initial closest pair values far apart
cpair = (10000, 0)
for ix, n in enumerate(slist):
# avoid IndexError: list index out of range
if ix >= len(slist) - 1:
break
# next element
y = slist[ix+1]
# pick the smallest difference
if abs(n - y) < abs(cpair[0] - cpair[1]):
# update closest pair values
cpair = (n, y)
return cpair

def closest_pair5(q):
'''return the closest pair of numeric elements in list q'''
mt = min([(abs(x-y), x, y) for x in q for y in q if abs(x-y) > 0])
return (mt[1], mt[2])

mylist = [90, 5, 27, 63, 12, 47, 10, 150, 120, 48]
mylist2 = [90.1, 5.7, 27.3, 63, 11.5, 47.1, 10.7, 150, 120.2, 48.0]

# timing
print("closest_pair1(mylist) = %f seconds" % mpm.timing(closest_pair1, mylist))
print("closest_pair2(mylist) = %f seconds" % mpm.timing(closest_pair2, mylist))
print("closest_pair3(mylist) = %f seconds" % mpm.timing(closest_pair3, mylist))
print("closest_pair4(mylist) = %f seconds" % mpm.timing(closest_pair4, mylist))
print("closest_pair5(mylist) = %f seconds" % mpm.timing(closest_pair5, mylist))

''' my result (Python273) ...
closest_pair1(mylist) = 0.000005 seconds
closest_pair2(mylist) = 0.000025 seconds
closest_pair3(mylist) = 0.000027 seconds
closest_pair4(mylist) = 0.000006 seconds
closest_pair5(mylist) = 0.000029 seconds
'''

# testing ...
print(closest_pair1(mylist))  # (47, 48)
print(closest_pair2(mylist))  # (47, 48)
print(closest_pair3(mylist))  # (47, 48)
print(closest_pair4(mylist))  # (47, 48)
print(closest_pair5(mylist))  # (47, 48)

print(closest_pair1(mylist2)) # (10.7, 11.5)
print(closest_pair2(mylist2)) # (11.5, 10.7)
print(closest_pair3(mylist2)) # (10.7, 11.5)
print(closest_pair4(mylist2)) # (10.7, 11.5)
print(closest_pair5(mylist2)) # (10.7, 11.5)``````
TrustyTony 888

Quite speed demon you got (you beat my new Core i7-3770 Windows7 times)! I got however (11.5, 10.7) as result to line 107.

Gribouillis 1,391

I got

``````closest_pair1(mylist) = 0.000008 seconds
closest_pair2(mylist) = 0.000038 seconds
closest_pair3(mylist) = 0.000040 seconds
closest_pair4(mylist) = 0.000010 seconds
closest_pair5(mylist) = 0.000041 seconds
``````

with an AMD Athlon(tm) X2 245 Processor

Lardmeister 461

Trying to make mild improvements:

``````''' list_closest_pair3a.py
find the closest pair of numeric elements in a list
Python27/Python33 experiments
'''

import mpmath as mpm

def closest_pair1(mylist):
'''
return the closest pair of numeric elements in mylist
original by snippsat
'''
# make elements unique and sort
lst = sorted(set(mylist))
# shift second list by 1 to avoid matches
# list() needed for Python3
number_par = list(zip(lst, lst[1:]))
lowest_par_result = [abs(y-x) for x, y in number_par]
lowest_par_index = lowest_par_result.index(min(lowest_par_result))
return number_par[lowest_par_index]

def closest_pair4(mylist):
'''return the closest pair of numeric elements in mylist'''
# make unique elements and sort
slist = sorted(set(mylist))
# put initial closest pair values far apart
cpair = (10000, 0)
for ix, n in enumerate(slist):
# avoid IndexError: list index out of range
if ix >= len(slist) - 1:
break
# next element
y = slist[ix+1]
# pick the smallest difference
if abs(n - y) < abs(cpair[0] - cpair[1]):
# update closest pair values
cpair = (n, y)
return cpair

def closest_pair5(q):
'''return the closest pair of numeric elements in list q'''
mt = min([(abs(x-y), x, y) for x in q for y in q if abs(x-y) > 0])
return (mt[1], mt[2])

def closest_pair6(mylist):
'''
return the closest pair of numeric elements in list mylist
combination of closest_pair1() and closest_pair6()
'''
# make unique elements and sort
slist = sorted(set(mylist))
# shift second list by 1 to avoid matches
q = zip(slist, slist[1:])
mt = min([(abs(x-y), x, y) for x, y in q])
return (mt[1], mt[2])

mylist = [90, 5, 27, 63, 12, 47, 10, 150, 120, 48]

# timing ...
print("closest_pair1(mylist) = %f seconds" % mpm.timing(closest_pair1, mylist))
print("closest_pair4(mylist) = %f seconds" % mpm.timing(closest_pair4, mylist))
print("closest_pair5(mylist) = %f seconds" % mpm.timing(closest_pair5, mylist))
print("closest_pair6(mylist) = %f seconds" % mpm.timing(closest_pair6, mylist))

''' my result (Python330, ordinary Toshiba Notebook) ...

closest_pair1(mylist) = 0.000038 seconds
closest_pair4(mylist) = 0.000039 seconds
closest_pair5(mylist) = 0.000164 seconds
closest_pair6(mylist) = 0.000032 seconds

'''

# testing ...
print(closest_pair1(mylist))  # (47, 48)
print(closest_pair4(mylist))  # (47, 48)
print(closest_pair5(mylist))  # (47, 48)
print(closest_pair6(mylist))  # (47, 48)
``````
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, learning, and sharing knowledge.