std:: unordered_setとstd:: unordered_mapのclearメソッドの計算量の記述について

[math-hiyoko]

std:: unordered_setとstd:: unordered_mapのclearメソッドについて、その計算量は
「本関数呼び出し前のコンテナの要素数（ size() ）に比例」と記述されている
https://cpprefjp.github.io/reference/unordered_set/unordered_set/clear.html
https://cpprefjp.github.io/reference/unordered_map/unordered_map/clear.html

しかし、多くの実装では、実際には本関数呼び出し前の( bucket_count() )に比例している
gccの実装: https://github.com/gcc-mirror/gcc/blob/fd50d2a24adaff9a9ba749fd0a1eb5a5c5ee35a8/libstdc%2B%2B-v3/include/bits/hashtable.h#L2707-L2720
clang LLVMの実装: https://github.com/llvm/llvm-project/blob/ad060dfa4c910e8253ba328be947ef70f6597326/libcxx/include/__hash_table#L1338-L1348

このことから、サイトの記述を実態にあったものに変えるべきである

[faithandbrave]

詳細な調査ありがとうございます。

本サイトの記述としては、以下の仕様に基づいていますので、まず間違った記載にはなっていません。

23.2.8 Unordered associative containers [unord.req]
23.2.8.1 General [unord.req.general]
…
a.clear()
Result: void
Effects: Erases all elements in the container.
Postconditions: a.empty() is true.
Complexity: Linear in a.size().

その上で実装としての最適化や非最適化について記載するのであれば、備考として記載することになるかと思います。
ハッシュ表のバケット内の要素を合計すると、ハッシュ表の要素数と一致しますので、バケット内の要素数が0のものもありますが、実態として「本関数呼び出し前のコンテナの要素数（ size() ）に比例」と変わらないように思えます。

これを「バケット数に比例する」と記載したい意図はどういったものになるでしょうか？

#include <iostream>
#include <unordered_map>
#include <algorithm>

int main()
{
  std::unordered_map<char, int> um = {
    {'A', 1},
    {'B', 2},
    {'C', 3},
    {'D', 4},
    {'E', 5}
  };

  decltype(um)::size_type c = um.bucket_count();
  std::cout << "bucket_count() = " << c << std::endl;

  int sum = 0;
  for (decltype(um)::size_type b = 0; b < c; ++b) {
    // 各バケットのサイズを取得
    decltype(um)::size_type s = um.bucket_size(b);
    std::cout << "bucket[" << b << "] size = " << s << std::endl;
    sum += s;
  }

  std::cout << "bucket sum size = " << sum << std::endl;
  std::cout << "container size = " << um.size() << std::endl;
}

出力：

bucket_count() = 13
bucket[0] size = 1
bucket[1] size = 1
bucket[2] size = 1
bucket[3] size = 1
bucket[4] size = 1
bucket[5] size = 0
bucket[6] size = 0
bucket[7] size = 0
bucket[8] size = 0
bucket[9] size = 0
bucket[10] size = 0
bucket[11] size = 0
bucket[12] size = 0
bucket sum size = 5
container size = 5

[math-hiyoko]

hash_tableでは要素の削除を行なってもバケット数が減ることはないので、要素数sizeとバケット数bucket_countが対応しなくなることは十分にあり得ます。
例えば何らかの理由で大きな要素数を持っていたunordered_mapに対するclearを複数回実行した場合、各回でbucket_countに比例した複雑度の処理が行われることになるため、このことに留意できるようにしたいという意図があります。

#include <iostream>
#include <unordered_map>

int main()
{
  std::unordered_map<char, int> um = {
    {'A', 1},
    {'B', 2},
    {'C', 3},
    {'D', 4},
    {'E', 5}
  };

  {
    decltype(um)::size_type c = um.bucket_count();
    decltype(um)::size_type s = um.size();
    std::cout << "before clear(): bucket_count() = " << c << std::endl;
    std::cout << "before clear(): size() = " << s << std::endl;
  }

  um.clear();

  {
    decltype(um)::size_type c = um.bucket_count();
    decltype(um)::size_type s = um.size();
    std::cout << "after clear(): bucket_count() = " << c << std::endl;
    std::cout << "after clear(): size() = " << s << std::endl;
  }
}

