3

描述了一个interleave可以lzip数据的函数:

% interleave {a b c} {1 2 3}
a 1 b 2 c 3

我正在寻找反向操作。此外,我想指定输入应拆分为多少个子列表。例如:

% lnth {a 1 b 2 c 3}  1
{a 1 b 2 c 3}

% lnth {a 1 b 2 c 3}  2
{a b c} {1 2 3}

% lnth {a 1 b 2 c 3}  3
{a 2} {1 c} {b 3}

% lnth {a 1 b 2 c 3}  6
{a} {1} {b} {2} {c} {3}

对于不均匀的分割,缺少的元素应该被省略。如果您愿意,可以提供要填写的默认参数,但这不是必需的。我也不介意两个极端情况的确切引用,其中n==1or n==[llength $L]。感谢 Hai Vu 在您之前的回答中指出这一点。

对时间和内存的复杂性有一些概念会很好。

我在 Tcl8.4 上(无法更改)。

更新

对于这类基准问题,有一个中心总结总是好的。所有测试都在同一台机器上运行,在(相当小的)示例列表$L中,如下所示。这都是非常不科学的。好的代码来自下面的答案,错误是我的。

测试代码:

#!/usr/bin/tclsh


proc build_list {len} {
    incr len
    while {[incr len -1]} {
        lappend res {}
    }
    set res
}



proc lnth3_prebuild_no_modulo {L n} {
    # Build empty 2D list to hold result
    set iterations [expr {int(ceil(double([llength $L]) / $n))}]
    set one [build_list $iterations]
    set res [list]
    set cnt [expr {$n+1}]
    while {[incr cnt -1]} {
        lappend res $one
    }

    # Fill in original/real values
    set iteration 0
    set subListNumber 0
    foreach item $L {
        lset res $subListNumber $iteration $item
        if {[incr subListNumber] == $n} {
            set subListNumber 0
            incr iteration
        }
    }
    set res
}


proc lnth3_no_modulo {L n} {
    # Create a list of variables: subList0, subList1, subList2, ...
    for {set subListNumber 0} {$subListNumber < $n} {incr subListNumber} {
        set subList$subListNumber {}
    }

    # Build the sub-lists    
    set subListNumber 0
    foreach item $L {
        lappend subList$subListNumber $item
        if {[incr subListNumber] == $n} {
            set subListNumber 0
        }
    }

    # Build the result from all the sub-lists    
    set result {}
    for {set subListNumber 0} {$subListNumber < $n} {incr subListNumber} {
        lappend result [set subList$subListNumber]
    }

    return $result
}


proc lnth {L n} {
    set listvars ""
    for {set cnt 0} {$cnt < $n} {incr cnt} {
        lappend listvars "L$cnt"
    }

    set iterations [expr {ceil(double([llength $L]) / $n)}]
    for {set cnt 0} {$cnt < $iterations} {incr cnt} {
        foreach listvar $listvars el [lrange $L [expr {$cnt*$n}] [expr {($cnt+1)*$n-1}] ] {
            lappend $listvar $el
        }
    }

    set res [list]
    foreach listvar $listvars {
        lappend res [eval "join \$$listvar"]
    }
    set res
}


proc lnth_prebuild {L n} {
    set iterations [expr {int(ceil(double([llength $L]) / $n))}]
    set one [build_list $iterations]

    set listvars ""
    for {set cnt 0} {$cnt < $n} {incr cnt} {
        lappend listvars L$cnt
        set L$cnt $one
    }

    for {set cnt 0} {$cnt < $iterations} {incr cnt} {
        foreach listvar $listvars el [lrange $L [expr {$cnt*$n}] [expr {($cnt+1)*$n-1}] ] {
            lset $listvar $cnt $el
        }
    }

    set res [list]
    foreach listvar $listvars {
        lappend res [eval "join \$$listvar"]
    }
    set res
}



proc lnth2 {L n} {
    set listLen [llength $L]
    set subListLen [expr {$listLen / $n}]
    if {$listLen % $n != 0} { incr subListLen }
    set result {}

    for {set iteration 0} {$iteration < $n} {incr iteration} {
        set subList {}
        for {set i $iteration} {$i < $listLen} {incr i $n} {
            lappend subList [lindex $L $i]
        }
        lappend result $subList
    }
    return $result
}


proc lnth3 {L n} {
    # Create a list of variables: subList0, subList1, subList2, ...
    for {set subListNumber 0} {$subListNumber < $n} {incr subListNumber} {
        set subList$subListNumber {}
    }

    # Build the sub-lists    
    set i 0
    foreach item $L {
        set subListNumber [expr {$i % $n}]
        lappend subList$subListNumber $item
        incr i
    }

    # Build the result from all the sub-lists    
    set result {}
    for {set subListNumber 0} {$subListNumber < $n} {incr subListNumber} {
        lappend result [set subList$subListNumber]
    }

    return $result
}



