ListとArrayとSeqの使い分け #F#

ListとArrayとSeq、どれもよう似てるけど、結局何が違うねん？と思って違いを調べてみた。

ざっくり言えば、以下の結論になった。

不変性のList
可変性とパフォーマンスのArray
遅延評価とメモリ節約のSeq

List&Array

ListとArrayは一回こっきり生成する。
だから要素数が特大な場合は、メモリに詰め切れなくて死ぬ事もある。

ListとArrayの差は、ざっくり言えばデータ構造的にはLinkedListかArrayListの差。

List

利点はデータの不変性を証明できる事。

ただ、パフォーマンス面では注意が必要。
リストの要素追加はなるべくcons(::)を使う。
consだとリスト先頭のポインタを変更するのみで済む。

一方List.appendは第一引数のリストの全コピー処理が発生するのでパフォーマンス面で不利。
スライスを使ってアクセスする時も、リストの後半を指定すればするほど不利になる。

List

let nums =
    [
        for i in 1 .. 5 do
            printfn "create %d" i
            yield i
    ]

List.item 4 nums |> printfn "%d"
List.item 2 nums |> printfn "%d"

// 文法エラーになる
// nums.[4]  <- 56

// consは先頭に要素を1個しか足せないが超早い
56::nums |> printfn "%A"
// appendは要素を複数足せるが、内部的に第一引数の要素は全コピーしないといけない
List.append [50..62] nums |> printfn "%A"

// スライス
[50..62].[10..11] |> printfn "%A"

create 1
create 2
create 3
create 4
create 5
5
3
[56; 1; 2; 3; 4; 5]
[50; 51; 52; 53; 54; 55; 56; 57; 58; 59; 60; 61; 62; 1; 2; 3; 4; 5]

Array

Arrayは中身がmutableである。

インデックスアクセスが必要な場合と、要素の変更が必要な場合に適している。
生成、インデックスアクセス共に、SeqとListの比にならないくらい圧倒的に早い。

ただし、Arrayは参照型であり、単純に別の束縛を作ってもコピーにはならない。
スライスの[*]を使うことで、全コピーを作る事ができる。

あとは、C#と違い、=で比較できるのがF#Arrayの強み。
同じ長さ、同じ中身なら同値と判定してくれる。

Array

let nums =
    [|
        for i in 1 .. 5 do
            printfn "create %d" i
            yield i
    |]

Array.item 4 nums |> printfn "%d"
Array.item 2 nums |> printfn "%d"

// エイリアスとなる
let nums2 = nums

// エイリアスにしたくない時はスライスでコピー
let nums3 = nums.[*]

// Arrayは中身はmutable
nums.[4]  <- 56
nums.[4] |> printfn "%A"

// 実体は同じなのでこっちも変更後の値が出る
nums2.[4] |> printfn "%A"

// これはそのまま
nums3.[4] |> printfn "%A"

create 1
create 2
create 3
create 4
create 5
5
3
56
56
5

Seq

Seqは中身にアクセスするたびに、再生成が行われる。
遅延評価ってこういう事か。
だからメモリは圧迫しないけど、そのかわりアクセスの度に生成コストがかかる。

使いどころは要素数が凄い量になる場合、すなわちメモリを節約しないといけない場合や、要素の値が後付けで決まる場合。

あとはyield!¹を使って、内包表記の中で再帰を使う事ができる。
特定ディレクトリの配下の全ファイルの探索...みたいなケースにも使えるそうな。
確かにこれをArrayやListでやろうとすると、生成時にすげーコストかかって死んでしまうと思われる。

Seq

let nums =
    seq {
        for i in 1 .. 5 do
            printfn "create %d" i
            yield i
    }

Seq.item 4 nums |> printfn "%d"
Seq.item 2 nums |> printfn "%d"

create 1
create 2
create 3
create 4
create 5
5
create 1
create 2
create 3
3

おわりに

中身をきちんと勉強すると、パフォーマンス計測の結果がしっくりきた。
https://qiita.com/aoi_erimiya/items/6a23114d6718b0ccc5f5

目的に合わせて適切なやつ選ばなあかんよって事やね。

「いーるどばん」と読むらしい ↩