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

Question

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

Учитывая Пандас 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 

    ... 

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

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

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

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 

Вы не могли бы этот подход, но я хотел бы отметить, имеющие рамки структур данных, таких как наборы, а не примитивы, как элементы не особенно панды-иш , поэтому рекомендуется перевод этой проблемы.