4
\$\begingroup\$

I'm trying to find distances between all points (latitude, longitude), and for each point, get the average price_area (price/area) of the closest points around it. This code is taking too long:

def create_pa_radius(df, radius):

    df['pa_' + str(radius)] = np.nan

    for index, row in df.iterrows():
        point = [row['latitude'], row['longitude']]
        df['distances'] = df.apply(lambda x: geo_dist(point, [x['latitude'], x['longitude']]).km, axis = 1)
        samples = df.price_area[df.distances < radius/1000]
        mean = samples.mean()

        df['pa_' + str(radius)].iloc[index] = mean

    return df

I would like at least to understand how to make this kind of iteration faster.

\$\endgroup\$
  • \$\begingroup\$ Welcome to Code Review! I changed the title to a different one that describes what the code does per site goals: "State what your code does in your title, not your main concerns about it.". Feel free to give it a different title if there is something more appropriate. \$\endgroup\$ – Sᴀᴍ Onᴇᴌᴀ Dec 6 '17 at 4:26
  • \$\begingroup\$ This code as presented does not work. There is not radius defined. \$\endgroup\$ – Stephen Rauch Dec 6 '17 at 5:32
  • \$\begingroup\$ Sorry, just fixed that. I'm new here, so let me know if I need to specify anything better for you to understand it. \$\endgroup\$ – Rodrigo Nader Dec 6 '17 at 6:32
  • 1
    \$\begingroup\$ Hey could you include a sample dataframe? \$\endgroup\$ – Neil Dec 6 '17 at 7:00
2
\$\begingroup\$

The problem you are having is most likely due to your code being O(n²) on the size of your dataframe. (It's possible you have a small df and a really bad implementation of geo_dist, but I'll ignore that.)

Let's strip out most of your code:

for index, row in df.iterrows():
    df['distances'] = df.apply(lambda x: geo_dist(point, [x['latitude'], x['longitude']]).km, axis = 1)

These lines can be rewritten:

for index, row in df.iterrows():        
    for i, r2 in df.iterrows():
        p2 = (r2['latitude'], r2['longitude'])
        df.distances[i] = geo_dist(point, *p2).km

The same is true for the filtering of distances < radius/1000: you are looping over all n rows, and then for each row you are looping over all n rows again. This is n * n operations, or O(n²).

There is no simple way to fix this. If you insist on computing the distances from each point to its surrounding points, you will have to structure your code this way. However, there are some alternatives:

  1. You could use a kd-tree or a space partitioning hash of your own design to access your points. This would make pandas secondary in your access, requiring you to write more python code yourself.

  2. You could take advantage of some other heuristic to determine proximity, and use this to filter your data before running your n² algorithm on it: note that 3² + 3² = 18, while (3 + 3)² = 36. Breaking your data down into smaller units can have a substantial impact on your performance. For example: in the United States, zip codes within a given state all start with a few identical 2 digit prefixes. You might build a dictionary of "adjoining" states, by hand, and then pre-filter your locations using a zip-code prefix, such that you only consider other points that have the same 2-digit prefixes, or the 2-digit prefixes of an adjacent state. If your locations were US cities, this would let you eliminate more than 90% of your data before you start your n² algorithm.

  3. There are surely some other approaches, which will tend to vary based on your application. Perhaps if you mention what problem you are trying to solve, someone will have a suggestion.

\$\endgroup\$
  • \$\begingroup\$ Nice answer. What I'm trying to accomplish is this: given a dataset of houses (lat, lot, area, price, price per area, etc) I'm trying to find the average 'price per area' in the region that each house is situated. I'm trying to do this by using a radius, for example 300 meters, so that the 'price per area' inside that radius would be averaged. \$\endgroup\$ – Rodrigo Nader Dec 6 '17 at 19:33
  • \$\begingroup\$ If your area is really small like that, try computing the maximum lat/long distance equal to that radius, then pre-filter the df using that distance: candidates = df[ center_lat - radius <= lat <= center_lat + radius]. This is still n² but it's a faster n² than the apply with python code. You can run that after you get your candidates, and it should be only on a subset, so much quicker. \$\endgroup\$ – Austin Hastings Dec 6 '17 at 19:43
  • \$\begingroup\$ @RodrigoNader must you recompute this all the time? Best way would be to preprocess the houses near each one (and store it) and for the real processing just compute with the updated prices of those \$\endgroup\$ – juvian Dec 6 '17 at 21:08
  • \$\begingroup\$ @juvian it should be atualized every month unfortunately. \$\endgroup\$ – Rodrigo Nader Dec 7 '17 at 0:27
  • \$\begingroup\$ @RodrigoNader how many houses are we talking about? And how many (at max) fit into your radius from a house? \$\endgroup\$ – juvian Dec 7 '17 at 1:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.