ラスベガス法 - Wikipedia
英語版記事を日本語へ機械翻訳したバージョン（Google翻訳）。 万が一翻訳の手がかりとして機械翻訳を用いた場合、翻訳者は必ず翻訳元原文を参照して機械翻訳の誤りを訂正し、正確な翻訳にしなければなりません。これが成されていない場合、記事は削除の方針G-3に基づき、削除される可能性があります。 信頼性が低いまたは低品質な文章を翻訳しないでください。もし可能ならば、文章を他言語版記事に示された文献で正しいかどうかを確認してください。 履歴継承を行うため、要約欄に翻訳元となった記事のページ名・版について記述する必要があります。記述方法については、Wikipedia:翻訳のガイドライン#要約欄への記入を参照ください。 翻訳後、{{翻訳告知|en|Las Vegas algorithm|…}}をノートに追加することもできます。 Wikipedia:翻訳のガイドラインに、より詳細な翻訳の手順・指針につい
モンテカルロ法 - Wikipedia
モンテカルロ法（モンテカルロほう、（英: Monte Carlo method、MC）とはシミュレーションや数値計算を乱数を用いて行う手法の総称。元々は、中性子が物質中を動き回る様子を探るためにスタニスワフ・ウラムが考案しジョン・フォン・ノイマンにより命名された手法。カジノで有名な国家モナコ公国の4つの地区（カルティ）の1つであるモンテカルロから名付けられた。ランダム法とも呼ばれる。 計算理論の分野において、モンテカルロ法とは誤答する確率の上界が与えられる乱択アルゴリズム（ランダム・アルゴリズム）と定義される[1]。一例として素数判定問題におけるミラー-ラビン素数判定法がある。このアルゴリズムは与えられた数値が素数の場合は確実に Yes と答えるが、合成数の場合は非常に少ない確率ではあるが No と答えるべきところを Yes と答える場合がある。一般にモンテカルロ法は独立な乱択を用いて繰り
linux のシステムコールをフックする : DSAS開発者の部屋
最近、とあるクローズドソースなデバイス管理ツールの挙動が気になり、その動作について解析してみることにしました。 プログラムをデバッグしたり解析したい時、どんなシステムコールが呼ばれ、どのような引数が渡されているかを、調べることができる strace は非常に有用です。 しかし、strace では ioctl で渡される複雑なデータ構造を表示することはできないため、システムコールをフックして引数を表示するという手段を取ることにしました。 そんな訳で linux でシステムコールをフックする方法について調べて見たところ、意外といろいろな方法が有ることを知りましたので、試してみた方法を幾つか紹介したいと思います。 注)今回の実験に使用した linux kernel のバージョンは 2.6.25.11 です。異なるバージョンではこの実験通りにはならない場合があります。 LD_PRELOAD を使っ
Ｇｏｏｇｌｅおかげさまで 10 周年
Google の使命は、世界中の情報を整理し、世界中の人がアクセスできて使えるようにすることです。
cpainvestor.com | 超長時間労働を厭わない組織風土をいかにして変えていくべきか
現役会計士が語るビジネス・会計・投資コラム このWebサイトに記載された事項は執筆者の私見であり、執筆者の所属ないし関係する機関・組織の見解ではないことをお断りしておきます。 1年半ほど前、今の主だったメンバーと仕事をするようになって、心に誓ったことが一つあります。「どんなにつらい状況に追い込まれたとしても、絶対に徹夜だけはするまい！」という信念です。 私が来る前の今のメンバーの組織は、「クライアントの期待に応える報告をするためには、何日か連続の徹夜も辞さない！」という方々が集まっていました。というか、そういう方しか残れない組織になっていました。「いくら日程的にタイトな状況に追い込まれることが多いM&A関連業務とはいえ、この状況は酷すぎる。体力的、精神的につらいからと言って反発して逃げるのではなく、自分が絶対にこの組織風土を変えてやる！」そう固く誓って、今のメンバーに合流しました。 それか
Skip Lists
Skip Lists は 1990年に William Pugh によって開発されたリスト構造体の一種である。 オリジナルの論文は William Pugh, "Skip Lists: A Probablistic Alternative to Balanced Trees", Communications of the ACM, June 1990 となっている。 この論文は ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf からコピーを入手可能である。 また、Unix Magazine 1999年 1月号 を入手できれば、 そこには日本語で書かれた解説があるが、 これはほとんど論文丸写しに近いので、きっと重宝するだろう。 数多くの、要素が増減しなおかつ入れ替わるようなデータ構造で、 さらにランダムアクセスが
要素の挿入、削除、ランダムアクセスが全部高速なリストを作った - kaisehのブログ
スキップリスト（Skip List）は1990年に発表された比較的新しいアルゴリズムで、要素の挿入や削除、検索を平衡木と同等のパフォーマンスで実行可能なリスト構造です。 Skip Listは連結リストの多層構成になっています。路線に例えると、最下層のリンクは各駅停車のように、全要素を結んでいます。一方、上層のリンクは急行や特急のように、途中の要素をスキップするようになっています。この路線を特急→急行→…→各駅と乗り継ぐことで、目的の要素に高速に到達できる仕組みです。もっと詳しい解説はこちらやこちらにあります。 で、ここからが本題です。Skip Listの実装はいくつも出ているんですが、Sorted Listとしての実装ばかりで、要素を任意順序で格納できてランダムアクセス（indexを指定してのアクセス）可能なSkip Listが見つからなかったので、自分で作ってみました。 通常のSkip
スキップリスト - Wikipedia
スキップリスト（英: skip list）は、平衡二分探索木と似た用途に使う乱択アルゴリズムのデータ構造。連結リストを並列に連結させて作る。比較により順序づけ可能な要素を挿入し、スキップリスト内ではソートされた状態で保持される。ソートされた連想配列や集合の実装などに使える。挿入と探索と削除は平均O(log n)である。1989年にウィリアム・ピューが発表した[1][2][3][4]。 スキップリストは順序つきの連結リストの前向きの飛び越しのリンクを追加したものである。ノードは幾何分布や負の二項分布にてランダムに高さを設定して追加され（高さ1が確率50%、高さ2が25%、高さ3が12.5%など）、リスト上の探索において連結リストの一部を高速に飛ばすことができる。 スキップリストの例。1〜10を追加し、ソートされた状態で保持されている。 スキップリストはリストの階層になっている。最下層は通常の
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
C/C++ Reference
Randomized Binary Search Trees