Go to Qiita Advent Calendar 2024 Top
LoginSignup
2
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

@aoi_erimiya(Hiroaki Wada)

SeqとListとArrayのパフォーマンス比較

Last updated at Posted at 2020-02-18

##SeqとListとArrayのパフォーマンス比較
気になったので実験してみた。
単純な生成コストと、インデックスアクセスの速度を比較。

速度はSeq > Array >> Listのようである。
@vain0x さんにコメント欄で指摘いただいた通り、計測コードの書き方が間違ってたみたい。

再計測の結果、速度はArray >>> List > Seq となった。
※数は公平にするために10^8のまま

###dotnetcore2.1で計測

Method Mean Error StdDev Median
ABench(Seq) 182,376.5 ns 5,210.94 ns 14,088.1 ns 175,500.0 ns
BBench(List) 214,139.7 ns 5,123.56 ns 12,759.4 ns 214,900.0 ns
CBench(Array) 766.0 ns 68.92 ns 199.9 ns 800.0 ns

###dotnetcore3.1で計測

Method Mean Error StdDev Median
ABench(Seq) 243.788 us 14.0499 us 41.206 us 230.800 us
BBench(List) 228.499 us 5.4869 us 15.743 us 226.600 us
CBench(Array) 2.068 us 0.6108 us 1.672 us 1.300 us

頂いたコメントとデータの傾向が違うなと思ってたら、dotnetのバージョンの差異のようだ。
3.1にするとだいたい近い結果になった。

サマリは単位がマイクロとナノでずれてるけど、
揃えて考えると2.1より3.1の方が全体的に遅くなってる感がある。

走行時間も増えてるし、なんでやろねぇ。

###感想
ベンチ走らせるのに約35分程かかった。
途中で気づいたけど、もっとまともなベンチ名にするべきだったね...

まあListはデータ構造的にアクセス速度遅くて当然として。

当初予想では、Seqはメモリ上一個しか存在しないらしいと聞いて
Arrayよりも生成コストかからず爆速になるのかなーって思ってた。

Arrayだとインスタンス2個とも100,000,000回ループ回すけど
Seqはインスタンス1個分だけ生成したら、2個目にはインスタンス1のアドレスが代入されるのかなーと。
内包表記を2個呼び出してるのはこれを試そうと思ったから。
実際見てるとリストよりも遅いので、そんなに早い訳ではないらしい。

##検証コードと結果
###テストコード(修正版)

テストコード
module Program

open BenchmarkDotNet
open BenchmarkDotNet.Attributes

let buildCardSeq = seq { 1..100000000 }
let buildCardList = [ 1..100000000 ]
let buildCardArray = [| 1..100000000 |]

let A () =
    let bs1 = buildCardSeq
    let bs2 = buildCardSeq
    bs1 |> Seq.item 56789

let B () =
    let bl1 = buildCardList
    let bl2 = buildCardList
    bl1 |> List.item 56789

let C () =
    let ba1 = buildCardArray
    let ba2 = buildCardArray
    ba1 |> Array.item 56789

type Benchmarks() =
    [<Benchmark>]
    member x.ABench() =
        A()

    [<Benchmark>]
    member x.BBench() =
        B()

    [<Benchmark>]
    member x.CBench() =
        C()

[<EntryPoint>]
let main _ =
    let _summary = Running.BenchmarkRunner.Run<Benchmarks>()
    0

###サマリ(dotnetcore3.1)

// * Summary *

BenchmarkDotNet=v0.12.0, OS=Windows 10.0.18363
Intel Core i7-4650U CPU 1.70GHz (Haswell), 1 CPU, 4 logical and 2 physical cores
.NET Core SDK=3.1.101
  [Host]     : .NET Core 3.1.1 (CoreCLR 4.700.19.60701, CoreFX 4.700.19.60801), X64 RyuJIT DEBUG
  DefaultJob : .NET Core 3.1.1 (CoreCLR 4.700.19.60701, CoreFX 4.700.19.60801), X64 RyuJIT


