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.
Numeric List Closest Pairs (Python)
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
downloaded Windows installer file (for Python27 to Python33)
mpmath-0.17.win32.exe
from
http://code.google.com/p/mpmath/
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 pyMod Team Colleague Featured Poster
Gribouillis 1,391 Programming Explorer Team Colleague
Lardmeister 461 Posting Virtuoso
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.