# stuff subcommands in a namespace
namespace eval ::unlzip {}

proc unlzip {L n} {
   # check if we have the proc already
   set name [format "::unlzip::arity%dunlzip" $n]
   if {[llength [info commands $name]]} {
      return [$name $L]
   } else {
      # create it
      proc $name {V} [::unlzip::createBody $n]
      return [$name $L]
   }
}

proc ::unlzip::createBody {n} {
   for {set i 0} {$i < $n} {incr i} {
       lappend names v$i
       lappend lnames lv$i
   }
   set lbody ""
   set ret {
   return [list }
   foreach lname $lnames name $names {
       append lbody [format {
       lappend %s $%s} $lname $name]
       append ret "\$$lname "
   }
   append ret {]}
   return [format {foreach {%s} $V { %s }
                   %s} $names $lbody $ret]
}




### Tests
set proc_reference lnth
set procs {lnth_prebuild lnth2 lnth3 unlzip lnth3_no_modulo lnth3_prebuild_no_modulo}
set L {a 1 b 2 c 3 d 4 e 5 f 6 g 7 h 8 j 9 i 10 k 11 l 12 m 13 n 14 o 15 p 16 q 17 r 18 s 19 t 20 u 21 v 22 w 23 x 24 y 25 z 26}
set Ns {1 2 3 4 5 6 7 8 9 10 13 26}

# Functional verification
foreach n $Ns {
    set expected [$proc_reference $L $n]
    foreach p $procs {
        set result [$p $L $n]
        if {$expected ne $result} {
            puts "Wrong result for proc $p, N=$n."
            puts "  Expected: $expected"
            puts "       Got: $result"
        }
    }
}

# Table header
puts -nonewline [format "%30s" {proc_name\N}]
foreach n $Ns {
    puts -nonewline [format "  %7d" $n]
}
puts ""

# Run benchmarks
foreach proc_name [concat $proc_reference $procs] {
    puts -nonewline [format "%30s" $proc_name]
    foreach n $Ns {
        puts -nonewline [format "  %7.2f" [lindex [time "$proc_name \$L $n" 10000] 0]]
    }
    puts ""
}

结果:

               proc_name\N        1        2        3        4        5        6        7        8        9       10       13       26
                      lnth    33.34    23.73    21.88    20.51    21.33    21.33    22.41    23.07    23.36    25.59    26.09    38.39
             lnth_prebuild    41.14    31.00    28.88    27.24    28.48    29.06    30.45    31.46    31.43    34.65    34.45    49.10
                     lnth2     8.56     8.08     8.35     8.78     9.12     9.29     9.66     9.98    10.29    10.61    11.22    14.94
                     lnth3    17.15    18.35    18.91    19.55    20.55    21.42    22.24    23.54    23.71    24.27    25.79    33.78
                    unlzip     5.36     5.25     5.03     4.97     5.27     5.42     5.52     5.43     5.42     5.96     5.51     6.83
           lnth3_no_modulo    14.88    16.56    17.20    17.97    18.63    19.42    19.78    20.74    21.53    21.84    23.60    31.29
  lnth3_prebuild_no_modulo    14.44    13.30    12.83    12.51    12.51    12.43    12.36    12.41    12.41    12.83    12.70    14.09
4

5 回答 5

3

一种选择是动态创建专门的 proc:

不确定对于更大的 N 或更大的集合有多快,但对于重复运行应该非常快,因为与直接调用foreachand相比,您几乎没有开销lappend

package require Tcl 8.4

# stuff subcommands in a namespace
namespace eval ::unlzip {}

proc unlzip {L n} {
   # check if we have the proc already
   set name [format "::unlzip::arity%dunlzip" $n]
   if {[llength [info commands $name]]} {
      return [$name $L]
   } else {
      # create it
      proc $name {V} [::unlzip::createBody $n]
      return [$name $L]
   }
}

proc ::unlzip::createBody {n} {
   for {set i 0} {$i < $n} {incr i} {
       lappend names v$i
       lappend lnames lv$i
   }
   set lbody ""
   set ret {
   return [list }
   foreach lname $lnames name $names {
       append lbody [format {
       lappend %s $%s} $lname $name]
       append ret "\$$lname "
   }
   append ret {]}
   return [format {foreach {%s} $V { %s }
                   %s} $names $lbody $ret]
}

proc ::unlzip::arity1unlzip {V} {
   return [list $V]
}

# example how the function looks for N=2