| Method |       Mean |      Error |    StdDev |     Median |
|------- |-----------:|-----------:|----------:|-----------:|
| ABench | 243.788 us | 14.0499 us | 41.206 us | 230.800 us |
| BBench | 228.499 us |  5.4869 us | 15.743 us | 226.600 us |
| CBench |   2.068 us |  0.6108 us |  1.672 us |   1.300 us |

// * Warnings *
MinIterationTime
  Benchmarks.ABench: Default -> The minimum observed iteration time is 200.2000 us which is very small. It's recommended to increase it.
  Benchmarks.BBench: Default -> The minimum observed iteration time is 200.9000 us which is very small. It's recommended to increase it.
  Benchmarks.CBench: Default -> The minimum observed iteration time is 900.0000 ns which is very small. It's recommended to increase it.
MultimodalDistribution
  Benchmarks.BBench: Default -> It seems that the distribution can have several modes (mValue = 2.86)

// * Hints *
Outliers
  Benchmarks.ABench: Default -> 1 outlier  was  removed (405.80 us)
  Benchmarks.BBench: Default -> 5 outliers were removed (289.60 us..393.00 us)
  Benchmarks.CBench: Default -> 13 outliers were removed (7.20 us..11.80 us)

// * Legends *
  Mean   : Arithmetic mean of all measurements
  Error  : Half of 99.9% confidence interval
  StdDev : Standard deviation of all measurements
  Median : Value separating the higher half of all measurements (50th percentile)
  1 us   : 1 Microsecond (0.000001 sec)

// ***** BenchmarkRunner: End *****
// ** Remained 0 benchmark(s) to run **
Run time: 00:37:52 (2272.5 sec), executed benchmarks: 3

Global total time: 00:37:58 (2278.54 sec), executed benchmarks: 3
// * Artifacts cleanup *

###サマリ(dotnetcore2.1)

// * Summary *

BenchmarkDotNet=v0.12.0, OS=Windows 10.0.18363
Intel Core i7-4650U CPU 1.70GHz (Haswell), 1 CPU, 4 logical and 2 physical cores
.NET Core SDK=3.1.101
  [Host]     : .NET Core 2.1.9 (CoreCLR 4.6.27414.06, CoreFX 4.6.27415.01), X64 RyuJIT DEBUG
  DefaultJob : .NET Core 2.1.9 (CoreCLR 4.6.27414.06, CoreFX 4.6.27415.01), X64 RyuJIT


| Method |         Mean |       Error |      StdDev |       Median |
|------- |-------------:|------------:|------------:|-------------:|
| ABench | 182,376.5 ns | 5,210.94 ns | 14,088.1 ns | 175,500.0 ns |
| BBench | 214,139.7 ns | 5,123.56 ns | 12,759.4 ns | 214,900.0 ns |
| CBench |     766.0 ns |    68.92 ns |    199.9 ns |     800.0 ns |

// * Warnings *
MinIterationTime
  Benchmarks.ABench: Default -> The minimum observed iteration time is 175.1000 us which is very small. It's recommended to increase it.
  Benchmarks.BBench: Default -> The minimum observed iteration time is 192.3000 us which is very small. It's recommended to increase it.
  Benchmarks.CBench: Default -> The minimum observed iteration time is 400.0000 ns which is very small. It's recommended to increase it.
MultimodalDistribution
  Benchmarks.BBench: Default -> It seems that the distribution can have several modes (mValue = 3.03)

// * Hints *
Outliers
  Benchmarks.ABench: Default -> 15 outliers were removed (245.20 us..340.60 us)
  Benchmarks.BBench: Default -> 12 outliers were removed (258.70 us..370.60 us)
  Benchmarks.CBench: Default -> 3 outliers were removed (1.60 us..2.10 us)

// * Legends *
  Mean   : Arithmetic mean of all measurements
  Error  : Half of 99.9% confidence interval
  StdDev : Standard deviation of all measurements
  Median : Value separating the higher half of all measurements (50th percentile)
  1 ns   : 1 Nanosecond (0.000000001 sec)

