Lock-freeとWait-freeアルゴリズム - Wikipedia
Lock-freeとWait-freeアルゴリズムとは、共有データにロックをかけてアクセスを防ぐアルゴリズムとは違い、複数のスレッドが同時並行的に、ある対象データを壊すことなしに読み書きすることを可能にするアルゴリズムである。Lock-free とはスレッドがロックしないことを意味しており、全てのステップにおいてシステムが必ず進行する。これはLock-free ではミューテックスやセマフォといった、排他制御のためのプリミティブを使ってはならないことを意味する。なぜならロックを持っているスレッドの実行が中断した場合、全体の進行を阻止しうるからである。Wait-free とは、他のスレッドの動作に関係なく、スレッドがいかなる操作も有限のステップで操作を完了させられることを指す。あるアルゴリズムがLock-freeであるがWait-freeでないことはありうる。Wait-free なアルゴリズム
ベジエ曲線とベジエ曲面
この授業では、ベジエ曲線・ベジエ曲面を学ぶことを目標としています。 これらの曲線曲面を理解するために、必要に応じてコンピュータソフト Mathematica を用いて解説する。 授業の内容を参考テキストとして配付する。 １０月５日（水） ベジエ曲線１ 今日のテキスト（pdfファイル）: ベジエ曲線とベジエ曲面１ 参考ファイル: 放物線1a 放物線1b 放物線2a 放物線2b 放物線3a 放物線3b ３次曲線1a ３次曲線1b ３次曲線2a ３次曲線2b ３次曲線3a ３次曲線3b 7次曲線a 7次曲線b レポート１ １０月１２日（水） ベジエ曲線２ 今日のテキスト（pdfファイル）: ベジエ曲線とベジエ曲面２ 参考ファイル: ３次曲線 レポート２ １０月１９日（水） ベジエ曲線３ 今日のテキスト（pdfファイル）: ベジエ曲線とベジエ曲面３ レポート３ 参考ファイル: ベジエ点 １０月２６
きまぐれ日記: 動的配列への追加コストはなぜ O(1)?
動的配列への追加コストは O(1) ってのは覚えていればそれだけの話ですが，どうしてかと言われると意外と難しいものです． というのも, このO(1)ってのは動的配列の実装方法に強く依存しているからです．実装を知っていないと答えられません． 一般論として，1つ要素を追加するとき，配列に空きがなかったら新しく配列を作り直して全要素をコピーする必要があります．コピーのコストは O(n) だから，追加コストも O(n) になるという議論が混乱の元になっています． こういうときは，要素追加を n 回繰り返したときの計算量を n で割った平均をとるという解析方法が使われるそうです．一般に, ある operation C の計算量を C を n 回行ったときの計算量 O(n) を n で割った値 O(n)/n で評価する手法をならし解析 (amortized analysis)と言うそうです． さて，s
d.y.d. 2倍だけじゃない
10:01 10/07/20 それでも２倍だ 先日のvectorの伸長度合いの記事に関して 本当に1.5倍のほうがメモリ効率がよいのか という反応をいただきました。とても興味深い。みんな読みましょう。 自分の理解メモ： 「再利用ができるから嬉しい」等の議論をするなら、 今までに確保したメモリ (1 + r^1 + ... + r^k) のうち、 有効に使えてるメモリ r^{k-1} (バッファ拡大直後) や r^k (次のバッファ拡大直前) の割合で評価してみようじゃないかという。 まず簡単のために再利用をしない場合を考えると、この割合はそれぞれ (r-1)/r^2、 (r-1)/r になります（途中計算略）。 この利用率が最悪になる瞬間 (r-1)/r^2 を最善にしよう、 という一つの指標で考えてみると、式を微分なりなんなりしてみると r = 2 で最大(25%)となることがわかります
ALGORITHM NOTE ヒストグラム中の最大の長方形の面積
データの離散型分布を表すヒストグラム（柱状グラフ）は、長方形を共通の基線上に並べた多角形として描画されます。これらの長方形は同じ幅を持ちますが、異なる高さのものを含みます。ヒストグラムを表す多角形に含まれる最大の長方形の面積を求めて下さい。入力は各データに対応する長方形の高さの列に対応した n 個の要素からなる１次元配列とします。(source: ACM/ICPC University of Ulm Local Contest) 以下のように、２重ループによって長方形の範囲を選び、そこにできる最大の長方形の面積を計算して更新していけば、全体での最大の面積を求めることができます。これはO(n2)のアルゴリズムです。 001 int getRectangleAreaBF( int size, int buffer[] ){ 002 int maxv = 0; 003 for ( int i =
動的計画法とナップサック問題を学びたい人におすすめのサイト - ダウンロードたけし（寅年）の日記
組み合わせ最適化の手法として「動的計画法」というモノがあります。 wikipediaから抜粋 動的計画法（どうてきけいかくほう、英: Dynamic Programming, DP） コンピュータ科学の分野において、ある最適化問題を複数の部分問題に分割して解く際に、そこまでに求められている以上の最適解が求められないような部分問題を切り捨てながら解いていく手法 一見難しそうですが、実は理解するのは以外と簡単です。いろいろな場面で応用が利く便利な手法ですので、覚えておいて損はないものです。コンピュータ系、情報系のお勉強をする人であれば、おそらく一度は習ったりするかもしれません。 ナップサック問題と動的計画法 動的計画法の一番親しみやすそうな例として「ナップサック問題」というのがよく取り上げられます。 こんな感じの問題です。 今ここに様々な大きさの品物が置いてあるとします。そしてそれらの品物は各
アルゴリズマーの登竜門、「動的計画法・メモ化再帰」はこんなに簡単だった
アルゴリズマーの登竜門、「動的計画法・メモ化再帰」はこんなに簡単だった：最強最速アルゴリズマー養成講座（5/5 ページ） 関連記事 トップクラスだけが知る「このアルゴリズムがすごい」――「探索」基礎最速マスター プログラミングにおける重要な概念である「探索」を最速でマスターするために、今回は少し応用となる探索手法などを紹介しながら、その実践力を育成します。問題をグラフとして表現し、効率よく探索する方法をぜひ日常に生かしてみましょう。 知れば天国、知らねば地獄――「探索」虎の巻 いよいよ今回から、具体的なアルゴリズムの紹介に入っていきます。今回は、プログラミングにおける重要な概念である「探索」について考えます。グラフに変換し、探索する、という流れを知るとともに、そのグラフを効率よく探索する方法について紹介します。 細かすぎて伝わりにくいTopCoderのコーディングスキル向上マジック 競技プ
Calculating Permutations
Calculating Permutations and Job Interview Questions The permutation of a set is the number of ways that the items in the set can be uniquely ordered. For example, the permutations of the set { 1, 2, 3} are { 1, 2, 3}, { 1, 3, 2}, { 2, 1, 3}, { 2, 3, 1}, { 3, 1, 2} and { 3, 2, 1}. For N objects, the number of permutations is N! (N factorial, or 1 * 2 * 3 * ... N). Aside from theoretical interest i
Paxosアルゴリズム - Wikipedia
Paxosとは信頼性が低いプロセッサのネットワークにおいて合意の問題を解決するためのプロトコルの集合である。 合意とは参加者のグループにおいて単一の結果について合意を得るプロセスである。参加者や通信手法に障害が起きる可能性がある場合、この問題は困難なものとなる[1]。 合意プロトコルは分散コンピューティングにおける状態機械アプローチの基礎であり、これはレスリー・ランポート[2]により提案され、Fred Schneiderによってサーベイがなされている[3]。 Paxosプロトコルは1990年に登場し命名されたが、論文として出版されたのは1998年であった[4]。 これ以前に、ナンシー・リンチ、Cynthia Dwork、Larry Stockmeyerは"部分同期"システムの広い範囲における合意形成方法を例証している。Paxosは分散トランザクションの文脈において、1988年にOkiとBa
第8回 倉庫番を解くアルゴリズム - 地球にやさしいアルゴリズム：ITpro
この記事は会員登録で続きをご覧いただけます申込は簡単3分！ 今すぐ会員登録（無料） 会員の方はこちら 【8/20まで】今なら年額プランが2カ月分お得！ 詳しくはこちら ▼日経クロステック有料会員になると… オリジナル記事がすべて読める 専門雑誌7誌の記事も読み放題 雑誌PDFを月100ページダウンロードできる
Ogita's Nonlinear Plane (Numerical Analysis)
BLASやATLASなどのライブラリを使うと，行列乗算やLU分解などの計算が，自分で組んだプログラムより数段速いことがよく知られている。それは，それらのライブラリではメモリやキャッシュの管理が高度になされているからであり，また，ループのアンローリングによるオーバーヘッドの低減やパイプライニングによるスケジューリングの最適化がなされているからであろう。 しかし，自分で組んだものが遅い，というのは悔しいものがあるので，なんとかしてチューニングできないものだろうかと思い立ち，いろいろやってみようと思う。 行列乗算のテスト ベンチマークによく使われる（と思う）のが，行列乗算である。これは，２つの行列Ａ,Ｂの掛け算Ｃ＝ＡＢを計算するもので，目的は単純だが，この計算を高速化しようといろいろなところで日々努力されている（はず）。行列乗算を普通に計算する手順をFortranで書くと，以下のようなプロ
Blocked LU Decomposition
ブロックLU分解プログラム 2003/09/08 日立製作所 & 早稲田大学 後 保範 ( Ushiro Yasunori ) 1. 概要 密実行列を係数とする連立一次方程式Ax=bの係数AをブロックGauss消去法でLU分解し、 数値解xを計算するFORTRAN及びCのソースプログラムを掲載する。 本プログラムは内容を理解してもらうことを目的とし、計算時間及び使用メモリ量の効率化 は目的としていない。本格的なプログラムは金田研究室から他のプログラムと合わせて 公開する予定。配列の格納順はCとFORTRANで異なる。CとFORTRANのそれぞれの配列順を 考慮したプログラムになっている。 2. 軸交換のないプログラム (1) 特異性チェックの無いプログラム (a) 計算方法 ： Aをブロックガウス消去法でLU分解し、LUx=bの解xを前進後退代入でもとめる。 (b) プログラム ：
Index of /OpenLecture
Name Last modified Size Description Parent Directory - JS20091008.pdf 08-10·î-2009 11:43 11M SP20090414.pdf 15- 4·î-2009 11:32 884K SP20090421.pdf 15- 4·î-2009 12:01 1.8M SP20090428.pdf 27- 4·î-2009 11:38 2.4M SP20090512.pdf 07- 5·î-2009 11:59 4.1M SP20090519.pdf 19- 5·î-2009 12:22 374K SP20091006.pdf 06-10·î-2009 09:48 2.8M SPC2009RepConS.pdf 06- 7·î-2009 15:32 205K SPC20090526.pdf 21- 5
LU分解の並列化について
LU分解の並列化について 斉藤 宏樹，廣安 知之，三木 光範 ISDL Report No. 20020612018 2002年 10月 9日 Abstract 本報告では，HPL(High-Performance Linpack Benchmark)のメインアルゴリズムであるLU分解について説明する．HPLは並列計算機用のベンチマークソフトウェアであり，LU分解を並列化させることで演算性能を測定している．LU分解の並列化について，その方法を示す． 1 はじめに HPL(High-Performance Linpack Benchmark)は，分散メモリ型並列計算機用のベンチマークソフトウェアであり，並列計算機の演算性能を測定するものである．そのメインアルゴリズムは，密行列の連立１次方程式をLU分解の並列化により解くというものである．LU分解についてのアルゴリズムと，LU分解の並列化
Programming Contests, Software Development, and Employment Services at TopCoder
AI Exponential League is Live!|Win Prizes and Climb the Leaderboard•$5,000 BonusCheck it out AI Exponential League is Live!|Win Prizes and Climb the Leaderboard•$5,000 BonusCheck it out Proud to announce that Topcoder earned 5 HC Badges badge for Winter 2026 Recognized by Human Cloud - a merit-based recognition of top workforce solutions demonstrating excellence in innovation, delivery, and talent
しかしSVMも最近は速いらしい - 射撃しつつ前転 改
Complement Naive BayesがSVMより速いよーと主張していたので、SVMもなんか最近は速くなってるらしいよ、という事を紹介してみたい。近年はSVMなどの学習を高速に行うという提案が行われており、実装が公開されているものもある。その中の一つにliblinearという機械学習ライブラリがある。ライブラリ名から推測できる通り、liblinearではカーネルを使うことが出来ない。しかし、その分速度が速く、大規模データに適用できるという利点がある。 liblinearを作っているのはlibsvmと同じ研究グループで、Chih-Jen Linがプロジェクトリーダーであるようだ。libsvmはかなり有名なライブラリで、liblinearにはそういった意味で安心感がある。（liblinearの方は公開されてしばらくは割とバグがあったらしいけど。） liblinearにはL1-SVM, L
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Amazon.co.jp：C言語による最新アルゴリズム事典 ソフトウェアテクノロジー: 本
Perl.com: How Hashes Really Work
How to find list of possible words from a letter matrix [Boggle Solver]
http://docs.google.com/gview?a=v&q=cache:pB15MqLRfgoJ:www.aoni.waseda.jp/ushiro/matrix/matrix5p.pdf