1.11M Members

Numeric List Closest Pairs (Python)

 
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)
 
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.

 
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

 
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)
Isn't it about time forums rewarded their contributors?

Earn rewards points for helping others. Gain kudos. Cash out. Get better answers yourself.

It's as simple as contributing editorial or replying to discussions labeled or OP Kudos

You
This is an OP Kudos discussion and contributors may be rewarded
Post:
Start New Discussion
Tags Related to this Article