当前位置: 首页 > 面试题库 >

分层数据:为每个节点有效地构建每个后代的列表

艾雪风
2023-03-14
问题内容

我有两列数据集,描述了形成一棵大树的多个子父母关系。我想使用它为每个节点建立每个后代的更新列表。

原始输入:

   child  parent
1   2010    1000
7   2100    1000
5   2110    1000
3   3000    2110
2   3011    2010
4   3033    2100
0   3102    2010
6   3111    2110

关系的图形描述:

<a href=示例数据关系树" src="https://imgs.xnip.cn/cj/l/13/fd3109c6-16cc-4cdc-bd7a-ca3d3145d288.jpg" />

预期产量:

    descendant  ancestor
0         2010      1000
1         2100      1000
2         2110      1000
3         3000      1000
4         3011      1000
5         3033      1000
6         3102      1000
7         3111      1000
8         3011      2010
9         3102      2010
10        3033      2100
11        3000      2110
12        3111      2110

最初,我决定对DataFrames使用递归解决方案。它可以按预期工作,但是Pandas效率很低。我的研究使我相信,使用NumPy数组(或其他简单数据结构)的实现在大型数据集(成千上万的记录中有10个)上会快得多。

使用数据帧的解决方案:

import pandas as pd

df = pd.DataFrame(
    {
        'child':     [3102, 2010, 3011, 3000, 3033, 2110, 3111, 2100],
        'parent':    [2010, 1000, 2010, 2110, 2100, 1000, 2110, 1000]
    },  columns=['child', 'parent']
)


def get_ancestry_dataframe_flat(df):

    def get_child_list(parent_id):

        list_of_children = list()
        list_of_children.append(df[df['parent'] == parent_id]['child'].values)

        for i, r in df[df['parent'] == parent_id].iterrows():
            if r['child'] != parent_id:
                list_of_children.append(get_child_list(r['child']))

        # flatten list
        list_of_children = [item for sublist in list_of_children for item in sublist]
        return list_of_children

    new_df = pd.DataFrame(columns=['descendant', 'ancestor']).astype(int)
    for index, row in df.iterrows():
        temp_df = pd.DataFrame(columns=['descendant', 'ancestor'])
        temp_df['descendant'] = pd.Series(get_child_list(row['parent']))
        temp_df['ancestor'] = row['parent']
        new_df = new_df.append(temp_df)

    new_df = new_df\
        .drop_duplicates()\
        .sort_values(['ancestor', 'descendant'])\
        .reset_index(drop=True)

    return new_df

因为以这种方式使用pandas DataFrames在大型数据集上效率很低, 所以我需要提高此操作的性能。
我的理解是,这可以通过使用更适合循环和递归的更有效的数据结构来完成。我想以最有效的方式执行相同的操作。

具体来说,我要求 优化速度。


问题答案:

这是一种使用numpy一次遍历树的方法。

码:

import numpy as np
import pandas as pd  # only used to return a dataframe


def list_ancestors(edges):
    """
    Take edge list of a rooted tree as a numpy array with shape (E, 2),
    child nodes in edges[:, 0], parent nodes in edges[:, 1]
    Return pandas dataframe of all descendant/ancestor node pairs

    Ex:
        df = pd.DataFrame({'child': [200, 201, 300, 301, 302, 400],
                           'parent': [100, 100, 200, 200, 201, 300]})

        df
           child  parent
        0    200     100
        1    201     100
        2    300     200
        3    301     200
        4    302     201
        5    400     300

        list_ancestors(df.values)

        returns

            descendant  ancestor
        0          200       100
        1          201       100
        2          300       200
        3          300       100
        4          301       200
        5          301       100
        6          302       201
        7          302       100
        8          400       300
        9          400       200
        10         400       100
    """
    ancestors = []
    for ar in trace_nodes(edges):
        ancestors.append(np.c_[np.repeat(ar[:, 0], ar.shape[1]-1),
                               ar[:, 1:].flatten()])
    return pd.DataFrame(np.concatenate(ancestors),
                        columns=['descendant', 'ancestor'])


