C++ Academy · レッスン

パフォーマンス上の考慮事項

Q: 「パフォーマンス上の考慮事項」で何を学びますか？

バケットと負荷率を理解します ブラウザで直接実行するハンズオンコードでC++ Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

バケットと負荷率を理解します

「パフォーマンス上の考慮事項」はCoddyKit上の無料C++ Academyレッスンです。これはレッスン4/4です。下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。これはC++ Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 C++ Academyコースには全4レッスンが含まれています。

ハッシュテーブルがデータを格納する仕組み

順序付けされないコンテナは、バケットの配列を保持します。キーのハッシュによってバケットが選ばれ、1つのバケットに複数のキーが入ると、線形に検索するチェーンが形成されます。

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m{{1, 1}, {2, 2}, {3, 3}};
    std::cout << "bucket count: " << m.bucket_count() << '\n';
    return 0;
}

どのバケットか

bucket(key) は、現在そのキーが対応付けられているバケットインデックスを示します。

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m{{10, 1}, {20, 2}, {30, 3}};
    std::cout << "key 20 in bucket " << m.bucket(20) << '\n';
    return 0;
}

負荷率

負荷率は size / bucket_count です。負荷率が高いほどチェーンが長くなり、検索が遅くなります。

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m{{1, 1}, {2, 2}};
    std::cout << "load factor: " << m.load_factor() << '\n';
    return 0;
}

最大負荷率

max_load_factor() はしきい値です。負荷率がこの値を超えると、テーブルはより多くのバケットへ再ハッシュされます。

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m;
    std::cout << "default max load: " << m.max_load_factor() << '\n';
    return 0;
}

再ハッシュ

再ハッシュでは、より多くのバケットを持つテーブルを再構築するため、コストが高くなります。負荷率がしきい値を超えると自動的に行われます。

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m;
    std::size_t before = m.bucket_count();
    for (int i = 0; i < 100; ++i) m[i] = i;
    std::cout << before << " -> " << m.bucket_count() << " buckets\n";
    return 0;
}

再ハッシュを避けるために reserve する

あらかじめサイズが分かっている場合は、reserve(n) を呼び出してバケットを事前に確保し、繰り返しの再ハッシュを避けます。

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m;
    m.reserve(1000);
    std::cout << "buckets reserved: " << (m.bucket_count() >= 1000 ? "yes" : "no") << '\n';
    return 0;
}

rehash を直接使う

rehash(n) はバケット数を少なくとも n に設定します。要素数には reserve を、バケット数には rehash を使います。

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m;
    m.rehash(64);
    std::cout << "buckets >= 64: " << (m.bucket_count() >= 64 ? "yes" : "no") << '\n';
    return 0;
}

バケットサイズを調べる

bucket_size(i) は、バケット i を共有する要素数を示します。衝突の診断に役立ちます。

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m;
    for (int i = 0; i < 10; ++i) m[i] = i;
    std::cout << "bucket 0 holds " << m.bucket_size(0) << " elements\n";
    return 0;
}

最悪の場合は O(n)

ハッシュが粗悪で衝突が多いと、すべてのキーが1つのバケット内でチェーンになり、操作の計算量が線形時間に低下します。良いハッシュなら O(1) を維持できます。

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m;
    for (int i = 0; i < 5; ++i) m[i] = i * i;
    std::cout << "avg lookups stay fast with good hashing\n";
    std::cout << "load: " << m.load_factor() << '\n';
    return 0;
}

最大負荷率を下げる

max_load_factor を低く設定すると、メモリを速度に振り替えられます。衝突は減りますが、バケット数は増えます。

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m;
    m.max_load_factor(0.5f);
    std::cout << "new max load: " << m.max_load_factor() << '\n';
    return 0;
}

イテレータの無効化

再ハッシュが発生するとイテレータは無効になりますが、要素への参照とポインタは有効なままです。それに合わせてループを設計してください。

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m{{1, 100}};
    int& ref = m[1];
    m.reserve(500);
    std::cout << "reference still valid: " << ref << '\n';
    return 0;
}

クイックチェック

ハッシュテーブルの性能について理解度を確認しましょう。

まとめ

ハッシュテーブルの内部の仕組みについて学びました。

キーはバケットに対応付けられ、衝突によってチェーンが形成されます
負荷率 = size / bucket_count。max_load_factorを超えると再ハッシュが実行されます
再ハッシュを避けるにはreserveを使用します。再ハッシュによってイテレーターは無効になりますが、参照は無効になりません

次のコースでは、fstreamを使ったファイルの読み書きを学びます。

よくある質問

「パフォーマンス上の考慮事項」レッスンは無料ですか？

はい。「パフォーマンス上の考慮事項」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、C++ Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 C++ Academyコースには全4レッスンが含まれています。

「パフォーマンス上の考慮事項」で何を学びますか？

バケットと負荷率を理解しますブラウザで直接実行するハンズオンコードでC++ Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

C++ Academyを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのC++ Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。これはレッスン4/4です。

「パフォーマンス上の考慮事項」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このC++ Academyレッスンでコードを書いて実行できますか？

はい。すべてのC++ Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

std::unordered_map
unordered_set
カスタムハッシュ関数
パフォーマンス上の考慮事項

← C++ Academyに戻る