Efficient way of iterating a list of records

[anguis]

Hi

First post for me so pls be gentle

There's a lot of pretext here for a fairly simple question but I thought it better to explain the context than just post a newbie question and invite a barrage of RTFM LMGTFY replies. I'm scoping for ways of doing a particular task, and Python is one of the options I have. This is what I need to do:

I have a small database of locations plus some other information fields which will look like

Lat,Long,Name,data1,data2 etc

and I expect to have 100-1000 order of magnitude number of records. When an event happens I need to iterate through the list as fast as possible and find the closest Lat/Long to my current lat/long then return the rest of the data associated with that record.

I'm planning to do this on a GPS module with embedded Python and this is the main reson for this post. Because as soon as I start searching for database/field/record etc I mostly get results about SQL plugins or suchlike which I doubt I will be able to use. Also, being embedded means resources will be pretty tight so what may work in PyCharm for example won't necessarily work for this platform.

What I think I need is to store my data in a list of dictionaries but I'd appreciate any [polite!] pointers or advice how to get started. Once I'm headed in the right direction I'm happy enough plugging away, RTFMing & Googling as I firmly believe doing is the best way of learning. (NB I'm a complete newbie to Python although I have dabbled in a fair few other languages over the years)

Thanks!

[scidam]

In case of traditional computational environment built on top of Python (numpy+pandas+python), that would be a quite simple problem. NumPy is implemented in C and aimed at computationally efficient workflow with arrays in Python.
But it is not clear, would it possible to install NumPy on your GPS module?!
You will likely need to implement Haversine distance using NumPy to get
numpy-vectorized form of the distance function.

[anguis]

In case of traditional computational environment built on top of Python (numpy+pandas+python), that would be a quite simple problem. NumPy is implemented in C and aimed at computationally efficient workflow with arrays in Python.
But it is not clear, would it possible to install NumPy on your GPS module?!
You will likely need to implement Haversine distance using NumPy to get
numpy-vectorized form of the distance function.

Sadly I think the answer is no That's the trouble with embedded implementations; they often contain a pretty basic or stripped down
interpreter. I'm aware of the Haversine calculation thanks, and fortunately trig functions are supported although in this case I'm after relative comparisons rather than absolute distances so I'm hoping I can work with lat/long values directly (happy to be corrected though!)

So it's back to manually trawling through the records and the best way to do it...

[perfringo]

Python dictionaries are fastest for key lookup (keys are/must be immutable and dict is hash table, so time complexity is O(1)).

You could use coordinates (tuple) as your dictionary keys. However, this probably will not help you as much as you don't look for exact match but nearest. Still there are some possibilities:

- if you have Python 3.7 (dictionaries are insertion ordered) or can use OrderedDict then you can have dictionary ordered by keys and use bisect to find insertion point and compare two adjacent keys to find which is closer
- you can use min() with keyfunc to find smallest difference in coordinates/keys.

[scidam]

python -m timeit -s "import numpy as np; np.random.seed(30); data = {(a, b): '' for a, b in np.random.rand(100, 2)}; point = (10, 20);" "min(data, key=lambda x: (x[0]-point[0])**2 + (x[1]-point[1])**2)"

Output:
10000 loops, best of 3: 192 usec per loop

python -m timeit -s "import numpy as np; np.random.seed(30); data = [(a, b) for a, b in np.random.rand(100, 2)]; point = (10, 20);" "min([(a - point[0]) ** 2 + (b - point[1]) ** 2 for a,b in data])"

Output:
10000 loops, best of 3: 159 usec per loop