Генерация отфильтрованных бинарных декартовых продуктов

12

Постановка задачи

Я ищу эффективный способ генерирования полных двоичных декартовых продуктов (таблиц со всеми комбинациями True и False с определенным числом столбцов), отфильтрованных по определенным исключительным условиям. Например, для трех столбцов / битов n=3мы получили бы полную таблицу

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

Предполагается, что это будет отфильтровано словарями, определяющими взаимоисключающие комбинации следующим образом:

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

Где ключи обозначают столбцы в таблице выше. Пример будет читаться как:

  • Если 0 - Ложь, а 1 - Ложь, 2 не может быть Истиной
  • Если 0 истинно, 2 не может быть истинно

На основе этих фильтров ожидаемый результат:

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

В моем случае использования отфильтрованная таблица на несколько порядков меньше, чем полное декартово произведение (например, около 1000 вместо 2**24 (16777216)).

Ниже представлены три моих текущих решения, каждое со своими плюсами и минусами, которые обсуждались в самом конце.

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

Решение 1. Сначала отфильтруйте, затем объедините.

Разверните каждую отдельную запись фильтра (например, {0: True, 2: True}) во вложенную таблицу со столбцами, соответствующими индексам в этой записи фильтра ( [0, 2]). Удалить одну отфильтрованную строку из этой вложенной таблицы ( [True, True]). Слияние с полной таблицей, чтобы получить полный список отфильтрованных комбинаций.

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

Решение 2: полное расширение, затем фильтр

Генерация DataFrame для полного декартова продукта: все это попадает в память. Прокрутите фильтры и создайте маску для каждого. Примените каждую маску к столу.


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

Решение 3: Итератор фильтра

Держите полный декартовой продукт итератором. Цикл, проверяя для каждой строки, исключен ли он каким-либо из фильтров.

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

Выполнить примеры

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

Анализ

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

введите описание изображения здесь

Решение 3 : Подход, основанный на итераторах ( comb_iterator), имеет мрачное время выполнения, но не требует значительного использования памяти. Я чувствую, что есть место для улучшений, хотя неизбежный цикл, вероятно, накладывает жесткие ограничения с точки зрения времени выполнения.

Решение 2. Расширение полного декартова произведения в DataFrame ( exp_filt) приводит к значительным скачкам в памяти, которых я хотел бы избежать. Время работы в порядке, хотя.

Решение 1 : Объединение DataFrames, созданных из отдельных фильтров ( filt_merge), кажется хорошим решением для моего практического применения (обратите внимание на сокращение времени работы для большего количества фильтров, что является результатом меньшей cols_missingтаблицы). Тем не менее, этот подход не совсем удовлетворителен: если один фильтр включает все столбцы, весь декартово произведение ( 2**n) окажется в памяти, что делает это решение хуже, чем comb_iterator.

Вопрос: есть еще идеи? Сумасшедший умный NumPy двухлинейный? Можно ли как-то улучшить подход, основанный на итераторах?

python pandas dataframe mcsoini
источник
1
Решатели ограничений, вероятно, превзойдут эти подходы, потому что они находят эти решения за счет сокращения пространства поиска. Может быть, взглянуть на или инструменты. Вот пример для SAT.
Айхан
1
@ayhan, я пытался (см. ответ). Это интересный подход, но не совсем подходящий в качестве общего решения. Спасибо за вклад. Я кое-что узнал :)
mcsoini
Да, это звучит как проблема SAT , поэтому вам обязательно следует использовать решатель, если проблема достаточно велика. Вы также можете попробовать or.stackexchange.com
Страдивари
Формулировка @Stradivari как проблема SAT определенно имеет смысл. Мне не нравится сильная зависимость от количества фильтров этого подхода. Возможно, я не получаю доступ к решениям должным образом. Так как вы
mcsoini

Ответы:

1

Попробуйте рассчитать следующее:

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]

Он рассматривает декартовы двоичные произведения как биты, закодированные в диапазоне целых чисел, 0..<2**nи использует векторизованные функции для рекурсивного удаления чисел, битовые последовательности которых соответствуют заданным фильтрам.

Эффективность памяти лучше, чем выделение всех [True, False]декартовых произведений, поскольку каждый логический тип будет храниться не менее чем с 8 битами (используя на 7 бит больше, чем требуется), но он будет использовать больше памяти, чем подход на основе итераторов. Если вам требуется решение для большого размера n, вы можете разбить эту задачу, выделяя и работая в одном поддиапазоне за раз. У меня это было в моей первой реализации, но это не принесло больших преимуществ, n<=22и потребовалось вычисление размера выходного массива, что усложняется при наличии перекрывающихся фильтров.

Себ
источник
Это действительно потрясающе!
Максоини
1

На основе комментария @ ayhan я реализовал решение на основе SAT or-tools. Хотя идея великолепна, она действительно борется за большее количество бинарных переменных. Я подозреваю, что это похоже на большие проблемы с IP, которые не являются прогулкой в ​​парке. Однако сильная зависимость от номеров фильтров может сделать эту опцию допустимой для определенных конфигураций параметров. Но в качестве общего решения я бы не стал его использовать.

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

введите описание изображения здесь

mcsoini
источник