Obtenez ensemble aléatoire de lignes de PCollection

Question

J'ai un ensemble de données de la forme

user_id, date, other_columns 
1, 2017-03-10, ... 
2, 2017-03-10, ... 
3, 2017-03-10, ... 
... 

et je dois faire ce qui suit: Pour chaque ligne de l'ensemble de données que je veux générer une nouvelle ligne qui contiendra le ligne courante et un sous-ensemble aléatoire de lignes N pour le même jour correspondant aux différents utilisateurs comme suit:

row, other_rows 
{'user_id': 1, 'date': '2017-03-10', ...}, [{'user_id': 2,...},...] 
{'user_id': 2, 'date': '2017-03-10', ...}, [{'user_id': 1,...},...] 
... 

Je l'ai mis en œuvre comme suit, mais il est très lent pour les grands ensembles de données lorsque exécuté sur le nuage.

dataset 
| 'map-to-date' >> beam.Map(lambda x: (x['date'], x)) 
| 'group-by-date' >> beam.GroupByKey() 
| 'generate-output' >> beam.ParDo(GenerateOutputRows()) 

où GenerateOutputRows est défini comme:

class GenerateOutputRows(beam.DoFn): 
    def process(self, element): 
     (date, rows) = element 
     for r in rows: 
      other_users_rows = list(filter(lambda x: x['user_id'] != r['user_id'], 
              rows)) 
      yield (r, random.sample(other_users_rows, N)) 

Pouvez-vous penser à une autre façon pour obtenir plus performant le résultat désiré?

Answer 1

Je ne vois pas immédiatement façon plus efficace algorithmiquement de le faire, à moins que vous pouvez fournir quelques hypothèses simplificatrices, par exemple:

• à moins de 1 jour, est user_id unique, ou peut-il y avoir plusieurs lignes avec le même utilisateur?
• Si oui, alors plusieurs échantillons de other_users_rows pour le même utilisateur doivent-ils être statistiquement indépendants? Si non, vous pouvez utiliser une mise en cache et réutiliser le même échantillon plusieurs fois pour les lignes ayant le même id_utilisateur. Les exemples other_users_rows pour différents utilisateurs doivent-ils être statistiquement indépendants, ou si, par exemple, un échantillon pour l'utilisateur A n'inclut pas l'utilisateur B, alors il est correct d'utiliser exactement le même échantillon pour l'utilisateur B?

En général, c'est une question algorithmiques plutôt qu'une question faisceau nuage Dataflow/Apache, parce que le goulot d'étranglement de votre code est la boucle O (rows.size()^2) à l'intérieur GenerateOutputRows et du faisceau ne peut pas faire c'est plus rapide automatiquement; Je recommanderais d'aller à http://cstheory.stackexchange.com pour des recommandations sur un algorithme plus efficace.