proc ::unlzip::arity2unlzip {V} {
   foreach {v1 v2} $V {
      lappend lv1 $v1
      lappend lv2 $v2
   }
   return [list $lv1 $lv2]
}

N=3 proc 的 Tcl 8.6 的反汇编字节码看起来像这样(通过 Tcl 8.6. ::tcl::unsupported::disassemble proc

ByteCode 0x00667988, refCt 1, epoch 5, interp 0x005E0B70 (epoch 5)
Source "foreach {v0 v1 v2} $V { \n\t      lappend lv0 $v0\n\t      "
Cmds 6, src 149, inst 86, litObjs 1, aux 1, stkDepth 3, code/src 0.00
Proc 0x00694368, refCt 1, args 1, compiled locals 9
  slot 0, scalar, arg, "V"
  slot 1, scalar, temp
  slot 2, scalar, temp
  slot 3, scalar, "v0"
  slot 4, scalar, "v1"
  slot 5, scalar, "v2"
  slot 6, scalar, "lv0"
  slot 7, scalar, "lv1"
  slot 8, scalar, "lv2"
Exception ranges 1, depth 1:
  0: level 0, loop, pc 17-57, continue 10, break 61
Commands 6:
  1: pc 0-63, src 0-94        2: pc 17-30, src 32-46
  3: pc 31-44, src 55-69        4: pc 45-57, src 78-93
  5: pc 64-84, src 120-148        6: pc 73-83, src 128-147
Command 1: "foreach {v0 v1 v2} $V { \n\t      lappend lv0 $v0\n\t      "
  (0) loadScalar1 %v0         # var "V"
  (2) storeScalar1 %v1        # temp var 1
  (4) pop
  (5) foreach_start4 0
            [data=[%v1], loop=%v2
             it%v1  [%v3, %v4, %v5]]
  (10) foreach_step4 0
            [data=[%v1], loop=%v2
             it%v1  [%v3, %v4, %v5]]
  (15) jumpFalse1 +46         # pc 61
Command 2: "lappend lv0 $v0"
  (17) startCommand +13 1     # next cmd at pc 30
  (26) loadScalar1 %v3        # var "v0"
  (28) lappendScalar1 %v6     # var "lv0"
  (30) pop
Command 3: "lappend lv1 $v1"
  (31) startCommand +13 1     # next cmd at pc 44
  (40) loadScalar1 %v4        # var "v1"
  (42) lappendScalar1 %v7     # var "lv1"
  (44) pop
Command 4: "lappend lv2 $v2 "
  (45) startCommand +13 1     # next cmd at pc 58
  (54) loadScalar1 %v5        # var "v2"
  (56) lappendScalar1 %v8     # var "lv2"
  (58) pop
  (59) jump1 -49      # pc 10
  (61) push1 0        # ""
  (63) pop
Command 5: "return [list $lv0 $lv1 $lv2 ]"
  (64) startCommand +21 2     # next cmd at pc 85, 2 cmds start here
Command 6: "list $lv0 $lv1 $lv2 "
  (73) loadScalar1 %v6        # var "lv0"
  (75) loadScalar1 %v7        # var "lv1"
  (77) loadScalar1 %v8        # var "lv2"
  (79) list 3
  (84) done
  (85) done

尽可能直截了当……好吧,如果列表不完整(llength $L$n不为零),您将需要一些额外的检查。只要列表是平衡的,您也可以预先填充列表并使用lset而不是lappend,这样更快,因为它不会经常重新分配列表数组。

于 2013-07-27T01:26:51.047 回答
2

这是我的方法:一次构建一个子列表,然后在构建下一个之前附加到结果。

proc lnth2 {L n} {
    set listLen [llength $L]
    set subListLen [expr {$listLen / $n}]
    if {$listLen % $n != 0} { incr subListLen }
    set result {}

    for {set iteration 0} {$iteration < $n} {incr iteration} {
        set subList {}
        for {set i $iteration} {$i < $listLen} {incr i $n} {
            lappend subList [lindex $L $i]
        }
        lappend result $subList
    }
    return $result
}

假设 L =和 n = 2,那么我将通过从原始列表中挑选第 0、第 2 和第 4 项来{a 1 b 2 c 3}构建第一个子列表,将其附加到结果中并继续第二个子列表。{a b c}同样,第二个子列表将是第 1、第 3 和第 5 个项目。

更新

在查看了我的解决方案后,我仍然不喜欢我必须使用lindex. 我想lindex必须遍历列表才能找到列表项,而我的解决方案lindex正好放在一个循环中;这意味着我们多次遍历同一个列表。下一次尝试是只遍历列表一次。这一次,我模仿你的算法,但避免使用列表函数,例如lrange.

proc lnth3 {L n} {
    # Create a list of variables: subList0, subList1, subList2, ...
    for {set subListNumber 0} {$subListNumber < $n} {incr subListNumber} {
        set subList$subListNumber {}
    }

    # Build the sub-lists    
    set i 0
    foreach item $L {
        set subListNumber [expr {$i % $n}]
        lappend subList$subListNumber $item
        incr i
    }

    # Build the result from all the sub-lists    
    set result {}
    for {set subListNumber 0} {$subListNumber < $n} {incr subListNumber} {
        lappend result [set subList$subListNumber]
    }

    return $result
}

可悲的是,这次尝试比我的第一次尝试更糟糕。我还是不明白为什么。

于 2013-07-26T17:56:06.263 回答
1

现在得到了一些东西 - 但不喜欢它,因为它似乎没有效率:

proc lnth {L n} {
    set listvars ""
    for {set cnt 0} {$cnt < $n} {incr cnt} {
        lappend listvars "L$cnt"
    }

    set iterations [expr {ceil(double([llength $L]) / $n)}]
    for {set cnt 0} {$cnt < $iterations} {incr cnt} {
        foreach listvar $listvars el [lrange $L [expr {$cnt*$n}] [expr {($cnt+1)*$n-1}] ] {
            lappend $listvar $el
        }
    }

    set res [list]
    foreach listvar $listvars {
        lappend res [eval "join \$$listvar"]
    }
    set res
}

诀窍是有几个子列表,存储在变量L0, L1, 中L2,并根据需要多少 ( $n) 动态创建这些子列表。

然后迭代次数取决于len($L)/$n,使用ceil()这里来覆盖不完整的迭代。

最后一个循环组装整个结果列表。

我根本不知道如何在主工作循环期间更有效地构建结果列表。lappend而且我对 Tcl或替代方案的内部效率知之甚少。此外,仅迭代 L 并将元素分配给这些子列表可能会更快......

于 2013-07-26T15:23:22.280 回答
1

出于好奇,并受到 Donal 的评论的启发,linsert实际上是O(1)因为 Tcl 列表是用 C 数组实现的,所以我尝试稍微改进Hai Vu 的回答:首先使用简单的计数器和比较来删除模运算。其次,将 替换lappendlset. 后一种更改需要预先构建结果数组。

这是代码:

proc lnth3_no_modulo {L n} {
    # Create a list of variables: subList0, subList1, subList2, ...
    for {set subListNumber 0} {$subListNumber < $n} {incr subListNumber} {
        set subList$subListNumber {}
    }

    # Build the sub-lists    
    set subListNumber 0
    foreach item $L {
        lappend subList$subListNumber $item
        if {[incr subListNumber] == $n} {
            set subListNumber 0
        }
    }

    # Build the result from all the sub-lists    
    set result {}
    for {set subListNumber 0} {$subListNumber < $n} {incr subListNumber} {
        lappend result [set subList$subListNumber]
    }

    return $result
}




proc build_list {len} {
    incr len
    while {[incr len -1]} {
        lappend res {}
    }
    set res
}
proc lnth3_prebuild_no_modulo {L n} {
    # Build empty 2D list to hold result
    set iterations [expr {int(ceil(double([llength $L]) / $n))}]
    set one [build_list $iterations]
    set res [list]
    set cnt [expr {$n+1}]
    while {[incr cnt -1]} {
        lappend res $one
    }

    # Fill in original/real values
    set iteration 0
    set subListNumber 0
    foreach item $L {
        lset res $subListNumber $iteration $item
        if {[incr subListNumber] == $n} {
            set subListNumber 0
            incr iteration
        }
    }
    set res
}

这两个在运行时间上做了一些小的改进——但幅度不大:

               proc_name\N        1        2        3        4        5        6        7        8        9       10       13       26
                     lnth3    17.41    18.62    19.07    19.99    21.39    21.45    23.90    23.58    23.62    24.50    25.67    33.91
           lnth3_no_modulo    14.95    16.39    16.95    17.80    18.20    19.17    19.86    20.62    21.23    21.99    23.40    31.71
  lnth3_prebuild_no_modulo    14.46    12.90    12.24    11.85    11.80    11.65    11.61    11.61    11.70    11.81    11.96    13.23

似乎预构建替代方案变得更有效,lappend否则必须执行更多列表操作。

于 2013-07-27T16:54:33.163 回答
0

一个简单有效的算法是这样的:

foreach {a b c} $data {
   lappend ra $a
   lappend rb $b
   lappend rc $c
}
list $ra $rb $rc

缺点是您必须指定不同的变量。
好处是它很有效。

于 2013-07-27T14:26:27.627 回答