python - 如何使用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 是 2.0

id 字段中没有重复项，而且我事先不知道 id 结构中可能有多少层嵌套。

下面是这个例子的代码:

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

决赛 table 应该是这样的:

这是生成该文件的代码。

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

与@Vaishali 的回答一样，这是一个使用 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)

循环守卫检查 np2nn.any()，它是 bool 系列上的向量操作。每次通过循环查找“下一个父”，因此通过循环的次数将是任何子父链的最大深度。 O(N) 中的最坏情况，如 1->2->3->4->...->n。对于没有 parent 的列表，最好的情况是 0。

循环使用 na_action='ignore' 执行 .map 以简单地传播 Nan 值。这是索引查找成本的 O(fast-N) 倍，应该为 O(1)。

随着 nextpar2 字段的计算，循环使用简单的 .notnull() 重新计算 np2nn，这又是 O (快-N)。

最后，nextpar 字段从 nextpar2 更新，同样应该是 O(fast-N)。

因此，最坏情况下的性能是O(slow-N * fast-N)，即N²，但它是 Pandas-N²，而不是 Python- N²。平均情况应该是 O(slow-m * fast-N) 其中 m 是平均情况的最大树深度，最好的情况是 O(fast -N) 1 次快速通过行。