出力

before clear(): bucket_count() = 13
before clear(): size() = 5
after clear(): bucket_count() = 13
after clear(): size() = 0

[faithandbrave]

なるほど。
ここでのポイントは以下の3点になるかと思います。

• cpprefjpにおけるunordered連想コンテナのclearページでの仕様記述が間違っているか
  • これは間違っているとは言えないので、そのままにしておく必要がある
• 「バケット数に比例する」実装の場合、「size()に比例する」という仕様には合致するのか
  • おそらく合致する。要素を削除する回数として考える場合、バケットをイテレートする回数は考慮する必要がない
    • これが正の場合は、実装への備考として「実際の実装ではbucket_count()に比例する」という追加の記述は必要なさそう
• 実装に対する備考としてどのような内容を記載すべきか
  • 全バケットが削除されるわけではなくバケットは維持されるという注意事項を記載する必要がある？
    • 必要に応じて空のunordered_mapとswapしたり、rehash()する必要があるという記述にする？

[math-hiyoko]

• cpprefjpにおけるunordered連想コンテナのclearページでの仕様記述が間違っているか
  • これは間違っているとは言えないので、そのままにしておく必要がある

こちら承知いたしました

• 「バケット数に比例する」実装の場合、「size()に比例する」という仕様には合致するのか

個人的にはこれは「合致していない」と考えます。
バケットをイテレートしている時点で、最低でもバケット数に比例した計算量の処理が発生しているためです。
https://ideone.com/LBt9Wo

• 実装に対する備考としてどのような内容を記載すべきか

上記二点を踏まえて、以下の点を記載すべきだと考えます

• https://eel.is/c++draft/unord.req.general によればsizeに比例する計算量が発生するとされている
• 実際の実装（gccやclang LLVM）ではバケット数に比例した計算量が発生している（注意事項として記載）

バケットの維持に関しては何も述べなくていいのではないかと個人的には思ってます。このメソッドの効果でバケットに関しては何も触れられていないためです。

[math-hiyoko]

bucket_countを様々に変えてclearの速度を計測しました
確かに要素数に関係なくbucket_countの大きさに比例しています
https://ideone.com/78vKAn

[faithandbrave]

検証ありがとうございます。

まず計算量について。仕様も場所によっては「正確にsize()回のデストラクタ呼び出しを行う」のように書かれていますが、ここではsize()に比例して何を行うかまでは記載されていません (ビッグオー記法と詳細な計算量説明が混在している)。
ですので、備考としてはより詳細に「バケット数 x その要素数だけ何を行うか」まで記載して、ビッグオー記法で説明しきれていない部分を補完するのはいかがでしょうか。

clear()の動作としては、要素が破棄されたバケットが残り続けているというのは、バケットの再利用という点では高速化が期待される一方で、動的メモリが残り続ける問題がある気はしています。
その点で、完全に解放する方法は記載あってもいい気はします。

[math-hiyoko]

分かりました

そうしましたら以下のような形で記載するのでいかがでしょうか？

計算量

本関数呼び出し前のコンテナの要素数(size())回のデストラクタ呼び出しが行われる。

計算量に関する備考

多くの実装（gcc, clang LLVMなど）では、全バケットの破棄も行われる(バケットのために確保された動的メモリは解放されない)。この操作には本関数呼び出し前のバケット数(bucket_size())に比例した計算量がかかる。

備考

本関数は要素の削除を行うのみであり、バケット数(bucket_size())の変更は行われない。
そのためバケットのために確保された動的メモリは残り続ける。これを完全に解放するには次のいずれかを行う。

// 方法1 : 空のオブジェクトと swap
std::unordered_set<int> tmp;
s.swap(tmp);

// 方法2 : rehash(0) でバケットを再確保
s.clear();
s.rehash(0);

[akinomyoga]

まず前提として cpprefjp は実際の処理系の観察に基づくのではなく、規格が保証している内容をベースにして各処理系の特性を備考として記述するという形になっています。従って、規格が保証していない内容を (但し書きなく) 断定的に書くことは避けたいことと思います。

