お手軽転置インデクスを用いた検索エンジン: (1) AND検索編 - シリコンの谷のゾンビ
突然Cでコードを書きたくなったので，なんちゃって転置インデクスを用いた検索プログラムを書いてみた． 転置インデクスとは，索引語と呼ばれる単語が出現する文書情報 (場合によっては位置情報も) を保持したデータ構造のことで，索引語と，それに対応する転置リストによって構成される． # 索引語 -> 転置リスト hoge -> 5: 1,2,3,4,5 fuga -> 3: 1,4,5 piyo -> 2: 4,5これは，hogeという単語が文書1,2,3,4,5に出現し，fugaという単語が文書1,4,5に出現し，piyoという単語が文書4,5に出現する情報を保持している．最初の5,3,2という数字はそれぞれ索引語がいくつの文書に出現したかという文書頻度 (document frequency; DF) を表している． 検索クエリhogeが入力された場合には，文書1,2,3,4,5を検索結果とし
KMC Staff Blog:K&R C ができるまで
2009年08月07日 K&R C ができるまで 少し前の話になりますが、いただいたコメントをきっかけに、puts になぜ改行が付くのかというネタについて調べていた時、面白い論文を教えてもらいましたので紹介します。 "C and the AT&T Unix Port -- A Personal History", Stephen C. Johnson (翻訳) http://roguelife.org/~fujita/COOKIES/HISTORY/USENIX/johnson.html 初期の UNIX v6 を書いた pre K&R C が、32 bit マシンへの移植を意識した時、どのように K&R C へと変遷していったかという歴史が書かれています。C に関しての疑問を調べていくと、やはり初期の言語 B や PDP-11 とのかかわりが鍵となってきます。 The Impact on
ディレクトリの中にある大量の小さなファイルを高速に読み込む方法 - 射撃しつつ前転 改
ディレクトリの中にある大量のファイルを高速に読み込む方法が知りたかったので、実験してみた。想定しているシチュエーションは、一つ一つのファイルは数KB程度だが数が多い、という場合である。適当な順番でアクセスすると、ランダムアクセスになってしまいとても時間がかかる。個々のファイルを読み込む順番はどうでも良く、すべてのファイルを処理することさえできればいいので、原理的にはシーケンシャルアクセスで処理できてしかるべきである。 まず、ファイルシステムについて。HDDやSSDなどのハードウェアにアクセスする際には、ファイル名などという概念はもちろん存在しない。ファイル名と実際のディスク上の対応を管理するのがファイルシステムの主な役割である。ファイルシステムは、ファイル名からそのファイルに対応するブロック番号（メモリアドレスみたいなもんだな）を調べて、そのブロック番号を指定してHDDやSSDにアクセスす
iPhone 開発に使える C99 仕様と gcc 拡張 - 2009-04-23 - Windchase
iPhone アプリの開発には、コンパイラとして gcc 以外を使うことは基本的にありません。 したがって、gcc に実装されている C99 仕様や gcc 拡張仕様を気がねすることなく利用することができます。 ここでは、便利な C99 仕様や gcc 拡張を紹介します。 配列の動的確保 (C99) 配列を定義するときに、動的にサイズを指定してメモリを確保することができます。 従来は、 int n = 100; char* buf = alloca(n); のように alloca を使っていたところを、 int n = 100; char buf[n]; と、言語仕様の範囲内で、より直観的に書けるようになりました。 case の範囲指定 (gcc 拡張) 従来、switch 〜 case で switch (n) { case 0: case 1: case 2: case 3: proc
常駐型サーバープログラムのデバッグ手法
BOOK: WEB+DB Press TITLE: 常駐型サーバーのデバッグ手法(ドラフト版) AUTHOR: (株)プリファードインフラストラクチャー 太田一樹 ＊注: この文章はWEB+DB PRESS Vol.48に掲載された記事のドラフト版です はじめに 今回はデバッグ関連特集ということで、常駐型サーバープログラムを作成する際のハマりどころやそれに対する解析方法・解析ツール・対策を、実際の経験を交えながら紹介したいと思います。 筆者は(株)プリファードインフラストラクチャーでインメモリ分散検索エンジン「Sedue (セデュー)」を開発しています。モバイル向け検索エンジン「エフルート」や、2008/11/6にリニューアルされました「はてなブックマーク2」などの検索バックエンドとして使われております。 この検索エンジンはいくつかの常駐型サーバープログラムから構成されており
lsコマンドをハックしてみよう
ヤフー株式会社は、2023年10月1日にLINEヤフー株式会社になりました。LINEヤフー株式会社の新しいブログはこちらです。LINEヤフー Tech Blog こんにちは、ショッピング事業部開発部の吉野です。 Yahoo!ショッピング開発部では新人エンジニア向けにコマンドのソースコードを読むことを奨励しています。 その初期の題材として、lsコマンドがよく挙げられます。 今回は「lsコマンドをハックしてみよう」と題し、lsコマンドについてお話しさせていただきます。 突然ですがエンジニアの皆さん、lsコマンドのソースコードを読んだことはありますか？ 読んだことのない方はぜひ一度、目を通しておくことをおすすめします。 意外と知られていませんが、lsはcd,pwdなどのコマンドと違いシェルの組み込みコマンドではありません。 一口にlsと言っても、複数のソースコードが存在します。 代表的なのはGN
きまぐれ日記: AjaxIMEのHTTPサーバは pre-pthread
C++と Pthreads でミニマルなHTTPサーバを書く にて、ネットワークサーバのさまざまな設計・実装方針がまとめられています。 1. クライアントごとに fork 2. 事前に fork - 各プロセスで accept 3. 事前に fork - ファイルロックで accept を保護 4. 事前に fork - Mutex ロックで accept を保護 (PTHREAD_PROCESS_SHARED) 5. 事前に fork - ソケットディスクリプタパッシング 6. クライアントごとにスレッド生成 7. 事前にスレッド生成 - Mutex ロックで accept を保護 8. 事前にスレッド生成 - メインスレッドで accept AjaxIMEの変換エンジンは自作サーバで運用しているのですが、初期の実装は prefork、 すなわち4番の実装でした。 その後、fork の部
C++と Pthreads でミニマルなHTTPサーバを書く - いやなブログ
C++と Pthreads でミニマルなHTTPサーバを書く 『UNIXネットワークプログラミング』を読んでいると、自分でも何かネットワーク系の小さなプログラムを書いてみたくなりました。そこで、ミニマルなHTTPサーバを C++と Pthreads で書いてみました。 同じ著者の「詳解UNIXプログラミング」もそうだったように、今回の本もほとんどすべてのページに、重要なことが書かれています（最後のほうのXTIの部分は例外かもしれませんが）。 たとえば、27章ではネットワークサーバの実装として、次の設計方針がそれぞれ検討され、実際のコード付きで解説されています。 クライアントごとに fork 事前に fork - 各プロセスで accept 事前に fork - ファイルロックで accept を保護 事前に fork - Mutex ロックで accept を保護 (PTHREAD_PRO
ホワット・ア・ワンダフル・ワールド Moe Effective C 第 2048 項 「標準入力をコンパイルしたい時は /dev/tty を include しよう」
こんなことができたのか… $ echo '#include "/dev/tty"' > tty.c $ gcc tty.c (cat と同様に，ソースコードを入力する) #include<stdio.h> int main() {printf("hello, tty!\n");return 0;} (Ctrl-d で終了) $ ls a.exe tty.c $ ./a.exe hello, tty! 研究室の Windows PC で試したので，/dev/stdin とかはありませんでした… /dev/tty は windows cygwin でも使えるのか．なんて汎用的 ！ (Windows と Linux 以外の OS なんて，この世に存在しませんよ．ファンタジーやメルヘンじゃないんですから (セカイ系自分が世界の中心病患者管理人)) さらに，shinichiro_h さんからいただい
memccpy() で文字列をコピーする - bkブログ
memccpy() で文字列をコピーする 詳解Unixプログラミングを読んでいたところ、標準入出力ライブラリの章に「この例からわかることは、行単位の関数は memccpy(3) を用いて実装されていることである」という記述がありました。 一瞬、memcpy(3) の誤植かと思いましたが、調べてみると 4.3 BSD で追加された関数ということがわかりました。 glibc に入っているので Linux でも使えます。 マニュアル によると memccpy() は次のような関数です。 書式 void *memccpy(void *dest, const void *src, int c, size_t n); 説明 memccpy() はメモリ領域src からメモリ領域dest に最大でnバイトコピーする。nバイトコピーする前に文字 c が見つかると、そこでコピーを中止する。 返り値 memc
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