def trace_nodes(edges):
    """
    Take edge list of a rooted tree as a numpy array with shape (E, 2),
    child nodes in edges[:, 0], parent nodes in edges[:, 1]
    Yield numpy array with cross-section of tree and associated
    ancestor nodes

    Ex:
        df = pd.DataFrame({'child': [200, 201, 300, 301, 302, 400],
                           'parent': [100, 100, 200, 200, 201, 300]})

        df
           child  parent
        0    200     100
        1    201     100
        2    300     200
        3    301     200
        4    302     201
        5    400     300

        trace_nodes(df.values)

        yields

        array([[200, 100],
               [201, 100]])

        array([[300, 200, 100],
               [301, 200, 100],
               [302, 201, 100]])

        array([[400, 300, 200, 100]])
    """
    mask = np.in1d(edges[:, 1], edges[:, 0])
    gen_branches = edges[~mask]
    edges = edges[mask]
    yield gen_branches
    while edges.size != 0:
        mask = np.in1d(edges[:, 1], edges[:, 0])
        next_gen = edges[~mask]
        gen_branches = numpy_col_inner_many_to_one_join(next_gen, gen_branches)
        edges = edges[mask]
        yield gen_branches


def numpy_col_inner_many_to_one_join(ar1, ar2):
    """
    Take two 2-d numpy arrays ar1 and ar2,
    with no duplicate values in first column of ar2
    Return inner join of ar1 and ar2 on
    last column of ar1, first column of ar2

    Ex:

        ar1 = np.array([[1,  2,  3],
                        [4,  5,  3],
                        [6,  7,  8],
                        [9, 10, 11]])

        ar2 = np.array([[ 1,  2],
                        [ 3,  4],
                        [ 5,  6],
                        [ 7,  8],
                        [ 9, 10],
                        [11, 12]])

        numpy_col_inner_many_to_one_join(ar1, ar2)

        returns

        array([[ 1,  2,  3,  4],
               [ 4,  5,  3,  4],
               [ 9, 10, 11, 12]])
    """
    ar1 = ar1[np.in1d(ar1[:, -1], ar2[:, 0])]
    ar2 = ar2[np.in1d(ar2[:, 0], ar1[:, -1])]
    if 'int' in ar1.dtype.name and ar1[:, -1].min() >= 0:
        bins = np.bincount(ar1[:, -1])
        counts = bins[bins.nonzero()[0]]
    else:
        counts = np.unique(ar1[:, -1], False, False, True)[1]
    left = ar1[ar1[:, -1].argsort()]
    right = ar2[ar2[:, 0].argsort()]
    return np.concatenate([left[:, :-1],
                           right[np.repeat(np.arange(right.shape[0]),
                                           counts)]], 1)

时序比较:

@ taky2提供的测试用例1和2,测试用例3和4分别比较了高大和阔树结构的性能-大多数用例可能在中间。

df = pd.DataFrame(
    {
        'child': [3102, 2010, 3011, 3000, 3033, 2110, 3111, 2100],
        'parent': [2010, 1000, 2010, 2110, 2100, 1000, 2110, 1000]
    }
)

df2 = pd.DataFrame(
    {
        'child': [4321, 3102, 4023, 2010, 5321, 4200, 4113, 6525, 4010, 4001,
                  3011, 5010, 3000, 3033, 2110, 6100, 3111, 2100, 6016, 4311],
        'parent': [3111, 2010, 3000, 1000, 4023, 3011, 3033, 5010, 3011, 3102,
                   2010, 4023, 2110, 2100, 1000, 5010, 2110, 1000, 5010, 3033]
    }
)

df3 = pd.DataFrame(np.r_[np.c_[np.arange(1, 501), np.arange(500)],
                         np.c_[np.arange(501, 1001), np.arange(500)]],
                   columns=['child', 'parent'])

df4 = pd.DataFrame(np.r_[np.c_[np.arange(1, 101), np.repeat(0, 100)],
                         np.c_[np.arange(1001, 11001),
                               np.repeat(np.arange(1, 101), 100)]],
                   columns=['child', 'parent'])

%timeit get_ancestry_dataframe_flat(df)
10 loops, best of 3: 53.4 ms per loop

%timeit add_children_of_children(df)
1000 loops, best of 3: 1.13 ms per loop

%timeit all_descendants_nx(df)
1000 loops, best of 3: 675 µs per loop

%timeit list_ancestors(df.values)
1000 loops, best of 3: 391 µs per loop

