这描述了一个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==1
or 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