title: Performing pair-wise comparisons of some pandas dataframe rows as efficiently as possible
body: <p>For a given pandas dataframe <code>df</code>, I would like to compare every sample (row) with each other. </p>
  
  <p>For bigger datasets this would lead to too many comparisons (<code>n**2</code>). Therefore, it is necessary to perform these comparisons only for smaller groups (i.e. for all of those which share the same <code>id</code>) and as efficiently as possible. </p>
  
  <p>I would like to construct a dataframe (<code>df_pairs</code>), which contains in every row one pair. Additionally, I would like to get all pair indices (ideally as a Python set).</p>
  
  <p>First, I construct an example dataframe:</p>
  
  <pre><code>import numpy as np
  import pandas as pd
  from functools import reduce
  from itertools import product, combinations
  
  n_samples = 10_000
  suffixes = ["_1", "_2"]  # for df_pairs
  id_str = "id"
  
  df = pd.DataFrame({id_str: np.random.randint(0, 10, n_samples),
                     "A": np.random.randint(0, 100, n_samples),
                     "B": np.random.randint(0, 100, n_samples),
                     "C": np.random.randint(0, 100, n_samples)}, index=range(0, n_samples))
  
  columns_df_pairs = ([elem + suffixes[0] for elem in df.columns] + 
                      [elem + suffixes[1] for elem in df.columns])
  </code></pre>
  
  <p>In the following, I am comparing 4 different options with the corresponding performance measures: </p>
  
  <p><strong>Option 1</strong></p>
  
  <pre><code>groups = df.groupby(id_str).groups  # get the groups
  pairs_per_group = [set(product(elem.tolist(), repeat=2)) for _, elem in groups.items()]  # determine pairs per group
  set_of_pairs = reduce(set.union, pairs_per_group)  # convert all groups into one set
  idcs1, idcs2 = zip(*[(e1, e2) for e1, e2 in set_of_pairs])
  df_pairs = pd.DataFrame(np.hstack([df.values[idcs1, :], df.values[idcs2, :]]), # construct the dataframe of pairs
                          columns=columns_df_pairs, 
                          index=pd.MultiIndex.from_tuples(set_of_pairs, names=('index 1', 'index 2')))
  df_pairs.drop([id_str + suffixes[0], id_str + suffixes[1]], inplace=True, axis=1)
  </code></pre>
  
  <p>Option 1 takes 34.2 s ± 1.28 s.</p>
  
  <p><strong>Option 2</strong></p>
  
  <pre><code>groups = df.groupby(id_str).groups  # get the groups
  pairs_per_group = [np.array(np.meshgrid(elem.values, elem.values)).T.reshape(-1, 2) for _, elem in groups.items()]
  idcs = np.unique(np.vstack(pairs_per_group), axis=0)
  df_pairs2 = pd.DataFrame(np.hstack([df.values[idcs[:, 0], :], df.values[idcs[:, 1], :]]), # construct the dataframe of pairs
                          columns=columns_df_pairs, 
                          index=pd.MultiIndex.from_arrays([idcs[:, 0], idcs[:, 1]], names=('index 1', 'index 2')))
  df_pairs2.drop([id_str + suffixes[0], id_str + suffixes[1]], inplace=True, axis=1)
  </code></pre>
  
  <p>Option 2 takes 13 s ± 1.34 s.</p>
  
  <p><strong>Option 3</strong></p>
  
  <pre><code>groups = df.groupby(id_str).groups  # get the groups
  pairs_per_group = [np.array([np.tile(elem.values, len(elem.values)), np.repeat(elem.values, len(elem.values))]).T.reshape(-1, 2) for _, elem in groups.items()]
  idcs = np.unique(np.vstack(pairs_per_group), axis=0)
  df_pairs3 = pd.DataFrame(np.hstack([df.values[idcs[:, 0], :], df.values[idcs[:, 1], :]]), # construct the dataframe of pairs
                          columns=columns_df_pairs, 
                          index=pd.MultiIndex.from_arrays([idcs[:, 0], idcs[:, 1]], names=('index 1', 'index 2')))
  df_pairs3.drop([id_str + suffixes[0], id_str + suffixes[1]], inplace=True, axis=1)
  </code></pre>
  
  <p>Option 3 takes 12.1 s ± 347 ms.</p>
  
  <p><strong>Option 4</strong></p>
  
  <pre><code>df_pairs4 = pd.merge(left=df, right=df, how="inner", on=id_str, suffixes=suffixes)
  # here, I do not know how to get the MultiIndex in
  df_pairs4.drop([id_str], inplace=True, axis=1)
  </code></pre>
  
  <p>Option 4 is computed the quickest with 1.41 s ± 239 ms. However, I do not have the paired indices in this case. </p>
  
  <p>I could improve the performance a little bit by using <code>comparisons</code> instead of <code>product</code> of itertools. I could also build the comparison matrix and use only the upper triangular one and construct my dataframe from there. This however does not seem to be more efficient than performing the cartesian product and removing the self-references as well as inverse comparisons <code>(a, b) = (b, a)</code>. </p>
  
  <ul>
  <li>Could you tell me a more efficient way to get pairs for comparison (ideally as a set to be able to use set operations)?</li>
  <li>Could I use <code>merge</code> or another <code>pandas</code> function to construct my desired dataframe with the multi-indices?</li>
  </ul>