タグ

ProgrammingとAlgorithmに関するringo6119のブックマーク (4)

  • Cuckoo Hashing - Radium Software

    ハッシュテーブルからエントリーを検索する処理は,一般に定数時間で済むとされている。つまり,どんなにエントリーが増えても検索の速さは変わらない,ということ。データ構造の教科書には必ず載っていることだね。 でも実際には,ハッシュの衝突が起こった場合に,速度の低下が発生する可能性がある。例えば,一般的なチェイン法(オープンハッシュ)だと,衝突したエントリーに関して線形検索を行うことになるから,衝突が多ければ多いほど,定数時間からは遠のいてしまう。 この速度低下を防ぐ方法はいろいろある。なかでも cuckoo hashing (カッコウ・ハッシング)は仕組みが面白い。こいつは,エントリーの検索を必ず定数時間で済ませてくれるという優れものなんだ。 Cuckoo hashing では,2つのハッシュ関数と,2つのテーブルを用いる。ここでは,2つのハッシュ関数をそれぞれ h1, h2 として,2つのテー

    Cuckoo Hashing - Radium Software
  • VisuAlgo moves to https://visualgo.net/en

    Redirecting you to https://visualgo.net/en

  • t.dvi

    Purely Functional Data Structures Chris Okasaki September 1996 CMU-CS-96-177 School of Computer Science Carnegie Mellon University Pittsburgh, PA 15213 Submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy. Thesis Committee: Peter Lee, Chair Robert Harper Daniel Sleator Robert Tarjan, Princeton University Copyright c 1996 Chris Okasaki This research was sponso

  • 素数判別、素因数分解<アルゴリズム<Web教材<木暮

    学習のポイント 素数判別、素因数分解の基的なアルゴリズムを理解します。 キーワード アルゴリズム、素数、剰余、素数判別、エラトステネスのふるい、素因数分解 これまでは、素数研究が社会に直接関係することはあまりありませんでした。ところが、電子メールなどの暗号化が必要になりました。その暗号鍵、復号鍵では、「非常に大きいを素因数分解する計算には非常に時間がかかる」ことをベースにしています(→参考:「公開鍵暗号方式の原理」)。そのため、素数に関する関心が高まっているのです。 2,3,5,7,11,13,17,…など、1と自分自身でしか割り切れない数を素数といいます。12=4×3や、18=2×9のように、素数ではない数のことを合成数といい、2、3、4、9など、合成数を割り切れる数を約数といいます。そして、2や3など約数自体が素数であるとき、その約数を素因数といいます。 素数を扱うアルゴリズムは、大

  • 1