高速な安定ソートアルゴリズム "TimSort" の解説 - Preferred Networks Research & Development
先日、TimSortというソートアルゴリズムが話題になりました。TimSortは、高速な安定ソートで、Python(>=2.3)やJava SE 7、およびAndroidでの標準ソートアルゴリズムとして採用されているそうです。 C++のstd::sort()よりも高速であるというベンチマーク結果1が話題になり(後にベンチマークの誤りと判明)、私もそれで存在を知りました。実際のところ、ランダムなデータに対してはクイックソート(IntroSort)ほど速くないようですが、ソートというシンプルなタスクのアルゴリズムが今もなお改良され続けていて、なおかつ人々の関心を引くというのは興味深いものです。 しかしながら、オリジナルのTimSortのコードは若干複雑で、実際のところどういうアルゴリズムなのかわかりづらいところがあると思います。そこで今回はTimSortのアルゴリズムをできるだけわかりやすく解
モダン並列・並行プログラミング ～ Concurrent Revisions による実装と現実 ～ - Preferred Networks Research & Development
本日社内向けのTechTalkにて、並列・並行プログラミングに関する話を行いました。 昨今、プログラムの並列化はなくてはならないものとなっています。しかし、そのプログラミング環境は依然としてロックを用いたものが主流です。今回の発表の主張を端的に申し上げますと、 “Locks must go！” ということになります。並列プログラミングに銀の弾丸はありません。しかし、ロックは別の何らかの安全性を確保したプログラミングモデルで置き換えられなければいけません。そうでなければ、再現しにくいバグに苦しめられ、終電を逃す日々と決別することはできないでしょう。また、ロックによるプログラミングの抱える本質的問題にも言及しています。 この界隈の最新の動向として、去年OOPSLA’10にて発表されたConcurrent Revisionsについての解説も行なっております。また、弊社研究開発において、先日Con
quick sortよりも高速でmerge sortのように安定しているソートアルゴリズムtim sort [勘違い] - Islands in the byte stream
<追記>ベンチマークプログラムに誤りがありました。ソート済のシーケンスに対してソートを掛けていました。ご指摘ありがとうございます＞ak氏 そんな夢のようなソートアルゴリズムがあるのかというと、あるらしいんです。それがtim sortと呼ばれるアルゴリズムです。 画期的（？）なソートアルゴリズム「Sleep Sort」：濃縮還元オレンジニュース｜gihyo.jp … 技術評論社 このあたりで拾ってきたネタですね。 merge sortを改良したアルゴリズムで、安定*1しており、しかも実行速度にも優れているとか。アルゴリズムの性能の評価は済んでいるらしく、CPythonやJDK7には既に導入済みのようですね。 ならば当然Perlのソートも…と考えるわけですが、まず評価のためにJavaのソースをC++にそのまま移植してみました。それがこれ（いちおうテスト済）： https://github.co
![quick sortよりも高速でmerge sortのように安定しているソートアルゴリズムtim sort [勘違い] - Islands in the byte stream](https://cdn-ak-scissors.b.st-hatena.com/image/square/f9103c273a45047a455a47c2322a4ec545cd77ee/height=288;version=1;width=512/https%3A%2F%2Fogimage.blog.st-hatena.com%2F17680117127143682567%2F17680117127143702106%2F1558185862)
jQuery custom event 応用編 - monjudoh’s diary
前置き custom eventとは何か?(前置きの前置き) ブラウザがサポートしているeventではない独自定義event。 clickとかはブラウザがサポートしているevent ユーザのアクションやブラウザの状態等によって直接発火されることはない click eventは、ユーザがマウスポインタを要素の上に移動後にマウスのボタンを押すと発火される DOMContentLoaded eventは、ページのHTMLがダウンロード完了し、すべてパースされると発火される jQueryではtrigger,triggerHandler methodでeventをユーザのアクション等に関係なく発火することが出来る custom eventも発火出来る 逆に言うとcustom eventはJavaScriptの側からしか発火されない 以前The JUI 2009 Returnsで話をしました。 htt
Java SE 7徹底理解 第6回 New I/O 2で非同期I/O
先々月、先月とNIO2の新しいファイルシステムについて解説してきました。今月は、NIO2の残りの機能である非同期I/Oとソケットチャネルでのマルチキャストについて解説していきます。 なお、ここではNIO2の機能を中心に解説するため、バッファやチャネルなどNIOの機能に関しては特に解説を加えておりません。NIOについては、本連載では2006年の4月から5月にかけて「New I/Oで高速な入出力」と題して解説していますので、そちらをご参照ください。 通常のI/O 一般的に入出力処理を行う場合、処理が完了するまで制御が戻ってくることはありません。たとえば、インプットストリームでstream.read(bytes);と記述した場合、読み込みが終了するまでreadメソッドが戻ってくることはありません(例外が発生することはあります)。つまり、処理がブロックされるわけです。 入出力が高速に行われるのであ
node.jsの非同期I/Oにおけるデータ受信のパターンのバリエーション - たごもりすメモ
そもそもなんでnode.jsのThriftライブラリではBufferedTransportがサポートされず、FramedTransportのみが使える状態だったのか。Thriftの歴史的にはBufferedTransportの方が先行して存在しており、また仕様自体も単純のようだ。*1 実装を開始してみてわかったが、node.jsが採用する非同期I/OアーキテクチャのAPIと実に相性が悪い。Thriftが定義ファイルから各言語用のコードを自動生成する仕組みであることも関係している気がする。いざnode.jsの都合に合わないからといって、カジュアルに生成結果のコードを修正するわけにはいかない。また受信データ(を持っているはずのI/Oストリーム)からデータを読み出すところまでがThriftによる自動生成の範囲に含まれる。 (Twitterで言及を読んで追記) 普通にアプリケーション側のコードをコ
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
