non-blockingの意味するところ - くまメモ
海外の文献を読み漁っていると気づくのですが 2003年を境にこの文脈で使われる言葉の定義が変わります。 ↑2003年ごろまでの構図 ↑現在の構図。*1 non-blocking = obstruction-free という理解でもおおよそ間違いではないとは思いますが 論文を読むに当たって non-blocking = ロックを使わないアルゴリズム全般 obstruction-free = 非lock-freeだけどロックだけはしない というニュアンスの違いを感じます。 以後、現在の構図の方を前提に話します。ご注意ください。 まずは3つの分類の違いから wait-free 操作が「他のスレッドの動向に関わらず有限ステップで完了できる」場合、そのアルゴリズムはwait-freeと呼ばれます。starvation-freeと呼んだりもします。 実際には初めからここに分類されるアルゴリズムは多くあ
Using Bloom Filters
Using Bloom Filters Apr 8, 2004 by Maciej Ceglowski Anyone who has used Perl for any length of time is familiar with the lookup hash, a handy idiom for doing existence tests: foreach my $e ( @things ) { $lookup{$e}++ } sub check { my ( $key ) = @_; print "Found $key!" if exists( $lookup{ $key } ); } As useful as the lookup hash is, it can become unwieldy for very large lists or in cases where the
quick sortよりも高速でmerge sortのように安定しているソートアルゴリズムtim sort [勘違い] - Islands in the byte stream
<追記>ベンチマークプログラムに誤りがありました。ソート済のシーケンスに対してソートを掛けていました。ご指摘ありがとうございます＞ak氏 そんな夢のようなソートアルゴリズムがあるのかというと、あるらしいんです。それがtim sortと呼ばれるアルゴリズムです。 画期的（？）なソートアルゴリズム「Sleep Sort」：濃縮還元オレンジニュース｜gihyo.jp … 技術評論社 このあたりで拾ってきたネタですね。 merge sortを改良したアルゴリズムで、安定*1しており、しかも実行速度にも優れているとか。アルゴリズムの性能の評価は済んでいるらしく、CPythonやJDK7には既に導入済みのようですね。 ならば当然Perlのソートも…と考えるわけですが、まず評価のためにJavaのソースをC++にそのまま移植してみました。それがこれ（いちおうテスト済）： https://github.co
![quick sortよりも高速でmerge sortのように安定しているソートアルゴリズムtim sort [勘違い] - Islands in the byte stream](https://cdn-ak-scissors.b.st-hatena.com/image/square/f9103c273a45047a455a47c2322a4ec545cd77ee/height=288;version=1;width=512/https%3A%2F%2Fogimage.blog.st-hatena.com%2F17680117127143682567%2F17680117127143702106%2F1558185862)
Clever Algorithms: Nature-Inspired Programming Recipes
Need help getting started with Genetic Algorithms, Neural Networks or Swarm Intelligence? Nature-Inspired Algorithms are Fascinating! But implementing them can be frustrating. The algorithm descriptions are incomplete, inconsistent and distributed across academic papers, websites and code. There are so many algorithms to choose from, it can feel overwhelming. Algorithms Handbook You need a handboo
10兆までの素数リスト - 雷雲の変奏曲
プログラミングコンテストチャレンジブックを読んでいたら、素数リストの作り方が出てきた。 そういえば、１０兆までの素数リストを作ってみる、なんて記事があったな。 これだ http://itpro.nikkeibp.co.jp/article/Watcher/20100519/348242/?ST=develop 読み返しているうちに、ついつい挑戦してみる気になってしまった。 色々試して意外だったのが、10億までの素数をリストアップした場合でも「試し割り」より「エラトステネスの篩」の方が100倍以上も高速だったことだ。リストが大きくなればその差はますます開いていく。 メモリ上の広い範囲をまんべんなくアクセスするエラトステネスの篩は、実際には効率が悪いのではないかと思ったりしたのだが、見当が外れてしまった。 考察してみるに 試し割りは意外と無駄が多い。まず素数の密度だがn/log(n)に従うらし
Binary Indexed Tree (Fenwick Tree) - naoyaのはてなダイアリー
圧縮アルゴリズムにおける適応型算術符号の実装では、累積頻度表を効率的に更新できるデータ構造が必要になります。もともと算術符号を実装するには累積頻度表が必要なのですが、これが適応型になると、記号列を先頭から符号化しながら、すでに見た記号の累積頻度を更新していく必要があるためです。 累積度数表をナイーブに実装すると、更新には O(n) かかってしまいます。配列で表を持っていた場合、適当な要素の頻度に更新がかかるとその要素よりも前の要素すべてを更新する必要があります。適応型算術符号のように記号を符号化する度に更新がかかるケースには向いていません。 Binary Indexed Tree (BIT, P.Fenwick 氏の名前を取って Fenwick Tree と呼ばれることもあるようです) を使うと、累積頻度表を更新 O(lg n)、参照 O(lg n) で実現することができます。BIT は更
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Intrusive linked lists - Data structures in practice