たけまる / Algorithm::VectorClocks を作った
_ Algorithm::VectorClocks を作った [distributed][algorithm][perl] Amazon Dynamo についての記事 [2008-01-31-1] で，Vector Clocks とい う分散アルゴリズムが使われているということを紹介しました．Vector Clocks は，分散システムでバラバラに発生したイベントの順序を明らか にします． Google Code Search で検索してみたところ，JGroup という group communication framework などごく一部でしか使われていないようです． まぁ，Vector Clocks を必要とするような完全分散システム (master 不在 のシステム) があまりないですから，そんなもんでしょう． 需要はなさそうですが，Algorithm::VectorClocks
vector clocks - いたわさににほんしゅ
たけまる / Algorithm::VectorClocks を作った Vector Clocks を実装したモジュールを作成しました．このモジュールを 使うと，Vector Clocks の管理や比較を簡単に行うことができます． http://teahut.sakura.ne.jp/b/2008-02-11-1.html さっそく作ってる! コメントが出来なかなったので、たいした感想じゃないけどここに書いてみる。 ノードが OS のプロセスと対応すると思っていいのかな? ハコ(筐体)毎に一つのクロックがあるのとプロセス毎にもつのはどっちが良いだろう。プロセス毎に持つと名前を付けるのが結構面倒になるかもなぁ、とちょっと気になってしまいました。
Nearly Optimal Sparse Fourier Transform
arXiv:1201.2501v1[cs.DS]12Jan2012 Nearly Optimal Sparse Fourier Transform Haitham Hassanieh MIT Piotr Indyk MIT Dina Katabi MIT Eric Price MIT {haithamh,indyk,dk,ecprice}@mit.edu Abstract We consider the problem of computing the k-sparse approximation to the discrete Fourier transform of an n-dimensional signal. We show: • An O(k log n)-time algorithm for the case where the input signal has at mo
New analysis reveals clearer picture of brain’s language areas
To address some of society’s most pressing health challenges, MIT President Sally Kornbluth is launching the MIT Health and Life Sciences Collaborative (MIT HEALS), a new effort aimed at harnessing the collective power of researchers from fields such as engineering, science, AI, economics, business, policy, design, and the humanities to develop high-impact health solutions. The Massachusetts Insti
Algorithm - 連想配列の実装としてのハッシュはオワコン? : 404 Blog Not Found
2012年01月17日11:45 カテゴリアルゴリズム百選Tips Algorithm - 連想配列の実装としてのハッシュはオワコン? 珠玉のプログラミング Jon Bentley / 小林健一郎訳 つまり「終わったコンテナ」。 以前からうすぼんやりと考えて来た危惧が、すこしはっきりと見えてきた。 徳丸浩の日記: Webアプリケーションに対する広範なDoS攻撃手法(hashdos)の影響と対策 もうそろそろハッシュ(テーブル)以外の手段の連想配列の実装手段を本格的に模索するべきではないか、と。 そのデータ構造は、君の魂を差し出すに足るものかい? 連想配列(Associative array)がコレクション(Collection)、すなわち数多のデータ構造をまとめるデータ構造としての覇者となったのはもはや疑いようがない事実でしょう「配列で実装されるデータ構造ではなくて、配列を実装するデータ構
高速な安定ソートアルゴリズム "TimSort" の解説 - Preferred Networks Research & Development
先日、TimSortというソートアルゴリズムが話題になりました。TimSortは、高速な安定ソートで、Python(>=2.3)やJava SE 7、およびAndroidでの標準ソートアルゴリズムとして採用されているそうです。 C++のstd::sort()よりも高速であるというベンチマーク結果1が話題になり(後にベンチマークの誤りと判明)、私もそれで存在を知りました。実際のところ、ランダムなデータに対してはクイックソート(IntroSort)ほど速くないようですが、ソートというシンプルなタスクのアルゴリズムが今もなお改良され続けていて、なおかつ人々の関心を引くというのは興味深いものです。 しかしながら、オリジナルのTimSortのコードは若干複雑で、実際のところどういうアルゴリズムなのかわかりづらいところがあると思います。そこで今回はTimSortのアルゴリズムをできるだけわかりやすく解
Island Life - O(n^2)正規表現
About 南の島のプログラマ。 たまに役者。 Practical Schemeの主。 WiLiKi:Shiro 最近のエントリ 米国の大学進学無限cxr高校受験Defense振り返ってみると2019年は色々学んで楽...覚えるより忘れる方が難しい(こともある)眼鏡のつると3DプリンタIris Klein Acting ClassSAG-AFTRA conservatory: Voice Acting創作活動って自分を晒け出さねばならないと...More... 最近のコメント Jessica Kirkpatrick on CLtL2 (2025/06/28)shiro on 歳を取ると時間が速く過ぎるのは、新しいことに挑戦しないから? (2023/03/14)1357 on 歳を取ると時間が速く過ぎるのは、新しいことに挑戦しないから? (2023/03/01)ベアトリーチェ on ハイポハ
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)
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
Java, 経度緯度から2点間の距離と方角（方向・方位）を求める : Serendip – Webデザイン・プログラミング
2点間の距離を求める関数 引数 precision で精度（小数点以下の桁数）を指定する。 public static float getDistance(double lat1, double lng1, double lat2, double lng2, int precision) { int R = 6371; // km double lat = Math.toRadians(lat2 - lat1); double lng = Math.toRadians(lng2 - lng1); double A = Math.sin(lat / 2) * Math.sin(lat / 2) + Math.cos(Math.toRadians(lat1)) * Math.cos(Math.toRadians(lat2)) * Math.sin(lng / 2) * Math.sin(lng
dag_vector: ランダムアクセス可能な圧縮配列 - Preferred Networks Research & Development
こんにちは、この夏はシルキードライで乗り切りたい岡野原です。 今日は最近公開したC++のオープンソースであるdag vectorについて紹介します。 github: dag_vector ライセンスは修正BSDライセンスです。 dag vector (direct accessible gamma code vector) は値を圧縮して格納したまま任意の場所の値を高速に参照可能な配列ライブラリです。しかもデータ末尾への追記が可能です。 dag vectorはstd::vectorのように利用できます。下にいくつか例を見ていきましょう。 dag_vectorの例 #include "dag_vector.hpp" // dag_vectorは0以上の正整数の配列を扱う配列。 dag_vector dv; // 値はいつでも追加可能。追加された値は圧縮して格納される // 正整数xは2lg(
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Microsoft Word - kurasawa_zenkokutaikai2008.doc
IBM Developer
ベクタークロック : kei@sodan: 分散システムでのクロック
Keccak Team
1 ブルーム フィルタを用いた検索自由度の 高い検索可能暗号の設計と実装評価 菅 孝 徳 †1 西 出 隆 志 †2 堀 良 彰 †2 櫻 井 幸 一†2 データの暗号化しながら，そのデータに対する検索を
Microsoft PowerPoint - umeda.hokke06-1.ppt
GitHub - codahale/vlock: [ABANDONED] Vector clocks in Scala
Sudoku Solver in 140bytes
AI-Powered Candidate Assessment Software & Tools | Hirevue
