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
汎用ソート殺し - d.y.d.
00:26 12/12/18 BookLive! 7月に出会ってからずっと電子書籍ストアとして BookLive! をひいきにしているのですが、一体どこが好きなのか語りたくなりました。 ITMedia の これでもう迷わない、電子書店完全ガイド という一連の記事の、 電子書籍の端末の話よりストアの話をしましょうよというコンセプトに思いっきり影響されています。 といっても、第一印象が「普通のことが普通にできるので感激した！！」というもので、 つまり今年の前半に使っていた幾つかの電子書籍ストア/専用アプリが残念だっただけかもしれません。 買った本がどこをクリックすれば読めるのか理解するのに10分かかった、とか、 6冊以上買うと本棚アプリから画面外に本がはみ出るので手でいちいち棚を変えて整理しないと読めない、とか。 本当に普通に使えるという以上に特筆することもないんですが、 あ、でも、今年になる
自動改札機の運賃計算プログラムはいかにデバッグされているのか？ 10の40乗という運賃パターンのテスト方法を開発者が解説（前編）
自動改札機の運賃計算プログラムはいかにデバッグされているのか？ 10の40乗という運賃パターンのテスト方法を開発者が解説（前編） ふだん何気なく使っている鉄道。改札を降りるときにICカードを自動改札にかざすと、「ピッ」という音と共に一瞬のうちに運賃を計算してくれます。けれど、複数の路線を乗り継いだり、途中で定期券区間が挟まっていたりと、想像しただけでもそこには膨大な組み合わせがあります。それでも運賃計算プログラムはわずか一瞬で正しい運賃計算が求められ、バグがあったら社会的な一大事にもつながりかねません。 爆発的な計算結果の組み合わせがあるはずの運賃計算プログラムは、どうやってデバッグされ、品質を維持しているのでしょうか？ 9月12日から14日のあいだ、東洋大学 白山キャンパスで開催された日本科学技術連盟主催の「ソフトウェア品質シンポジウム 2012」。オムロンソーシアルソリューションズ 幡
「フカシギの数え方」の問題を解いてみた
先日、「『フカシギの数え方』 おねえさんといっしょ！ みんなで数えてみよう！」という動画を見た。格子状のマスの左上から右下までの経路が何通りあるのかを調べて、格子が多くなればなるほど組み合わせの数が爆発的に増えることを教えてくれる動画だ。これは自己回避歩行(Self-avoiding walk)と呼ばれている問題らしい。 これだけ聞いてもそれほどインパクトはないのだが、動画に出てくるおねえさんの経路を調べあげる執念がもの凄く、ネット上でも結構な話題になっている。執念と言うよりも狂気に近い。しかし、話題になった割には動画内で言及されている高速なアルゴリズムを実装したという話を聞かなかったので、自分で確かめることにした。 動画のおねえさんは深さ優先探索によるプログラムを使っていると思われるが、それだとスパコンを使っても10×10マスの格子を解くのに25万年も掛かってしまう。そこで、高速化のため
［CEDEC 2012］プレイヤーはごまかされている？ アクセスゲームズの開発者が語るAIキャラクターの実装手法
［CEDEC 2012］プレイヤーはごまかされている？ アクセスゲームズの開発者が語るAIキャラクターの実装手法 編集部：荒井陽介 開催中のCEDEC 2012で，アクセスゲームズの今井新太郎氏と片岡英樹氏による「ゲームAIはプレイヤーを虜にできるか？ 〜アクションゲームにおいて、AIを使って華麗に誤魔化しつつ魅せる手法」というセッションが行われた。 タイトルから想像できるとおり，このセッションは，そこそこの出来のAIをうまく使って，高性能AIのように見せるという手法を紹介するもの。「戦国BASARA クロニクルヒーローズ」や「ACECOMBAT 3D CROSS RUMBLE」など，数々のタイトルを手がけるアクセスゲームズだけに，「なるほど」と思わせるものが多かったので，その模様をレポートしよう。 今井新太郎氏 片岡英樹氏 最初に今井氏は，アクセスゲームズが考えるAIの制作や使用方針を披
GPGPU時代のハッシュアルゴリズム
Coding Horror: Speed Hashing xkcd: Password Strength GPGPUが一般的になった現代では、従来のハッシュアルゴリズムは十分な強度ではないというお話。一般人が五百ドル程度で購入できるハイエンドグラフィックカードは、現在のハイエンドCPUより150倍も高速にハッシュ計算ができる。しかも、GPGPUで高速に計算できるということは、並列性が高いということを意味する。つまり、GPUを増やせば容易にスケールするので、さらに危ない。 もはや、MD5やSHA-1、SHA-2の時代は終わった。これからの開発者は、GPGPUに対しても十分な強度を持つ、容易に並列化できないハッシュアルゴリズムを採用しなければならない。 ユーザーは、長いパスワードを使わなければならない。現時点でのJeff Atwoodのおすすめは、12文字以上である。1(xY%08などという、
Why are elementwise additions much faster in separate loops than in a combined loop?
Suppose a1, b1, c1, and d1 point to heap memory, and my numerical code has the following core loop. const int n = 100000; for (int j = 0; j < n; j++) { a1[j] += b1[j]; c1[j] += d1[j]; } This loop is executed 10,000 times via another outer for loop. To speed it up, I changed the code to: for (int j = 0; j < n; j++) { a1[j] += b1[j]; } for (int j = 0; j < n; j++) { c1[j] += d1[j]; } Compiled on Micr
自動微分 ≪フォワード・モード≫ - d.y.d.
23:21 11/12/22 今年読んだ面白コンピュータサイエンス論文紹介カレンダー 第 n (1<n) 週目モードです。 ☆ 「難しい問題」 ☆ 「名のない関数」 ☆ 「演算のせいしつ」 「難しい問題」 [5] R. Impagliazzo and L. A. Levin. "No Better Ways to Generate Hard NP Instances than Picking Uniformly at Random." FOCS 1990. ランダム生成に興味があります。 パズルゲームを作りました。 さて、手強い難易度の面データを無限にランダム生成するにはどうすればいいだろう。 プログラミングコンテストの問題を作りました。 さて、自動チェック用のテストデータをランダム生成するにはどうすればいいだろう。 適当なランダム生成では、簡単なケースばっかり作られてしまい 嘘解法 に突
高速な安定ソートアルゴリズム "TimSort" の解説 - Preferred Networks Research & Development
先日、TimSortというソートアルゴリズムが話題になりました。TimSortは、高速な安定ソートで、Python(>=2.3)やJava SE 7、およびAndroidでの標準ソートアルゴリズムとして採用されているそうです。 C++のstd::sort()よりも高速であるというベンチマーク結果1が話題になり(後にベンチマークの誤りと判明)、私もそれで存在を知りました。実際のところ、ランダムなデータに対してはクイックソート(IntroSort)ほど速くないようですが、ソートというシンプルなタスクのアルゴリズムが今もなお改良され続けていて、なおかつ人々の関心を引くというのは興味深いものです。 しかしながら、オリジナルのTimSortのコードは若干複雑で、実際のところどういうアルゴリズムなのかわかりづらいところがあると思います。そこで今回はTimSortのアルゴリズムをできるだけわかりやすく解
Soft maximum 関数
Soft maximum 関数というものがある。簡単に言えば「なだらかな max 関数」だ。下のグラフのような曲線を描く（角張っているのが普通の max 関数）。 式も簡単だ。次のようなシンプルな式で表される。 softmax(x, y) = log(exp(x) + exp(y)) これをちょっといじくって次のようにすれば “soft minimum” 関数も実現できる。 softmin(x, y) = -log(exp(-x) + exp(-y)) 更にこのふたつを組み合わせれば “soft clamp” 関数も可能だ。 softclamp(x, min, max) = log(exp(max) + exp(-log(exp(-min) + exp(-x)))) ゲームなどを作っていると、とにかく値の変化をなだらかにしたいという場面がよくある。イーズイン・アウトと比較すると使用の機会は
Suffix Array を作る - SA-IS の実装
Suffix Array は今若者の間で人気のデータ構造です． マイ suffix array を実装することで，オシャレ度がアップしてモテ系になり，女子力も上がると言われています． その中でも今特に，手軽でクールな SA-IS (アルファベットサイズ固定の下で線形時間で省メモリで suffix array が作れる今最強のアルゴリズム) の実装がブームです． 僕もブームに便乗して，実装してみました． ところで，SA-IS は流行っているので，日本語でもすでに様々なところで記事が書かれています (日付順)． SAIS(Suffix Array - Induced Sorting) - EchizenBlog-Zwei SA-IS: SuffixArray線形構築 - sileの日記 SA-IS - (iwi) ｛ 反省します - TopCoder部 接尾辞配列(Suffix Array)の
数値の先頭に0を追加して桁をあわせる - うなの日記
数値の先頭に0を追加して桁をあわせる関数を書きました。 /** * 必要な桁数まで0を埋める。 * @param number 数値 * @param size 桁数 */ function fillZero( number, size ) { var s = Math.log( number ) * Math.LOG10E; for( i=1,n=size-s,str="";i<n;i++ ) str += "0"; return str+number; } サンプルは以下。 var out = document.getElementById("out"); out.innerHTML += "3, 1 : " + fillZero( 3, 1 ) + "<br/>"; out.innerHTML += "3, 2 : " + fillZero( 3, 2 ) + "<br/>"; ou
対数を使った数値の0詰め処理について解説してみた - Seasons.NET
JavaScriptでsprintfのフォーマット書式みたいに桁数に満たない数字の場合、 左0詰めをしてほしいのですが、それがないっぽいので調べていたところ。 こちらの記事にその式が掲載されており、 対数に対する知識が少し乏しかったので 学習がてらキモになるところ調べてみました。 ポイントとなるのは、 Math.log(x) * Math.LOG10E だと思います。これがなぜいきなり出てきているか？を解説してみます。 あとの計算は非常に簡単なので解説を割愛します。 まず数字の桁数を求める前に, 10 = 10 = pow(10,1) 100 = 10x10 = pow(10,2) 1000 = 10x10x10 = pow(10,3) と表すことができるのはわかりますよね。 powの第2引数は、指数を示しているわけですが、 この数に+1した数が桁数になっていますよね。 この指数(x)にあ
計算のきまり - d.y.d.
00:41 11/08/04 計算のきまり ( )を使った式の計算には次のようなきまりがあります。 （□ ＋ ○） × △ ＝ □ × △ ＋ ○ × △ （□ － ○） × △ ＝ □ × △ － ○ × △ ... たし算とかけ算には、次のようなきまりがあります。 □ ＋ ○ ＝ ○ ＋ □ （□ ＋ ○） ＋ △ ＝ □ ＋ （○ ＋ △） □ × ○ ＝ ○ × □ （□ × ○） × △ ＝ □ × （○ × △） この考えを使って、くふうして暗算で計算しよう。 小学校算数 5学年 - Wikibooks 分配法則・交換法則・結合法則。 とても当たり前で、当たり前すぎて、ほとんどの人は、もう特に意識することもない法則かもしれません。 でも、プログラミングを知っている僕らは、立ち止まってこの法則の価値に触れることができる。 末尾再帰化 最近のコンパイラは、こんな最適化をします。 i
STL風に使えるマップ型コンテナの紹介と性能比較 - Preferred Networks Research & Development
最近スマートフォンに乗り換えました。徳永です。 C++は世に数あるプログラミング言語の中では比較的メモリを食わない方ですが、それでもメモリ使用量が問題となる場合はあります。そのような場合の対処方法はいくつか有りますが、手軽に選択できる方法として、今日はSTLのmapやunordered_mapと同じ感じで使えるデータ構造をいくつか紹介したい思います。 以下、計算量の表記をする際には、要素数をnとします。 Loki::AssocVector LokiはModern C++ Designという本の作者であるAndrei Alexandrescuが開発したライブラリです。AssocVectorはその中の一つとして提供されているクラスで、vector<pair<key, value> >という型のベクターをkeyでソートした状態で持つ事により、二分探索による要素の探索を可能にしたデータ構造です。こ
ICFPC2011 - w_o’s diary
"CopyKawaii"で参加してた。どのカードが一番かわいいか議論になって僕はzombieかわいい派だったが、copyかわいい派がいたので腹いせに名前をそれにした。 ↓submitしたコード http://int.main.jp/files/ltg-opt.d.tar.gz 半分くらい使ってないが。(これも反省だなぁ) 色々反省はあるが、一応時系列で書いておくと、 最初どうしたらいいかわからんかった。 で、とりあえず、 LTGプログラムをもっと簡単に書けるようにする(eval.cppから呼ばれてる関数達) その上でアルゴリズム書く(zombie-help.cpp) という問題かなー、と、思って、 上を僕が、下を @taitai_jp が書いていた。 LTGプログラムは、定数書くのが超めんどくさくて、f (g 10) とかが書けないので、それをコンパイルするコードを書いた。 最初のメモによ
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
「なぜsetを使っちゃいけないの？」
http://homepage1.nifty.com/herumi/diary/1202.html
https://sleepy-yoshi.hatenablog.com/entry/20111002/p1
「ソートも、サーチも、あるんだよ」 ～標準C++ライブラリにみるアルゴリズムの面白さ