523066680

原来写的方案之一

use File::Slurp; use JSON::PP; my $json = JSON::PP->new->relaxed->pretty->canonical(); my $raw = read_file( "Category_Plain.json" ); my $data = $json->decode( $raw ); my $tree = { 0 => {} }; my $ref = { 0 => $tree->{0} }; for my $e ( sort { $a->[3] <=> $b->[3] } @{$data->{data}} ) {     my ($foo, $bar, $desc, $lv) = @$e;     if ( not exists $ref->{$foo}{$bar} )     {               $ref->{$foo}{$bar} = {};         $ref->{$bar} = $ref->{$foo}{$bar};     } } printf "%s\n",  $json->encode( $tree );

$tree 是将要创建的结构体
$ref 是一个协助构建$tree层级关系的哈希表。考虑类目所有ID的唯一性，所有ID都可以通过 $ref->{$id} 查到对应 $tree 中相应的引用位置。
于是：

    if ( not exists $ref->{$foo}{$bar} )
    {       
        $ref->{$foo}{$bar} = {};              # $ref->{$foo} 得到 $tree 中 $foo 键的引用，新增{$bar}子键的操作直接作用于 $tree 的对应节点
        $ref->{$bar} = $ref->{$foo}{$bar};    # 将 $bar 节点更新到引用表单
    }
复制代码

优点是关联数据的表单可以随意打乱，最终都能得到完整结果。
缺点是需要确保表单中的层级(第四项)是升序的，这个通过 sort { $a->[3] <=> $b->[3] } @{$data->{data}} 对层级排序，
以及空间复杂度比15楼多了一个n

flashercs

回复 15# 523066680


    数据来源应该可以控制是树的遍历顺序是 pre-order 或post-order; 固定pre-order 就可以用此法.

523066680

回复 13# netbenton

    把你的方案翻译成其他语言，加载改用JSON解析器一次性加载（逐行解析相对耗时）
处理过程是复刻你的逻辑，实测70W行数据只需要0.9秒完成输出（到文件）


15楼代码 1.3秒
16楼代码 2.2秒

use Modern::Perl;
use File::Slurp;
use Time::HiRes qw/time/;
use JSON qw/from_json/;
use feature 'signatures';
no warnings 'experimental::signatures';
STDOUT->autoflush(1);

my $ta = time();
my $n = 0;
open my $FH, ">:raw", "Category_Tree_benton.json";
say $FH "{";

my %hash;
my $prev;
my $raw = read_file( "gener_big.json" );
my $data = from_json( $raw, {relaxed => 1} );

for my $e ( @{$data->{data}} )
{
    my ( $parent, $child, $label, $lv ) = @$e;
    next unless defined $lv;

    if ( $n < $lv )
    {
        if ( not defined $hash{$parent} )
        {
            say $FH "\t"x$lv, qq("$parent"), ":{";
            $hash{$parent} = 1;
        }
        else
        {
            say $FH "\t"x($lv+1), $child;
        }
        $prev = $child;
        $n = $lv;
    } 
    elsif ( $n > $lv )
    {
        my $m = $lv + 1;
        for my $e ( reverse ($m .. $n)  ) 
        {
            if ( defined $prev ) {
                say $FH "\t"x($e+1), qq("$prev"), ":{}" ;
                undef $prev;
            }
            say $FH "\t"x$e, "},";
            $n = $lv;
        }
        $prev = $child;
    }
    else
    {
        if ( defined $prev ) {
            say $FH "\t"x($lv+1), qq("$prev"), ":{},";
        }
        $prev = $child;
    }
}

if ( defined $prev )
{
    say $FH "\t"x$n, qq("$prev"), ":{}";
    undef $prev;
}

# 收尾
grep { say $FH "\t"x$_, "}"; } reverse ( 0 .. $n );
close $FH;

time_delta(\$ta);

sub time_delta ($t)
{
    printf "Time Delta: %.2f\n", time() - $$t;
    $$t = time();
}
复制代码

tigerpower

升级、降级、跳级都可以。打乱列表次序也可以。

#python 3
import json, networkx as nx
with open("Category_Plain.json") as f:
    el = [i[:2] for i in json.load(f)['data']]
    g = nx.from_edgelist(el, create_using=nx.DiGraph())
    print(json.dumps(nx.tree_data(g, root=0), indent=2))
复制代码