Какой самый быстрый способ сделать жадный набор прикрытием пандами?

Question

Этот вопрос не совсем совпадает с проблемой покрытия жадных множеств, но они разделяют ту же идею.

Для данного Pandas dataframe df1 с одним столбцом df['s'] состоит из набора ключей df2:

import numpy as np
import pandas as pd
>>> df = pd.DataFrame(np.array([set([1,3,5]), set([1,3,5,6]), set([2,3,4,12]), set([1,3,7]), set([1,15,11]), set([1,16]), set([16])]),columns=['s'])
>>> df
                    s
0      set([1, 3, 5])
1   set([1, 3, 5, 6])
2  set([12, 2, 3, 4])
3      set([1, 3, 7])
4    set([1, 11, 15])
5        set([1, 16])
6           set([16])
        ...

>>> df2 = pd.DataFrame(np.array([[1,2,3,3,3,6,4,8,9,10,11,12,13,14,15,16,5,7],[2.,1.,3.,2.,1.,2.,3.,1.,1.,1.,1.,1.,1.,1.,1.,16.,1.,1.]]).T,columns=['key', 'value'])
>>> df2
    key  value
0     1      2
1     2      1
2     3      3
3     3      2
4     3      1
5     6      2
6     4      3
7     8      1
8     9      1
9    10      1
10   11      1
11   12      1
12   13      1
13   14      1
14   15      1
15   16     16
16    5      1
17    7      1

    ...

Фрейм данных df2 выше может содержать дубликаты ключей. Мы выбираем последний. Например, выберите значение "1.0" для клавиши "3" выше.

Я хочу найти шесть верхних строк df['s'], которые могут максимально суммировать значения соответствующих им ключей, и отсортировать строки нового информационного кадра по их вкладу в значение. Какой самый быстрый способ сделать это?

Для приведенного выше набора данных первые две строки результирующего кадра данных должны быть

df3:
    set([1,16])
    set([12,2,3,4])
    ...

Второе выше не установлено ([16]), потому что "16" уже содержится в наборе ([1,16]), а добавленное значение равно нулю от набора ([16]).

отсортировано по сумме соответствующих значений ключей набора.

Обновить:

Чтобы упростить эту проблему, давайте рассмотрим, что df2 содержит только уникальные ключи. И это может быть легко исправлено на основе трюка Эндрю.

Answer 1

Предполагая, что у вас не слишком много ключей, вы можете представить свой список наборов в виде разреженной матрицы с колонкой для каждого ключа.

In [29]: df = pd.DataFrame([{1:1,3:1,5:1}, {1:1,3:1,5:1,6:1}, {2:1,3:1,4:1,12:1}, {1:1,3:1,7:1}, {1:1,15:1,11:1}, {9:1}, {16:1}]).fillna(0)

In [30]: df
Out[30]: 
   1   2   3   4   5   6   7   9   11  12  15  16
0   1   0   1   0   1   0   0   0   0   0   0   0
1   1   0   1   0   1   1   0   0   0   0   0   0
2   0   1   1   1   0   0   0   0   0   1   0   0
3   1   0   1   0   0   0   1   0   0   0   0   0
4   1   0   0   0   0   0   0   0   1   0   1   0
5   0   0   0   0   0   0   0   1   0   0   0   0
6   0   0   0   0   0   0   0   0   0   0   0   1

А затем представьте ваши веса в виде Серии, проиндексированной по ключу:

In [37]: weights = df2.drop_duplicates('key', keep='last').set_index('key')['value']

Затем взвесьте и суммируйте ваши множества:

In [40]: totals = (df * weights).sum(axis=1)

In [41]: totals
Out[41]: 
0     4
1     6
2     6
3     4
4     4
5     1
6    16
dtype: float64

А затем просто найдите 6 верхних рядов:

In [55]: top6 = totals.order(ascending=False).head(6)

In [56]: top6
Out[56]: 
6    16
2     6
1     6
4     4
3     4
0     4
dtype: float64

Вы можете использовать индексы обратно в разреженную матрицу, чтобы восстановить, какие наборы были:

In [58]: df.ix[top6.index]
Out[58]: 
   1   2   3   4   5   6   7   9   11  12  15  16
6   0   0   0   0   0   0   0   0   0   0   0   1
2   0   1   1   1   0   0   0   0   0   1   0   0
1   1   0   1   0   1   1   0   0   0   0   0   0
4   1   0   0   0   0   0   0   0   1   0   1   0
3   1   0   1   0   0   0   1   0   0   0   0   0
0   1   0   1   0   1   0   0   0   0   0   0   0

Возможно, вам не понравится этот подход, но я хотел бы отметить, что наличие фреймов структур данных, таких как наборы, а не примитивы, поскольку элементы не особенно подходят для панд, поэтому рекомендуется некоторая трансляция проблемы.