タグ

データ構造に関するytokuのブックマーク (3)

  • ABA問題 - Wikipedia

    この記事には参考文献や外部リンクの一覧が含まれていますが、脚注による参照が不十分であるため、情報源が依然不明確です。適切な位置に脚注を追加して、記事の信頼性向上にご協力ください。(2023年1月) ABA問題(英: ABA problem)とは、マルチスレッドプログラミングにおいて同期化の過程で発生する問題であり、ある記憶域を二回読み出し、二回の読み出しが同じ値であることを「変更がない」とみなすことにしたとき、二回の読み出しの間に別のスレッドが値を変更し、他の作業を行った後また元の値に戻すと、最初のスレッドが誤って「変更がなかった」とみなしてしまうというものである。 ABA 問題は、複数のスレッドや(or プロセス)が共有されたメモリにアクセスする場合に生じる。下記のイベントの流れは、ABA 問題を発生させる。 プロセス が共有メモリから値 A を読み出す はプリエンプトされ、プロセス が

  • ときどきの雑記帖 - スタックを使ってキューを実装

    ■_ ・ボールペン LAMY【ラミー】 ボールペン pico(ピコ) L284 プラチナコート わたしが使ってるのは実はこの色じゃないんですが、これしかなかったので:) いろいろと携帯用のボールペンを試してきましたが、これで決まりという感じです。 値段が高いのがちと難点ですが、安くて(といいつつも1000円くらいはする)も すぐにダメになるとか不満がでるよりはいいと思います。 どんなのを試してきたのか全部アサマシ貼り付けたいところなんですが、 メーカーやら思い出したり調べたりするのが面倒なのでそれは止めます。 よく手帳と一緒にあるようなものだと、軸が細くて書きにくいのと、 先の円錐形になってるところがすぐに取れちゃうんですよね。 使い方が悪いといわれればそうなのかもしれませんけど。 ほかにも、この LAMY Pico のように普段は格納形式で使うときに伸ばすタイプのも 二つ三つ試しましたが

  • ブルームフィルタ - Wikipedia

    この項目では、確率的データ構造について説明しています。画像にぼかし効果を付加する画像フィルタについては「川瀬のブルームフィルター」をご覧ください。 ブルームフィルタ(英語: Bloom filter)は、1970年に Burton H. Bloom が考案した空間効率の良い確率的データ構造であり、あるデータが集合の要素である(集合に含まれている)かどうかの判定に使われる。ただし判定は正確ではなくて、含まれていないのに含まれていると誤って判定すること偽陽性(false positive)の可能性がある。しかし含まれているものを含まれていないと誤判定すること偽陰性(false negative)はない。なお集合に要素を追加することはできるが、集合から要素を削除することはできない(ただし、拡張をした counting filter であれば削除もできる)。集合に要素を追加していくにつれて偽陽性の

    ブルームフィルタ - Wikipedia
    ytoku
    ytoku 2009/12/10
    なるほど。集合Aに対して ハッシュ関数集合H={h_1, ..., h_k}; フィルタのデータF={h(x)|h∈H, x∈A}; でxがAの要素かどうかの判定が(∀h∈H)h(x)∈F
  • 1