finding the closest floating point number in a list

[Skaperen]

i am not asking for anyone to code this for me. i'm just wanting to know if there might be an already existing tool out there to do this. otherwise i'll code it myself.

i have a big list of tuples. the first item in each tuple is a floating point number. the remaining items in each tuple are items with association to that first item. the list is sorted. there may be tuples with exactly the same first item, and the order of these does not matter.

i need a function that is given a floating point number and with that number, needs to find the tuple with the closest first item. if adjacent tuples are exactly the same, the function needs to return a list of all that have exactly identical first items that meet the requirement of being closest.

i might redo this all using decimal.Decimal type instead of float.

speed is not important. the lookup will be rarely done, maybe a few dozen times at boot-up and once every few hours thereafter. if it takes a couple seconds to run, no big deal. the list will be just a few thousand in length at most.

i've imagined a few ways to optimize this lookup. but this is not needed in this case. sequential is sufficient.

[Gribouillis]

Wouldn't the bisect module suit your needs?

[Skaperen]

perhaps it would. i'd have to construct the list that way. but it is also overkill, since the list is completed and then sorted before the one search is needed. one of my ideas was to select the closer values above and below as the numbers were loaded in the order they are created (not sorted). each time a number is closer, it replaces the previous number, done for above and done separately for below. with that, i would not have to store the numbers or do a sort.

---

the bisect module looks like it may be useful for another project. this will walk its way through the entire file tree of a file system of any size and keep the last {os.environ['ROWS']} largest files in a list sorted in largest-last order. if there is a way to remove items from a bisect object, then i can keep a finite size list by removing the smallest item before adding a new one each time. i just need to find a bisect.delete_lowest() method.

[Gribouillis]

An interesting thin wrapper above bisect is the ActiveState recipe SortedCollection. It does implement the CRUD capabilities that you're talking about. Have a look at it. Also a module such as sortedcontainer could be relevant.

[ThomasL]

Hi Skaperen, what do you think about this?

import random
import numpy as np

# create a big list of tuples with a float as first column
big_list_of_tuples = [(random.random(), 1, 2, 3, "A", "B") for i in range(10000)]

# make three entries the same
big_list_of_tuples[4999] = big_list_of_tuples[5000]
big_list_of_tuples[5001] = big_list_of_tuples[5000]

# we are searching for the float of that three entries
value = big_list_of_tuples[5000][0]
print(value)

# create a numpy array out of the tuple list
array = np.asarray(big_list_of_tuples, dtype=np.object)

# create an array with the first column being real floats
floats = array[:, 0].astype(np.float)

# calculate the difference of the floats and the float we are looking for
difference = (np.abs(floats - value))

# use argmin() to find the index of the first closest value
closest = difference.argmin()
print(closest)

# let´s look if there are other entries with the same difference
identical = difference == difference[closest]

# use this mask as a view into the array
print(array[identical])

[wavic]

I am not a math guy but simple extraction should work. You just get the smallest absolute result.

[Gribouillis]

I am not a math guy but simple extraction should work. You just get the smallest absolute result.

This is true if the set of numbers is unordered, you don't have anything better than a 0(n) algorithm. But if it is a sorted list of data, as was implied by Skaperen's first post, binary search has complexity O(log2(n)). That's why I suggested bisect.

Numpy also has a searchsorted function that could perhaps be used.

[Skaperen]

@ThomasL: i'm lost at line 19 in that code.

i will have to look at numpy, then.

[ThomasL]

That´s just one column with all the float values, all the first values in your tuples

[Skaperen]

i'm going to need to find some extra time to learn numpy. then i will try regex again. but it will never try again to learn perl or lisp ... never, ever!