嵌套数据结构的排序

104359176

回复 10# zhlong8


    这个代码可以处理嵌套结构，用的是递归，每次处理两层。

1. use v6;
   
2. 
   
3. my @array = ([1,'a'], [[3,'d'], [[5,'c'], [4, 'e']]], [2, 'b']);
   
4. 
   
5. say sort-list(@array).perl;
   
6. 
   
7. #=> Array.new([1, "a"], [2, "b"], [[3, "d"], [[4, "e"], [5, "c"]]])
   
8. 
   
9. sub sort-list( @list ) {
   
10.     @list = @list.sort: -> $pair {
    
11.         $pair[0] ~~ Int ?? $pair[0] !! sort-list(@$pair).[0][0];
    
12.     }
    
13. }
    

复制代码

zhlong8

回复 11# 104359176


    把3改成6呢？又或没有 [3,'d'] 这一项，直接两层数组 [ [ [ 5, 'c'], [4 , 'e'] ] ] 呢？

104359176

把 3 改成 6：

1. Array.new([1, "a"], [2, "b"], [[[4, "e"], [5, "c"]], [6, "d"]])

复制代码

取消 3 这项，就出现了问题：

1. Array.new([1, "a"], [2, "b"], [[[5, "c"], [4, "e"]]])

复制代码

zhlong8

回复 13# 104359176


    第一条结果正确很出乎意料，不会查 Perl6 的文档于是试验了下 sort 1, [0], 3, [4] 竟然能返回 [0], 1, 3, [4]，但里面有两条数据比如 [4,-10] 也只会取第一项4来排序。也就是说数组同数字比较，空数组相当于0， 否则取数组第一个元素同数字比较（这句话里包含了递归，如[[[2]]] > 0）。

    第二条结果错误/不合预期是因为只有一个元素的数组自然是不需要排序的，实际上排序时比较的key是 1  [5,'c']  2,  因为 [5, 'c'] > 2 所以出现你贴出的结果。

    我不停给你提问是因为我觉得你根本还没理解你自己提的这个问题，你能写出正确处理任意嵌套的代码吗？

jason680

回复 14# zhlong8

>> ...你根本还没理解你自己提的这个问题，...

在CU中这是"正常"的
提问者反而不知自已"真正"的问题

一直都不懂这样的sort排序 要做什么
   

drakness

   看看精彩的代码

104359176

是我没说清楚，这个问题的原型并不是单纯探讨一种算法，而是从解析 Perl 6 的 Grammar 中的 Match 的数据结构衍生出来的。所以没有考虑跨层嵌套的可能性。

至于这种 sort 办法，也不是从官方文档看看到的，是从 Rakudo 的源代码中看到的，后来从其他文档得到了证实。

1. #!perl6
   
2. 
   
3. my $str = q< say'hello' if True >;
   
4. 
   
5. grammar my-grammar {
   
6.   rule  TOP { ^ <exp> <if-exp> $ }
   
7.   token String { <.single-quote> <-[\']>+ <.single-quote> }
   
8.   token Op { say || print || sort || printf }
   
9.   token If  { unless || if || while }
   
10.   token bool { 'True' || 'False' }
    
11.   token single-quote { "'" }
    
12.   rule  exp { <Op> <String> }
    
13.   rule  if-exp  { <If> <bool> }
    
14. }
    
15. 
    
16. my $match = my-grammar.parse($str);
    
17. my $ast = get-match-ast($match);
    
18. # say $ast.perl;
    
19. say ast-lisp($ast);
    
20. 
    
21. sub get-match-ast($match) {
    
22.   if is-blank-match($match) {
    
23.     return [ $match.from, $match.Str ];
    
24.   }
    
25.   my @ast;
    
26.   for $match.kv -> $key, $value {
    
27.     given $value {
    
28.       when Array {
    
29.         for $value.values -> $sub-value {
    
30.           push @ast, get-match-ast($sub-value);
    
31.         }
    
32.       }
    
33.       when Match { push @ast, get-match-ast($value); }
    
34.       default { say 'Unknown type of Match hash value'; exit }
    
35.     }
    
36.   }
    
37.   return [ sort-match-ast(@ast) ];
    
38. }
    
39. 
    
40. sub sort-match-ast(@ast) {
    
41.   @ast.sort: -> $value {
    
42.     $value[0] ~~ Int ?? $value[0] !! $value.[0][0];
    
43.   }
    
44. }
    
45. 
    
46. sub is-blank-match($match) {
    
47.   if is-blank-list($match) {
    
48.     if is-blank-hash($match) {
    
49.       return True;
    
50.     }
    
51.   }
    
52.   return False;
    
53. }
    
54. 
    
55. sub is-blank-list($match) {
    
56.   $match.list.perl eq '().list' ?? True !! False;
    
57. }
    
58. 
    
59. sub is-blank-hash($match) {
    
60.   my $blank-hash = 'EnumMap.new()'|'EnumMap.new("" => [])';
    
61.   $match.hash.perl eq $blank-hash ?? True !! False;
    
62. }
    
63. 
    
64. sub ast-lisp($ast) {
    
65.   return $ast[1] if $ast[0] ~~ Int;
    
66.   my @map-ast;
    
67.   for $ast.values -> $value {
    
68.     push @map-ast, ast-lisp($value);
    
69.   }
    
70.   my $lisp = join ' ', @map-ast;
    
71.   return '(' ~ $lisp ~ ')';
    
72. }
    
73. 
    
74. # vim: ft=perl6
    

复制代码

output:

1. ((say 'hello') (if True))

复制代码

liti

我收藏你。。。。

rubyish

youyisi
yinyuemi de zhege code youyisi:

1. sub f {
   
2.     my $f = shift;
   
3.     ref( $f->[0] ) eq "ARRAY"
   
4.       ? f( @$f = sort { f($a) <=> f($b) } @$f )
   
5.       : $f->[0];
   
6. }
   
7. 
   

复制代码

1. my @array = (
   
2.     [ 1, 'a' ],
   
3.     [ [ 14, 'n' ], [ 15, 'o' ] ],
   
4.     [
   
5.         [
   
6.             [ [ [ [ 13, 'm' ], [ 12, 'l' ] ], [ 11, 'k' ] ], [ 10, 'j' ] ],
   
7.             [ 9, 'i' ]
   
8.         ],
   
9.         [ 7, 'g' ],
   
10.         [ 8, 'h' ]
    
11.     ],
    
12.     [ [ [ 6, 'f' ], [ 5, 'e' ] ], [ [ 4, 'd' ], [ 3, 'c' ] ] ],
    
13.     [ 2, 'b' ],
    
14. );

复制代码

1. [ [ 1, a ], [ 2, b ], [ [ [ 3, c ], [ 4, d ] ], [ [ 5, e ], [ 6, f ] ] ], [ [ 7, g ], [ 8, h ], [ [ 9, i ], [ [ 10, j ], [ [ 11, k ], [ [ 12, l ], [ 13, m ] ] ] ] ] ], [ [ 14, n ], [ 15, o ] ] ]
   

复制代码

zhege paixu, wo pai le 2 tien, cai pai chu zhengquede jieguo.
dan yu yinyuemi de code shizai xiangcha taiyuan le.

kk861123

回复 19# rubyish


    拼音看起来真心累，比看代码累啊...