¿Cómo llenar eficientemente los valores faltantes en columnas con dependencia pareja en pandas?

Tengo un conjunto de datos donde cada observación tiene dos tipos de IDs, es decir, hay una dependencia de pares entre ellos. Sin embargo, a veces falta uno de los IDs en la fila. Los datos se ven así:

Donde “‘''” es una cadena vacía y no “np.NaN”. Las filas de datos no están ordenadas (es decir, las observaciones de “user_1” pueden estar intercaladas). En el ejemplo anterior, nos gustaría llenar “id_x” en las filas 2 y 3 con “user_2”, ya que vemos que esta es la asignación correcta para “user_2” vista en la fila 5. Al mismo tiempo, nos gustaría llenar “id_y” en la fila 6 con “user_c” ya que esa es la asignación correcta vista en la fila 4.

Una solución es iterar sobre todos los usuarios únicos, dividir el dataframe y retroceder.

Otra solución es crear un diccionario con todas las asignaciones entre pares y luego hacer una función de aplicación. En este caso, básicamente haremos una búsqueda de diccionario para cada valor faltante. Estoy trabajando con dataframes bastante grandes, por lo que me pregunto si hay una solución más eficiente que las dos soluciones anteriores.