ランダムだと！？！？(ガタッ - 西尾泰和のはてなダイアリー
確かに、このテンプレには僕も飽きている： onk:「リンゴが10個あります。ランダムに3人で取り分けなさい」ってどうコードに落とすと綺麗かな。。 yoshiori: @onk ランダムだと！？！？ onk: @yoshiori 擬似ランダムでいいです yoshiori: @onk ふう、焦らせやがって……(俺の中でここまでテンプレ) yoshiori: もう、「ランダム」という言葉に反応してしまうのはネタでも良くない気がしてきた そこで新しいマサカリを考えてみた。「お前はなにを等確率にしたいんだ！？！？」 2個のりんごをAさんとBさんの2人に配ることを考えてみよう。全部で4通りの配り方がある。(A, A), (A, B), (B, A), (B, B)の4つだ。 この4通りを等確率にしたいのならば、それぞれのりんごについて1/2の確率でAとBに振り分ければ良い。ちなみにPythonのran
「フカシギの数え方」の問題を解いてみた
先日、「『フカシギの数え方』 おねえさんといっしょ！ みんなで数えてみよう！」という動画を見た。格子状のマスの左上から右下までの経路が何通りあるのかを調べて、格子が多くなればなるほど組み合わせの数が爆発的に増えることを教えてくれる動画だ。これは自己回避歩行(Self-avoiding walk)と呼ばれている問題らしい。 これだけ聞いてもそれほどインパクトはないのだが、動画に出てくるおねえさんの経路を調べあげる執念がもの凄く、ネット上でも結構な話題になっている。執念と言うよりも狂気に近い。しかし、話題になった割には動画内で言及されている高速なアルゴリズムを実装したという話を聞かなかったので、自分で確かめることにした。 動画のおねえさんは深さ優先探索によるプログラムを使っていると思われるが、それだとスパコンを使っても10×10マスの格子を解くのに25万年も掛かってしまう。そこで、高速化のため
平方根を使わずに高速で２点間の距離を近似する - きしだのHatena
２点間の距離の計算では平方根が必要になりますが、平方根は少し重い計算です。ということで、平方根を使わず、掛け算・割り算・足し算と絶対値・最大・最小だけで距離を近似する方法についての記事を翻訳してみました。 flipcode - Fast Approximate Distance Functions (12:02 補足：おそらく今の標準的なCPUでやる意味はほとんどないと思います。近似のアプローチとして面白いというくらいの話。Z80でやりましょう) 距離関数高速近似 by Rafael Baptista (27 June 2003) ２点間のユークリッド距離を求める計算式は次のようになる。 二次元では次のようになる。 この関数の計算には、平方根が必要になる。これは最近のコンピュータでも高価な計算である。平方根は逐次近似によって求められる。つまり、コンピュータは平方根近似のループを行って、与え
http://swatmac.info/?p=942
See related links to what you are looking for.
Bloom filterのシンプルな実装 - 西尾泰和のはてなダイアリー
Bloom filterは指定されたものがリストに含まれるならばTrue、含まれないならばFalseを返すようなデータ構造である。もちろん、単純にリストを保持するだけでもリストに含まれるかどうかの判定は可能だが、Bloom filterのメリットはオリジナルのリストを保存しておく必要がないという点にある。そのためメモリの消費量を格段に節約することができる。しかし、そのメモリ効率の代償として多少正確性が失われる。Bloom filterは指定されたものがリストにない場合でもたまにTrueを返すのだ。しかし、間違ってTrueを返す確率はあらかじめ計算することができるので、誤差が許容できる範囲であれば問題なく使うことができる。 下記はアルゴリズム勉強用のシンプルな実装である。 SIZE = 1987 def hashes(s): xs = [0, 0, 0] for c in s: o = or
Algorithm - 連想配列の実装としてのハッシュはオワコン? : 404 Blog Not Found
2012年01月17日11:45 カテゴリアルゴリズム百選Tips Algorithm - 連想配列の実装としてのハッシュはオワコン? 珠玉のプログラミング Jon Bentley / 小林健一郎訳 つまり「終わったコンテナ」。 以前からうすぼんやりと考えて来た危惧が、すこしはっきりと見えてきた。 徳丸浩の日記: Webアプリケーションに対する広範なDoS攻撃手法(hashdos)の影響と対策 もうそろそろハッシュ(テーブル)以外の手段の連想配列の実装手段を本格的に模索するべきではないか、と。 そのデータ構造は、君の魂を差し出すに足るものかい? 連想配列(Associative array)がコレクション(Collection)、すなわち数多のデータ構造をまとめるデータ構造としての覇者となったのはもはや疑いようがない事実でしょう「配列で実装されるデータ構造ではなくて、配列を実装するデータ構
機械学習 はじめよう 記事一覧 | gihyo.jp
運営元のロゴ Copyright © 2007-2025 All Rights Reserved by Gijutsu-Hyoron Co., Ltd. ページ内容の全部あるいは一部を無断で利用することを禁止します。個別にライセンスが設定されている記事等はそのライセンスに従います。
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
プログラミングコンテストでの乱択アルゴリズム