Generar productos cartesianos binarios filtrados.

12

Planteamiento del problema

Estoy buscando una forma eficiente de generar productos cartesianos binarios completos (tablas con todas las combinaciones de Verdadero y Falso con un cierto número de columnas), filtradas por ciertas condiciones exclusivas. Por ejemplo, para tres columnas / bits n=3obtendríamos la tabla completa

df_combs = pd.DataFrame(itertools.product(*([[True, False]] * n)))
       0      1      2
0   True   True   True
1   True   True  False
2   True  False   True
3   True  False  False
...

Se supone que esto debe ser filtrado por los diccionarios que definen combinaciones mutuamente excluyentes de la siguiente manera:

mutually_excl = [{0: False, 1: False, 2: True},
                 {0: True, 2: True}]

Donde las teclas denotan las columnas en la tabla de arriba. El ejemplo se leería como:

  • Si 0 es falso y 1 es falso, 2 no puede ser verdadero
  • Si 0 es verdadero, 2 no puede ser verdadero

Según estos filtros, el resultado esperado es:

       0      1      2
1   True   True  False
3   True  False  False
4  False   True   True
5  False   True  False
7  False  False  False

En mi caso de uso, la tabla filtrada es de múltiples órdenes de magnitud más pequeña que el producto cartesiano completo (por ejemplo, unos 1000 en lugar de 2**24 (16777216)).

A continuación se presentan mis tres soluciones actuales, cada una con sus propios pros y contras, discutidos al final.

import random
import pandas as pd
import itertools
import wrapt
import time
import operator
import functools

def get_mutually_excl(n, nfilt):  # generate random example filter
    ''' Example: `get_mutually_excl(9, 2)` creates a list of two filters with
    maximum index `n=9` and each filter length between 2 and `int(n/3)`:
    `[{1: True, 2: False}, {3: False, 2: True, 6: False}]` '''
    random.seed(2)
    return [{random.choice(range(n)): random.choice([True, False])
                           for _ in range(random.randint(2, int(n/3)))}
                           for _ in range(nfilt)]

@wrapt.decorator
def timediff(f, _, args, kwargs):
    t = time.perf_counter()
    res = f(*args)
    return res, time.perf_counter() - t

Solución 1: Primero filtre, luego combine.

Expanda cada entrada de filtro individual (p {0: True, 2: True}. Ej. ) En una subtabla con columnas correspondientes a los índices en esta entrada de filtro ( [0, 2]). Eliminar una sola fila filtrada de esta subtabla ( [True, True]). Combinar con la tabla completa para obtener la lista completa de combinaciones filtradas.

@timediff
def make_df_comb_filt_merge(n, nfilt):

    mutually_excl = get_mutually_excl(n, nfilt)

    # determine missing (unfiltered) columns
    cols_missing = set(range(n)) - set(itertools.chain.from_iterable(mutually_excl))

    # complete dataframe of unfiltered columns with column "temp" for full outer merge
    df_comb = pd.DataFrame(itertools.product(*([[True, False]] * len(cols_missing))),
                            columns=cols_missing).assign(temp=1)

    for filt in mutually_excl:  # loop through individual filters

        # get columns and bool values of this filters as two tuples with same order
        list_col, list_bool = zip(*filt.items())

        # construct dataframe
        df = pd.DataFrame(itertools.product(*([[True, False]] * len(list_col))),
                                columns=list_col)

        # filter remove a *single* row (by definition)
        df = df.loc[df.apply(tuple, axis=1) != list_bool]

        # determine which rows to merge on
        merge_cols = list(set(df.columns) & set(df_comb.columns))
        if not merge_cols:
            merge_cols = ['temp']
            df['temp'] = 1

        # merge with full dataframe
        df_comb = pd.merge(df_comb, df, on=merge_cols)

    df_comb.drop('temp', axis=1, inplace=True)
    df_comb = df_comb[range(n)]
    df_comb = df_comb.sort_values(df_comb.columns.tolist(), ascending=False)

    return df_comb.reset_index(drop=True)

Solución 2: expansión completa, luego filtrar

Genere DataFrame para un producto cartesiano completo: todo termina en la memoria. Recorra los filtros y cree una máscara para cada uno. Aplica cada máscara a la mesa.


