Cache-oblivious algorithm - Wikipedia
In computing, a cache-oblivious algorithm (or cache-transcendent algorithm) is an algorithm designed to take advantage of a processor cache without having the size of the cache (or the length of the cache lines, etc.) as an explicit parameter. An optimal cache-oblivious algorithm is a cache-oblivious algorithm that uses the cache optimally (in an asymptotic sense, ignoring constant factors). Thus,
Locality of reference - Wikipedia
This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Locality of reference" – news · newspapers · books · scholar · JSTOR (July 2008) (Learn how and when to remove this template message) In computer science, locality of reference, also known as the princip
アルゴリズムの紹介
ここでは、プログラムなどでよく使用されるアルゴリズムについて紹介したいと思います。 元々は、自分の頭の中を整理することを目的にこのコーナーを開設してみたのですが、最近は継続させることを目的に新しいネタを探すようになってきました。まだまだ面白いテーマがいろいろと残っているので、気力の続く限りは更新していきたいと思います。 今までに紹介したテーマに関しても、新しい内容や変更したい箇所などがたくさんあるため、新規テーマと同時進行で修正作業も行なっています。 アルゴリズムのコーナーで紹介してきたサンプル・プログラムをいくつか公開しています。「ライン・ルーチン」「円弧描画」「ペイント・ルーチン」「グラフィック・パターンの処理」「多角形の塗りつぶし」を一つにまとめた GraphicLibrary と、「確率・統計」より「一般化線形モデル」までを一つにまとめた Statistics を現在は用意していま
文書比較（diff）アルゴリズム
文書比較（diff）アルゴリズム 前のドキュメント 次のドキュメント ＶｉＶｉの文書比較（diff）機能で使用しているアルゴリズムについて解説する。 これらのアルゴリズムは Myers 氏らの論文によるもので、氏は筆者のためにわざわざ論文をＷｅｂサイトで入手可能な形式にしてくださった。この場を借りてお礼申し上げる。 オリジナル論文は以下のＷｅｂサイトから入手可能である。 http://www.cs.arizona.edu/people/gene [1] E.W.Myers, "An O(ND) Difference Algorithm and Its Variations", Algorithmica, 1 (1986), pp.251-266 [2] S. Wu, U. Manber, G. Myers and W. Miller, "An O(NP) Sequence Comparis
[C#][.NET] .NET diff class - 当面C#と.NETな記録
.NET 高速 diff classを公開します。２つの文字列のdiffを取ります。行単位のdiff(UNIXのdiffコマンドのような)と、文字単位のdiffを取れます。 "An O(NP) Sequence Comparison Algorithm"(PDF), Sun Wu, Udi Manber, Gene Myers, (1989) のアルゴリズムを使用したC#によるdiffクラスです。非常に賢い処理を作り上げた著者らに感謝いたします。 自由に使用してください。ただし、内容のいかなる保障もしません。バグを見つけたらコメントで教えてください。 テストはしていますが、仕事に使うのであれば再テストをしてから使用してください。 API 行単位diff public static DiffResult[] Diff( string textA, string textB ) public
![[C#][.NET] .NET diff class - 当面C#と.NETな記録](https://cdn-ak-scissors.b.st-hatena.com/image/square/e05fabf1e0eefb301ebaca7b7a11fb0ca5dec376/height=288;version=1;width=512/https%3A%2F%2Fcdn-ak.d.st-hatena.com%2Fdiary%2Fsiokoshou%2F2007-03-15.jpg)
モンテカルロ囲碁は必ず半目勝ちを目指す - 武蔵野日記
コンピュータ囲碁の世界でモンテカルロ法という確率的な手法が成功を収めていることは前も書いたが、今号の情報処理学会誌に「プロ棋士対コンピュータ:FIT2008における囲碁対局報告」と題して村松正和さんが記事を書かれており、最近の様子が(棋譜付きで)書かれているのでおもしろかった。 結論から言うとプロ棋士(4段)に8子置いて勝った(実力的にはアマ2-3段程度)というけっこうすごい話で、自分ではもう平手では勝てないところまで来てしまったのかなぁ、という感じ(自分はアマ2級くらいだった)。ここで使われた Crazy Stone というプログラムは第1回 UEC 杯コンピュータ囲碁大会(2007年12月開催)で優勝したプログラムである。 モンテカルロ囲碁の特徴について同記事でいくつか書かれている(pp.70-71)ので引用すると、 Crazy Stone も含め，モンテカルロ囲碁の打ち方には非常に特
C/C++向け多倍長整数資料を探している人のためのガイド - 世界線航跡蔵
多倍長整数の解説執筆がいつまで経っても進展しないので、お詫びの印にガイドを書いてみる 実装が欲しいよ派（実用主義派） お金は掛けたくないよ派 GMPとか、Mintはどうでしょうね。前者は開発者もユーザーも多いのでその点で信頼性が期待できますし、かなり速いです。後者は、x86限定ですが、ドキュメントも日本語ですし分かりやすく、設計上も使いやすい感じです。作者の苫米地聰さんは数体篩い法の実装などで知られる、計算実験に関してはかなり凄い人です。 あるいは、いっそPythonインタプリタやGaucheを埋め込んでしまうのはどうでしょうね。どちらもCプログラムに埋め込み易く書かれていますし、元来は汎用のスクリプティング言語ですから、アプリケーションにマクロ言語機能も付けられるというおまけがあってお得な感じです。アプリケーションのマクロ言語としてはRubyは最高と思うのですが、如何せん、現Ruby実装
2007-05-06
前書き 先日の日記のSPOJにおける√2を200万桁求めるという課題で、私はCを用いてそれを達成したのであるが、Haskellで100万桁を求めている人がいて、それがずっと気になっていた。普通に計算すると10万桁で精一杯で、とてもHaskellで100万桁なんて無理のように見える。ところが、ふとしたことから、Haskellで100万桁が可能であるように思えてきて、実際にやってみたら出来てしまった。しかし、そのためにはGHCのIntegerに対する深い理解が必要なのであった。 戦績： http://www.spoj.pl/ranks/SQRT2/ Haskellで100万桁 http://www.spoj.pl/ranks/EVAL/ ついでにeも100万桁 http://www.spoj.pl/ranks/PIVAL/ さらについでの円周率50万桁 GHCのIntegerにおける乗算 GH
Bignum#* を Karatsuba 乗算で高速化した - まめめも
例によってどーでもいい速度の話ですが、Ruby の Bignum の乗算を Karatsuba 法で高速化しました (ruby-dev:37392) 。これで Python より一歩進んだ気がします。 今年の初めに書いた多倍長整数演算の速度比較の実験をやり直してみました。詳細はそっちをみてね。使用した処理系のバージョンはそれぞれ以下のとおり。 ruby 1.9.0 (2008-12-14 revision 20739) perl v5.10.0 python 3.0 実験 1: 5 の累乗の計算 5 の 30,000 乗、100,000 乗、300,000 乗、1,000,000 乗の計算にかかる時間。単位は秒。 30000 100000 300000 1000000 ruby 0.02 0.08 0.37 1.69 python 0.04 0.11 0.32 1.76 perl(bigi
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
多倍長演算について