Generuj filtrowane binarne produkty kartezjańskie

12

Opis problemu

Szukam wydajnego sposobu generowania pełnych binarnych produktów kartezjańskich (tabele ze wszystkimi kombinacjami prawdy i fałszu z pewną liczbą kolumn), filtrowane według określonych warunków wyłączności. Na przykład dla trzech kolumn / bitów n=3otrzymalibyśmy pełną tabelę

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

Ma to być filtrowane przez słowniki definiujące wzajemnie wykluczające się kombinacje w następujący sposób:

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

Gdzie klucze oznaczają kolumny w powyższej tabeli. Przykład zostanie odczytany jako:

  • Jeśli 0 to False, a 1 to False, 2 nie może być Prawdą
  • Jeśli 0 to Prawda, 2 nie może być Prawdą

W oparciu o te filtry oczekiwane dane wyjściowe to:

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

W moim przypadku filtrowana tabela jest o wiele rzędów wielkości mniejsza niż pełny produkt kartezjański (np. Około 1000 zamiast 2**24 (16777216)).

Poniżej moje trzy aktualne rozwiązania, każde z własnymi zaletami i wadami, omówione na samym końcu.

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

Rozwiązanie 1: Najpierw przefiltruj, a następnie scal.

Rozwiń każdy pojedynczy wpis filtra (np. {0: True, 2: True}) Do podtabeli z kolumnami odpowiadającymi indeksom w tym wpisie filtra ( [0, 2]). Usuń pojedynczy filtrowany wiersz z tej pod-tabeli ( [True, True]). Scal z pełną tabelą, aby uzyskać pełną listę odfiltrowanych kombinacji.

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

Rozwiązanie 2: Pełne rozszerzenie, a następnie filtrowanie

Generuj DataFrame dla pełnego produktu kartezjańskiego: Cała rzecz kończy się w pamięci. Zapętlaj filtry i utwórz dla nich maskę. Zastosuj każdą maskę do stołu.


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

Rozwiązanie 3: Filtruj iterator

Zachowaj iterator pełnego produktu kartezjańskiego. Pętla sprawdza, czy każdy wiersz jest wykluczony przez którykolwiek z filtrów.

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

Uruchom przykłady

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

Analiza

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

wprowadź opis zdjęcia tutaj

Rozwiązanie 3 : Podejście oparte na iteratorze ( comb_iterator) ma fatalny czas działania, ale nie ma znaczącego wykorzystania pamięci. Wydaje mi się, że jest miejsce na ulepszenia, choć nieunikniona pętla prawdopodobnie narzuca twarde ograniczenia w zakresie czasu działania.

Rozwiązanie 2 : Rozszerzenie pełnego produktu kartezjańskiego do DataFrame ( exp_filt) powoduje znaczne skoki pamięci, których chciałbym uniknąć. Czasy pracy są jednak w porządku.

Rozwiązanie 1 : Scalanie ramek danych utworzonych z poszczególnych filtrów ( filt_merge) wydaje się dobrym rozwiązaniem dla mojej praktycznej aplikacji (zwróć uwagę na skrócenie czasu działania większej liczby filtrów, co wynika z mniejszej cols_missingtabeli). Jednak to podejście nie jest w pełni satysfakcjonujące: jeśli pojedynczy filtr zawiera wszystkie kolumny, cały produkt kartezjański ( 2**n) znalazłby się w pamięci, co pogorszyłoby to rozwiązanie comb_iterator.

Pytanie: Jakieś inne pomysły? Szalony, inteligentny, dwuwarstwowy linijka? Czy można w jakiś sposób ulepszyć podejście oparte na iteratorze?

python pandas dataframe Mcsoini
źródło
1
Rozwiązania ograniczające prawdopodobnie przewyższyłyby te podejścia, ponieważ znajdują te rozwiązania, zmniejszając przestrzeń wyszukiwania. Może rzuć okiem na narzędzia. Oto przykład dla SAT.
ayhan
1
@ayhan, próbowałem (patrz odpowiedź). To ciekawe podejście, ale nie nadaje się jako ogólne rozwiązanie. Dzięki za wkład. Nauczyłem się czegoś :)
mcsoini,
Tak, to brzmi jak problem SAT , więc zdecydowanie powinieneś użyć solvera, jeśli problem jest wystarczająco duży. Możesz także spróbować or.stackexchange.com
Stradivari
Formułowanie @Stradivari jako problem SAT zdecydowanie ma sens. Nie podoba mi się jednak silna zależność od liczby filtrów tego podejścia. Możliwe, że nie mam prawidłowego dostępu do rozwiązań. Ponieważ znasz się na swoich narzędziach i narzędziach, może chcesz
rzucić

Odpowiedzi:

1

Spróbuj mierzyć czas:

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]

Traktuje kartezjańskie produkty binarne jako bity zakodowane w zakresie liczb całkowitych 0..<2**ni wykorzystuje wektoryzowane funkcje do rekurencyjnego usuwania liczb, które mają sekwencje bitów pasujące do podanych filtrów.

Wydajność pamięci jest lepsza niż alokacja wszystkich [True, False]produktów kartezjańskich, ponieważ każdy logiczny byłby przechowywany z co najmniej 8 bitami każdy (przy użyciu 7 bitów więcej niż wymagane), ale zużyje więcej pamięci niż podejście oparte na iteratorze. Jeśli potrzebujesz rozwiązania dla dużych n, możesz rozbić to zadanie, przydzielając i działając na jednym podzakresie na raz. Miałem to w mojej pierwszej implementacji, ale nie przyniosło to wiele korzyści n<=22i wymagało obliczenia rozmiaru tablicy wyjściowej, co komplikuje się, gdy nakładające się filtry są nakładające się.

Seb
źródło
To jest naprawdę niesamowite!
mcsoini,
1

Na podstawie komentarza @ ayhan wdrożyłem rozwiązanie oparte na or-tools SAT. Chociaż pomysł jest świetny, tak naprawdę walczy o większą liczbę zmiennych binarnych. Podejrzewam, że jest to podobne do dużych problemów związanych z IP, które również nie są walką w parku. Jednak silna zależność od numerów filtrów może sprawić, że będzie to prawidłowa opcja dla niektórych konfiguracji parametrów. Ale jako ogólnego rozwiązania nie użyłbym tego.

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

wprowadź opis zdjęcia tutaj

Mcsoini
źródło