批处理新手入门导读[视频教程]批处理基础视频教程[视频教程]VBS基础视频教程
[批处理文件精品]批处理版照片整理器[批处理文件精品]纯批处理备份&还原驱动在线第三方下载
返回列表 发帖
本帖最后由 523066680 于 2021-12-18 19:41 编辑

原来写的方案之一
      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 中相应的引用位置。
于是:
  1.     if ( not exists $ref->{$foo}{$bar} )
  2.     {      
  3.         $ref->{$foo}{$bar} = {};              # $ref->{$foo} 得到 $tree 中 $foo 键的引用,新增{$bar}子键的操作直接作用于 $tree 的对应节点
  4.         $ref->{$bar} = $ref->{$foo}{$bar};    # 将 $bar 节点更新到引用表单
  5.     }
复制代码
优点是关联数据的表单可以随意打乱,最终都能得到完整结果。
缺点是需要确保表单中的层级(第四项)是升序的,这个通过 sort { $a->[3] <=> $b->[3] } @{$data->{data}} 对层级排序,
以及空间复杂度比15楼多了一个n

TOP

回复 15# 523066680


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

TOP

本帖最后由 523066680 于 2021-12-19 19:24 编辑

回复 13# netbenton

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


15楼代码 1.3秒
16楼代码 2.2秒
  1. use Modern::Perl;
  2. use File::Slurp;
  3. use Time::HiRes qw/time/;
  4. use JSON qw/from_json/;
  5. use feature 'signatures';
  6. no warnings 'experimental::signatures';
  7. STDOUT->autoflush(1);
  8. my $ta = time();
  9. my $n = 0;
  10. open my $FH, ">:raw", "Category_Tree_benton.json";
  11. say $FH "{";
  12. my %hash;
  13. my $prev;
  14. my $raw = read_file( "gener_big.json" );
  15. my $data = from_json( $raw, {relaxed => 1} );
  16. for my $e ( @{$data->{data}} )
  17. {
  18.     my ( $parent, $child, $label, $lv ) = @$e;
  19.     next unless defined $lv;
  20.     if ( $n < $lv )
  21.     {
  22.         if ( not defined $hash{$parent} )
  23.         {
  24.             say $FH "\t"x$lv, qq("$parent"), ":{";
  25.             $hash{$parent} = 1;
  26.         }
  27.         else
  28.         {
  29.             say $FH "\t"x($lv+1), $child;
  30.         }
  31.         $prev = $child;
  32.         $n = $lv;
  33.     }
  34.     elsif ( $n > $lv )
  35.     {
  36.         my $m = $lv + 1;
  37.         for my $e ( reverse ($m .. $n)  )
  38.         {
  39.             if ( defined $prev ) {
  40.                 say $FH "\t"x($e+1), qq("$prev"), ":{}" ;
  41.                 undef $prev;
  42.             }
  43.             say $FH "\t"x$e, "},";
  44.             $n = $lv;
  45.         }
  46.         $prev = $child;
  47.     }
  48.     else
  49.     {
  50.         if ( defined $prev ) {
  51.             say $FH "\t"x($lv+1), qq("$prev"), ":{},";
  52.         }
  53.         $prev = $child;
  54.     }
  55. }
  56. if ( defined $prev )
  57. {
  58.     say $FH "\t"x$n, qq("$prev"), ":{}";
  59.     undef $prev;
  60. }
  61. # 收尾
  62. grep { say $FH "\t"x$_, "}"; } reverse ( 0 .. $n );
  63. close $FH;
  64. time_delta(\$ta);
  65. sub time_delta ($t)
  66. {
  67.     printf "Time Delta: %.2f\n", time() - $$t;
  68.     $$t = time();
  69. }
复制代码
1

评分人数

TOP

返回列表