Gerar produtos cartesianos binários filtrados

12

Declaração do problema

Estou procurando uma maneira eficiente de gerar produtos cartesianos binários completos (tabelas com todas as combinações de True e False com um certo número de colunas), filtradas por determinadas condições exclusivas. Por exemplo, para três colunas / bits n=3obteríamos a tabela 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
...

Isso deve ser filtrado por dicionários que definem combinações mutuamente exclusivas da seguinte maneira:

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

Onde as chaves denotam as colunas na tabela acima. O exemplo seria lido como:

  • Se 0 for Falso e 1 for Falso, 2 não poderá ser Verdadeiro
  • Se 0 for verdadeiro, 2 não pode ser verdadeiro

Com base nesses filtros, a saída esperada é:

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

No meu caso de uso, a tabela filtrada é várias ordens de magnitude menores que o produto cartesiano completo (por exemplo, 1000 em vez de 2**24 (16777216)).

Abaixo estão minhas três soluções atuais, cada uma com seus próprios prós e contras, discutidas no 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

Solução 1: filtre primeiro e depois mescle.

Expanda cada entrada de filtro única (por exemplo {0: True, 2: True}) em uma sub-tabela com colunas correspondentes aos índices nessa entrada de filtro ( [0, 2]). Remova uma única linha filtrada desta sub-tabela ( [True, True]). Mesclar com a tabela completa para obter a lista completa de combinações 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)

Solução 2: expansão total e depois filtrar

Gere o DataFrame para o produto cartesiano completo: A coisa toda acaba na memória. Passe pelos filtros e crie uma máscara para cada um. Aplique cada máscara na 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)

Solução 3: iterador de filtro

Mantenha o produto cartesiano completo em um iterador. Faça um loop enquanto verifica para cada linha se ela foi excluída por qualquer um dos 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)

Executar exemplos

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álise

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())

insira a descrição da imagem aqui

Solução 3 : A abordagem baseada no iterador ( comb_iterator) tem tempos de execução sombrios, mas nenhum uso significativo de memória. Sinto que há espaço para melhorias, embora o loop inevitável imponha limites rígidos em termos de tempo de execução.

Solução 2 : expandir o produto cartesiano completo para um DataFrame ( exp_filt) causa picos significativos na memória, o que eu gostaria de evitar. Os tempos de execução são bons.

Solução 1 : Mesclar DataFrames criados a partir de filtros individuais ( filt_merge) parece uma boa solução para minha aplicação prática (observe a redução no tempo de execução para um maior número de filtros, resultado da cols_missingtabela menor ). Ainda assim, essa abordagem não é totalmente satisfatória: se um único filtro incluir todas as colunas, todo o produto cartesiano ( 2**n) acabaria na memória, piorando essa solução comb_iterator.

Pergunta: Alguma outra idéia? Um louco inteligente e inteligente de duas linhas? A abordagem baseada no iterador poderia ser melhorada de alguma forma?

python pandas dataframe Mcsoini
fonte
11
Os solucionadores de restrições provavelmente superariam essas abordagens porque encontram essas soluções reduzindo o espaço de pesquisa. Talvez dê uma olhada nas ferramentas. Aqui está um exemplo para o SAT.
ayhan
11
@ayhan, eu tentei (ver resposta). É uma abordagem interessante, mas não é realmente adequada como solução geral. Obrigado pela contribuição. Eu aprendi alguma coisa :)
mcsoini
Sim, isso parece um problema de SAT , então você definitivamente deve usar um solucionador se o problema for grande o suficiente. Você também pode tentar or.stackexchange.com
Stradivari
A formulação @Stradivari como um problema SAT definitivamente faz sentido. Não gosto da forte dependência do número de filtros dessa abordagem. Pode não estar acessando as soluções corretamente. Desde que você sabe seu redor forma ou-ferramentas, talvez você queira dar uma olhada no meu correspondente pergunta ... ele ainda carece de uma resposta aceita;)
mcsoini

Respostas:

1

Tente cronometrar o seguinte:

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]

Ele trata os produtos binários cartesianos como os bits codificados no intervalo de números inteiros 0..<2**ne usa funções vetorizadas para remover recursivamente números que possuem sequências de bits que correspondem aos filtros fornecidos.

A eficiência da memória é melhor do que alocar todos os [True, False]produtos cartesianos, pois cada booleano seria armazenado com pelo menos 8 bits cada (usando 7 bits a mais do que o necessário), mas utilizará mais memória do que uma abordagem baseada em iterador. Se você precisar de uma solução de grande porte n, poderá interromper essa tarefa alocando e operando em um subintervalo por vez. Eu tive isso na minha primeira implementação, mas não ofereceu muitos benefícios n<=22e exigiu o cálculo do tamanho da matriz de saída, o que se torna complicado quando há filtros sobrepostos.

Seb
fonte
Isso é realmente incrível!
Mcsoini 19/11/19
1

Com base no comentário de @ ayhan, implementei uma solução baseada em SAT ou ferramentas. Embora a ideia seja ótima, isso realmente luta por um número maior de variáveis ​​binárias. Suspeito que isso seja semelhante a grandes problemas de IP, que também não são um passeio no parque. No entanto, a forte dependência dos números de filtro pode tornar essa uma opção válida para determinadas configurações de parâmetros. Mas, como solução geral, eu não usaria.

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

insira a descrição da imagem aqui

Mcsoini
fonte