1,105,395 Community Members

Numeric List Closest Pairs (Python)

Member Avatar
Reputation Points: 1,544 [?]
Q&As Helped to Solve: 1,872 [?]
Skill Endorsements: 67 [?]
 
5
 

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.

''' 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)
Member Avatar
pyTony
pyMod
6,104 posts since Apr 2010
Reputation Points: 818 [?]
Q&As Helped to Solve: 1,056 [?]
Skill Endorsements: 42 [?]
Moderator
Featured
 
0
 

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.

Member Avatar
Gribouillis
Posting Maven
3,456 posts since Jul 2008
Reputation Points: 1,140 [?]
Q&As Helped to Solve: 884 [?]
Skill Endorsements: 18 [?]
Moderator
 
0
 

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

Member Avatar
Lardmeister
Posting Virtuoso
1,966 posts since Mar 2007
Reputation Points: 434 [?]
Q&As Helped to Solve: 111 [?]
Skill Endorsements: 8 [?]
 
1
 

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)
You
Post:
Start New Discussion
Tags Related to this Article