これは何？
go の slice や C++ の std::vector のようなものに要素を追加する場合に世の人々がどうするのかを調べた。
そもそも
いわゆる可変長配列というものの代表的な実装は
- 適当にメモリ確保して、そこに要素を格納する
- 確保した容量に入らなくなったら、別の場所にメモリを確保して、そこに全部移動してから新要素を追加する
というものになっている。
この「別の場所にメモリを確保」の際にどうするのかが悩みどころ。
必要サイズぴったりにメモリ確保すると「1個追加」を1000回行った場合に絶望的に遅くなる。
多めに確保したいところだけど、多すぎるのはやっぱり損。
みんなどうしているのかなと思って調べてみた。
各実装
go の slice
https://github.com/golang/go/blob/go1.18.1/src/runtime/slice.go#L193
辺りに実装がある。
- 旧キャパシティが 256未満なら、新キャパシティは旧キャパシティの倍。
- 旧キャパシティが 256以上なら、新キャパシティは旧キャパシティ×1.25 + 192
ということになっている。
この計算は 2021年に変わったらしい。
C++ の std::vector (clang++)
手元の clang++ が使っているヘッダを見ると、
新キャパシティは、旧キャパシティの倍。
という実装の模様。
ruby の 配列の push
わからないけどこの辺りかな。
https://github.com/ruby/ruby/blob/master/array.c#L669
https://github.com/ruby/ruby/blob/master/array.c#L525
新キャパシティは、必要サイズ + 旧キャパシティの半分
だと思う。
Python3 の list.append
ここ
https://github.com/python/cpython/blob/836b17c9c3ea313e400e58a75f52b63f96e498bb/Objects/listobject.c#L70
じゃないかな。
その前後にも計算があるので難しいけど、概ね
新キャパシティ = ((旧キャパシティ+1)×9/8+6) の 4進数下一桁切り捨て
ということだと思う。
Java の ArrayList
新キャパシティ = 必要サイズ と 旧キャパシティ×1.5 の大きい方
かな。
.NET Core の ArrayList と Generics.List
ここ
https://source.dot.net/#System.Private.CoreLib/ArrayList.cs,9df2bbf8d237742e,references
だと思う。
新キャパシティ = 必要サイズ と 旧サイズ×2 の大きい方
かな。
※ 以下、@Tokeiya 様の指摘 を受けて追記
Generics.List の方は、ここ
https://source.dot.net/#System.Private.CoreLib/List.cs,c65229c53eb7ee1c
で、ArrayList と同じ。
まとめ
増え具合を表にしてみた。
| 言語とか | 倍率 |
|---|---|
| go | ×2 (しきい値未満), ×1.25（しきい値以上) |
| C++ (clang++) | ×2 |
| .NET Core | ×2 |
| PHP | ×2 （@rana_kualu 様のコメント と 拙コメント を参照） |
| Rust | ×2 （@scivola 様のコメント を参照） |
| ruby | ×1.5 |
| Java | ×1.5 |
| Python3 | ×1.125 |
こうしてみると、Python3 の 1.125 が小さすぎるようにも見えるけど、どうなんだろ。
あと、キャパシティを指定できる人たち（go, C++ など）と、キャパシティを指定する口のない人たち（ruby など）で傾向が違うかなとも思ったんだけど、そうでもない。
誰が予約できて誰がそうではないのかよくわかってないけれど。
いずれにせよ。
新キャパシティは 概ね 旧キャパシティ×定数 という感じにするのが普通だということだと思う。
そうしないと、追加のコストが $O(1)$ より大きくなってしまうからね。
各言語・ライブラリで工夫してるけど、どれが正解ということはない。
使い方次第で何がベストなのかは変わるから。
そう思うと。
この計算をチューニングすると速くなる、みたいなことは大いにありそうなんだけどだれもカスタマイズ可能にしていない。
追記
他に、この言語はこういう実装だよ、みたいなのをコメントに書いていただけると嬉しいです。