規格でいうコンテナの計算量は "実際にかかる計算時間" や "空間計算量" ではなくてコンテナに含まれるオブジェクトに対する操作の数ということになっています (cf [container.requirements.pre]/2) ¹。一般的にもコンテナの計算量は要素に対する操作の数で議論することが多いことと思います。上記提案ですと、size() 回のデストラクタ呼び出し以外にオブジェクトに対して何らの操作も行われないことが保証されているようにも読めます。飽くまで「コンテナに含まれるオブジェクトに対する操作の数が size() に対して線形である」ということを誤解が生じないように書くのが良いではないでしょうか。備考として、計算量にはバケットに対する操作は含まれないこと、実際の計算時間と計算量は異なる概念であるということ、などなど書くのが良いと思います。

本関数は要素の削除を行うのみであり、バケット数(bucket_size())の変更は行われない。

これは保証されていますか? 要素が少なくなった時の rehashing が unordered_map で全般に要求されていない理由は unordered_map::max_load_factor で説明されていますが、殊に a.clear() に関しては全イテレータ・参照が無効化するので、親切な処理系なら自動で rehash してハッシュ空間を縮小しても良いような気がします。

// 方法2 : rehash(0) でバケットを再確保
s.clear();
s.rehash(0);

.rehash(0) でバケットの数が減少することは保証されていますか? 関数名的には減少して欲しいような気がしますが、規格の Postconditions を見る限りは rehash() はバケットを増やしたいとき専用のように見えます。

追記: 他に言葉尻などありますがそれは PR 上で。

Footnotes

1. その意味で、バケットの走査は計算量にはカウントされませんので、現状の記述があながちに間違いとはいえません。ただ、そのことが記事内で明記されていないのが分かりにくいのは事実です。 ↩

[faithandbrave]

@akinomyoga さんのおっしゃるように、規格に明記されているもの以外は断定的にはしない感じでお願いします。

計算量の直接の仕様については、規格を反映したものとして現在の記述は正しいですので、ここは変更しないでいただきたいです。
ここを変えたい場合は、C++標準化委員会のLWG (Library Working Group) にDefect Reportを送って採用される必要があるかと思います。仕様解釈としてどう考えても合致しないけどC++標準化委員会のメンバーに相談したい場合は、std-proposalsやstd-discussionのメーリングリストがあるので、そちらで相談するのがよいかと思います。

rehash()は、バケット数がn以上になるよう調整するものなので、たしかに小さくする用途ではなさそうですね。

[math-hiyoko]

計算量の直接の仕様については、規格を反映したものとして現在の記述は正しいですので、ここは変更しないでいただきたいです。

承知しました。
そうしたら基本的には今記述されているものは変えず、備考のみを追加する形で変更を行うことになりますね。

規格でいうコンテナの計算量は "実際にかかる計算時間" や "空間計算量" ではなくてコンテナに含まれるオブジェクトに対する操作の数ということになっています (cf [container.requirements.pre]/2)

備考として、計算量にはバケットに対する操作は含まれないこと、実際の計算時間と計算量は異なる概念であるということ、などなど書くのが良いと思います。

なるほど、このことを僕が存じ上げておらず判然としない議論にしてしまっていました。
このことはぜひ備考で明記しておきたいです。

[math-hiyoko]

以下の案でいかがでしょうか？
PR #1450 にも同様の変更をしていますので、必要であればPRにsuggestionなど頂ければと思います

備考

• clear() は バケット数(bucket_count())を縮小することを規格上は要求していない。
  実装によっては clear 後もバケット配列が温存され、動的メモリが残る場合がある。
• メモリを確実に解放したいときには以下の操作を行う

std::unordered_set<int> tmp;
s.swap(tmp);

計算量

本関数呼び出し前のコンテナの要素数（ size() ）に比例

計算量に関する備考

• 多くの実装（GCC libstdc++, LLVM libc++ など）は
  1. すべてのバケットを順に走査し
  2. 各バケットを破棄する

という手順を取るため、実行時間は概ね bucket_count() + size() に比例する傾向がある。
これは規格が定義する「計算量」（オブジェクトに対する操作の数）とは別物である。