Help us understand the problem. What is going on with this article?

ListとArrayとSeqの使い分け

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!1を使って、内包表記の中で再帰を使う事ができる。
特定ディレクトリの配下の全ファイルの探索...みたいなケースにも使えるそうな。
確かにこれを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

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


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

aoi_erimiya
No problem. Everything's fine.
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした