いまさらgrepが10倍高速化したのはなぜか – はむかず！
最近GNU grepコマンドの最新バージョンがリリースされ、速度が10倍になったとのアナウンスがあった。それを聞いて、なんであんな枯れた技術に10倍もの高速化の余地があったのだろうと不思議に思った人も多いだろう。 ニュース記事：grepコマンド最新版、”-i”で10倍の高速化 本家のリリースノート：grep – News: grep-2.17 released [stable] 今回のリリースでは正確には、マルチバイトロケールで、-iオプション（–ignore-case、つまり大文字小文字を区別しないオプション）をオンにした時の速度が10倍くらいになったそうだ。 なぜそんなに速くなったのか？逆を言えば今までなぜそんなに遅かったのか？ そもそも、多くの日本人にとって「大文字小文字の区別」というと英語のアルファベットか、せいぜいフランス語とかドイツ語とかのアクサン記号・ウムラウトがついたものく
アルゴリズムの勉強のしかた - きしだのHatena
この記事で、アルゴリズムの勉強はアルゴリズムカタログを覚えることじゃないよということを書きました。 プログラムの理論とはなにか アルゴリズムの勉強というのは、スポーツで言えば腕立て伏せや走り込みみたいな基礎体力を養うようなもので、「ソートなんか実際に自分で書くことないだろう」とかいうのは「サッカーは腕つかわないのに腕立ていらないだろう」とか「野球で1kmも走ることなんかないのに長距離の走り込みいらないだろう」とか言うようなものです。 Twitterでアルゴリズムの勉強とはなにかと尋ねられて、「アルゴリズムの基本的なパターンを知って、それらの性質の分析のしかたをしって、いろいろなアルゴリズムでどのように応用されているか知って、自分が組むアルゴリズムの性質を判断できるようになることだと思います。 」と答えたのですが、じゃあ実際どういう本で勉強すればいいか、ぼくの知ってる本からまとめてみました。
Rubyによる関数型プログラミング
古き良き小学校の時代、この行には困惑させられたものだった。 魔術的な x が、加算されたのに等しいままでいる事に。 どういうわけか、プログラミングを始めると、それに構わなくなる。 「やれやれ、それは重大な事柄じゃないし、プログラミングとは現実のビジネス行為なんだから、 数学的な純粋さについてあら探しなんて必要無い (その議論なら、大学にいる狂った髭面野郎どもにさせておけばいい)」と思っていた。 けれども、ただ知らなかっただけで、我々が間違っていて高い代償を支払っていたのは 明らかである。 Wikipedia によれば、「関数型プログラミング(functional programming, FP)とは、 計算を数学的な関数の評価とみなし、 状態や可変データを避けるプログラミングパラダイム」である。 言い換えると、関数型プログラミングは、 副作用が無く変数の値を変化させないコードを推奨する。
へ、変態っ！！読めないからやめてっ！bit使ったデータ構造・アルゴリズム実装集 - Negative/Positive Thinking
この記事はCompetitive Programming Advent Calendar Div2012の2日目の記事です。 12月20日追記： Darseinさんが20日目の記事で、ビット演算についての詳しい説明を紹介してくださっています！必読ですね！！！！：） はじめに Y＾´ ∨／／ ／,∠ ,. ' ／l／／／ ／, ' , '／ ! ｜ ｌ }´ 〈 〉 変 〈/ , ' ／／￣｀>< ／／／ ／／／ _,.=‐|'"´l ｌ〈 変 / 〈 態. ∨, '／l| ,.'-‐､｀/／｀7/ ／''"´__ ｜ ﾊ l丿 態 { 人） ! ! （／! |ヽ〈_ ・.ﾉ〃 〃 ／ '／⌒ヾ.! ,' !く ! ! （_ ト､__／ ヽ､_,.イ ／ｌ ｌ ｜:::::::｀｀`/:::::／...´..
「プログラマが本当に理解するには実装しないといけない」か - 木曜不足
ジュンク堂池袋本店にて 10/11 に行われた「パターン認識と機械学習」(PRML) 愛好家の集まり、じゃあなかった、トークセッションにのこのこ行ってきた、ばかりか前でしゃべってきた。ありがとうございました＆お疲れ様でした＞各位 PRML同人誌 『パターン認識と機械学習の学習』（暗黒通信団） 刊行記念トークセッション 「今度こそわかる!? PRMLの学習の学習」 http://www.junkudo.co.jp/tenpo/evtalk.html#20121011_talk 参加して下さった上に感想までブログにしたためて下さった方には感謝感謝なわけだが、そういったブログの中で、@yag_ays さんがちょうど今気にしていたことを書かれていたので、ちょこっと紹介。 「今度こそわかる!? PRMLの学習の学習」に参加しました - Wolfeyes Bioinformatics beta 余談：
プログラマの実力は経験だけであがらないことがレベル格差につながる - きしだのはてな
プログラマというのは、道具に慣れることが、実力があがることにならないのですよね。だから、勉強せず業務経験だけだとレベルが低いままということになってしまう。 Javaを10年さわり続けて、Strutsを5年さわり続けても、それだけでは、与えられた画面を手際よく作成できるようになるだけで、たとえばStrutsすらよりよく使えるようになるわけではなかったりする。 Javaにしても、「volatileってなんですか？」という問いに、まあ知らないのはしかたないとしても、解説を見ながらですら答えられない可能性がある。 プログラムの反復生産は、プログラミング能力の向上にあまりつながらない。設定や記述に慣れるだけだ。そして、この「慣れ」というのには「難しいからそもそも実装を回避する」というようなものも含まれる。実力の向上は、作業ができるレベルで止まってしまう。 プログラマとしての実力をあげるための勉強が自
｢それでもね。私はみんなに『組み合わせ爆発の凄さ』を教えたいの！止めないで！｣日本科学未来館のアニメが狂気すぎて笑える（動画）
｢それでもね。私はみんなに『組み合わせ爆発の凄さ』を教えたいの！止めないで！｣日本科学未来館のアニメが狂気すぎて笑える（動画）2012.09.12 20:00 面白いから是非最後まで観てください。 ｢組み合わせ爆発｣（数える対象が少し増えるだけで組み合わせの数が膨大になること）を分かりやすく解説するビデオなわけなんですが。。 ＊ 主人公のお姉さんは、みんなの前でスタートからゴールまでの道順総数を求めようとするんですが... お姉さんには謎の使命感があるようで... 何故かわざわざ手で数えたり、すげぇ時間のかかる問題をノートパソコンで計算しようとします。スパコン持ってるのに。 途中から組み合わせ数が増え、さすがに普通のノートパソコンじゃ計算しきれないのでスパコンを利用しはじめるも、膨大な時間のかかる計算を、答えが出るまで何故かラボに１人とじこもりスパコンを見張っている様子。 やつれていくお姉
EMアルゴリズムによる混合分布のパラメーター推定の解析計算＆実装例 from 「Rによるモンテカルロ法入門」 - My Life as a Mock Quant
問題設定 R言語の書籍「Rによるモンテカルロ法入門」 のEMアルゴリズムに関連した「練習問題5.14」をpthonの練習がてらEMアルゴリズム構築までの数式もメモりながら解いてみたというお話。問題設定としては という混合分布(分布から確率、分布から確率でサンプリング)から個サンプリングした状況を考えて、このパラメーターをEMアルゴリズムで推定するというもの。機械学習の分野でいう所の「教師なし２クラス分類」に該当する（たぶん）。 グラフを使ってもうちょっとちゃんと説明しておくと、実際に観察された青い棒グラフで示されているデータは赤色のグラフで示されているからのサンプルなのか、それとも緑色のグラフで示されているからのサンプルなのかを識別するための閾値的な量になっているというパラメーターを推定してましょうと、そして、既存のデータはのどちらの分布から来た可能性が高いのかを判断しましょうとそういう問
コンピュータビジョンのソースコード/ライブラリのまとめ - takminの書きっぱなし備忘録 @はてなブログ
今まで自分が見つけたコンピュータビジョンの研究に役に立ちそうなフリーのライブラリやソースコードをまとめてみました。自分ではまだ使っていないものも多いので、そこはご容赦を。主にC/C++が中心です。 またライブラリ形式でない、いわゆる学会で発表した研究のコードをそのまま公開しているという人がたくさんいて、それに関しては特にメジャーなもののみ紹介しています。なにぶん僕の観測範囲は限られてますので、「このライブラリに触れないのはおかしい」、「説明が間違っている」等、ご意見大歓迎です。 定番(Standard) OpenCV 定番中の定番です。コンピュータビジョンに関して広範なアルゴリズムが実装されています。 http://code.opencv.org/projects/OpenCV/wiki/WikiStart Point Cloud Library ３次元点群データを扱うならこれ。Kinec
サービス終了のお知らせ - NAVER まとめ
サービス終了のお知らせ NAVERまとめは2020年9月30日をもちましてサービス終了いたしました。 約11年間、NAVERまとめをご利用・ご愛顧いただき誠にありがとうございました。
algorithm - bucket sort - 比較しなければソートは相当速い : 404 Blog Not Found
2012年01月11日07:00 カテゴリアルゴリズム百選Math algorithm - bucket sort - 比較しなければソートは相当速い 珠玉のプログラミング Jon Bentley / 小林健一郎訳 絶賛風邪こじらせ中につきコードと戯れることに。 新ソートアルゴリズム「配列挿入ソート」だ! - hp12c その名も「配列挿入ソート」! すでに突っ込み入ってるけど、それ、もしかしたら人類最古のアルゴリズムだから。 最古にして最速? おそらくプログラムを組んだことがない人でも「誰にも教えられずに」知った「天然の」アルゴリズムの筆頭に来るのがこのバケットソートではないでしょうか。 ソートしたいものに適当に番号を振っておく 番号がついたバケツを用意する ソートしたいものの番号がついたバケツにそれを放り込む 必要があればバケツの中身を同じやり方でソートする 番号順にバケツの中身をぶち
隠れマルコフモデルで自然言語を学習 - 西尾泰和のはてなダイアリー
隠れマルコフモデルで社内掲示板の1万個弱の書き込みを学習させてみた。 まず初期値について。遷移確率はおおよそ対角行列。それだけだと差別化できないし、確率が0だと遷移が置きなくて面白く無いので対角成分を11、対角線の一つ上を2、それ以外1として確率として正しくなるように正規化した。出力確率はランダム。ただし今回、文末の構造に注目したいので最後の状態だけ句点「。」の出力確率を2倍にした。 図の見方は、一番左が遷移確率の行列の値の大きさを黒四角の大きさで表現したもの。最大値と最小値で正規化しているので黒四角が見えないところは確率0ってわけではなく、小さな値だという意味。中央はその表示を2倍に拡大したもの。小さい確率値がどうしても見づらいのでね。赤く塗ってあるのは2倍にした結果1を超えたことを意味している。一番右はなんとなく黒→赤→緑→白のスケールになっている。まあ最初に作ったのがこれだったんだけ
研究動向から考えるx86/x64最適化手法
2. Today Agenda 本日の概要 CPU上のマルチコア化や，各種ペナルティの増大に対して，ペナルティの軽減， または完全に排除するデータ構造やアルゴリズムの研究に関する話題 ---- 本日は2000年以降のIntel Lab.や関連研究者による成果の俯瞰が目的 本スライドの目的は以下 ・マルチコア/メニーコア時代における性能改善観点の理解 ・具体例でのx86/x64最適化アルゴリズムの概要理解 ⇒探索，整数圧縮，並び替え処理 2 3. Today Agenda • 自己紹介 • Intel Lab.とは？ • 最近の研究動向 • 研究分野における最適化の観点 – キャッシュミス/DTLBミスの低減化 – 分岐排除 – メモリバンド使用量の考慮 • 具体例1: SIMD命令を利用した探索の分岐排除 • 具体例2: 整数の固定長圧縮によるPipelineハザードの回避 • 具体例3:
可変次数 N-gram デコードのアルゴリズム - アスペ日記
前に書いた N-gram 漢字-かな変換 - アスペ日記 のアルゴリズムについて。 かなり縦に長いエントリになると思う。途中までは一般的な日本語自然言語処理にかかわること。 例として、「かれがくるまでまつ」というひらがなの文をデコードして、対応する漢字かな混じり文にすることを考える。 こういう時に使われるのが「ラティス構造」。こういうやつ↓ （この図は一回しか出てきません。ちなみにこのために Keynote 買ったようなもの） それぞれのノードで、そこに入ってくるエッジの中で一番確率が高いものとその確率を覚えていくことで、動的計画法によって最適なパスを導くことができる。 これをプログラム上でどう実現するか。 まず、共通接頭辞検索というものを使う。 これは、あるキーを渡すと、そのキーに前から一致するようなキーを持つ候補を列挙してくれるというもの。 例えば、「くるまで」をキーとして使うと、「く
MapReduce以外の分散処理基盤BSP, Piccolo, Sparkの紹介 - Preferred Networks Research & Development
どうも，実は今年から開発チームにjoinしていた中川です．可愛い犬の写真がなかったので，可愛いマスコットの画像を貼っておきます． 最近MapReduceとかその実装であるHadoopとかをよく聞くようになりました．これはつまり，それだけ大量のデータをなんとか処理したいという要望があるからだと思います．しかし当たり前ですが，MapReduceは銀の弾丸ではありません． ということで，最近気になっているMapReduceとは違ったアプローチを取っている分散処理基盤について，社内のTechTalkで話した内容を簡単にまとめて紹介したいと思います． Bulk Sychronous Parallel このアルゴリズム自体は1990年に誕生したものです．長いのでBSPと書きます．さて，グラフから最短経路を求める時，MapReduceは使えるでしょうか？このような論文が出るくらいですから出来ないことはあ
常識を覆すソートアルゴリズム！その名も"sleep sort"！ - Islands in the byte stream (legacy)
TwitterのTLで知ったのだが、少し前に海外の掲示板で"sleep sort"というソートアルゴリズムが発明され、公開されたようだ。このアルゴリズムが面白かったので紹介してみる。 Genius sorting algorithm: Sleep sort 1 Name: Anonymous : 2011-01-20 12:22 諸君！オレは天才かもしれない。このソートアルゴリズムをみてくれ。こいつをどう思う？ #!/bin/bash function f() { sleep "$1" echo "$1" } while [ -n "$1" ] do f "$1" & shift done wait example usage: ./sleepsort.bash 5 3 6 3 6 3 1 4 7 2 Name: Anonymous : 2011-01-20 12:27 >>1 なん…だと
Googleアルゴリズム200項目全てを特別公開 – 店舗集客マーケティングブログ
Googleアルゴリズムの200の要素を発見しましょう！（Let’s Try to Find All 200 Parameters in Google Algorithm） は2009年に書かれた記事ですが、パンダアップデートが適用された今現在（2011年4月）でも重要項目が多く書かれているもので。 多くはGoogleの特許（合衆国特許出願0050071741）に基づいていますが、筆者のアンが自身の解析結果や予測を盛り込んでいる事で、より実践に近い内容になっています。 SEO初心者の方は、これからのウェブ制作の軸に、SEOエキスパートの方はもう一度自身のサイトを見直す目次として確認してみてはいかがでしょうか。 ドメインに関する13要因 ドメイン年齢 ドメイン取得からの長さ ドメイン登録情報（Who is情報）の表示/非表示 ドメイン種類（サイトレベルドメイン（.com や co.uk） ト
プログラミングコンテストチャレンジブックを読みながらダイクストラ法を実装したよ - nokunoの日記
前回のベルマンフォード法から時間があいてしまいましたが、プログラミングコンテストチャレンジブック（通称アリ本）を読みながらグラフの最短経路を求めるためのアルゴリズム、ダイクストラ法を実装しました。 ベルマンフォード法 - nokunoの日記ダイクストラ法 - Wikipedia ダイクストラ法ではグラフ中のノードを次の3つに分類します。 未探索 探索済み 次の探索候補この「次の探索候補」の中から最もコストの小さいノードを選んで探索済みとし、その隣接ノードのコストを更新するというのがダイクストラ法の根本のアルゴリズムとなります。 最初の実装それでは実装を見ていきましょう。まず最初の実装では次に探索済みとなる要素を線形探索しているためあまり効率的ではありません。 #include using namespace std; #define MAX_E 20 #define MAX_V 7 #d
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
あなたの知らないハッシュテーブルの世界