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)ってのは動的配列の実装方法に強く依存しているからです．実装を知っていないと答えられません． 一般論として，1つ要素を追加するとき，配列に空きがなかったら新しく配列を作り直して全要素をコピーする必要があります．コピーのコストは O(n) だから，追加コストも O(n) になるという議論が混乱の元になっています． こういうときは，要素追加を n 回繰り返したときの計算量を n で割った平均をとるという解析方法が使われるそうです．一般に, ある operation C の計算量を C を n 回行ったときの計算量 O(n) を n で割った値 O(n)/n で評価する手法をならし解析 (amortized analysis)と言うそうです． さて，s
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%)となることがわかります
データの離散型分布を表すヒストグラム（柱状グラフ）は、長方形を共通の基線上に並べた多角形として描画されます。これらの長方形は同じ幅を持ちますが、異なる高さのものを含みます。ヒストグラムを表す多角形に含まれる最大の長方形の面積を求めて下さい。入力は各データに対応する長方形の高さの列に対応した 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 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とは信頼性が低いプロセッサのネットワークにおいて合意の問題を解決するためのプロトコルの集合である。 合意とは参加者のグループにおいて単一の結果について合意を得るプロセスである。参加者や通信手法に障害が起きる可能性がある場合、この問題は困難なものとなる[1]。 合意プロトコルは分散コンピューティングにおける状態機械アプローチの基礎であり、これはレスリー・ランポート[2]により提案され、Fred Schneiderによってサーベイがなされている[3]。 Paxosプロトコルは1990年に登場し命名されたが、論文として出版されたのは1998年であった[4]。 これ以前に、ナンシー・リンチ、Cynthia Dwork、Larry Stockmeyerは"部分同期"システムの広い範囲における合意形成方法を例証している。Paxosは分散トランザクションの文脈において、1988年にOkiとBa
「倉庫番」＊1というゲームをご存じでしょうか。図1のように盤面にはいくつかの「荷物」とそれを運ぶ「人」がいます。人は1個の荷物を押して運ぶことができます。荷物を引っ張ったり，二つ並んだ荷物を同時に押して運ぶことはできません。人と荷物は縦横4方向に動けますが，壁のある位置には進めません。人を使って盤面上の荷物を動かし，すべての荷物を目的地（ゴール）に収めることができればゲーム・クリアとなります。図1の問題を解くための手順を示すアルゴリズムを作ってください。 友人たちと車でスキーに行くとき，いつも困るのは「トランクへ荷物を詰め込む順番」です。大きなスキー靴やかさばるスキーウエアを詰め込んでいるうえ，人によってはゲーム機や本を持ってきたりするので，各自の荷物の量がまったく違うのです。狭い車のトランクには，これら荷物をうまい順番で入れていかないとなかなか全部収まりません。寒い冬の夜中にごそごそと詰
BLASやATLASなどのライブラリを使うと，行列乗算やLU分解などの計算が，自分で組んだプログラムより数段速いことがよく知られている。それは，それらのライブラリではメモリやキャッシュの管理が高度になされているからであり，また，ループのアンローリングによるオーバーヘッドの低減やパイプライニングによるスケジューリングの最適化がなされているからであろう。 しかし，自分で組んだものが遅い，というのは悔しいものがあるので，なんとかしてチューニングできないものだろうかと思い立ち，いろいろやってみようと思う。 行列乗算のテスト ベンチマークによく使われる（と思う）のが，行列乗算である。これは，２つの行列Ａ,Ｂの掛け算Ｃ＝ＡＢを計算するもので，目的は単純だが，この計算を高速化しようといろいろなところで日々努力されている（はず）。行列乗算を普通に計算する手順をFortranで書くと，以下のようなプロ
ブロック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) プログラム ：
Lately I have been playing a game on my iPhone called Scramble. Some of you may know this game as Boggle. Essentially, when the game starts you get a matrix of letters like so: F X I E A M L O E W B X A S T U The goal of the game is to find as many words as you can that can be formed by chaining letters together. You can start with any letter, and all the letters that surround it are fair game, an
![How to find list of possible words from a letter matrix [Boggle Solver]](https://cdn-ak-scissors.b.st-hatena.com/image/square/98d6f053a97a87156775f60757c60865d0f2c47d/height=288;version=1;width=512/https%3A%2F%2Fsiteproxy.ruqli.workers.dev%3A443%2Fhttps%2Fcdn.sstatic.net%2FSites%2Fstackoverflow%2FImg%2Fapple-touch-icon%402.png%3Fv%3D73d79a89bded)
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分解の並列化について 斉藤 宏樹，廣安 知之，三木 光範 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分解の並列化
Topcoder is a crowdsourcing marketplace that connects businesses with hard-to-find expertise. The Topcoder Community includes more than one million of the world’s top designers, developers, data scientists, and algorithmists. Global enterprises and startups alike use Topcoder to accelerate innovation, solve challenging problems, and tap into specialized skills on demand.
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言語による最新アルゴリズム事典 ソフトウェアテクノロジー: 本
