サクサク読めて、
アプリ限定の機能も多数！
アプリで開く
<追記>ベンチマークプログラムに誤りがありました。ソート済のシーケンスに対してソートを掛けていました。ご指摘ありがとうございます＞ak氏 そんな夢のようなソートアルゴリズムがあるのかというと、あるらしいんです。それがtim sortと呼ばれるアルゴリズムです。 画期的（？）なソートアルゴリズム「Sleep Sort」：濃縮還元オレンジニュース｜gihyo.jp …技術評論社 このあたりで拾ってきたネタですね。 merge sortを改良したアルゴリズムで、安定*1しており、しかも実行速度にも優れているとか。アルゴリズムの性能の評価は済んでいるらしく、CPythonやJDK7には既に導入済みのようですね。 ならば当然Perlのソートも…と考えるわけですが、まず評価のためにJavaのソースをC++にそのまま移植してみました。それがこれ（いちおうテスト済）： https://github.co
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 exampleusage: ./sleepsort.bash 5 3 6 3 6 3 1 4 7 2 Name:Anonymous : 2011-01-20 12:27 >>1 なん…だと
UNIXの基本的なコマンドの1つであるdiff。 これに実装されているアルゴリズムは実に興味深い世界が広がっています。本稿では、筆者が開発した独自ライブラリ「dtl」をもとに「diffのしくみ」を解説します。 はじめに diffは2つのファイルやディレクトリの差分を取るのに使用するプログラムです。 ソフトウェア開発を行っている方であれば、SubversionやGitなどのバージョン管理システムを通して利用していることが多いかと思います。本稿ではそのdiffの動作原理について解説します。 差分の計算の際に重要な3つの要素 差分を計算するというのは次の3つを計算することに帰結します。 編集距離 2つの要素列の違いを数値化したもの LCS（Longest Common Subsequence） 2つの要素列の最長共通部分列SES（Shortest Edit Script） ある要素列を別の要
Posted at 2010/10/22 01:59, Modified at 2010/10/22 03:42 Facebook のフロントエンドは結構かわったことをやっていて、例えば、ログイン後の http://www.facebook.com/home.php には <div id="pagelet_home_stream"></div> みたいな空のHTML があり、その後に <script>big_pipe.onPageletArrive({ … });</script> <script>big_pipe.onPageletArrive({ … });</script> ... と script 要素が何個もならんでいる。 BigPipe: Pipelining web pages for high performance この仕組みは (変数名のとおり) BigPipe と呼
昨日のTwitter の XSS 騒ぎは、まだ皆さんの記憶に新しいことと思います。いい機会なので、ツイートのような構造化テキストのエスケープ手法について触れておきたいと思います。Twitter のメッセージは、単なる平文（プレインテキスト）ではなく、「@英数字」のような他のユーザーへの言及と「http://〜」のような URL を自動的にハイパーリンク化する構造化テキストです。 このような複数のルールをもつ構造化テキストをHTML 化する際には、どのようなコードを書けばいいのでしょう？ まず「@〜」をリンク化してから、URL をリンク化すればいいのでしょうか？ それだと、@〜 のをリンク化した A HREF タグの中の URL がさらにリンク化されていまいますね。 では、URL をリンク化してから @〜 をリンク化すればいいのでしょうか？ それだと、@ を含む URL があった場合に
Kyoto Cabinet 1.2.2から加わったGrassDBは、オンメモリでページ管理を行うB+木を実装してメモリを節約しちゃう仕組みである。それを使ってJava、Python、Ruby、Perlなどのハッシュ（連想配列）機構を鬼のように省メモリにしてみる。頑張ればなんと20分の1になる。 前提 B木やその変種のB+木などは、キーの順序が近いレコード群を「ページ」という単位にまとめてシリアライズしてストレージに書き込むことで、入出力の頻度を減らして高速化することを意図している。メモリに比べて低速なストレージの上で大量のデータを管理するために使われる。多くのRDBMSやいくつかのDBMがB+木をサポートしているのはそれが理由であろう。一方で、メモリ上で検索可能なデータ構造を表現するためには、二分探索木やその特殊例である赤黒木が使われる。STLのstd::mapの実装にも赤黒木を使うのが一
Quicksilverの検索性能が、感性をくすぐってきた。 「apple」→「AppleScript Editor」 「ase」→「AppleScript Editor」 「prol」→「Property List Editor」 「im」と入力して、「Image Capture」を起動したいが、「iMove」がトップヒットになってしまう...。 そんな状況でも、候補リストから2回連続で「Image Capture」を選択すれば、3回目以降は「Image Capture」がトップヒットになる。 直近のユーザーの好みを学習してくれるのだ。 もちろん、「ima」まで入力すれば「Image Capture」がトップヒットになる。 「ase」「prol」のような、単純な前方一致でも、部分一致でもない検索には恐れ入る。しかも、シンプルだけど学習もしてくれる。使うほどに手に馴染んでくる仕組みは、この辺
あらかじめ整列してある2つの配列を合体させて、新しい、整列された配列を得るのは容易です。マージソートはこれに着目して、並べ替えたい配列を再帰的に分割していき、再び併合（マージ）していくことで、並び替えを実現しようとする、ソートアルゴリズムです。 次の図は、マージソートが行われる過程を表しています。 ばらばらな順番で与えられた配列データは、まず始めに小さい配列へと分解されます。このとき、マージソートでは各配列がほぼ2分割されるように分解していきます。 もっとも小さい配列（要素数1）まで分解されたら、それを順序良く併合していきます。このとき、2つの配列の先頭から小さい方を取り出して新しい配列を作成するようにすれば、取り出すだけで整列された配列を作成することができます。 /* * マージ * 2つの配列a1[]とa2[]を併合してa[]を作ります。 */ void merge(int[] a1,
このパートでは，プログラミングを勉強するうえで欠かせないアルゴリズムの中でも定番中の定番を紹介します。ソート（並べ替え）やサーチ（検索）などの機能は今では標準のライブラリとして提供されています。実用的なプログラムを作るときにそのものずばりをいちいち書く機会は少ないかもしれません。しかし定番のアルゴリズムは，様々に形を変えて普段のプログラミングに登場します。 解説を読んで仕組みがわかったら，ぜひそれをプログラムにしてみてください。読んだだけではプログラムを書けるようにはなりませんし，プログラムを書いてみて初めて，実は十分に理解できていなかったと気付くことがよくあります。しかもアルゴリズムは特定のプログラミング言語に依存しないので，一度身に付ければ，後でどんな言語を学ぶ場合でも役に立ちます。 1番目から6番目まではソートのアルゴリズム，7番目から9番目まではサーチのアルゴリズムです。一つひとつ
Consistent Hashing は、 複数のノードにレコードを分散させる方法として、Amazon Dynamo や Cache::Memcached::Fast などで使われているアルゴリズムです。 この文章では、Perl で実際に Consistent Hashing を実装し、 その特徴を理解することを目的とします。 更新履歴 2008-06-01: 公開 サーバー台数で割った余り (mod) を使用する まず Consistent Hashing と比較するために、レコードに対して整数のハッシュ値を求め、 ハッシュ値をノード数で割った余り (mod) で、ノードを選択するという方法を書いてみます。 ここでは、ハッシュ値の算出に CRC (Cyclic Redundancy Check) を使用しています。 use strict; use String::CRC; use Pe
ConsistentHashing - コンシステント・ハッシュ法 目次 この文書について コンシステント・ハッシュ法 実例 実装 用途 コンシステント・ハッシュ法 この文書について "Tom White'sBlog: Consistent Hashing" の日本語訳です. http://weblogs.java.net/blog/tomwhite/archive/2007/11/consistent_hash.html 推敲歓迎: 誤訳, タイポ, 訳語の不統一, そのほか... 原文のライセンス: http://creativecommons.org/licenses/by-nc-sa/2.0/ 私は今までに何度かコンシステント・ハッシュ法にとりくんだことがある。 このアイデアをあらわした論文 ( David Karger らによる Consistent Hashing and R
English Version News: MTToolBox をGitHubで公開しました。(2013/10/04) TinyMTをリリースしました。 (2011/06/20)MTGPをリリースしました。(2009/11/17)SIMD-oriented Fast Mersenne Twister (SFMT) をリリースしました。SFMTはオリジナルのMersenne Twisterより約二倍速く、 よりよい均等分布特性を持ち、零超過初期状態からの回復も高速です。SFMTのページを見てください。 (2007/1/31) お願い：使う時にemailを一通下されば、 今後の改良のはげみになります。 どんなささいな問題点でも、見つけ次第御連絡下さい。 m-mat ＠ math.sci.hiroshima-u.ac.jp (このメールアドレスは スペースを抜いて手で打ち直してください)
<body> <p>このページにはフレームが使用されていますが、お使いのブラウザではサポートされていません。</p> </body>
1リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