%timeit get_ancestry_dataframe_flat(df2)
10 loops, best of 3: 168 ms per loop

%timeit add_children_of_children(df2)
1000 loops, best of 3: 1.8 ms per loop

%timeit all_descendants_nx(df2)
1000 loops, best of 3: 1.06 ms per loop

%timeit list_ancestors(df2.values)
1000 loops, best of 3: 933 µs per loop

%timeit add_children_of_children(df3)
10 loops, best of 3: 156 ms per loop

%timeit all_descendants_nx(df3)
1 loop, best of 3: 952 ms per loop

%timeit list_ancestors(df3.values)
10 loops, best of 3: 104 ms per loop

%timeit add_children_of_children(df4)
1 loop, best of 3: 503 ms per loop

%timeit all_descendants_nx(df4)
1 loop, best of 3: 238 ms per loop

%timeit list_ancestors(df4.values)
100 loops, best of 3: 2.96 ms per loop

笔记:

get_ancestry_dataframe_flat 由于时间和记忆的原因,未对情况3和4进行计时。

add_children_of_children修改为在内部标识根节点,但允许采用唯一的根。root_node = (set(dataframe.parent) - set(dataframe.child)).pop()添加第一行。

all_descendants_nx 修改为接受数据框作为参数,而不是从外部名称空间提取。

演示正确行为的示例:

np.all(get_ancestry_dataframe_flat(df2).sort_values(['descendant', 'ancestor'])\
                                       .reset_index(drop=True) ==\
       list_ancestors(df2.values).sort_values(['descendant', 'ancestor'])\
                                 .reset_index(drop=True))
Out[20]: True


 类似资料:
  • 问题内容: 如果有人可以建议每个ES节点的最佳分片数量以获得最佳性能,或者提供任何建议的方式来得出一个应该使用的分片数量(如果有核心数量和内存占用量的话),我将不胜感激。 问题答案: 分片前要考虑以下三种情况。 情况1) 您想将Elasticsearch与故障转移和高可用性一起使用。然后,您要进行分片。在这种情况下,您需要根据要在生产中使用的节点[ES实例]的数量来选择分片的数量。 考虑您要在生产

  • 我们有一个项目,其中我们有几个Jenkins作业:一种类型的作业运行交付(a), 一个只进行编译和单元测试的程序(B) 和 运行集成测试、静态代码分析等(C)的人。 我们在四个 Jenkins 节点(主节点三个从节点)上运行,我们的作业是声明性管道作业的混合,并在 Jenkins 作业中手动单击。 我们一次只想为每个节点运行一个集成测试构建。然而,我们希望运行尽可能多的交付(A)和代码质量(B)构

  • 假设我正在创建手机和平板电脑产品,标签为 然后是笔记本电脑。那么,下面

  • 目前,Jenkins 上有多个管道(A、B、C)和节点(X、Y、Z)。我们启用了 Throttle Concurrent Builds 插件,以确保管道中只有一个构建在单个节点上运行。 问题是,使用这种方法,来自不同管道的构建可能会发生冲突(例如,管道A可能已经在节点X上执行,我们不希望任何其他管道在节点X上执行,直到管道A完成)。TCB插件确保来自单个管道的多个构建不会在一个节点上运行,但它不会

  • 问题内容: 我有一个字符串列表。我想为每个字符串分配一个唯一的数字(确切的数字并不重要),并依次使用这些数字创建一个长度相同的列表。以下是我的最佳尝试,但由于以下两个原因,我不满意: 假定相同的值彼此相邻 我必须以开头列表,否则输出将不正确 我的代码: 我想使代码更通用,因此可以使用未知列表。有任何想法吗? 问题答案: 无需使用外部库(检查 EDIT 以获取解决方案),您可以按照以下步骤进行操作:

  • 问题内容: 在一些示例之后,似乎我们可以注入一个工厂,其中包含一个REST服务的终结点,如下所示 这看起来不错,但可以想象我还有其他端点,即/ users /:id和/ groups /:id,因为您可以想象到不同端点的数量将会增加。 因此,对于每个终结点,都有一个不同的工厂,这是一个好习惯。 还是有另一种推荐的方法? 我确实没有发现任何问题,但是它迫使我创建许多工厂来处理不同的端点。 确实需要任