非復元抽出の高速かつ実装が簡単な方法を考える - シリコンの谷のゾンビ
※ @tomerun さんに書いてもらったコードとその検証結果を記事の最後に追記しました．(2013-07-21 2:00) ふとしたきっかけで非復元抽出 (random sampling without replacement) を実装するときに気になったのでどんな実装がよいのか考えてみた．なお非復元抽出はビンゴのように，N個の要素の中からk個の異なる要素をランダムに選択するという意味である． 復元抽出については @unnonouno さんのブログなどに書いてあり，非復元抽出についてもリンクが張ってあったのだけれど，リンク先のブログ記事が読めない状態になっていていたのが残念． unnonouno: 高速な復元抽出の直感的な説明 はじめに std::vector
FLP35-C. 浮動小数点数値を比較する際には精度を考慮する
FLP35-C. 浮動小数点数値を比較する際には精度を考慮する C の浮動小数点演算は正確ではない。特に、浮動小数点数を比較する際は、可搬性があり計算結果が同じになる方法で行う必要がある。 違反コード c と a / b の比較の結果は、あらかじめ予測することはできず、実行するマシンやコンパイラ、最適化レベルの違いによって変わる可能性がある。 float a = 3.0; float b = 7.0; float c = a / b; if (c == a / b) { printf("Comparison succeeds\n"); } else { printf("Unexpected result\n"); } 処理系固有の詳細 このコードを、IA-32 Linux 上の GCC 3.4.4 で最適化レベル 1 以上、あるいは IA-32 Windows XP 上の Microsof
min_heapを用いた上位r個の要素の抽出 - tsubosakaの日記
MG勉強会の発表があるため4.6ランキング検索の部分を読むついでに、最後のサブセクションの上位r個の要素を取り出す部分について実装してみた。 情報検索において、N個の候補集合から上位r個の要素を取り出すことが多い。 値が配列に格納されているとするとこれを実現するためのコードはもっとも単純に行うと以下のようになる //長さlenの配列arrayの中でトップr個の値をresultに挿入する void sort_method(int * array , int len, int r , vector<int> & result){ sort(array , array + len); copy(array + len - r , array + len , back_inserter(result)); } しかし、Nが大きいとき、MGの例だとN=100万のときにsortの処理にはおおよそ100
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
GitHub - mapbox/earcut.hpp: Fast, header-only polygon triangulation
