Pythonを使ってネストしたテーブル構造から最終的な親を特定する方法は？

Question

私は、次の表を持っている：

私の質問は：私はプログラム的に究極の親をどのように識別していますか？ここ

ルールは、例えばを通して説明されている：

• をID 5.0の親が51.0あります。 id 51.0には親がありません。したがって、id 5.0の最終的な親は51.0です。
• id 6.0の親は1.0です。 id 1.0の親は10.0です。 id 10.0には親がありません。したがって、id 6.0の最終的な親は10.0です。
• id 2.0には親がありません。したがって、2.0のための究極のPARENT_IDがありIDフィールドには重複していないと私はID構造であっ可能性が事前にどのように多くのレベルのネストの知らない2.0

です。ここで

は、この例のコードである：ここでは、そのファイルを生成するためのコードがある

：ここ

import pandas as pd 
import numpy as np 

original_df = pd.DataFrame({'id': pd.Series([5., 6, 2, 51, 1, 70, 10]) 
       ,'parent_id': pd.Series([51, 1, np.nan, np.nan, 10, np.nan, np.nan])}) 
original_df['ultimate_parent_id'] = '' 
original_df 

は、最終的なテーブルがどのように見えるかです。

final_df = pd.DataFrame({'id': pd.Series([5., 6, 2, 51, 1, 70, 10]) 
       ,'parent_id': pd.Series([51, 1, np.nan, np.nan, 10, np.nan, np.nan])}) 
final_df['ultimate_parent_id'] = pd.Series([51., 10, 2, 51, 10, 70, 10]) 
final_df 

可能であれば、whileループを使用するソリューションと、ベクトル化された操作を使用するソリューションの両方に非常に興味があります。

Answer 1

ここでは、mapとcombine_firstを使用した1つのソリューションがあります。まず、マッピングのためにdf値から辞書を作成します。今度はparent_idのmapを使ってそれらの値を最初にマッピングし、mapを使って値をidにマップします。 Combine_firstは、parent_idからマッピングされた値が優先されるようにします。最終的にcombine_firstでNaNの値をidで埋める。

d = final_df.dropna().set_index('id').to_dict() 
final_df['ultimate_parent_id'] = 
final_df['parent_id'].map(d['parent_id'])\ 
.combine_first(final_df['id'].map(d['parent_id']))\ 
.combine_first(final_df['id']) 

あなたは

id  parent_id ultimate_parent_id 
0 5.0  51.0  51.0 
1 6.0  1.0   10.0 
2 2.0  NaN   2.0 
3 51.0 NaN   51.0 
4 1.0  10.0  10.0 
5 70.0 NaN   70.0 
6 10.0 NaN   10.0 

Answer 2

てみましょう最初のクリーンアップのデータフレームを取得し、nan Sを取り除きます。負の数は、良い代替です：

original_df = original_df.fillna(-1).astype(int) 

辞書にデータフレームを変換します

d = original_df.set_index('id').to_dict()['parent_id'] 
#{1: 10, 2: -1, 51: -1, 5: 51, 6: 1, 10: -1, 70: -1} 

は今、あなたは究極の親IDにIDを変換するために再帰関数が必要になります。

def translate(x): 
    return x if d[x] == -1 else translate(d[x]) 

各辞書キーに再帰関数を適用し、結果を別のDataFrameに収集します。

ultimate = pd.DataFrame(pd.Series({x: translate(x) for x in d.keys()}), 
       columns=('ultimate_parent_id',)) 

元のデータフレームで結果を組み合わせる：Vaishaliのの答え@と同じ静脈で

original_df.merge(ultimate, left_on='id', right_index=True) 

# id parent_id ultimate_parent_id 
#0 5   51     51 
#1 6   1     10 
#2 2   -1     2 
#3 51   -1     51 
#4 1   10     10 
#5 70   -1     70 
#6 10   -1     10 

Answer 3

は、ここでは主要な操作をループのPythonを使用したバージョンですが、データフレーム内np/pd操作を使用しています。

import pandas as pd 
import numpy as np 

df = pd.DataFrame(
     { 'id': pd.Series([5., 6, 2, 51, 1, 70, 10]), 
     'parent_id': pd.Series([51, 1, np.nan, np.nan, 10, 51, np.nan]) 
     } 
    ) 

def find_ultimate_parents(df): 
    # Make a copy of df, using 'id' as the index so we can lookup parent ids 
    df2 = df.set_index(df['id']) 
    df2['nextpar'] = df2['parent_id'] 

    # Next-parent-2 not null - fake it for now 
    np2nn = df2['nextpar'].notnull() 

    while np2nn.any(): 
     # Lookup df2[parent-id], since the index is now by id. Get the 
     # parent-id (of the parent-id), put that value in nextpar2. 
     # So basically, if row B.nextpar has A, nextpar2 has (parent-of-A), or Nan. 

     # Set na_action='ignore' so any Nan doesn't bother looking up, just copies 
     # the Nan to the next generation. 
     df2['nextpar2'] = df2['nextpar'].map(df2['parent_id'], na_action='ignore') 

     # Re-evaluate who is a Nan in the nextpar2 column. 
     np2nn = df2['nextpar2'].notnull() 

     # Only update nextpar from nextpar2 if nextpar2 is not a Nan. Thus, stop 
     # at the root. 
     df2.loc[np2nn, 'nextpar'] = df2[np2nn]['nextpar2'] 

    # At this point, we've run out of parents to look up. df2['nextpar'] has 
    # the "ultimate" parents. 

    return df2['nextpar'] 


df['ultimate_parent_id'] = find_ultimate_parents(df) 
print(df) 

ブールシリーズのベクターOPでループガードをチェックnp2nn.any()。ループを通過するたびに「次の親」が検索されるため、ループを通過する回数は子 - 親チェーンの最大深度になります。 O（N）、の最悪の場合は、1-> 2-> 3-> 4-> ...-> nのようになります。親を持たないリストの場合、最良のケースは0です。

ループは、na_action='ignore'と.mapで、単純にNan値を伝播します。これはO（fast-N）回インデックス検索のコストです。はになるO（1）です。計算nextpar2フィールドに

、再びO（高速-N）である単純な.notnull()使用ループ再計算するnp2nn。

最後に、nextparフィールドは再びO（高速-N）であるべきnextpar2,から更新されます。

したがって、最悪の場合のパフォーマンスはN²あるO（スロー-N *の高速-N）、はあるが、それはパンダ-N²、ないのPython-N²です。平均ケースはO（低速*高速N）mは平均の場合の最大樹木の深さであり、最良の場合は行を1速く通過するためにO（fast-N）です。