これは、次のデータを取得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
または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