diffの動作原理を知る～どのようにして差分を導き出すのか | gihyo.jp
UNIXの基本的なコマンドの1つであるdiff。 これに実装されているアルゴリズムは実に興味深い世界が広がっています。 本稿では、筆者が開発した独自ライブラリ「dtl」をもとに「diffのしくみ」を解説します。 はじめに diffは2つのファイルやディレクトリの差分を取るのに使用するプログラムです。 ソフトウェア開発を行っている方であれば、SubversionやGitなどのバージョン管理システムを通して利用していることが多いかと思います。本稿ではそのdiffの動作原理について解説します。 差分の計算の際に重要な3つの要素 差分を計算するというのは次の3つを計算することに帰結します。 編集距離 2つの要素列の違いを数値化したもの LCS（Longest Common Subsequence） 2つの要素列の最長共通部分列 SES（Shortest Edit Script） ある要素列を別の要
知ってる？ クレジットカード番号の意味と暗算認証術
知ってる？ クレジットカード番号の意味と暗算認証術2011.01.24 12:0029,477 satomi 暗算で偽造カード見分けられるなんて...知らなかった！ 毎日のように使うクレジットカード。丸暗記して時間セーブしてる人も、あの数字16桁の意味までは知らないんじゃ？ 16個の数字にはそれぞれ意味があるんですよ。米国で人気のオンライン資産管理サービス｢Mint｣がズバリ図解してくれました！ （図の訳） 1）最初の1桁：主要産業識別子 （MII:Major industry identifier）。カード発行者の業界を表します。 0 予備 1、2 航空 3 旅行・娯楽 4、5 銀行・金融 6 商品輸送・銀行 7 石油 8 通信 9 国ごとの割り当て分 2）MIIを含む最初6桁：発行者識別番号（IIN:Issuer Identifier Number）。カード発行者の身元を表します。 [
一番右端の立っているビット位置を求める「ものすごい」コードのていねいな説明 - 2009-07-06 - 当面C#と.NETな記録
id:siokoshou:20090704 のはてブのコメント見てるとわからないってコメントが結構あるので、もう一度がんばって説明してみます。まあわかったところで得はないかもしれませんｗ public static int GetNumberOfTrailingZeros( long x ) { if ( x == 0 ) return 64; ulong y = ( ulong ) ( x & -x ); int i = ( int ) ( ( y * 0x03F566ED27179461UL ) >> 58 ); return table[ i ]; } static int[] table; table = new int[ 64 ]; ulong hash = 0x03F566ED27179461UL; for ( int i = 0; i < 64; i++ ) { table[
一番左端の立っているビット位置を求めるすんごいコード(NLZ) - Koonies/こりゃいいな！
昨日、先輩に2009-07-04を教えてもらった。 何だか分からないが凄いコードだ。 僕的にはNTZ（右端のビット位置を求める）より32bitのNLZ（左端を..）の方が色々と利用できる場面があるのでそっちに使えないのか考えてみた。 ハッカーのたのしみ―本物のプログラマはいかにして問題を解くかposted with amazlet at 09.07.07ジュニア,ヘンリー・S. ウォーレン エスアイビーアクセス 売り上げランキング: 16618 おすすめ度の平均: ビットの楽しみ たのしみ？ たしなみ？ ちゃんと読むと得した気分になれます 最後の頑張りに効きます Hackっていうのは、こういうコトさ Amazon.co.jp で詳細を見る 一応説明しておくとNLZは32bitの値を2進で表示したとき一番左からの0の個数。 0x80000000なら0、0x08000000なら4、8なら24で
すごい乱数生成アルゴリズム「xorshift」 - Pashango’s Blog
みなさん、こんにちは、今回は乱数の話です。 特に複数機種でのコンシューマ機でゲームを開発をしていると、機種間で乱数値を統一するために乱数生成アルゴリズムを自作しますよね。 そこでよく使われるアルゴリズムが「線形合同法」です、内容は至って簡単で、以下の漸化式を使います。 A,B,Mは定数で、どの値が入るかは処理系依存です。 例えばUnixなどの処理系ではA=1103515245,B=12345,M=2147483647などが入ります。 C言語ですと以下のようになります。 static unsigned int x=1; void srand(unsigned int s) { x=s; } unsigned int rand() { x=x*1103515245UL+12345UL; return x&2147483647UL; } この「線形合同法」は計算が簡単で高速ですから、いろいろな環
Geekなぺーじ : Linuxにデフラグが無い理由
「ピアリング戦記」の英訳版EPUBを無料配布します！ 英語のIT系技術書が日本語訳されて海外に届けられることは多く行われていますが、日本語版から英語版への翻訳には高いハードルがあります。 過去に、何度か私が書いた本を英語に翻訳して出版することはできないかを模索したことがありますが、これまで企画が実現することはありませんでした（中国語への翻訳はあります）。 しかし、今回、私としては初となる英訳版を上梓することができました。 2022年に出版した「ピアリング戦記 - 日本のインターネットを繋ぐ技術者たち」ですが、これを日本語だけにしておくのはもったいないという声を内外でいただき、それを受けて英訳を行うプロジェクトが去年動き始めました。 続きを読む... IPv4アドレス移転の売買価格推移および移転組織ランキング100 IPv4アドレスの中央在庫が2011年に枯渇後、IPv4アドレスの移転や、移
一番右端の立っているビット位置を求める「ものすごい」コード - 当面C#と.NETな記録
一番右端の立っているビット位置(RightMostBit)を求めるコードで速いのないかなーと探していたら、ものっっっすごいコードに出会ってしまったのでご紹介。2ch のビット演算スレで 32bit 値のコードに出会って衝撃を受けて、その後 64bit 値版のヒントを見つけたのでコードを書いてみました。 この問題は ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか (Google book search で原著 Hacker's delight が読めたのでそれで済ませた) で number of trailing zeros (ntz) として紹介されています。bit で考えたときに右側に 0 がいくつあるかを数えるもの。1 だと 0、2 だと 1、0x80 なら 7、12 なら 2 といったぐあい。0 のときに表題どおりの問題として考えるといくつを返すの？ってことになるので、
ジャンル別ゲームの作り方とアルゴリズムまとめ - ネットサービス研究室
ゲームの作り方とアルゴリズムをジャンル別にまとめてみました。ゲーム制作や、プログラミングの勉強用にご活用ください。言語別ゲームプログラミング制作講座一覧もあわせてお読みください。 リンク切れがおきていたものは、URLを表示しておくので、Internet Archiveなどでキャッシュを表示させてみてください。 RPG ゲームの乱数解析 乱数を利用した敵出現アルゴリズムの解説 各種ゲームプログラム解析 FF、ドラクエ、ロマサガのプログラムの解析。乱数の計算など ダメージ計算あれこれ（http://ysfactory.nobody.jp/ys/prg/calculation_public.html） ダメージの計算式 エンカウントについて考えてみる エンカウント（マップでの敵との遭遇）の処理方法いろいろ RPGの作り方 - ゲームヘル2000 RPGのアルゴリズム ドルアーガの塔 乱数の工夫の
配列のシャッフル
イントロダクション よく、ランダムな数字の並びで、それぞれの数字がちょうど１回ずつしか出てこない、という数列が欲しいことがあります。例えば、カードのシャッフル等がこれにあたります。こういう時は配列に数字を入れ、その配列の要素をシャッフルして目的の数列を得るのが定石です。そのシャッフルをどうやるのがいいのか、というのが今回の話題です。 まず思いついた方法 昔私が最初に考えついたのは、ランダムに２つの要素を選んで swap する、という操作を複数回繰り返すという方法でした。コードっぽく書くと、次のような感じになります。 M = count_of_iteration; N = size_of_array; rand(x) = random_value_less_than_x; for(i = 0; i < M; i++){ a = rand(N); b = rand(N); swap(array
Spaghetti Source - アトキンのふるい
ソースコード void sieve_of_atkin() { int n; for (int z = 1; z <= 5; z += 4) { for (int y = z; y <= sqrtN; y += 6) { for (int x = 1; x <= sqrtN && (n = 4*x*x+y*y) <= N; ++x) isprime[n] = !isprime[n]; for (int x = y+1; x <= sqrtN && (n = 3*x*x-y*y) <= N; x += 2) isprime[n] = !isprime[n]; } } for (int z = 2; z <= 4; z += 2) { for (int y = z; y <= sqrtN; y += 6) { for (int x = 1; x <= sqrtN && (n = 3*x*x+y*
ベイズを学びたい人におすすめのサイト - download_takeshi’s diary
ベイジアンフィルタとかベイズ理論とかを勉強するにあたって、最初はなんだかよくわからないと思うので、 そんな人にお勧めのサイトを書き残しておきます。 @IT スパム対策の基本技術解説（前編）綱引きに蛇口当てゲーム？！楽しく学ぶベイズフィルターの仕組み http://www.atmarkit.co.jp/fsecurity/special/107bayes/bayes01.html いくつかの絵でわかりやすく解説してあります。 自分がしるかぎり、最もわかりやすく親切に解説してる記事です。数学とかさっぱりわからない人はまずここから読み始めるといいでしょう。 茨城大学情報工学科の教授のページから http://jubilo.cis.ibaraki.ac.jp/~isemba/KAKURITU/221.pdf PDFですが、これもわかりやすくまとまってます。 初心者でも理解しやすいし例題がいくつかあ
シムシティーの仕組み
シムシティーを作り始めていちばん最初に考えたのは、街を一種の生き物のように表現できないかってことだった。 僕が街についてどう考えているかはすでに説明したけど、大事なのは街を構成する建物とか道路じゃなくって、そこでどんな活動が行なわれているかってことだと思うんだ。道路を車が走り、電車が動き、人々が動き回り、常に要素が変化し続ける“動きのある”システム。街を表現する方法っていうと誰でも地図を思い浮かべると思うけど、僕は動きがない地図じゃなくって、たとえば飛行機から眺めた街、動きのある世界をディスプレイに表現しようって考えた。それこそが僕の考える街の姿だからね。 それともう一つ考えたことは、プレイヤーに伝える情報をできるだけわかりやすく、それも“面白い”って思えるような形で表現しようってことだった。シミュレーション・ソフトっていうとたいてい数値や図表がたくさん出てくるけれど、数字が並んでいるのを
Perlでアニメ顔を検出＆解析するImager::AnimeFace - デー
というのを作ったので自己紹介します。 2月頃から、コンピュータでアニメ顔を検出&解析する方法をいろいろ試しつつ作っていて、その成果のひとつとして、無理やり出力したライブラリです。 はじめに はじめにざっとライブラリの紹介を書いて、あとのほうでは詳細な処理の話を僕の考えを超交えつつグダグだと書きたいと思います。 Imager::AnimeFaceでできること Imager::AnimeFaceは、画像に含まれるアニメキャラクター的な人物の顔の位置を検出し、さらに目や口など顔を構成する部品位置や大きさの推定、肌や髪の色の抽出を簡単に行うことができるライブラリです。 これらが可能になると、 画像から自動でいい感じのサムネイルを作成できる 動画から自動でいい感じのサムネイルを作成できる 自動的にぐぬぬ画像が作れる 自動的に全員の顔を○○にできる 顔ベースのローカル画像検索 など、最新鋭のソリューシ
ベア速 マイクロソフト米国本社の実地面接に行ったけど質問ある？
4 名前：以下、名無しにかわりましてVIPがお送りします。[] 投稿日：2007/12/08(土) 06:49:04.61 ID:Bh8D4QeU0 >>1 話が本当なら こんなとこにきてはいけない人だよ君は 自分の場所にかえれというか二度とくんな こんな掃き溜めにいたらだめになるぞ なんでそっち系の板で立てないのか >>4 アメリカは現在夕方で少しヒマなんですよ。 あと2chとかniconicoは大好きです。 7 名前：以下、名無しにかわりましてVIPがお送りします。[sage] 投稿日：2007/12/08(土) 06:50:51.74 ID:7Trqg13a0 なんだ受けただけか 意味分からん >>7 力及ばず、最終面接で落とされました。 でも、試験の傾向とか多少参考になる話もできると思います。 9 名前：以下、名無しにかわりましてVIPがお送りします。[] 投稿日：2007/12/
Re:意外と馬鹿にする特許でもないような (#1413796) | マイクロソフト、なんとPage UP, Page Downで特許取得？ | スラド
本文ちょっとだけ読んでみた。 この特許の認可がなぜ今頃？という感じはあるが、そこまで馬鹿にされる内容でもない気がする。 ページがズームやズームアウトされた時や、 windowが小さくなった時や大きくなった時のpage down処理をどうやってやるのか？ プログラム書け！と言われるとそんなに簡単でもない。 page upかpage downが押された時のvertical offsetを以下の式で算出するんだってさ。 {[(p-1)/c]h}+r, where p is equal to the number of pages in the document, c is equal to the number of columns of the document which are simultaneously displayed,
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Hacker's Delight