unordered 系コンテナの max_load_factor 周りについて - melpon日記 - HaskellもC++もまともに扱えないへたれのページ
この記事は LL/ML Advent Calendar １９日目の記事です。 C++11 で追加された unordered 系のコンテナは、ハッシュを使って要素を管理するコンテナです。 そのハッシュを使ったアルゴリズムもいくつかありますが、C++11 では OpenHashing 方式を想定しているようです。 OpenHashing 方式は、同じバケットに対して複数の要素が入ってしまう場合、リンクリストなどでそれらの要素を繋いでやる方式です。 細かいことやその他の方式については SlideBoom closed down を見ましょう。 この記事では C++11 の unordered 系コンテナ特有の、バケットやリハッシュ関数について説明します。 バケット操作関数 バケットの数は bucket_count() で取得できます。また、n 番目のバケットに入っている要素数は bucket_s
平方根のアルゴリズム
平方根である。sqrtである。私の数学知識は非常に乏しく、かろうじて平方根の何たるかを解するばかりであるが、ふと、平方根を計算するアルゴリズムが知りたくなった。理由は、constexprなsqrtを実装してみたくなったからだ。 日本語では、いい情報がWeb上に存在しないので、ここに書いておく次第。この説明は、私のように数学の知識を持たない人間にも理解できるはずである。 ここで使うのは、バビロニア人の方法（Babylonian method）と呼ばれている、歴史あるアルゴリズムである。この方法は、手動でも、プログラミングでも、非常に簡単に計算できる、大変便利で汎用的なアルゴリズムである。しかも、速度もそれほど遅くない。 √Sに対して、 任意の正の整数を初期値X0と定める（できるだけ平方根に近い値が望ましい） Xn+1を、Xnと S / Xnの平均値とする（平均値は相加平均で求める） 必要な精
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
