高速かつ省メモリで文字列を扱うデータ構造「wavelet tree」
はじめに 大規模なデータを扱うアプリケーションでは、速度とともに作業領域量も大きな問題となります。作業領域がメインメモリに収まらない場合、スワッピングが発生し、大幅な速度低下につながります。そのため近年、データ構造は高速なだけでなく、作業領域量が小さいことも求められています。今回紹介するのは2003年に提案されたデータ構造、wavelet tree（以下「WT」と表記）です。WTは圧縮索引やSuccinct Data Structureなど、データをコンパクトに表現する際に重要なデータ構造です。WTは文字列T[0...n-1]が与えられた時、次の2つの操作を定数時間でサポートします。 rank(p, c)――T[0...p]中のcの出現回数を返す select(i, c)――(i+1)番目のcの位置を返す WTの作業領域量は、文字列をそのまま保存した時の約2倍程度です。 対象読者 C++の
プログラマーを採用する際に重視すべき10の資質
印刷する メールで送る テキスト HTML 電子書籍 PDF ダウンロード テキスト 電子書籍 PDF クリップした記事をMyページから読むことができます プログラマーが有するスキルには大きな幅があり、彼らの出身国や文化もさまざまであるため、プログラマーの素性や経歴というものはそれぞれ異なっているはずである。とは言うものの、プログラマーの優劣に大きな影響を与える資質というものも存在しているのだ。そこで本記事では、プログラマーを採用する際に重視すべき資質を10個選んで解説する。 ＃1：好奇心 優秀なプログラマーはものごとを「ありのままに」捉えるということをしない：彼らは、きちんと動作しているように見えるものに対しても、詳細を学ぼうとその中身に深く踏み込んでいくのである。そして彼らがそういった態度をとることで、存在すら明らかになっていなかった問題が解決されることも多々あり、それは通常、深刻な問
Linuxカーネルの作り出す世界 − ＠IT自分戦略研究所
本連載は、ソフトバンククリエイティブ刊行の『ふつうのLinuxプログラミング』のうち第1部「Linuxの仕組み」の中から「第2章 Linuxカーネルの正解」と「第3章 Linuxを描き出す3つの概念」を、同社の許可を得て転載するものです。 本書は、LinuxにおけるC言語プログラミングの入門書です。「Linuxの世界が何でできているのか」に着目し、「ファイルシステム」「プロセス」「ストリーム」という3つの概念を紹介しています。 なお、本連載は転載を行っているため＠IT自分戦略研究所の表記とは一部異なる点があります。ただし、Webで掲載するに当たり、（例えば「本書は」としている部分は「本連載は」としていること、図版などの省略など）、表現を若干変更している点がありますが、その点ご了承ください。 ■オペレーティングシステム 今どきのコンピュータにはオペレーティングシステム（OS：Operatin
マージ・ソート : 巨大データのソート法：CodeZine
はじめに まずはともあれ腕試し、この問題を解いてみてくださいな:【問1】 デタラメな順序で並んだ文字列の集合がテキストファイル「input.txt」に収められています。この文字列群を辞書順（昇順）に並び換えたテキストファイル「sorted.txt」を作りなさい。 ※各文字列は改行で区切られています。 プログラミング教本の練習問題、あるいは学校の課題で出てきそうな“お馴染み”の問題です。ソート（整列）アルゴリズムの実装には配列/代入/条件分岐/ループなどなどプログラミングの基本中の基本となる構文を総動員するため、練習問題としてよく使われますね。 早速解いてみましょう、ソート・アルゴリズムにはこれまたお馴染みのバブル・ソートを使います。C#、VB.NET、C++/CLIの3本まとめて一気にいきますよ: using System; using System.IO; using System
Emacs で C とか Perl とか Ruby のデバッグをすると気持ちいい | フッ君の日常
全国のprintデバッグ愛好家の皆様、こんにちは。VSとかEclipseとかのIDE以外でデバッガを使ったことのない僕がやってきましたよ。 最近、C言語でヒーコラ言ってる真っ最中な訳ですが、C言語だとprintデバッグがやりにくい訳で、デバッガ様の力を借りてみたくなった訳です。という訳で、巷で有名な gdb をちょっと試してみました。 基本的な使い方は、以下を参考にしてます。gdb を用いたデバッグ方法GDBウノウラボ Unoh Labs: gdbの使い方 で、なんだか Emacsからも使えるみたいなんで、試してみたんですが、これが使いやすくてびっくり。"M-x gdb" で起動すると、Emacs のソース上に、現在の行が黒三角で、ブレークポイントが赤丸で表示されます。後は、コマンドラインでの操作と同じように、s とか n でステップ実行できます。 あー、もしかして、Perl とか Rub
MOONGIFT: » GoogleのソースレビューシステムMondrianのオープンソース版「Rietveld」:オープンソースを毎日紹介
※ 一部の画面はデモより Googleの高度なエンジニアリングを支える技術の一つにソースコードレビューがある。ソースの修正点について、レビューし、議論することでさらに良いコードができあがっていく。世界中にいるエンジニアのために、議論はネットを介して行うことになる。 ソースコードの行ごとにコメントが書ける そのためのシステムがMondrianだ。これを作ったのはGuido van Rossum氏、Python開発者でもある方だ。そしてこのMondrianをなんとかオープンソースとして公開したいと願ってきたRossum氏が実現させたのがこのソフトウェアだ。 今回紹介するオープンソース・ソフトウェアはRietveld、Google App Engineで作られたソースコードレビューシステムだ。 Rietveldは任意のリポジトリに対して、古い版と新しい版のソースの差分を表示し、レビューを行うこと
プログラマの心の健康
目次 はじめに 情報不安について 人の話を聞くこと 寝てから考えよう わ・ざ・と、ゆ・っ・く・り・、や・っ・て・み・よ・う ロビンソン式悩み解決法 驚き、最小の法則 むしょうに腹が立つあいつのこと あなたは、そのままでいいんです はじめからやり直したい症候群 人から信頼されるためにはどうしたらよいか トラブルがチャンス あなたはひとりではありません あなたのための聖書の言葉 ぜひ、感想をお送りください リンク集 更新履歴 はじめに 私はプログラマです。 プログラムを書いて生活の糧を得ています。 プログラマというのは精神的にも肉体的にも過酷な仕事だと思われています。 夜遅くまでディスプレイに向かい、 キーボードを叩き、ジャンクフードを食べながらバグをとる…そんな職業だと思われています。 確かにそういうところもありますが、プログラマも人間です。 不健康な生活を長いこと続けることはできません。
第11回 スクリプトインジェクションを防ぐ10のTips | gihyo.jp
前回はスクリプトインジェクションがなくならない理由を紹介しました。それをふまえて今回はスクリプトインジェクションを防ぐ10のTipsを紹介します。 デフォルト文字エンコーディングを指定 php.iniには、PHPが生成した出力の文字エンコーディングをHTTPヘッダで指定するdefault_charsetオプションがあります。文字エンコーディングは必ずHTTPヘッダレベルで指定しなければなりません。しかし、デフォルト設定ではdefault_charsetが空の状態で、アプリケーションで設定しなければ、HTTPヘッダでは文字エンコーディングが指定されない状態になります。 HTTPヘッダで文字エンコーディングを指定しない場合、スクリプトインジェクションに脆弱になる場合あるので、default_charsetには“UTF-8”を指定することをお勧めします。サイトによってはSJIS、EUC-JP
SQLによる数独の解法：CodeZine
はじめに SQLを使って数独（ナンプレ）を解く方法を紹介します。 データベースを操作するための言語であるSQLを別の用途に使おうとする理由は、SQLが宣言的な記述が可能な言語の中で最も普及していると思われるからです（宣言的言語と言えばPrologを思い浮かべる方も多いかもしれませんが、残念なことにPrologは、SQLほどには普及していません）。 まず、宣言的な記述について説明しましょう。タクシーに乗ることを想像してください。「渋谷に行ってください」というように、欲しい結果を書くのが宣言的な記述です。具体的な道筋は運転手が考えてくれます。それに対して「まずA通りを北に行って、B交差点を左折して・・・」というように、具体的な道筋を示すのは手続き的記述です。プログラミング言語の場合も同様です。SQLやPrologにおいては、欲しい結果をプログラマが書けば、具体的な実現方法はコンピュータが考えて
モノーキ〜デバッグパターン
デザインパターンを勉強していて、ふとデバッグにもパターンがあるよな。 と思って作ってみました。 これって、どこかに協力を仰ぎたいけど、誰に頼むんだ？ （結果的に協力してもらいました。thanks XPMLの皆さん、lemonさん） 何かおもいついた方はこちらへメールか、掲示板へ プログラマ用セキュリティホールパターンってのが欲しいな 例えばSQL injectionとかいうセキュリティホール。 こんなの知らないと絶対やってしまう。 OSとかの設定ではなく、プログラマの設計において注意するセキュリティホールのパターンが欲しい。 集計などはやってもいいので、どこかで有志を募って集めてくれませんかね？ ○デバッグパターンについて ・デバッグパターンとはプログラマから観測できる現象とそれに対する原因と対策をパターンとして登録したものです。中にはアンチパターンという、やってはいけないパターンも存在し
こんな経営者は必要ない - カレーなる辛口Javaな加齢日記
http://e0166.blog89.fc2.com/blog-entry-224.html ネタとしか思えないな． 沢山のネットビジネスをされている経営者の方にもお会いしました。 せっかくなので、優秀なプログラマとは一体どんな人材ですかと聞いてきました。 １）企画力のある人材 企画力が欲しければ企画部門に配属すれば？ 実際には中小企業では企画部門 兼 開発者ということもあるだろうが，それはプログラマの能力とは別の話． ２）デスクトップとマイドキュメントが綺麗な人材 これは論外． デスクトップやマイドキュメントのインターフェースは初代Macintoshが作られた頃の設計を引きずっているだけで，今やとっくの昔に時代遅れの代物なのだ．*1 ３）網2.0って何だろうと聞いて、返事が返ってくるプログラマ そんなもん専門家も知らない． 単なるバズワードの一つだ． ４）期日はいつですかと聞いてくるプ
Unit Testの書き順(1)
私が概ね全てのお仕事コードにUnit Testをつけるようになって、だいたい3年になります。 Testabilityという物に高い意識を持つようになった期間とだいたい一致している為、Unit Testを書くという事自体のキャリアもまだ3年です。 プログラムを書くという事だともうすぐ10年になりますが、Unit Testはようやく素人の域を脱した程度の所です。 まだまだそんなレベルではありますが、それでも3年続ければ3年続けただけの物もあります。 その一つとして、Unit Testの書き順という考え方があります。 Unit Testを書く時に、最初に何から書くでしょうか？ 私は expectedの変数 inputの変数 その他 という風に書きます。1と2は入れ替わる事もあります。例を挙げましょう。 function Adder() { return {add: function(a, b)
デバッグ指向のススメ - 職業としてのプログラミング
デバッグ指向プログラミング(debug-oriented programming)とは何か。一言で言うとすると、「デバッグしやすいプログラムを書きましょう」ということです。テスト指向(test-oriented)と近いところもありますが、よりデバッグの効率に重点を置いた考え方です。詳しい内容は今回だけでは書ききれませんが、とりあえず今回は、なぜデバッグ指向なのか、デバッグ指向とは具体的にどんなものか、ということについて書いてみたいと思います。 バグの発生は必然 バグの発生は予定外の出来事ではありません。よほど小規模のプログラムでない限り、ソースコードが一発で不具合なく動くことはほとんどありません。つまり、デバッグ作業というものは、ソフトウェア開発において重要なステップなのです。実際、大抵のソフトウェア開発では、コーディングそのものよりもデバッグに費やす時間の方が多いことが多いのではないでし
kajidaiの日記 - 新しいプログラミング言語を習得するための15の方法
↓で紹介されてた新しいプログラミング言語を習得するための15の方法についてhttp://forums.programming-designs.com/viewtopic.php?pid=3482I've working knowledge of a bunch of programming languages but job demands to learn a new language frequently in a short time. Instead of reading hundreds manual/book pages, I quickly read 10-15 pages of tutorial or primer. (As you know google is the best search engine to look for such stuff). I keep p
【ハウツー】"重たいJavaScript処理"もこれで解決! - Google Gearsのワーカプールを試す (3) それでは実装! | エンタープライズ | マイコミジャーナル
サンプルコードの解説 今回作成したサンプルは、以下のような画面だ。 今回作成したサンプル 「非同期処理」ボタンをクリックすると、ワーカプールを使用してバックグラウンドで「重たい処理」を実行する。「同期処理」の場合はワーカプールを使用しない。UIのブロックを防ぐ、ということを体感するための比較用だ。「重たい処理」が完了すると、ボタンの下に所要時間を表示する。 今回、「重たい処理」として行っているのは、Gearsのデータベース機能を用いてテーブルを作成した後、そのテーブルに新しい行を100件追加する、という処理だ。オンラインからオフラインに移行するとき、メモリ上のデータをローカルに保存する、といった処理を想定した。 以下がそのサンプルコードだ。 index.html <html> <head> <meta http-equiv="Content-Type" content="text/html
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
「300 秒でズバリ !!」 & 「10 行でズバリ !!」 シリーズ [Visual Studio 2005 対応版]![「300 秒でズバリ !!」 & 「10 行でズバリ !!」 シリーズ [Visual Studio 2005 対応版]](https://cdn-ak-scissors.b.st-hatena.com/image/square/d6e4cb632c7025e9f5e05fd314fbf6dcd6144e8d/height=288;version=1;width=512/https%3A%2F%2Flearn.microsoft.com%2Fen-us%2Fmedia%2Fopen-graph-image.png)
Loading...
そんなプログラマは必要ない！優秀なプログラマの8つの条件*ホームページを作る人のネタ帳
M.Hiroi's Home Page / xyzzy Lisp Programming
REXML：RubyによるXML処理