Générer des produits cartésiens binaires filtrés

12

Énoncé du problème

Je recherche un moyen efficace de générer des produits cartésiens binaires complets (tableaux avec toutes les combinaisons de Vrai et Faux avec un certain nombre de colonnes), filtrés par certaines conditions exclusives. Par exemple, pour trois colonnes / bits, n=3nous aurions le tableau complet

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
...

Ceci est censé être filtré par les dictionnaires définissant les combinaisons mutuellement exclusives comme suit:

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

Où les clés désignent les colonnes du tableau ci-dessus. L'exemple se lirait comme suit:

  • Si 0 est faux et 1 est faux, 2 ne peut pas être vrai
  • Si 0 est vrai, 2 ne peut pas être vrai

Sur la base de ces filtres, la sortie attendue est:

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

Dans mon cas d'utilisation, la table filtrée est de plusieurs ordres de grandeur plus petite que le produit cartésien complet (par exemple, environ 1000 au lieu de 2**24 (16777216)).

Voici mes trois solutions actuelles, chacune avec ses propres avantages et inconvénients, discutées à la toute fin.

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

Solution 1: filtrez d'abord, puis fusionnez.

Développez chaque entrée de filtre unique (par exemple {0: True, 2: True}) dans un sous-tableau avec des colonnes correspondant aux indices de cette entrée de filtre ( [0, 2]). Supprimez une seule ligne filtrée de ce sous-tableau ( [True, True]). Fusionnez avec le tableau complet pour obtenir la liste complète des combinaisons filtrées.

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

Solution 2: expansion complète, puis filtre

Générer DataFrame pour un produit cartésien complet: le tout se retrouve en mémoire. Parcourez les filtres et créez un masque pour chacun. Appliquez chaque masque sur la table.


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

Solution 3: filtrer l'itérateur

Gardez le produit cartésien complet comme itérateur. Boucle en vérifiant pour chaque ligne si elle est exclue par l'un des filtres.

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

Exécuter des exemples

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]}

Une analyse

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

entrez la description de l'image ici

Solution 3 : l'approche basée sur les itérateurs ( comb_iterator) a des temps d'exécution lamentables, mais aucune utilisation significative de la mémoire. Je pense qu'il y a place à amélioration, bien que la boucle inévitable impose probablement des limites strictes en termes de durée de fonctionnement.

Solution 2 : l'expansion du produit cartésien complet dans un DataFrame ( exp_filt) provoque des pics de mémoire importants, que j'aimerais éviter. Les temps de course sont corrects cependant.

Solution 1 : La fusion de DataFrames créés à partir des filtres individuels ( filt_merge) semble être une bonne solution pour mon application pratique (notez la réduction du temps d'exécution pour un plus grand nombre de filtres, qui est le résultat de la plus petite cols_missingtable). Pourtant, cette approche n'est pas entièrement satisfaisante: si un seul filtre inclut toutes les colonnes, l'ensemble du produit cartésien ( 2**n) se retrouverait en mémoire, ce qui rend cette solution pire que comb_iterator.

Question: D'autres idées? Un bi-liner fou numpy intelligent? L'approche basée sur les itérateurs pourrait-elle être améliorée d'une manière ou d'une autre?

python pandas dataframe mcsoini
la source
1
Les résolveurs de contraintes surpasseraient probablement ces approches car ils trouvent ces solutions en réduisant l'espace de recherche. Jetez peut-être un œil à or-tools. Voici un exemple pour SAT.
ayhan
1
@ayhan, j'ai essayé (voir réponse). C'est une approche intéressante, mais pas vraiment appropriée comme solution générale. Merci pour la contribution. J'ai appris quelque chose :)
mcsoini
Oui, cela ressemble à un problème SAT , vous devez donc absolument utiliser un solveur si le problème est suffisamment important. Vous pouvez également essayer or.stackexchange.com
Stradivari
La formulation de @Stradivari en tant que problème SAT a vraiment du sens. Je n'aime pas la forte dépendance du nombre de filtres de cette approche. Peut-être que je n'accède pas correctement aux solutions. Puisque vous connaissez votre chemin ou des outils, peut-être que vous voulez jeter un œil à ma question correspondante ... il manque toujours une réponse acceptée;)
mcsoini

Réponses:

1

Essayez de chronométrer ce qui suit:

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]

Il traite les produits binaires cartésiens comme les bits codés dans la plage d'entiers 0..<2**net utilise des fonctions vectorisées pour supprimer récursivement les nombres dont les séquences de bits correspondent aux filtres donnés.

L'efficacité de la mémoire est meilleure que l'allocation de tous [True, False]les produits cartésiens car chaque booléen serait stocké avec au moins 8 bits chacun (en utilisant 7 bits de plus que nécessaire), mais il utilisera plus de mémoire qu'une approche basée sur un itérateur. Si vous avez besoin d'une solution pour les grands n, vous pouvez décomposer cette tâche en allouant et en opérant sur une sous-plage à la fois. J'avais cela dans ma première implémentation, mais cela n'offrait pas beaucoup d'avantages n<=22et cela nécessitait le calcul de la taille du tableau de sortie, ce qui devient compliqué quand il y a des filtres qui se chevauchent.

Seb
la source
C'est vraiment incroyable!
mcsoini
1

Sur la base du commentaire de @ ayhan, j'ai implémenté une solution basée sur SAT or-tools. Bien que l'idée soit géniale, cela se bat vraiment pour un plus grand nombre de variables binaires. Je soupçonne que cela est similaire à de gros problèmes IP, ce qui n'est pas non plus une promenade dans le parc. Cependant, la forte dépendance à l'égard des numéros de filtre pourrait en faire une option valide pour certaines configurations de paramètres. Mais comme solution générale, je ne l'utiliserais pas.

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

entrez la description de l'image ici

mcsoini
la source