誤り許容カウント法(lossy count method)のサンプルプログラム
誤り許容カウント法(lossy count method)のサンプルプログラム 2010-05-12-1 [Programming][Algorithm] 1行1ラベル形式で、 1万種類のラベルを持つ、 100万行のデータがあるとします （ラベルの頻度分布はジップの法則にだいたい準拠するとします）。 各ラベルの頻度をハッシュを使ってカウントするとなると、ハッシュエントリ1万個分のメモリ容量が必要になります。（1万じゃたいしたことないな、という人はもっと大きな数に置き換えて読んでください。） しかし、カウント後に高頻度のものしか使わないということも多いと思います。例えば頻度5000以上のもののみ取り出してあとはいらない、とか。 そうなると、全部のラベルのカウントデータを最後まで保持するのは無駄に思えます。 そこで登場するのが「誤り許容カウント法(lossy count method)」。 低
幅優先探索で迷路の最短経路を探す
幅優先探索で迷路の最短経路を探す 2010-01-14-4 [Algorithm][Programming] 迷路の最短経路を探すプログラムを作成するという問題について。 - 人材獲得作戦・４ 試験問題ほか (人生を書き換える者すらいた。) http://okajima.air-nifty.com/b/2010/01/post-abc6.html これは単なる幅優先でOKですね。 足跡を記録していき、すでに別の子が通った道にぶつかるか（足跡の有無で判定）、行き止まりに到達したら枝狩り。 幅優先なんだからこれで見つかるのが最短経路。 後からの「最短性のチェック」は不要です。 「アルゴリズム知らないとできない」とか以前の問題で、正式にプログラミングの基礎を学んだ人ならできて当たり前の問題です。ピンと来ない人は、ポインタわからない、再帰わからない人と同列かなあ。 バリバリプログラミングからは一線
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