@timediff
def make_df_comb_exp_filt(n, nfilt):

    mutually_excl = get_mutually_excl(n, nfilt)

    # expand all bool combinations into dataframe
    df_comb = pd.DataFrame(itertools.product(*([[True, False]] * n)),
                           dtype=bool)

    for filt in mutually_excl:

        # generate total filter mask for given excluded combination
        mask = pd.Series(True, index=df_comb.index)
        for col, bool_act in filt.items():
            mask = mask & (df_comb[col] == bool_act)

        # filter dataframe
        df_comb = df_comb.loc[~mask]

    return df_comb.reset_index(drop=True)

Solución 3: iterador de filtro

Mantenga el producto cartesiano completo como un iterador. Haga un bucle mientras verifica para cada fila si está excluido por alguno de los filtros.

@timediff
def make_df_iter_filt(n, nfilt):

    mutually_excl = get_mutually_excl(n, nfilt)

    # switch to [[(1, 13), (True, False)], [(4, 9), (False, True)], ...]
    mutually_excl_index = [list(zip(*comb.items()))
                                for comb in mutually_excl]

    # create iterator
    combs_iter = itertools.product(*([[True, False]] * n))

    @functools.lru_cache(maxsize=1024, typed=True)  # small benefit
    def get_getter(list_):
        # Used to access combs_iter row values as indexed by the filter
        return operator.itemgetter(*list_)

    def check_comb(comb_inp, comb_check):
        return get_getter(comb_check[0])(comb_inp) == comb_check[1]

    # loop through the iterator
    # drop row if any of the filter matches
    df_comb = pd.DataFrame([comb_inp for comb_inp in combs_iter
                       if not any(check_comb(comb_inp, comb_check)
                                  for comb_check in mutually_excl_index)])

    return df_comb.reset_index(drop=True)

Ejecute ejemplos

dict_time = dict.fromkeys(itertools.product(range(16, 23, 2), range(3, 20)))

for n, nfilt in dict_time:
    dict_time[(n, nfilt)] = {'exp_filt': make_df_comb_exp_filt(n, nfilt)[1],
                             'filt_merge': make_df_comb_filt_merge(n, nfilt)[1],
                             'iter_filt': make_df_iter_filt(n, nfilt)[1]}

Análisis

import seaborn as sns
import matplotlib.pyplot as plt

df_time = pd.DataFrame.from_dict(dict_time, orient='index',
                                 ).rename_axis(["n", "nfilt"]
                                 ).stack().reset_index().rename(columns={'level_2': 'solution', 0: 'time'})

g = sns.FacetGrid(df_time.query('n in %s' % str([16,18,20,22])),
                  col="n",  hue="solution", sharey=False)
g = (g.map(plt.plot, "nfilt", "time", marker="o").add_legend())

ingrese la descripción de la imagen aquí

Solución 3 : El enfoque basado en iterador ( comb_iterator) tiene tiempos de ejecución pésimos, pero no utiliza significativamente la memoria. Siento que hay margen de mejora, aunque el ciclo inevitable probablemente impone límites duros en términos de tiempo de ejecución.

Solución 2 : expandir el producto cartesiano completo en un DataFrame ( exp_filt) causa picos significativos en la memoria, lo que me gustaría evitar. Sin embargo, los tiempos de funcionamiento están bien.

Solución 1 : Fusionar marcos de datos creados a partir de los filtros individuales ( filt_merge) se siente como una buena solución para mi aplicación práctica (tenga en cuenta la reducción en el tiempo de ejecución para un mayor número de filtros, que es el resultado de la cols_missingtabla más pequeña ). Aún así, este enfoque no es completamente satisfactorio: si un solo filtro incluye todas las columnas, todo el producto cartesiano ( 2**n) terminaría en la memoria, lo que empeoraría esta solución comb_iterator.

Pregunta: ¿Alguna otra idea? ¿Un loco inteligente numpy de dos líneas? ¿Podría el enfoque basado en iterador mejorar de alguna manera?

