Numeric List Closest Pairs (Python)

vegaseat 5 Tallied Votes 745 Views Share

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

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 Programming Explorer Team Colleague

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 Posting Virtuoso

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, networking, learning, and sharing knowledge.