Mapに対するsizeの使い方

Question

Elixirでは、lengthはコンパイル時に長さが不明なもの(ex.List)に適用するもので
sizeはコンパイル時に長さが分かるものに適用するものと思っていましたが、
Mapに対してsizeを適用している例を見ました。(ex.map_size)

Mapは実行時にキーを追加することもできて、長さは実行時に変化するものと
思いますが、なぜlengthではなく、sizeを適用するのでしょうか？

https://elixir-lang.org/getting-started/protocols.html#protocols-and-structs

Answer 1

sizeはコンパイル時に長さが分かるものに適用するものと思っていましたが、

https://elixir-lang.org/getting-started/protocols.html#protocols-and-structs

On the other hand, tuple_size(tuple) and byte_size(binary) do not depend on the tuple and binary size as the size information is pre-computed in the data structure.

最後の文 "as the size information is pre-computed in the data structure."（事前に算出済みのサイズ情報がデータ構造に含まれているため）ですが、ここでいう「事前」はコンパイル時だけを指すわけではなく、実行時に追跡しているケースも含んでいます。

たとえばこの文に出てくるtupleのサイズはコンパイル時にわかりますが、binaryのサイズは（mapと同様に）実行時に変化します。ただ、binaryとmapはデータ構造自体にサイズ情報が含まれていて、binaryにデータをappendしたときや、mapに要素を追加したときに、そのサイズ情報が更新されるようになっています。そのためbyte_size/1などを適用した際には、単にサイズ情報を返すだけで済みます。

一方、その前のlengthに関する文ですが、以下のように書かれています。

"length means the information must be computed. For example, length(list) needs to traverse the whole list to calculate its length."（lengthはその情報を必ず算出しないといけないことを意味します。たとえばlength(list)はリストの長さを算出するためにリスト全体を順にたどる必要があります）

まとめるとこういう違いになります。

• *_size：この関数はデータ構造がコンパイル時に求めた、または、実行時に追跡しているサイズ情報を返すだけ
• length：この関数が呼ばれるたびに長さを算出しないといけない

Elixirのlistはconsリストと呼ばれるシンプルな内部データ構造を採用しており、長さ情報を持ちません。長さを算出するのは大変ですが、headへの要素の追加や、headとtailの分解などは低コスト（少ない計算量）で行えます。

一方、binaryとmapは少し複雑な内部データ構造を採用しており、サイズ情報も持っています。その代わり、要素の追加や削除はlistと比べると（ほんの少しですが）コストが高くなります。

Comments

[otaks]

分かりやすい説明ありがとうございました。