python pandas dataframe mcsoini
fuente
1
Los solucionadores de restricciones probablemente superarían estos enfoques porque encuentran estas soluciones al reducir el espacio de búsqueda. Quizás eche un vistazo a las herramientas o. Aquí hay un ejemplo para SAT.
ayhan
1
@ayhan, lo intenté (ver respuesta). Es un enfoque interesante, pero no es realmente adecuado como solución general. Gracias por el aporte. Aprendí algo :)
mcsoini
Sí, esto suena como un problema SAT , por lo que definitivamente deberías usar un solucionador si el problema es lo suficientemente grande. También puedes
Stradivari el
La formulación de @Stradivari como un problema SAT definitivamente tiene sentido. Sin embargo, no me gusta la fuerte dependencia del número de filtros de este enfoque. Puede ser que no estoy accediendo a las soluciones correctamente. Dado que conoce bien las herramientas o, tal vez desee ver mi pregunta correspondiente ... todavía carece de una respuesta aceptada;)
mcsoini

Respuestas:

1

Intenta cronometrar lo siguiente:

def in_filter(arr, arr_filt, n):
    return ((arr[:, None] >> (n-1-arr_filt[:, 0])) & 1 == arr_filt[:, 1]).all(axis=1)

def bits_to_boolean(arr, n):
    return ((arr[:, None] >> np.arange(n, dtype=arr.dtype)[::-1]) & 1).astype(bool)

@timediff
def recursive_filter(n, nfilt, dtype='uint32'):
    filts = get_mutually_excl(n, nfilt)
    out = np.arange(2**n, dtype=dtype)
    for filt in filts:
        arr_filt = np.array(list(filt.items()))
        out = out[~in_filter(out, arr_filt, n)]
    return bits_to_boolean(out, n)[::-1]

Trata los productos binarios cartesianos como los bits codificados en el rango de enteros 0..<2**ny utiliza funciones vectorizadas para eliminar recursivamente números que tienen secuencias de bits que coinciden con los filtros dados.

La eficiencia de la memoria es mejor que la asignación de todos [True, False]los productos cartesianos, ya que cada booleano se almacenaría con al menos 8 bits cada uno (utilizando 7 bits más de lo requerido), pero utilizará más memoria que un enfoque basado en iteradores. Si necesita una solución grande n, puede desglosar esta tarea al asignar y operar en un subrango a la vez. Tuve esto en mi primera implementación, pero no ofrecía muchos beneficios n<=22y requería el cálculo del tamaño de la matriz de salida, lo que se complica cuando hay filtros superpuestos.

Seb
fuente
¡Esto es realmente asombroso!
mcsoini
1

Basado en el comentario de @ ayhan, implementé una solución basada en SAT de herramientas o. Si bien la idea es genial, esto realmente lucha por un mayor número de variables binarias. Sospecho que esto es similar a los grandes problemas de IP, que tampoco es un paseo por el parque. Sin embargo, la fuerte dependencia de los números de filtro podría hacer que esta sea una opción válida para ciertas configuraciones de parámetros. Pero como solución general no lo usaría.

from ortools.sat.python import cp_model

class VarArraySolutionCollector(cp_model.CpSolverSolutionCallback):

    def __init__(self, variables):
        cp_model.CpSolverSolutionCallback.__init__(self)
        self.__variables = variables
        self.solution_list = []

    def on_solution_callback(self):
        self.solution_list.append([self.Value(v) for v in self.__variables])


@timediff
def make_df_comb_sat(n, nfilt):

    mutually_excl = get_mutually_excl(n, nfilt)

    model = cp_model.CpModel()

    make_var_name = 'x{:02d}'.format
    vrs = dict.fromkeys(map(make_var_name, range(n)))
    for var_name in vrs:
        vrs[var_name] = model.NewBoolVar(var_name)

    for filt in mutually_excl:
        list_expr = [vrs[make_var_name(iv)]
                     if not bool_ else getattr(vrs[make_var_name(iv)], 'Not')()
                     for iv, bool_ in filt.items()]
        model.AddBoolOr(list_expr)

    solver = cp_model.CpSolver()
    solution_printer = VarArraySolutionCollector(vrs.values())
    solver.SearchForAllSolutions(model, solution_printer)

    df_comb = pd.DataFrame(solution_printer.solution_list).astype(bool)
    df_comb = df_comb.sort_values(df_comb.columns.tolist(), ascending=False)
    df_comb = df_comb.reset_index(drop=True)

    return df_comb

ingrese la descripción de la imagen aquí

mcsoini
fuente