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==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
4

5 に答える 5

2

これが私のアプローチです。一度に 1 つのサブリストを作成し、結果に追加してから次のサブリストを作成します。

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 ={a 1 b 2 c 3}および n = 2 とすると、元のリストから 0 番目、2 番目、および 4 番目の項目を選択して最初のサブリストを作成し、{a b c}それを結果に追加して、2 番目のサブリストに移動します。同様に、2 番目のサブリストは 1 番目、3 番目、5 番目の項目になります。

アップデート

私の解決策を見直した後、私はまだ使用しなければならないという事実が好きではありませんlindex. lindexリスト項目を見つけるためにリストをたどる必要があると思いますが、私のソリューションはループ内に配置されてlindexいます。これは、同じリストを数回トラバースすることを意味します。次の試みは、リストを 1 回だけトラバースすることです。今回は、アルゴリズムを模倣しますが、 などのリスト関数の使用は避けます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

好奇心から、linsert実際にはO(1)Tcl リストが C 配列で実装されているという Donal のコメントに触発されて、 Hai Vu の答えを少し改善しようとしました。まず、単純なカウンターと比較でモジュロ演算を削除します。lappend次に、をに置き換えlsetます。この後者の変更では、結果配列を事前に構築する必要があります。

コードは次のとおりです。

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
}

これら 2 つは、実行時間をわずかに改善しますが、大幅には改善しません。

               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 に答える
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
}

秘訣は、いくつかのサブリストを変数L0L1、に保存し、必要なL2( ) の数に応じてそれらのサブリストを動的に作成する$nことです。

反復回数は に依存しlen($L)/$nceil()here を使用して不完全な反復をカバーします。

最後のループは、全体の結果リストを組み立てます。

メインの作業ループ中に結果リストをより効率的に構築する方法がわかりません。lappendまた、Tcl inまたは代替の内部効率についてはほとんど知りません。また、 L を反復処理して、それらのサブリストに要素を追加する方が速い場合があります...

于 2013-07-26T15:23:22.280 に答える
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 に答える