// ***** BenchmarkRunner: End *****
// ** Remained 0 benchmark(s) to run **
Run time: 00:34:56 (2096.23 sec), executed benchmarks: 3

Global total time: 00:35:05 (2105.93 sec), executed benchmarks: 3
// * Artifacts cleanup *

##修正前
今後の自分のために残しておく

###テストコード(修正前)

テストコード

module Program

open BenchmarkDotNet
open BenchmarkDotNet.Attributes

let buildCardSeq = seq { 1..100000000 }
let buildCardList = [ 1..100000000 ]
let buildCardArray = [| 1..100000000 |]

let A =
    let bs1 = buildCardSeq
    let bs2 = buildCardSeq
    bs1 |> Seq.item 56789

let B =
    let bl1 = buildCardList
    let bl2 = buildCardList
    bl1 |> List.item 56789

let C =
    let ba1 = buildCardArray
    let ba2 = buildCardArray
    ba1 |> Array.item 56789

type Benchmarks() =
    [<Benchmark>]
    member x.ABench() =
        A

    [<Benchmark>]
    member x.BBench() =
        B

    [<Benchmark>]
    member x.CBench() =
        C

[<EntryPoint>]
let main _ =
    let _summary = Running.BenchmarkRunner.Run<Benchmarks>()
    0

###サマリ(修正前)

// * Summary *

BenchmarkDotNet=v0.12.0, OS=Windows 10.0.18363
Intel Core i7-4650U CPU 1.70GHz (Haswell), 1 CPU, 4 logical and 2 physical cores
.NET Core SDK=3.1.101
  [Host]     : .NET Core 2.1.9 (CoreCLR 4.6.27414.06, CoreFX 4.6.27415.01), X64 RyuJIT DEBUG
  DefaultJob : .NET Core 2.1.9 (CoreCLR 4.6.27414.06, CoreFX 4.6.27415.01), X64 RyuJIT


| Method |         Mean |       Error |      StdDev |       Median |
|------- |-------------:|------------:|------------:|-------------:|
| ABench | 182,376.5 ns | 5,210.94 ns | 14,088.1 ns | 175,500.0 ns |
| BBench | 214,139.7 ns | 5,123.56 ns | 12,759.4 ns | 214,900.0 ns |
| CBench |     766.0 ns |    68.92 ns |    199.9 ns |     800.0 ns |

// * Warnings *
MinIterationTime
  Benchmarks.ABench: Default -> The minimum observed iteration time is 175.1000 us which is very small. It's recommended to increase it.
  Benchmarks.BBench: Default -> The minimum observed iteration time is 192.3000 us which is very small. It's recommended to increase it.
  Benchmarks.CBench: Default -> The minimum observed iteration time is 400.0000 ns which is very small. It's recommended to increase it.
MultimodalDistribution
  Benchmarks.BBench: Default -> It seems that the distribution can have several modes (mValue = 3.03)

// * Hints *
Outliers
  Benchmarks.ABench: Default -> 15 outliers were removed (245.20 us..340.60 us)
  Benchmarks.BBench: Default -> 12 outliers were removed (258.70 us..370.60 us)
  Benchmarks.CBench: Default -> 3 outliers were removed (1.60 us..2.10 us)

// * Legends *
  Mean   : Arithmetic mean of all measurements
  Error  : Half of 99.9% confidence interval
  StdDev : Standard deviation of all measurements
  Median : Value separating the higher half of all measurements (50th percentile)
  1 ns   : 1 Nanosecond (0.000000001 sec)

// ***** BenchmarkRunner: End *****
// ** Remained 0 benchmark(s) to run **
Run time: 00:34:56 (2096.23 sec), executed benchmarks: 3

Global total time: 00:35:05 (2105.93 sec), executed benchmarks: 3
// * Artifacts cleanup *
2
0
2

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
2
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?