レイトレ合宿９(*)のセミナー発表スライドです。 * https://sites.google.com/view/rtcamp9/home - 2023/09/08 “除算法2”追記。（@Reputelessさんありがとうございました）
アルゴリズムに関するt-tanakaのブックマーク (29)
-
t-tanaka 2023/09/04
-
-
分散ロックという名の過ち - Software Transactional Memo
 TL;DR; 「分散ロック」が分散システムの設計図に登場した時 だいたいその設計は間違っていて本当に必要なものはトランザクションだ 並行システムを実装する際にロックを用いるのはとても自然なことだ。 僕も普段はロックフリー系のアルゴリズムに詳しいと言われがちだが知識量でいったら実はロック系の方が多く蓄えているかも知れない。 分散システムは並行システムであることが多いので、その中にロックが登場するのはとても自然な発想である。 よく「分散」「並行」「並列」の言葉の定義がごっちゃになっているケースがあり、この記事の主題にしたいわけではないので深くは言及しないが、分散システムは環境などの要因で突如として参加者が音信不通になったり復活したりする点で並行システムと大きく異なる。 並行システムと同じノリで分散システムを設計しようとした際に陥る頻出の過ちが「分散ロック」である。そのアイデアはとても簡単で
-
-
最近よく聞くQuorumは過半数(多数決)よりも一般的でパワフルな概念だった - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? 最近では珍しくもなくなった"Quorum"という言葉。Zookeeper, etcd, Serfといったクラスタ中でデータのレプリケーションを行ってくれるようなツールや、Cassandra, Riakといった分散データベース(NoSQL系)のようなツールにおいても、データの複製に一貫性を持たせる仕組みとしてよく聞かれます。 しかしながら、多くのスライドやWebの記事を読んでも、"Quorum"という語が意味するところは要するに「過半数ノードによる多数決」というような説明が多いように感じていました。 にも関わらず、"Quorum"と呼ばれ
-
-
文字列アルゴリズムの学びかた - Hatena Developer Blog
こんにちは！はてなアプリケーションエンジニアの id:takuya-a です。 みなさんは、このような疑問をもったことはありませんか？ grep はどのように文字列を検索しているのか？ MeCab はどうやって辞書を高速にルックアップしているのか？ パーサやコンパイラを作りたいけど、何から始めればいいのか？ 本稿では、「文字列アルゴリズムとはどんなものなのか？」「なぜ重要なのか？」「何を知っておくべきか？」「どうやって勉強すればいいのか？」といった疑問にお答えしていこうと思います。 文字列アルゴリズムの意外な応用や、モチベーションを保ちやすい勉強のしかた、文字列アルゴリズムを勉強するために行った社内での取り組み、実装するときのコツといったトピックについても触れています。 このエントリは、はてなエンジニアアドベントカレンダー2016の22日目の記事です。昨日は id:syou6162 さんに
-
視覚化による5つのガベージコレクションアルゴリズム入門 | POSTD
ほとんどの開発者は、自動のガベージコレクション（GC）を当たり前のように使っています。これは、私たちの仕事を容易にするために言語ランタイムが提供する素晴らしい機能の1つです。 しかし、最新のガベージコレクタの中をのぞいてみれば、実際の仕組みは非常に理解しづらいことが分かります。実装の詳細が無数にあるため、それが何をしようとしているのか、また、それがとんでもなく間違った事態を引き起こしかねないことについて十分理解していない限り、すっかり混乱してしまうでしょう。 そこで、5種類のガベージコレクションアルゴリズムを持つおもちゃを作ってみました。小さいアニメーションはランタイムの動作から作成しました。もっと大きいアニメーションとそれを作成するコードは github.com/kenfox/gc-viz で見ることができます。単純なアニメーションによってこうした重要なアルゴリズムを明らかにできることは
-
スパコンで約2時間36分かかったという、5×5の魔方陣の全解列挙を、パソコンで試す（C ） | 配電盤
魔方陣の解の列挙は並列化しやすそうな問題ですが、ここでの方針では、探索効率を上げるためには条件分岐が不可欠なので、（「数」を求めるだけだとしても）GPGPUでうまくやる方法がわかりません。そこで、CPUに載っているコアのみで並列化します（Xeon Phiなら簡単なのでしょうか→追記参照）。 一番外側の、0から(1<<25)-1まで変化する変数iのループをOpenMPで並列化します（schedule(guided)では遅くなります。schedule(auto)はVisual C++でサポートされたら試します）。変数iは上の図の緑の部分（カンで5個にしました）を各数5ビットで表現し、つなげたものです。マスに入りうる数は1から25までなので、5ビットというのはちょっと冗長ですが、とりあえずはよしとしましょう。 出力はバイナリ形式で、1つの解に25バイト使います（1つのマスに入る数を1バイトで表現
-
いまさらgrepが10倍高速化したのはなぜか – はむかず！
最近GNU grepコマンドの最新バージョンがリリースされ、速度が10倍になったとのアナウンスがあった。それを聞いて、なんであんな枯れた技術に10倍もの高速化の余地があったのだろうと不思議に思った人も多いだろう。 ニュース記事：grepコマンド最新版、”-i”で10倍の高速化 本家のリリースノート：grep – News: grep-2.17 released [stable] 今回のリリースでは正確には、マルチバイトロケールで、-iオプション（–ignore-case、つまり大文字小文字を区別しないオプション）をオンにした時の速度が10倍くらいになったそうだ。 なぜそんなに速くなったのか？逆を言えば今までなぜそんなに遅かったのか？ そもそも、多くの日本人にとって「大文字小文字の区別」というと英語のアルファベットか、せいぜいフランス語とかドイツ語とかのアクサン記号・ウムラウトがついたものく
-
-
へ、変態っ！！読めないからやめてっ！bit使ったデータ構造・アルゴリズム実装集 - Negative/Positive Thinking
この記事はCompetitive Programming Advent Calendar Div2012の2日目の記事です。 12月20日追記： Darseinさんが20日目の記事で、ビット演算についての詳しい説明を紹介してくださっています！必読ですね！！！！：） はじめに Y＾´ ∨／／ ／,∠ ,. ' ／l／／／ ／, ' , '／ ! ｜ ｌ }´ 〈 〉 変 〈/ , ' ／／￣｀>< ／／／ ／／／ _,.=‐|'"´l ｌ〈 変 / 〈 態. ∨, '／l| ,.'-‐､｀/／｀7/ ／''"´__ ｜ ﾊ l丿 態 { 人） ! ! （／! |ヽ〈_ ・.ﾉ〃 〃 ／ '／⌒ヾ.! ,' !く ! ! （_ ト､__／ ヽ､_,.イ ／ｌ ｌ ｜:::::::｀｀`/:::::／...´..
-
サービス終了のお知らせ - NAVER まとめ
サービス終了のお知らせ NAVERまとめは2020年9月30日をもちましてサービス終了いたしました。 約11年間、NAVERまとめをご利用・ご愛顧いただき誠にありがとうございました。
-
竹内関数で音楽生成 - aike’s blog
Lisperの人ならみんな知ってる竹内関数（たらいまわし関数）という関数があります。 定義としてはこんな感じ。 そのシンプルな定義からは想像もつかないほど複雑で膨大な再帰呼び出しがおこなわれるとても興味深い関数です。たとえば引数にTarai(10,5,0)を与えると343,073回も再帰呼び出しされたりします。 この関数呼び出しの引数がどのように変化するか知りたくてプログラムを書いて調べてみたところ、Tarai(10,5,0)の場合は3つの引数がそれぞれ0〜10（xは-1〜10）の間で少しずつ変化するなかで、2つの値を固定してひとつの値が下降していくような挙動があったりして、なんだか音楽の3和音のコード進行を思わせるような動き方です。 そういうことなら、ということで実際に音にして聴いてみました。Tarai関数が呼ばれるたびに引数のx、y、zを、0=ミ、1=ファ、2=ソ、……、のように音に割
-
脳とコンピュータとの違い
脳と現状のコンピュータは、計算モデル、アーキテクチャ、 アルゴリズムなどいろいろな観点からみて違いがあります。 はたしてコンピュータの上で脳と同じ機能は実現できるのでしょうか。 実現を難しくする要因として何が考えられるでしょうか。 ◆計算モデルの違い 計算する機械を数学的に抽象化したものを計算モデルと呼びます。 チューリングマシンは計算モデルの１つです。 チューリングマシンとは数学的に異なる計算モデルとしては、 例えば非決定性チューリングマシン、 （理想的な）アナログコンピュータ、量子チューリングマシン （量子コンピュータのモデル）があります。 これらはチューリングマシンよりも強力だったり速かったりします。 さて、「脳の計算モデル」はチューリングマシンと等価でしょうか、 それともより強力だったり速かったりするのでしょうか。 非決定性チューリングマシンは並列度が無限の計算機です。 脳は超並列
-
ゲームプレイヤーがNatureの論文をゲット！? | Chem-Station (ケムステ)
一般的な話題 ゲームプレイヤーがNatureの論文をゲット！? 2010/9/6 一般的な話題, 化学者のつぶやき, 論文 Nature, ゲーミフィケーション, タンパク質, ヒューリスティクス, 分散コンピューティング, 構造生物学 投稿者: cosine 少し前の話題ですが、あまり取り上げられてないようなんでご紹介します。 研究に関わったことがあれば名を知らぬ者はいない、世界最高峰たるジャーナル・Nature。 「一生に一度は自分の名前を載せたい」と誰もが掲載目標に据える雑誌の一つです。 しかしそんなことに一生懸命な研究者をすっとばし、なんとゲームで遊んでいただけの輩がNatureに載ってしまったという、前代未聞の事態が起きてしまいました。 こんな異例な事態が見られたのはこの論文（Nature 2010, 466, 756.）。 著者欄を見ると、おお確かに、最後になんか見慣れない感じ
-
-
YAPC::Asia
32. ●Geo::Hash (http://search.cpan.org/dist/Geo-Hash/) ●ベンチマーク ●隣接するgeohashを求めるadjacentメソッドがある geohash Encode Benchmark: timing 500000 iterations of Geo::Hash encode, Geo::Hash::XS encode... Geo::Hash encode: 137 wallclock secs (136.95 usr + 0.00 sys = 136.95 CPU) @ 3650.97/s (n=500000) Geo::Hash::XS encode: -1 wallclock secs ( 0.66 usr + 0.00 sys = 0.66 CPU) @ 757575.76/s (n=500000) Rate Geo::Has
-
-
3回に1回出力するだけの簡単ではないお仕事 - やねうらおブログ(移転しました)
なんかさ、3回に1回出力するだけの簡単なプログラムのお仕事ってあるじゃん。 if ( (++counter % 3) == 0) printf("Fizz\n"); これって意外と難しいんだよね。 ……なんてことを言うと「おいおい、天下のやねうらお、ついに頭おかしくなったか」とか言われるだろうけど、これ実際うちの仕事であった話で、このコードが原因でお客さんと大きなトラブルになった。 あまり具体的には言えないので、ちょっと別のものに置き換えて話すけど、それは、ひよこの餌やりプログラム(仮)だったわけ。 上のプログラムは、3回に1回だけど、このソフトには、N時間に1回、餌をやるロジックが書いてあった。 if ( (++counter % N) == 0) printf("餌やるでー\n"); なんかこんな感じな。それでNの値は、UI(ユーザーインターフェース)で調整できる作りにしてあった。一度
公式Twitter
- @HatenaBookmark
リリース、障害情報などのサービスのお知らせ
- @hatebu
最新の人気エントリーの配信
キーボードショートカット一覧
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Copyright © 2005-2025 Hatena. All Rights Reserved.
設定を変更しました