2
Help us understand the problem. What are the problem?

posted at

updated at

可変長配列に要素を追加する処理の色々

これは何?

go の slice や C++ の std::vector のようなものに要素を追加する場合に世の人々がどうするのかを調べた。

そもそも

いわゆる可変長配列というものの代表的な実装は

  • 適当にメモリ確保して、そこに要素を格納する
  • 確保した容量に入らなくなったら、別の場所にメモリを確保して、そこに全部移動してから新要素を追加する

というものになっている。
この「別の場所にメモリを確保」の際にどうするのかが悩みどころ。
必要サイズぴったりにメモリ確保すると「1個追加」を1000回行った場合に絶望的に遅くなる。
多めに確保したいところだけど、多すぎるのはやっぱり損。

みんなどうしているのかなと思って調べてみた。

各実装

go の slice

https://github.com/golang/go/blob/go1.18.1/src/runtime/slice.go#L193
辺りに実装がある。

  1. 旧キャパシティが 256未満なら、新キャパシティは旧キャパシティの倍。
  2. 旧キャパシティが 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

ここだと思う。
https://github.com/openjdk/jdk/blob/739769c8fc4b496f08a92225a12d07414537b6c0/src/java.base/share/classes/java/util/ArrayList.java#L231

新キャパシティ = 必要サイズ と 旧キャパシティ×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)$ より大きくなってしまうからね。

各言語・ライブラリで工夫してるけど、どれが正解ということはない。
使い方次第で何がベストなのかは変わるから。

そう思うと。
この計算をチューニングすると速くなる、みたいなことは大いにありそうなんだけどだれもカスタマイズ可能にしていない。

追記

他に、この言語はこういう実装だよ、みたいなのをコメントに書いていただけると嬉しいです。

Register as a new user and use Qiita more conveniently

  1. You can follow users and tags
  2. you can stock useful information
  3. You can make editorial suggestions for articles
What you can do with signing up
2
Help us understand the problem. What are the problem?