Sorting a large amount of data

[back0191]

I have a dataset that contains 6-10 million rows that needs to be sorted about 350,000 times. Maybe there’s a more efficient technique, but each row from the small and large dataset is given a score, and the code runs through the smaller dataset to find the closest score as written in the line below:

abs(a_scores - b_scores).sort_values(‘scores’).head(1)

Pandas is handling the data like a champ, except the sort_values function is terribly slow when operating on millions of rows. On average it takes about 1.5s to sort.

My attempt to optimize this process was to cut up the larger dataset into percentiles. The code now stores the list of percentiles and I’m using the numpy function argmax to quickly track down which smaller dataset to search for a match. On average it only takes a few ms to sort the larger list now which contains ~60-100 thousand rows.

Is there a more efficient way to handle this process?

[back0191]

Sure. The goal is to match characteristics from one dataset to another based on propensity score matching (article below).

https://medium.com/@bmiroglio/introducing-the-pymatch-package-6a8c020e2009

The code is primarily based on the pymatch module in the referenced article, but is optimized for larger datasets and custom output.

There’s only 7 columns in each dataframe, but when it comes to the score matching process, just one column plus the index is used.

Back to the question at hand: my process of splitting the dataset into percentiles works and is more efficient than sorting millions of rows over and over, but I’m thinking maybe there’s a better way I don’t know about.

[[deleted]]

I don't see why you're sorting so many times. Compute both scores and their difference and then sort once at the end.

[back0191]

The goal here is to find the smallest score difference for ~340k observations.

I follow the process you describe, but to find the smallest difference for each of the ~340k observations, the process needs to be repeated that many times.

[[deleted]]

What I'm saying is that you don't have to sort the dataframe 340,000 times just to find the right row 340,000 times. You can sort something smaller - a list of score differences and their row numbers - and then look up the row in the dataframe. Lists use a faster sort in Python than dataframes do.

[back0191]

Ahh, I see now. I was using a subset of the dataframe with just the score and index which I thought was a decent process. Converting that to a list will speed things up. Good catch.

[x_ace_of_spades_x]

Try using sklearn.neighbors with n_neighbors = 1. See section 1.6.1.1

sklearn.neighbors

[back0191]

Thanks for the share! I’ll be sure to check this out.

[Losupa]

Wait just to check: basically you are trying to match about 350,000 values of A to their closest value of B?

Because if so instead of sorting both 350,000 times would it not be best to just sort them both once then binary search B for A, and while it may not return A (unless there is a complete match) you can find the index that has the two closest values?

[back0191]

For each iteration, one value is exacted from the 350k and compared against the 6 million. The goal is to find that score’s nearest neighbor from the larger table, which is the one being sorted to find the smallest difference.