Hasilkan produk kartesian biner yang difilter

12

Pernyataan masalah

Saya mencari cara yang efisien untuk menghasilkan produk kartesian biner penuh (tabel dengan semua kombinasi Benar dan Salah dengan sejumlah kolom), difilter oleh kondisi eksklusif tertentu. Sebagai contoh, untuk tiga kolom / bit n=3kita akan mendapatkan tabel lengkap

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

Ini seharusnya difilter oleh kamus yang mendefinisikan kombinasi yang saling eksklusif sebagai berikut:

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

Di mana tombol menunjukkan kolom pada tabel di atas. Contohnya akan dibaca sebagai:

  • Jika 0 salah dan 1 salah, 2 tidak mungkin benar
  • Jika 0 Benar, 2 tidak bisa Benar

Berdasarkan filter ini, output yang diharapkan adalah:

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

Dalam kasus penggunaan saya, tabel yang disaring adalah beberapa urutan besarnya lebih kecil dari produk kartesius penuh (misalnya beberapa 1000 bukannya 2**24 (16777216)).

Di bawah ini adalah tiga solusi saya saat ini, masing-masing dengan pro dan kontra mereka sendiri, yang dibahas pada bagian paling akhir.

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

Solusi 1: Saring dulu, lalu gabungkan.

Rentangkan setiap entri filter tunggal (misalnya {0: True, 2: True}) ke dalam sub-tabel dengan kolom yang sesuai dengan indeks dalam entri filter ini ( [0, 2]). Hapus satu baris yang difilter dari sub-tabel ini ( [True, True]). Gabungkan dengan tabel lengkap untuk mendapatkan daftar lengkap kombinasi yang difilter.

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

Solusi 2: Ekspansi penuh, lalu filter

Hasilkan DataFrame untuk produk kartesius lengkap: Semuanya berakhir dalam memori. Ulangi filter dan buat masker untuk masing-masing. Oleskan setiap topeng ke tabel.


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

Solusi 3: Filter iterator

Jaga agar produk kartesian lengkap menjadi iterator. Ulangi sambil memeriksa untuk setiap baris apakah dikecualikan oleh salah satu filter.

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

Jalankan contoh

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

Analisis

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

masukkan deskripsi gambar di sini

Solusi 3 : Pendekatan berbasis iterator ( comb_iterator) memiliki waktu menjalankan yang suram, tetapi tidak menggunakan memori secara signifikan. Saya merasa ada ruang untuk perbaikan, meskipun loop yang tak terhindarkan cenderung memaksakan batas keras dalam hal waktu berjalan.

Solusi 2 : Memperluas produk kartesius penuh ke dalam DataFrame ( exp_filt) menyebabkan lonjakan signifikan dalam memori, yang ingin saya hindari. Waktu berlari tidak apa-apa.

Solusi 1 : Menggabungkan DataFrames yang dibuat dari masing-masing filter ( filt_merge) terasa seperti solusi yang baik untuk aplikasi praktis saya (perhatikan pengurangan waktu berjalan untuk lebih banyak filter, yang merupakan hasil dari cols_missingtabel yang lebih kecil ). Namun, pendekatan ini tidak sepenuhnya memuaskan: Jika filter tunggal mencakup semua kolom, seluruh produk kartesius ( 2**n) akan berakhir di memori, membuat solusi ini lebih buruk daripada comb_iterator.

Pertanyaan: Ada ide lain? Dua-liner pintar pintar gila? Bisakah pendekatan berbasis iterator ditingkatkan entah bagaimana?

python pandas dataframe mcsoini
sumber
1
Pemecah kendala mungkin akan mengungguli pendekatan ini karena mereka menemukan solusi ini dengan mengurangi ruang pencarian. Mungkin lihat atau-alat. Ini contoh untuk SAT.
ayhan
1
@ayhan, saya mencoba (lihat jawaban). Ini pendekatan yang menarik, tetapi tidak benar-benar cocok sebagai solusi umum. Terima kasih atas masukannya. Saya belajar sesuatu :)
mcsoini
Ya, ini terdengar seperti masalah SAT , jadi Anda harus menggunakan solver jika masalahnya cukup besar. Anda juga dapat mencoba or.stackexchange.com
Stradivari
Formulasi @ Stradivari sebagai masalah SAT pasti masuk akal. Saya tidak suka ketergantungan yang kuat pada jumlah filter dari pendekatan ini. Mungkin saya tidak mengakses solusi dengan benar. Karena Anda tahu jalan atau-alat, mungkin Anda ingin melihat pertanyaan saya yang sesuai ... masih tidak memiliki jawaban yang diterima;)
mcsoini

Jawaban:

1

Coba waktu berikut ini:

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]

Ini memperlakukan produk biner Cartesian sebagai bit yang dikodekan dalam kisaran bilangan bulat 0..<2**ndan menggunakan fungsi vektor untuk secara rekursif menghapus angka yang memiliki urutan bit yang cocok dengan filter yang diberikan.

Efisiensi memori lebih baik daripada mengalokasikan semua [True, False]produk Cartesian karena setiap Boolean akan disimpan setidaknya masing-masing 8 bit (menggunakan 7 bit lebih banyak dari yang dibutuhkan), tetapi akan menggunakan lebih banyak memori daripada pendekatan berbasis iterator. Jika Anda membutuhkan solusi untuk ukuran besar n, Anda dapat menguraikan tugas ini dengan mengalokasikan dan beroperasi pada satu sub-rentang sekaligus. Saya memang memiliki ini dalam implementasi pertama saya, tetapi tidak menawarkan banyak manfaat untuk n<=22dan diperlukan perhitungan ukuran array output, yang menjadi rumit ketika ada tumpang tindih filter.

Seb
sumber
Ini sungguh menakjubkan!
mcsoini
1

Berdasarkan komentar @ ayhan, saya menerapkan solusi berbasis-or-tools SAT. Walaupun idenya bagus, ini benar-benar memperjuangkan jumlah variabel biner yang lebih besar. Saya menduga ini mirip dengan masalah IP besar, yang tidak berjalan di taman juga. Namun, ketergantungan yang kuat pada nomor filter dapat menjadikan ini opsi yang valid untuk konfigurasi parameter tertentu. Tetapi sebagai solusi umum saya tidak akan menggunakannya.

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

masukkan deskripsi gambar di sini

mcsoini
sumber