Generieren Sie gefilterte binäre kartesische Produkte

12

Problemstellung

Ich suche nach einer effizienten Möglichkeit, vollständige binäre kartesische Produkte (Tabellen mit allen Kombinationen von Wahr und Falsch mit einer bestimmten Anzahl von Spalten) zu generieren, die nach bestimmten exklusiven Bedingungen gefiltert werden. Zum Beispiel n=3würden wir für drei Spalten / Bits die vollständige Tabelle erhalten

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

Dies soll durch Wörterbücher gefiltert werden, die sich gegenseitig ausschließende Kombinationen wie folgt definieren:

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

Wobei die Schlüssel die Spalten in der obigen Tabelle bezeichnen. Das Beispiel würde wie folgt gelesen werden:

  • Wenn 0 falsch und 1 falsch ist, kann 2 nicht wahr sein
  • Wenn 0 wahr ist, kann 2 nicht wahr sein

Basierend auf diesen Filtern ist die erwartete Ausgabe:

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

In meinem Anwendungsfall ist die gefilterte Tabelle um mehrere Größenordnungen kleiner als das vollständige kartesische Produkt (z. B. etwa 1000 statt 2**24 (16777216)).

Im Folgenden sind meine drei aktuellen Lösungen aufgeführt, von denen jede ihre eigenen Vor- und Nachteile hat und die ganz am Ende besprochen werden.

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

Lösung 1: Zuerst filtern, dann zusammenführen.

Erweitern Sie jeden einzelnen Filtereintrag (z. B. {0: True, 2: True}) in eine Untertabelle mit Spalten, die den Indizes in diesem Filtereintrag ( [0, 2]) entsprechen. Entfernen Sie eine einzelne gefilterte Zeile aus dieser Untertabelle ( [True, True]). Mit vollständiger Tabelle zusammenführen, um die vollständige Liste der gefilterten Kombinationen zu erhalten.

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

Lösung 2: Volle Expansion, dann filtern

Generieren Sie DataFrame für ein vollständiges kartesisches Produkt: Das Ganze landet im Speicher. Durchlaufen Sie die Filter und erstellen Sie für jeden eine Maske. Wenden Sie jede Maske auf die Tabelle an.


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

Lösung 3: Filteriterator

Halten Sie das vollständige kartesische Produkt als Iterator. Schleife, während für jede Zeile geprüft wird, ob sie von einem der Filter ausgeschlossen wird.

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

Führen Sie Beispiele aus

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

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

Geben Sie hier die Bildbeschreibung ein

Lösung 3 : Der iteratorbasierte Ansatz ( comb_iterator) hat schlechte Laufzeiten, aber keine signifikante Speichernutzung. Ich denke, es gibt Raum für Verbesserungen, obwohl die unvermeidliche Schleife wahrscheinlich harte Grenzen in Bezug auf die Laufzeit auferlegt.

Lösung 2 : Das Erweitern des vollständigen kartesischen Produkts zu einem DataFrame ( exp_filt) führt zu erheblichen Speicherspitzen, die ich vermeiden möchte. Die Laufzeiten sind jedoch in Ordnung.

Lösung 1 : Das Zusammenführen von DataFrames, die aus den einzelnen Filtern ( filt_merge) erstellt wurden, scheint eine gute Lösung für meine praktische Anwendung zu sein (beachten Sie die Verkürzung der Laufzeit für eine größere Anzahl von Filtern, die sich aus der kleineren cols_missingTabelle ergibt ). Dieser Ansatz ist jedoch nicht ganz zufriedenstellend: Wenn ein einzelner Filter alle Spalten enthält, würde das gesamte kartesische Produkt ( 2**n) im Speicher landen, was diese Lösung schlechter macht als comb_iterator.

Frage: Irgendwelche anderen Ideen? Ein verrückter schlauer Numpy Two-Liner? Könnte der iteratorbasierte Ansatz irgendwie verbessert werden?

python pandas dataframe mcsoini
quelle
1
Constraint-Löser würden diese Ansätze wahrscheinlich übertreffen, da sie diese Lösungen finden, indem sie den Suchraum reduzieren. Vielleicht werfen Sie einen Blick auf or-tools. Hier ist ein Beispiel für SAT.
Ayhan
1
@ayhan, ich habe es versucht (siehe Antwort). Es ist ein interessanter Ansatz, aber als allgemeine Lösung nicht wirklich geeignet. Danke für die Eingabe. Ich habe etwas gelernt :)
McSoini
Ja, das klingt nach einem SAT- Problem, daher sollten Sie auf jeden Fall einen Solver verwenden, wenn das Problem groß genug ist. Sie können auch versuchen, or.stackexchange.com
Stradivari
@ Tradivari-Formulierung als SAT-Problem macht definitiv Sinn. Die starke Abhängigkeit von der Anzahl der Filter dieses Ansatzes gefällt mir jedoch nicht. Könnte sein, dass ich nicht richtig auf die Lösungen zugreife. Da Sie sich mit
Or

Antworten:

1

Versuchen Sie Folgendes zu planen:

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]

Es behandelt die kartesischen Binärprodukte als die im Bereich von Ganzzahlen codierten Bits 0..<2**nund verwendet vektorisierte Funktionen, um rekursiv Zahlen zu entfernen, deren Bitsequenzen mit den angegebenen Filtern übereinstimmen.

Die Speichereffizienz ist besser als die Zuweisung aller [True, False]kartesischen Produkte, da jeder Boolesche Wert mit jeweils mindestens 8 Bit gespeichert wird (wobei 7 Bit mehr als erforderlich verwendet werden), jedoch mehr Speicher als bei einem iteratorbasierten Ansatz verwendet wird. Wenn Sie eine Lösung für große nBereiche benötigen , können Sie diese Aufgabe aufschlüsseln, indem Sie jeweils einen Teilbereich zuweisen und bearbeiten. Ich hatte dies in meiner ersten Implementierung, aber es bot nicht viel Nutzen für n<=22und es erforderte die Berechnung der Größe des Ausgabearrays, was kompliziert wird, wenn es überlappende Filter gibt.

Seb
quelle
Das ist wirklich erstaunlich!
McSoini
1

Basierend auf @ ayhans Kommentar habe ich eine SAT-basierte Lösung für or-tools implementiert. Obwohl die Idee großartig ist, kämpft dies wirklich um eine größere Anzahl von binären Variablen. Ich vermute, dass dies großen IP-Problemen ähnelt, die auch kein Spaziergang im Park sind. Die starke Abhängigkeit von Filternummern könnte dies jedoch zu einer gültigen Option für bestimmte Parameterkonfigurationen machen. Aber als allgemeine Lösung würde ich es nicht verwenden.

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

Geben Sie hier die Bildbeschreibung ein

mcsoini
quelle