Non-matching join operation
from @yarden on the mailing list

```
Hi,

I have a very common use case which pandas which involve a JOIN
operation related to coordinate arithmetic on two dataframes,
with queries like: for each entry in dataframe A, return all the
entries from dataframe B that have coordinates overlapping with
this entry. This join is not just matching on the columns values
of A and B, since the column values here are coordinates that
require simple arithmetic operations like intersection, overlap,
etc.

Following Wes's answer to someone else's question
here (http://stackoverflow.com/questions/7837722/), I implemented
this in a naive way using iteration. My solution is extremely
inefficient however, probably in part since it is non-vectorized
and requires iterating through each element of the DataFrame.

Do you know of a more efficient/elegant way to do this?  The
naive implementation is unfortunately not workable for anything
even moderately large (e.g. dataframes with a couple thousand
entries.)

Complete example below. The first dataframe, df1, is made up of
two datasources, and each entry has a coordinate
column "loc1". The second dataframe df2 has an interval (start
and end coordinate) for each position. The "join" operation
function my_join() simply returns all the entry numbers in df2
that have intervals that contain the loc1 column from df1. The
join is not unique, so entries in df1 can be contained in
multiple entries in df2 (in which case they are stored as
comma-separated strings), or they can be contained in none of the
entries in df2, in which case the function stores the value
as "-1".

I'd like this to scale to instances where df1 and df2 contain
~50k entries. What is the best way to do this?

Thanks very much.

import pandas as p
import scipy
import numpy
# DataFrames for each data source
source1_data = np.array([0, 7, 2, 5, 0, 5, 4, 3, 9, 0, 4, 2, 5, 8, 0, 4, 0, 3, 3, 6])
source1_size = len(source1_data)
source1 = p.DataFrame({"id": range(source1_size),
                       "loc1": source1_data})
source1.set_index(["id"])
source2_data = np.array([8, 4, 1, 1, 9, 3, 7, 2, 8, 7])
source2_size = len(source2_data)
source2 = p.DataFrame({"id": range(source2_size),
                       "loc1": source2_data})
source2.set_index(["id"])
dataframe_dict = {"source1": source1,
                  "source2": source2}
# Concatenated into one DataFrame
df1 = p.concat(dataframe_dict, keys=["source1", "source2"])

df2_size = 6
# dataframe with intervals
intervals = np.array([[ 5,  6],
                      [ 3,  6],
                      [ 6, 13],
                      [ 7, 10],
                      [ 8,  9],
                      [ 9, 12]])
df2 = p.DataFrame({"entry": range(df2_size),
                   "coord1": intervals[:, 0],
                   "coord2": intervals[:, 1]})
# JOIN df1 and df2 based on interval containment
def my_join(first_df, second_df):
    all_hits = []
    for entry, value in first_df.T.iteritems():
        # Look for cases where loc1 field of df1 falls within
        # (coord1, coord2)
        coord = value["loc1"]
        hits = second_df.ix[(coord > second_df["coord1"]) & \
                            (coord < second_df["coord2"])]
        num_hits = len(hits)
        if num_hits == 0:
            hits = [-1]
        else:
            hits = hits["entry"].values
        # If there are any hits, record their entries in a
        # column of df1. When none, record them as -1
        print "%d falls within %d hits: " %(coord, num_hits)
        if num_hits > 0: print hits
        # Must convert hits to string to store these
        # non-scalars in first_df later on
        hits_str = ",".join(map(str, hits))
        all_hits.append(hits_str)
        # Store hits in first_df
    first_df["hits"] = all_hits
    print "Revised first_df: "
    print first_df

my_join(df1, df2)
```
