seq使うのむずかし。(Seq.skipおそい)

f#

まとめ

  • seq式で遊ぼうとした
  • combinationsとか生成すれば良さそう。
  • 全部seqにすると遅い。

seq式で遊ぼうとした

seq式は値の列を返す計算を返してくれる。

> seq {for x in [1..10] do yield x*x} |> Seq.toList;;
val it : int list = [1; 4; 9; 16; 25; 36; 49; 64; 81; 100]
  • 要素を結果として与えてくれるyield
  • 列をconcatしてくれるyield!

の2つがある。

> seq {yield 1; yield 2; yield 3};;
val it : seq<int> = seq [1; 2; 3]

> seq {yield! [1;2;3]; yield 4; yield! [5]};;
val it : seq<int> = seq [1; 2; 3; 4; ...]

combinationsでも生成すれば良さそう

普通に再帰で書いたことはあるけれど、seq式のようなものでまとめて書いたことない。
yield!があるので、全部seq式で書けそう。
書いた。


全部seqにすると遅い。

[1..20]までの列から8個取る組み合わせを列挙してみる

$ time ./permtations.exe

  ...]./permtations.exe  39.82s user 0.81s system 176% cpu 23.075 total

すっごい遅い。

profilerを使ってみる。

monoなので以下のような感じでprofiler使う。

$ mono --profile=default:stat permtations.exe

prof counts: total/unmanaged: 2383/1115
   1014	42.57 % mono()
    349	14.65 % Microsoft.FSharp.Collections.SeqModule/Skip@1428<int>:GenerateNext (System.Collections.Generic.IEnumerable`1<int>&)
    267	11.21 % Microsoft.FSharp.Core.CompilerServices.GeneratedSequenceBase`1<int>:MoveNextImpl ()
    109	 4.58 % Microsoft.FSharp.Core.CompilerServices.GeneratedSequenceBase`1<int>:System-Collections-IEnumerator-MoveNext ()
     69	 2.90 % (wrapper alloc) object:Alloc (intptr)
     60	 2.52 % Microsoft.FSharp.Core.CompilerServices.GeneratedSequenceBase`1<int>:System-Collections-Generic-IEnumerator`1-get_Current ()
     53	 2.23 % Microsoft.FSharp.Core.Operators/OperatorIntrinsics/BaseRangeEnumerator`1<int>:System-Collections-IEnumerator-MoveNext ()
     43	 1.81 % Microsoft.FSharp.Collections.PrivateListHelpers/ListEnumerator`1<int>:System-Collections-IEnumerator-MoveNext ()
     34	 1.43 % (wrapper managed-to-native) object:__icall_wrapper_mono_object_new_fast (intptr)
     34	 1.43 % Microsoft.FSharp.Collections.SeqModule/Skip@1428<int>:Close ()

Seq.skipが遅い。Seq.skipが遅い。

Seq.skip

Seq.skipはdropみたいなもの。N個飛ばした列を返す

> seq {yield 1; yield 2} |> Seq.skip 1;;
val it : seq<int> = seq [2]
> [1;2;3] |> List.tail;;
val it : int list = [2; 3]

Seq.skip使っている箇所をlistに置き換えてみる。


$ time ./permtations2.exe

...]./permtations2.exe  2.63s user 0.11s system 173% cpu 1.575 total

早くなった。

ちなみに

pythonのitertolsを使った場合はこれくらいの速度([:20]はf#の出力に大体合わせるため)

 $ time python -c "import itertools as i; print [x for x in i.combinations(range(20),8)][:20]"                                                                                                                  [~/sandbox/fsharp]
[(0, 1, 2, 3, 4, 5, 6, 7), (0, 1, 2, 3, 4, 5, 6, 8), (0, 1, 2, 3, 4, 5, 6, 9), (0, 1, 2, 3, 4, 5, 6, 10), (0, 1, 2, 3, 4, 5, 6, 11), (0, 1, 2, 3, 4, 5, 6, 12), (0, 1, 2, 3, 4, 5, 6, 13), (0, 1, 2, 3, 4, 5, 6, 14), (0, 1, 2, 3, 4, 5, 6, 15), (0, 1, 2, 3, 4, 5, 6, 16), (0, 1, 2, 3, 4, 5, 6, 17), (0, 1, 2, 3, 4, 5, 6, 18), (0, 1, 2, 3, 4, 5, 6, 19), (0, 1, 2, 3, 4, 5, 7, 8), (0, 1, 2, 3, 4, 5, 7, 9), (0, 1, 2, 3, 4, 5, 7, 10), (0, 1, 2, 3, 4, 5, 7, 11), (0, 1, 2, 3, 4, 5, 7, 12), (0, 1, 2, 3, 4, 5, 7, 13), (0, 1, 2, 3, 4, 5, 7, 14)]
python -c   0.07s user 0.01s system 93% cpu 0.086 total